Модели объектно – ориентированных субд для информационно-расчетных задач
На правах рукописи
Камашев Мстислав Андреевич
« МОДЕЛИ ОБЪЕКТНО – ОРИЕНТИРОВАННЫХ СУБД ДЛЯ ИНФОРМАЦИОННО-РАСЧЕТНЫХ ЗАДАЧ»
Специальность: 05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей.
А в т о р е ф е р а т
диссертации на соискание ученой степени
кандидата физико-математических наук
Казань – 2011
Работа выполнена на кафедре теоретической кибернетики ФГАОУВПО «Казанский (Приволжский) федеральный университет»
| Научный руководитель: | Кандидат физико-математических наук, доцент ФГАОУВПО «Казанский (Приволжский) федеральный университет» Еникеев Арслан Ильясович |
| Официальные оппоненты: | 1.Доктор физико-математических наук, профессор ФГАОУВПО «Казанский (Приволжский) федеральный университет» Ш.Т. Ишмухаметов 2.Кандидат физико-математических наук, заведующий отделом Института информатики АН РТ И.И.Макаров |
| Ведущая организация: | Московский государственный технический университет имени Н.Э.Баумана |
Защита диссертации состоится 20 октября 2011г. в 15.30 на заседании диссертационного совета Д. 212.081.24 при ФГАОУВПО «Казанский (Приволжский) федеральный университет» по адресу: 420008, г. Казань, ул. Кремлевская, Д.18, конференц-зал научной библиотеки им. Н.И.Лобачевского.
С диссертацией можно ознакомиться в научной библиотеке им. Н.И. Лобачевского при ФГАОУВПО «Казанский (Приволжский) федеральный университет». Автореферат диссертации опубликован на сайте ФГАОУВПО «Казанский (Приволжский) федеральный университет» (www.ksu.ru).
Автореферат разослан «16» сентября 2011 г.
Учёный секретарь
диссертационного Совета,
к.ф.-м.н, доцент А.И.Еникеев
Общая характеристика работы
Актуальность темы исследования
Одним из важных аспектов современного подхода к разработке программного обеспечения является использование формализованных средств, с помощью которых создаются модели соответствующих программных систем с целью однозначного описания и исследования свойств создаваемых программных средств. Эффективность такой модели определяется не только наличием адекватных средств описания и исследования, но и главным образом в идеале предполагает создание средств автоматической генерации программных средств из соответствующих формализованных спецификаций. Таким образом конечной целью формализованного подхода является создание многоуровневой интегрированной среды разработки программных средств, включающей в себя формализованные средства для построения модели и средства автоматической генерации программ из их спецификаций. Однако формализм большинства предлагаемых в настоящее время методов, основывается, как правило, на сложных математических средствах высокого уровня и следовательно является труднодоступным на этапе практической реализации моделей. Поэтому задача интеграции традиционных полуформальных методов с формальными представляется весьма актуальной. Опыт соответствующих разработок в этой области показывает, что универсальные подходы к решению указанной выше задачи не дают желаемых результатов и наибольший эффект достигается на пути построения специализированных систем моделирования.
Представляемая работа посвящена построению объектно-ориентированной модели программных систем, ориентированных на автоматизацию решения так называемых информационно – расчетных задач, в число которых включаются задачи компьютерной бухгалтерии, делопроизводства, статистики и т.п. Основной особенностью упомянутого класса задач является использование относительно простых структур данных, в большинстве случаев адекватно представляемых аппаратом реляционной алгебры. Однако, такое важное понятие, как иерархия, определяющее один из основных принципов объектно-ориентированного подхода, в рамках реляционной модели представляется далеко неадекватными способами, что может существенно отразиться на эффективности функционирования соответствующей интегрированной среды разработки программных приложений. Особенностью предлагаемого подхода является расширение реляционной модели путем включения аппарата алгебраических спецификаций и средств функционального программирования с целью гибкого сочетания простоты реляционной модели со средствами эффективного представления иерархически организованных структур.
Цель работы
Основной целью диссертационной работы является методология построения специализированной модели, ориентированной на разработку программных приложений для автоматизации решения информационно-расчетных задач на основе соединения алгебраических спецификаций и средств функционального языка программирования с целью последующей реализации модели в реляционной среде.
Перечень решаемых задач
- Разработать специализированную модель для класса информационно-расчетных задач на основе расширения реляционной модели средствами алгебраических спецификаций и функционального языка программирования.
- Создать интегрированную среду разработки информационно-расчетных задач на основе специализированной модели.
- Предложить адекватные способы представления и исследования иерархических структур данных в рамках реляционной модели на основе алгебраических спецификаций и функционального языка программирования.
- Разработать средства, обеспечивающие адекватную реализацию модели в среде систем JAVA, Visual FoxPro и MS SQL.
- Построить демонстрационную модель на примере системы автоматизации учета автомобильного транспорта с целью обоснования работоспособности предлагаемых в диссертации средств и методов.
Методы исследования
В работе использованы методы реляционной алгебры, математической логики, элементы системного анализа, прикладного программирования, а также современные методологии организации иерархических систем.
Модель построена на основе сочетания средств реляционной алгебры с аппаратом алгебраических спецификаций и средств функционального программирования. Язык спецификаций модели обеспечивает формальное описание внутренней структуры классов объектов, включающей описание атрибутов и операций, а также поведения соответствующих процессов
Научная новизна
1. Создание специализированной модели для класса информационно-расчетных задач на основе расширения реляционной модели средствами алгебраических спецификаций и функционального языка программирования
2. Создание интегрированной среды разработки информационно-расчетных задач на основе специализированной модели.
3. Разработка адекватных способов представления и исследования иерархических структур данных в рамках реляционной модели на основе алгебраических спецификаций и функционального языка программирования.
4. Разработка средств, обеспечивающих адекватную реализацию модели в среде систем JAVA, Visual FoxPro и MS SQL.
Практическая ценность результатов
На защиту выносятся
1. Специализированная модель для класса информационно-расчетных задач на основе расширения реляционной модели средствами алгебраических спецификаций и функционального языка программирования
2. Интегрированная среда разработки информационно-расчетных задач на основе специализированной модели..
3. Разработанные средства, обеспечивающие адекватную реализацию
модели в среде систем JAVA, Visual FoxPro и MS SQL.
4. Демонстрационная модель на примере системы автоматизации учета автомобильного транспорта с целью обоснования работоспособности предлагаемых в диссертации средств и методов
Апробация работы
Основные научные результаты диссертационной работы были доложены на научных семинарах кафедры теоретической кибернетики и на XV Международной конференции Проблемы теоретической кибернетики (Казань, Россия, 2–7 июня, 2008).
Публикации
По теме диссертации опубликовано 5 работ, в том числе 1 – в журнале, входящем в Перечень ВАК РФ.
Структура и объем работы
Диссертация состоит из введения, четырех глав, заключения и списка использованной литературы из 87 наименований, включая работы автора. Объем диссертации составляет 118 страниц машинописного текста.
Краткое содержание работы
Введение обосновывает актуальность темы, излагаются цели, задачи исследования, новизна и практическая ценность выносимых на защиту результатов.
В первой главе автором производится анализ литературы по сходной тематике для обоснования применения представляемых в диссертационной работе формализованных средств для построения модели. Также автором анализируются различные способы представления моделей (неформальные, полуформальные и формальные), их преимущества и недостатки. В качестве основного вывода предложено заключение о необходимости расширения аппарата реляционной алгебры посредством включения в него средств функционального программирования и алгебраических спецификаций с целью построения адекватной модели для класса информационно-расчетных задач.
Во второй главе предлагаются средства для построения моделей иерархических структур данных на основе алгебраических спецификаций и средств функционального языка программирования с целью последующей реализации модели в реляционной среде. Данные средства предлагаются в связи с тем, что в процессах реализации информационно-расчетных задач традиционно используется реляционная модель представления данных. Однако в этих задачах часто возникает необходимость использования иерархических структур. Для обеспечения преемственности реляционных моделей возникает необходимость их расширения путем включения адекватных средств представления и обработки иерархических структур.
Спецификация обеспечивает формальное описание внутренней структуры классов объектов, включающей описание атрибутов и операций.
Для описания структуры данных и операций использованы средства функционального языка программирования на основе языка LISP.
Любую таблицу базы данных можно представить в виде списка (S,I,T), где S- объект, определяющий структуру таблицы, I –список индексных выражений, а T – непосредственно сама таблица. Объекты S,I и T определяются
следующим образом:
S=(s1, s2, …, sm), где si (i=1..m) – описания атрибутов таблицы. Каждое описание атрибута представим в виде списка s=(a,c, l1, l2), где a – наименование атрибута, c - тип атрибута, l1, l2 – модификаторы длины. Например, (NAME,Char,50,0) – означает атрибут с именем NAME символьного типа с максимальной длиной в 50 символов, (SALARY,Numeric,12,2) - атрибут с именем SALARY численного типа с максимальной длиной в 12 позиций, включая десятичную точку, и 2 –цифры после десятичной точки.
I=( i1, i2, …, ik), где ij (j=1..k)- индексное выражение, представляемое в виде выражения E(a1, a2, …,al), где ai (i=1..l) – атрибуты таблицы.
T=( t1, t2,..., tn ) Через nil будем обозначать пустую таблицу. Пусть t – запись таблицы T, то есть t T, тогда любую запись t можно представить в виде последовательности t =( a1,a2,..., ak), где a1,a2,..., ak – атрибуты.
Определим специальную функцию struct(T), значением которой будет являться структура таблицы T, а через index(T) - список индексных выражений таблицы T. Далее, для простоты изложения последующего материала будем в качестве таблицы рассматривать только объект T, имея в виду, что для любого такого объекта мы можем всегда определить его структуру посредством функции struct(T), а список индексных выражений - через функцию index(T). Структурную и индексную части будем рассматривать только в случае необходимости.
Определим следующие операции:
- seta(t,i,v) – присвоение значения v i-ому атрибуту записи t
seta(t,i,v) =df IF(i=1,cons(v,tail(t),seta(tail(t),i-1,v))), причем
i=1..n, где n- число атрибутов записи t;
- new(S) – значением функции является пустая запись, построенная
в соответствии со структурой S;
- create(S,I) – создание таблицы со структурой S и списком индексов I, то естьT= create(S,I) struct(T)=S & index(T)=I ;
- appendb(T) – добавление новой пустой записи к таблице T,
appendb(T) =df cons(new(struct(T)),T);
filter(T,b) – значением функции является новая таблица, включающая в себя все те записи из таблицы T, которые удовлетворяют условию b,
- filter(T,b) =df IF(cond(Head(T),b),cons(Head(T),filter(tail(T),b), filter(tail(T),b)),
где cond(t,b) - функция, принимающая булевское значение в результате вычисления логического выражения b для записи t;
- delete(T) – значением функции является новая таблица, которая
получается в результате удаления головной записи из таблицы T, то есть
delete(T) =df tail(T)
Следующая ниже алгебраическая спецификация описывает структуру таблицы:
Далее предлагаются способы представления иерархических структур на основе приведенных выше формализованных средств.
Традиционные способы представления иерархических структур в реляционных моделях сводятся к следующим: иерархическая структура в рамках одной таблицы, иерархическая организация которой определяется специальным способом кодирования ключевого атрибута таблицы, и иерархическая структура на основе отношений между двумя и более таблицами.
Ниже приводится описание 3-х способов представления иерархических структур, из которых первые 2 способа основываются на представлении иерархии в рамках одной таблицы, а последний - на представлении иерархии в рамках двух и более таблиц.
Описание модели иерархических структур приводится на основе определенных выше формализмов.
Первый способ представления иерархии
При этом способе представления ключевое выражение таблицы, однозначно идентифицирующее каждую запись таблицы, определяется парой атрибутов
<Id, Par>, где Id – уникальный номер записи, а Par – номер родительской записи. Пусть T –некоторая иерархическая таблица, представленная в виде последовательности записей T=(t1, t2,..., tn). Через nil будем обозначать пустую таблицу. Пусть t – запись таблицы T, то есть t T, тогда любую запись t можно представить в виде последовательности t =(Id,Par, a1,a2,..., ak), где a1,a2,..., ak – все остальные атрибуты. Определим функции fid(t) для выделения собственного номера записи t и fpar(t) для выделения номера родительской записи, то есть fid(t)= Id и fpar(t)=Par. Запись, определяющая начальный уровень иерархии не имеет родителя, поэтому в качестве номера родительской записи будет 0. Для описания модели были использованы средства языка функционального программирования.
Для данного способа определены основные операции для иерархических структур.
Это – следующие операции:
- maxcode(T) – максимальное значение номеров записей таблицы T
- add(T,t,p) – добавление записи t в конец таблицы T c формированием
- в записи t собственного номера и номера родительской записи p
- del(T,k) – удаление из таблицы T записи с идентификационным номером k, при этом вместе с упомянутым элементом удаляются все связанные записи с более низкими уровнями иерархии (дочерние, дочерние дочерних и так до самого конца). Такой способ удаления обеспечивает сохранение целостности иерархической структуры, которая предусматривает наличие родителя для каждого элемента, кроме начального. Начальный элемент является единственным, у которого вместо номера родительского элемента указывается нулевое значение.
- down(T,k) – обеспечивается выделение всех дочерних записей
по отношению к записи с идентификационным номером k
- up(T,k) – обеспечивается возврат на предыдущий (родительский)
уровень иерархии относительно дочерней записи с идентификационным номером k посредством выделения записей, принадлежащих одному и тому же родителю
Следующая ниже алгебраическая спецификация полностью описывает
структуру объектов и основные функции первого способа представления.
Второй способ представления иерархии
При этом способе представления ключевое выражение таблицы, однозначно идентифицирующее каждую запись таблицы, определяется атрибутом Id, где Id=(n1,n2,n3,….,nk) – где ni (i=1..k)– натуральные числа, определяющие номера вершин на каждом уровне иерархии. Таким образом данный атрибут представляет из себя список, однозначно определяющий полный путь соответствующей записи, начиная от корня иерархии до текущей записи. Поскольку идентификационное выражение для каждой записи представляется в виде списка, то вместо понятия идентификационного выражения будем употреблять термин «идентификационный список», или для сокращения – «идентификатор». Последнее число идентификатора записи (nk) будем называть собственным номером записи. Для данного способа также определены те же самые основные операции над иерархическими структурами, что и в первом способе. Однако определения и реализация этих операций являются другими в соответствии с учетом своей специфики кодировки.
Следующая ниже алгебраическая спецификация полностью описывает
структуру объектов и основные функции второго способа представления.
2.3 Третий способ.
Данный способ представления иерархии основывается на создании
специальных отношений между 2-мя или более таблиц. Здесь ограничимся рассмотрением 2-х таблиц, имея в виду, что все результаты, получаемые в этом случае легко можно обобщить для большего количества таблиц. Такие отношения между таблицами классически делятся на виды:
«один ко многим», «один к одному» и «многие ко многим». Для представления иерархии будем рассматривать только первый из перечисленных выше видов отношений. При этом способе представления ключевое выражение первой таблицы, определяется индексным выражением, однозначно идентифицирующее каждую запись таблицы, а в качестве 2-ого элемента отношения выбирается соответствующее индексное выражение второй таблицы. Наложим следующие ограничения на структуры упомянутых выше таблиц:
1)список атрибутов первой из таблиц T1 будем представлять в виде
(Id, a1,a2,..., ak), где Id- ключевой атрибут, a1,a2,..., ak – все остальные атрибуты таблицы T1; определим функцию fid(t) для выделения уникального номера записи t, то есть fid(t)= Id, причем t T1& s T1&st => fid(t) fid(s);
2) список атрибутов второй из таблиц T2 будем представлять в виде
(Par, a1,a2,..., am), где Par – номер родительской записи в таблице T1, a1,a2,..., am – все остальные атрибуты таблицы T1 ; функция fpar(t) определяет номер родительской записи в таблице T1 причем s T2=>(t T1).(fpar(s)= fid(t)) (нарушение этого условия рассматривается как нарушение целостности соответствующей базы данных).
Таким образом отношение иерархии между таблицами T1 и T2 можно определить следующим образом:
H(T1, T2) =df (t T1& s T1&st) => fid(t) fid(s)) &
(s T2=>(t T1).(fpar(s)= fid(t)))
Следующий ниже пример демонстрирует отношение иерархии
между двумя таблицами (отношение вида «один ко многим» ):
Таблица T1(список университетов)
Id Name
| 1 | Казанский университет | ||
| 2 | Московский университет | ||
Таблица T2 (список факультетов)
Par Name
| 1 | ВМК | |
| 1 | ФИЗФАК | |
| 2 | ВМК | |
| 2 | ФИЗФАК |
В последующем таблицу T1 будем называть родительской, а таблицу
T2-дочерней.
Определим основные операции для иерархических структур.
1.Add1(T,t) – добавление записи t в конец таблицы T c формированием в записи t уникального значения ключевого атрибута, то есть
maxcode(T) – максимальное значение номеров записей таблицы T,
то есть:
Эта операция применима только к таблице типа T1.
2.Add2(T1,T2,t,p) – добавление записи t в конец таблицы T2 c формированием в записи t номера родительской записи p, то есть
T2= (t1, t2,…, tn) & (t T1)(fid(t)= p) =>
Add2(T1,T2,t,p) = (t1, t2,…, tn,fill2(t,p)),
где fill2(t,p)=( p, a1,a2,..., ak)
3. del1(T,k) – удаление из таблицы T записи с номером k, то есть
Эта операция применима только к таблице типа T1.
4.Delcs(T1,T2,k) – удаление из таблицы T1 записи с номером k. При удалении записи из родительской таблицы в дочерней таблице происходит удаление всех соответствующих дочерних записей.
Таким образом:
Delcs(T1,T2,k) =df (T1=Del1(T1,k) & T2= Del2(T2,k)), где T1 и T2 определяют новые состояния таблиц T1 и T2 после выполнения операции удаления,
Del2(T,k) ) =df IF(T=nil, nil, IF(fpar(head(T))=k, Del2(tail(T),k), cons(head(T), Del1(tail(T),k)).
Функция Delcs(T1,T2,k) определяет так называемое каскадное удаление
(CASCADE). Выполнение этой операции возможно лишь в том случае, если на соответствующее отношение не наложено ограничение на удаление (RESTRICT). В противном случае из родительской таблицы разрешено удалять только те записи, для которых нет дочерних записей.
5.Down1(T1,T2,k) – обеспечивается выделение всех тех записей из таблицы T2, являющихся дочерними по отношению к записи таблицы T1 с номером k. То есть
Down1(T1,T2,k) =df IF( IsPar1(T1,k), Down2(T2,k), nil),
IsPar1(T,k) =df (t T).(fid(t)=k) (функция проверки существования записи с номером k в таблице T )
Down2(T,k) =df IF(T=nil, nil, IF(fpar(head(T))=k, cons(head(T),
Down2 (tail(T),k)), Down2 (tail(T),k)))
6.Up1(T1,T2) обеспечивается возврат на родительский уровень иерархии, Up1(T1,T2) =df T1.
Использование приведенного выше способа представления иерархии для больших глубин иерархии является нецелесообразным, так как требует привлечения большого количества таблиц и соответственно может серьезно
снизить эффективность обработки иерархических структур.
Третья глава описывает разработанные автором средства, обеспечивающие перевод формализованной модели в соответствующие средства СУБД Visual Foxpro, MS SQL и JAVA среды. Кроме этого предлагаются средства преобразования данных таблицы представления иерархии второго типа в данные таблицы представления иерархии первого типа.
Структура таблицы для первого способа представления иерархии:
Для данной таблицы:
- Id – уникальный номер записи, имеет числовое значение
- Par – номер родительской записи, имеет числовое значение
- Name – имя записи, имеет символьное значение
- Prs – признак записи, указывающий наличие дочерних элементов, имеет символьное значение
Структура таблицы для второго способа представления иерархии:
Для данной таблицы:
- kod – уникальный номер записи, имеет символьное значение
- Name – имя записи, имеет символьное значение
- Prs – признак записи, указывающий наличие дочерних элементов, имеет символьное значение
Модуль преобразования данных таблицы представления иерархии второго типа в данные таблицы представления иерархии первого типа.
Схематично процесс преобразования данных можно изобразить в виде следующей блок-схемы.
Данный модуль использует методы, ранее реализованные в классах представления таблиц, для получения данных содержащихся на различных уровнях таблиц.
Для каждого уровня иерархии таблицы второго типа происходит считывание всех записей данного уровня и сопоставление их идентификаторов, соответствующих идентификаторам в таблице первого типа.
В четвертой главе приводится описание демонстрационной модели на примере системы автоматизации учета автомобильного транспорта с целью обоснования работоспособности предлагаемых в диссертации средств и методов.
Заключение
В соответствии с поставленной задачей в диссертационной работе создана специализированная модель для класса информационно-расчетных задач на основе расширения реляционной модели средствами алгебраических спецификаций и функционального языка программирования. Также создана интегрированная среда разработки информационно-расчетных задач на основе построенной специализированной модели и предложены адекватные способы представления и исследования иерархических структур данных в рамках реляционной модели на основе алгебраических спецификаций и функционального языка программирования.
Основная особенность упомянутой интегрированной среды разработки заключается в том, что она включает в себя наряду с формализованными средствами модели средства реализации модели в программную среду СУБД Visual Foxpro, MS SQL и системы JAVA.
Благодарности. Автор выражает искреннюю благодарность своему
научному руководителю Арслану Ильясовичу Еникееву за постоянное внимание и неизменную поддержку данной работы.
Публикации по теме диссертации
Работа опубликованная в журнале, входящем в Перечень ВАК :
- Камашев М.А. Специализированные модели для разработки программных приложений на основе алгебраических спецификаций и средств функционального программирования// Системы управления и информационные технологии. Научно-технический журнал № 4(42). – Воронеж: Изд-во «Научная книга», 2010. – С. 73-78 ISSN 1729-5068.
Другие публикации :
- А. И. Еникеев, Т. Бендума, М. А. Камашев. Специализированные объектно-ориентированные модели программных систем. // Материалы XV Международной конференции Проблемы теоретической кибернетики (Казань, Россия, 2–7 июня, 2008). – Казань: Изд-во «Отечество», Июнь 2008. – С. 36-37.
- Камашев М.А, Специализированная обьектно-ориентированная модель для представления иерархических структур// Информационные технологии моделирования и управления. Международный научно-технический журнал № 5(64). –Воронеж: Изд-во «Научная книга», 2010. - С. 669-678. ISSN 1813-9744
- Камашев М.А. // О технологии создания специализированных объектно-ориентированных приложений Исследования по информатике. Вып. 11. – Казань: Изд-во “Отечество”, 2007. - С. 123-128.
- Камашев М.А. // Описание программного обеспечения// Техника и технология", №4 (июль)– Москва: Изд-во “Спутник+”, 2011. - С. 17-38
