автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Матрично-реляционная модель данных в организационно-производственных системах мониторинга и управления

На правах рукописи

г»-

ет. -г О"

- ас

зс 3 •гг

сч»

<=> УДК 681.3.06:800.92

Ковтун Игорь Иванович

МАТРИЧНО-РЕЛЯЦИОННАЯ МОДЕЛЬ ДАННЫХ В ОРГАНИЗАЦИОННО-ПРОИЗВОДСТВЕННЫХ СИСТЕМАХ МОНИТОРИНГА И УПРАВЛЕНИЯ

Специальность 05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

Автореферат диссертации па соискание ученой степени кандидата технических наук

*ч У

Москва 1997

Работа выполнена в Московском государственном институте электроники и математики (техническом университете).

Научный руководитель: доктор технических наук, профессор Кравченко Виктор Алексеевич.

Официальные оппоненты: доктор технических наук, профессор Подбельский Вадим Валериевич; кандидат технических наук, старший научный сотрудник Фоминых Игорь Борисович.

Ведущая организация: в/ч 11135.

Защита диссертации состоится у 1997 года

часов на заседании диссертационного совета Д0636805 при

Московском государственной институте электроники и математики по адресу: 109028, г. Москва, Б.Трехсвятительскин (Б.Вузовский) пер., д.3/12 .

С диссертацией можно ознакомиться в библиотеке МГИЭМ.

Автореферат разослан «_»_1997 года

Ученый секретарь диссертационного совета кандидат технических наук, доцент

Бузников С. Е.

Общая характеристика работы Актуальность проблемы

Организационно-производственные системы мониторинга и управления играют одну из важных ролей в деятельности предприятий и учреждений.

Одной го серьезных проблем создания автоматизированных систем является конструирование конкретной базы данных.

Наибольшее распространение получили реляционная модель, обладающая простотой, независимостью представления данных от их организации и хорошей формализуемостью, и сетевая модель, позволяющая исключать избыточность данных и организовывать высокие скорости их обработки. Недостатком реляционной модели является неэффективность организации' связей между множествами разнотипных объектов. Недостаток сетевой модели - неудовлетворительные средства представления информации.

Цель работы

Цель диссертационной работы - разработка модели данных, совмещающей наглядность представления информации в реляционной модели и достоинства физической организации данных в сетевой.

Методы исследования

Основные методы исследования:

■ чтение и анализ научной литературы;

В чтение и анализ технической документации известных СУБД; Я участие в научно-исследовательских работах по тематикам кафедры АИЛУ МГИЭМ; В участие в договорах кафедры АИЛУ МГИЭМ, НИЦ ИТЭП, ГУВД МО, СК МВД России.

Научная новизна

Разработана матрично-реляционная модель данных, которая, сохраняя все достоинства реляционного подхода, позволяет моделировать связи между множествами объектов в виде матриц, называемых перемычками. Механизм перемычек позволил:

■ уменьшить избыточность информации и повысить скорость ее обработки; В упростить языки запросов к базам данных;

В упростить языки модификации баз данных;

В упростить модификацию баз и обрабатывающих алгоритмов в процессе сопровождения автоматизированных организационных и производственных систем. •

Практическая ценность

Матрично-реляционная модель данных использована:

■ при разработке и создании национального регистра больных сахарным диабетом (внедрен в эксплуатацию и растиражирован);

И при разработке и создании системы учета материальных ценностей в подразделениях МВД (внедрена в опытную эксплуатацию);

И при создании программы учета потерпевших по уголовному делу N47265 в ГУВД Московской области (внедрена в эксплуатацию);

■ в ходе научно-исследовательских работ по тематикам кафедры АИПУ МГИЭМ (отмечены дипломами).

Апробация работы

Апробация работы состоялась:

■ на международном студенческом школе-семинаре «Новые ' информационные технологии в образовании» в г. Гурзуфе в 1993 году;

■ на международном студенческом школе-семинаре «Новые информациошше технологии в образовании» в г. Гурзуфе в 1994 году;

в на конкурсе «Молодые дарования» в г. Москве, организованном Российской академией наук в 1994 году;

■ на научно-технической конференции-конкурсе молодых специалистов, организованная МГИЭМ в 1994 году;

■ ненаучном семинаре «Управление и устойчивость» кафедры «Кибернетика» МГИЭМ в 1997 году;

В на собраниях преподавательского и ученого состава кафедры АИПУ МГИЭМ в 19941997 г.

На защиту выносятся

1. Матрично-реляционная модель данных.

2. Система модификации матрично-реляционных БД.

3. Матрично-реляционная алгебра.

4. Матрично-реляционные исчисления.

5. Подходы к построению организационно-производственных систем на основе

матрично-реляционной модели данных.

Публикации

Список опубликованных работ приведен в конце данного автореферата.

Структура и объем работ

Диссертационная работа включает:

• печатную работу на правах рукописи, в которой: • 183 страницы, содержащие:

• 5 глав, в которых:

• 12 определений;

• 4 теоремы;

• 34 рисунка;

• основные результаты;

• список литературы из 71 наименования;

• список терминов и сокращений;

» 3 приложения, в которых:

• копии актов о внедрении и дипломов;

• фрагменты экрашагх форм разработанных систем;

• фрагменты исходных текстов программ.

Содержание работы

Глава 1 посвящена анализу проблем моделирования данных. Определены цели и задачи диссертационной работы. Кратко изложены способы их решения.

Глава 2 посвящена матрично-реляционной алгебре. Описана система модификации ее носителя. Формализована связь матрично-реляционной алгебры с реляционной.

Глава 3 посвящена матрично-реляционной базе данных и языкам запросов к ней. Разработан формализм использования матрично-реляционной модели в продукционных системах.

Глава 4 посвящена физической организации данных при использовании матрично-реляционной модели на логическом уровне представления информации.

Глава 5 посвящена систематизации построения организационно-прогаводственньк систем на основе матрично-реляционной модели.

Глава 1

Под организационно-производственными системами мониторинга и управления даштмаются автоматизированные системы управления, автоматизированные системы управления производством, автоматизированные системы управления технологическими процессами, автоматизированные информационные системы, банки данных.

Показано, что одной из важнейших проблем создания организационно-производственных систем является конструирование базы данных (БД).

Проводится анализ существующих методов и моделей организации и обработки

данных.

Установлено; что основными достоинствами сетевых и иерархических моделей являются малая избыточность данных и высокие скорости обработки взаимосвязей между множествами разнотипных объектов, а недостатками - большая зависимость алгоритмов от данных и плохая сопровождаемого систем.

Достоинства реляционного подхода: ■ база данных представляется как совокупность двумерных таблиц, поиск и обработка информации в которых не зависит от организации и хранения данных в памяти ЭВМ, что упрощает взаимодействие пользователя с автоматизированной системой; ■. реляционная БД с математической точки зрения - конечный набор конечных отношений различной арности, над которыми можно осуществлять различные алгебраические операции. Таким образом, теория реляционных баз данных является областью приложений теории множеств и математической логики.

Выявлен недостаток реляционной модели - неэффективность моделирования связей типа «один к одному», «один ко многим» и особенно «многие ко многим» между множествами разнотипных объектов.

Поставлена цель и намечены пути ее реализации, состоящие в следующем. В основу положена реляционная модель. Однако данные, обеспечивающие связь между двумя таблицами, представлены в виде матрицы, число строк (столбцов) в которой равно числу кортежей одной таблицы, а число столбцов (строк) - числу кортежей другой. Если между некоторыми кортежами двух таблиц есть связь, в пересечении соответствующей строки и столбца матрицы ставится единица; в противном случае - ноль. Матрицу, реализующую связь между двумя множествами объектов, предложено называть перемычкой, а модель, в которой данные представлены с помощью отношений (таблиц) и перемычек - матрично-репяционной моделью данных. Поскольку сами по себе элементы матриц не несут полезной информации, предложено рассматривать пятерки вида (r(R), fj Ls. r±s, gsj_r, s(S)), где r(R) и s(S) - двумерные таблицы, в теории реляционных БД называемые отношениями, ris - перемычка между ними, a frxs и - функции, названные связующими функциями, которые устанавливают взаимно однозначное соответствие между кортежами отношения r(R) и строками (столбцами) перемычки r_Ls и

кортежами отношения s(S) и столбцами (строками) перемычки rJ_s соответственно.

\

Указанные пятерки предложено называть связями. Пятерки вида (r,(R), fru.s|, r,_Ls,, gsiiri, s,(S)), где ri(R) и Si(S) - двумерные таблицы, riJ-Sj - перемычка между ними, a f*rj_Lsi и gsijji - связующие функции, где в каждой строке и в каждом столбце перемычки г¡Xs, хоть один элемент равен 1, предложено называть бинарными звеньями. В каждой связи предложено выделять (см. определение 4) бинарное звено. Отношения реляционной

алгебры, например отношения г(Л), э(8) названы упорными звеньями. В основу матрично-реляционной модели данных предложено положить матрично-реляционную алгебру, носителем которой является множество унарных и бинарных звеньев; Для унарных звеньев (отношений) Кодцом и Мейером разработаны следующие операции: объединение, пересечение, разность, активное дополнение, проекция,' селекция, переименование, 8-соединение, естественное соединение (в т.ч. декартово произведение), деление. Предлагается доказать теорему о том, что бинарные звенья являются отношениями реляционной алгебры. Тогда для них можно доработать

г

операции над унарными звеньями. Так же предложено разработать еще две операции: операцию, операндом которой является унарное звено, а результатом - бинарное, и операцию, операндом которой является бинарное звено, а результатом - унарное. Совокупность введенных операций и операций реляционной алгебры предложено положить в основу сигнатуры матрично-реляционной алгебры.

Вышеописанный подход к представлению данных имеет следующие достоинства:

■ упрощение языков запросов матрично-реляционной модели в сравнении с реляционной, так как бинарные звенья позволяют моделировать два множества объектов разных типов и связь между ними как одно отношение, тогда как в реляционной модели для этого требуется в зависимости от типа связи два-три отношения;

И значительная экономия машинной памяти, так как на уровне физической • организации уменьшается избыточность данных, характерная при моделировании связей для реляционной модели, за счет хранения ссылок на элементы базы (таких элементов в некоторых базах может содержаться до нескольких миллионов) вместо хранения действительных значений этих элементов; И увеличение скорости обработки базы данных, так как поиск ответов на сложные запросы ведется не путем анализа данных (особенно длинных строк), а путем поиска , элементов базы по их ссылкам;

И упрощение языков и алгоритмов модификации информации, так как при изменении ключей объектов отпадает необходимость изменения ключей объектов в таблицах, моделирующих связь;

И упрощение процесса сопровождения организационно-производственных систем мониторинга и управления, гак как при изменении типа взаимосвязей между двумя множествами объектов не нужно модифицировать структуру базы, а достаточно изменить признак матрицы;

■ матрично-peляциоиная модель будет дальнейшим развитием реляционной и будет обладать ее важнейшими достоинствами, а именно, независимостью представления данных от их физической организации и хорошей формализуемостью.

Глава 2

В основу формализации модели положены следующие определения, данные Мейером:

■ схемой R отношения г называется конечное множество имен атрибутов {Аь Аг, ..., АЛ;

■ доменом атрибута А; называется множество D„ которое ставится в соответствие каждому имени атрибута А,. Соответствия задаются с помощью некоторой функции dorn. Здесь 1 < i < п. Домены являются произвольными непустыми множествами чисел или строк конечных длин;

В отношение г со схемой R - это конечное множество функций {t,, t2, ..., tp} из R в D = D( U D2 U ... U Dtt; причем каждая функция ter должна удовлетворять следующему ограничению: t(A,) принадлежит D„ 1 < i < п. Эти функции называются кортежами; мощностью отношения г, обозначаемой как I ri, называется количество кортежей отношения г.

Даны формальные определения основных понятий:

Определение 1. Унарным звеном называется отношение r(R), имеющее вид таблицы, где строки (столбцы) являются кортежами, а значения в столбцах (строках) соответствуют одному и тому же домену.

Определение 2. Пусть заданы унарные звенья г и s. Пусть Iii = а, I si = ß. Перелшчкой звеньев г и s называется матрица M[m,j]axii, где каждому кортежу t зв^на г взаимно однозначно соответствует некоторая строка i матрицы М, задаваемая функцией frJ.s, и каждому кортежу и звена s взаимно однозначно соответствует некоторый, столбец j матрицы М, задаваемый функцией ' gs±r. Элементами матрицы - М[ту]дар являются ноли и единицы. Функция frl! называется связующей функцией звена г со звеном s. Функция g,,ir называется связующей функцией звена s со звеном г.

def '

Обозначение: ris = М[Шц}ахр. ' ' ' -

г-

Определение 3. Связью t(RlS) называется пятерка (r(R), frls, ris, gs±r,

s(S)).

Определение 4. Пусть задана' связь (r(R), fris, ris, gslr, s(S)). Рассмотрим в звеньях r(R) и s(S) множества всех, кортежей, для которых в соответствующей строке (столбце) перемычки ris хоть один элемент равен 1. Обозначим их как унарные звенья ri(R) и s ¡(S). Такое обозначение правомерно по определению отношения, так как подмножество некоторого множества также является множеством. Функции frJ.s и gslr однозначно определяют перемычку rils!. Уменьшим область определения frls до г3, а область определения gsj.r до S). Переименуем frls и gsir в frli_sl и gsUji соответственно. Бинарным звеном называется пятерка (rt(R), frIisl, i^lsj, gsUri. Si(S)).

* def

Обозначение: t = t(RlS) = t(r„s,) = t(ri(R),s,(S)) = (r,(R), frlJtsb r,±s„ s,(S».

Бинарное звено (г,(К), frlisb r|lsb gsJir!, s,(S)) названо активной частью связи (r(R), frls, ris, g^j, s(S)); r,(R) - активной частью r(R); a Sj(S) - активной частью s(S). t, ri, s, названы неявными звеньями, a r, s - явными звеньями.

Пусть задана связь t = (r(R), frls, ris, g^, s(S)). Ее активная часть обозначена t = (r,(R), frixsi, r,ls,, gsiiri, S|(S)). В операторах модификации под таким обозначением подразумевается связь, а в операциях матрично-реляционной алгебры - бинарное звено.

Определение 5. Пусть задано бинарное звено t(RlS) = (r(R), frxs, ris, gs±r, s(S)). Схемой бинарного звена t называется множество {R,S}.

• def

Обозначение: RIS = {R,S}.

Две схемы бинарных звеньев R,1S| и R2IS2 равны, если множества {RbS,} и {R2,S2} равны.

Определение 6. Пусть задано бинарное звено t(RlS) = (r(R), frj_s, ris, gsir, s(S)) и D = Dr U Ds. Кортежем z бинарного звена t называется функция из R U S в D, такая что z(R) = x(R) и z(S) = y(S), и элемент перемычки ris, определяемый функциями frls при подстановке х и gsXr при подстановке у, равен 1, где х и у - кортежи звеньев г и s соответственно.

Обозначение: z = z(R1S) = z(x,y).

Доказана следующая теорема:

Теорема 1. Множество кортежей бинарного звена является отношением.

Введено отношение равенства на множестве бинарных звеньев: бинарные звенья равны, если множества их кортежей равны.

Следствие теоремы 1. Операции реляционной алгебры разработаны для обработки отношений. Бинарное звено абстрагировано до отношения. Следовательно, на множестве бинарных звеньев применимы операции реляционной алгебры.

Ввиду того, что в схеме бинарных звеньев появляется дополнительный элемент - символ перемычки, было необходимо доработать формальные определения реляционных операций над бинарными звеньями. Результаты доработки в совокупности с определениями реляционных операций имеют вид: Пересечение: ^И) = г(Я) П 5(11) = {г(К.) | Зхег(И) ЗуевСЙ.): г=х а 2=у}; ¡ОШ) = г(Я18) Р]Х1т) = {г(Ш-8) | Зхег(Ш-8) ЗуевСЕЦЗ) : г=х а г=у}. Объединение: 1(Я) = г(В.)и 5(11) = {г(К.),| (Зхег(К): г=х) V (Зу=5(К): г=у)>; 1(1118) = г(&18) и = {гСКХБ) | (Эхе 1(11X5): г=х) V (ЗуейОт) : г=у)}.

Разность: 1(И) = г(К) - 5(В.) = {'¿(К) | Зхег(П) : Ууе5(Я) гФу\;

г(1а8) = г(1и-8)- эСШ-Б) = (гСШ-в) I Зхег(К15) : \7y6sCRjLS) л

Активное дополнение: 1(Я) = ас!от(К,г) - г(Д), где ас!от(11,г) - множество всех кортежей над атрибутами схемы К и их активными доменами относительно г; ^Ю-Б) = ас1от(Ю-8,г) - г(Ю.Б) , где аск>т(Щ.8,1) - множество всех кортежей над атрибутами схемы Ьи.Б и их активными доменами относительно г. Выбор (селекция): 1(К) = стЛ,а(г(К)) = ^(И) | Зхег(И): г=х л х(А) = а}; Г(1т) = стА-_,(г(Я±8)) = {г(Ю_8) I ЗХ6Г(Ю.8): 2=х а х(А)=а}.

Переименование: «(К-А)В) = 5А^ь(г(И)) = {г(К-А)П ! Зхег(Я) : г(К - А) = х(К - А) л г(В) = х(А)}; ,

1((К-А)В1.8) = 6а_в(г(Ю.5)) = {г(11-А)В±8 | Зхег(Ю_8): г(11-А±8) = х(К-А15) л 2(В) = х(А)}.

Проекция : г(Х) = ях(г(11)) = {г(Х) I Эхег(И): г(Х)=х(Х)}; 1. г,(Х) = тгх(1(К18)) = {г(Х) | Зхег(Я): г(Х)=х(Х)}, если ХеК.; 2.8,(Х) = ях(1(Ю.8)) = {г(Х) | ЗхеХБ): г(Х)=х(Х)}, если Xев;

3. t,(X'_LX") = JTx(t(RlS)) = {z(X'±X") I 3xet(Ri_S): z(X'1X")=x(X,1X")}, если X' eR, X"eS, X=X'{JX".

Естественное соединение: t(RQS) = r(QR)As(QS) = {z(RQS) I 3xer(QR) 3yes(QS)': z(QR)=x(QR) л z(QS)=y(QS)};

p(QPR-LS) = t(PR±S)Aq(QP) = {z(QPRlS) | Bxst(PRlS) 3yeq(QP): z(PRJ_S)=x(PR-LS) л z(QP)=y(QP)}.

Деление: t(Q) = r(QS>s(S) = (z(Q) | Vxes(S) 3ye<QS): y(Q)=z л y(S)=x}; t(R±S)=r(RQ±S>s(Q)={z(RIS) [ Vxes(Q) 3yer(RQ±S): y(RJ_S)-z л y(Q)=x}. 0-соединение:

t(RS) = r(R)[A9BJs(S) = {z(RS) | 3xer(R) 3yss(S): z(R)=xл z(S)=y л x(A)Gy(B)}; p(QR-LS) = t(Ri.S)[A0B]q(Q) = {z(QR1S) | 3xetCRJ-S) 3yeq(Q) : z(R_LS)=x л z(Q)=y л x(A)9y(B)}.

Соединение на перемычке: q(RS) = aA,a(t(RiS» = {z(RS) I 3xet(RJLS) : z(^)=x(R) л z(S)=x(S) л x(A)=a}.

Разложение: t(R_!S) = %;S(q(RS)) = {z(R_LS) | 3xeq(RS) : z(R)=x(R) л z(S)=x(S)}. Дано формальное определение матрично-реляционной алгебры: Определение 7. Пусть: И U - множество атрибутов, называемых универсумом; i D - множество доменов; И dorn - полная функция из U в D;

В R = {R|, R2,..., Rp} - множество схем унарных звеньев, где Re U;

0 г = {ri, г2, -.., tp} - множество таких наборов унарных звеньев, что унарное звено из п имеет схему Ri; 1 < i < р;

53 е = {ej(ej', ej")} - множество связей, где 1 < j < ш,

р

такое, что для любого] следует ej\ ej" с 1Л,;

¡=i

В t = {tj(t'j,t"j)}, 1 < j < m, - множество всех бинарных звеньев, таких что для каждого t(t',t") из t взаимно однозначно существует элемент е(е',е") ю е, такой, что t(t',t") -активная часть е(е',е");

01 N - множество имен; ^ 1

р ш ш га m

И паше - полная функция из X = {U^ U Uej U Utj U Ц' U Ц"} в N,

i-1 j = l j-i j = i j = i

такая что name(ej) =name(tj) для любого j = l,m, и -name(x') Ф name(x"), гдех',х"с: X

во всех остальных случаях; ■ 0 - множество бинарных отношений над доменами из D, содержащее по крайней мере отношения равенства и неравенства для каждого домена.

Матрично-реляционной алгеброй называется набор Algebra = {U, D, dorn, R, г, е, t, N, name, ©, О}, где О - множество вышеперечисленных операций над унарными и бинарными звеньями.

Показано, что преимущества матрично-реляционной алгебры над реляционной проявляются при постановке запросов на нахождение взаимосвязей между неключевыми признаками двух множеств разнотипных объектов. Приведены примеры.

Доказана следующая теорема:

Теорема 2. Реляционная алгебра является подалгеброй матрично-реляционной, в которой отсутствуют операции разложения и соединения на перемычке.

Следствие теоремы 2. Если в силу каких либо обстоятельств нельзя воспользоваться формализмом матрично-реляционной алгебры, а именно запрограммировать механизм хранения и обработки бинарных звеньев, можно попытаться свести представление базы к совокупности унарных звеньев и воспользоваться формализмом реляционной.

Разработаны следующие операторы модификации матричио-реляционяых структур.

Create relation(...). Данный оператор создает в базе новое унарное звейо.

Delete relatlon(...). Оператор удаляет из базы унарное звено.

Create chain(...). Оператор создает в базе связь и одноименное бинарное звено.

Delele chain(.,.). Оператор удаляет из базы связь и одноименное бинарное звено. Причем унарные звенья, на которых определена связь, не удаляются.

Connection(...). Оператор настраивает физическую структуру перемычки на определенный тип связи;

ADD(...). Оператор создает в унарном звене дополнительный кортеж, а во всех необходимых перемычках - строку (столбец), все элементы которой равны 0.

DEL(...). Оператор удаляет в унарном звене кортеж, а из всех необходимых перемычек - строки, соответствующие этому кортежу.

СЩ...). Оператор изменяет в унарном звене кортеж..

CR(...). Оператор присваивает некоторому элементу перемычки значение 1, при условии, что он равен 0.

FILL(...). Оператор присваивает некоторому элементу перемычки значение 1-.

CASTf...): Оператор присваивает некоторому элементу перемычки значение О, при условии, что он равен 1.

CL(...j. Оператор присваивает некоторому элементу перемычки значение 0.

IN(...}. Оператор изменяет некоторый элемент перемычки.

Показано, что система модификации матрично-реляционных БД позволяет писать' более простые алгоритмы модификации базы, нежели система модификации реляционных при моделировании той же информации. Приведены примеры.

Глава 3

Даны формальные определения матрично-реляционной модели и матрично-реляционной базы данных.

Определение 8. Матрично-реляционной моделью данных называется

десятка Model ~ (U, D, dorn, R, г, е, t, N, name, ©).

«

Принято, что схема S унарного звена s состоит из двух частей R и К, где R с: R, а К - множество ключей. Введено S - множество схем, такое что для любого унарного звена s из любого набора г с г существует единственная S с S, заданная функцией sch.

Это позволило дать определения:

Определение .9. Схемой матрично-реляционной базы данных называется двойка Scheme = (S,N).

Определение 10. Матрично-реляционной базой данных со схемой БД Scheme = (S,N) называется троГжа Base = (г, е, t).

Разработаны формы представления данных в рамках матрично-реляционной модели. Преимущества форм представления матрично-реляционной БД по отношению к формам представления реляционной заключаются в более простых механизмах модификации базы в процессе сопровождения автоматизированных систем и показаны на примерах.

Язык магрично-реляционного исчисления кортежей является языком исчисления предикатов первого порядка.

Алфавит языка включает в себя следующие группы символов: В элементы универсального множества имен атрибутов U;

■ константы - элементы множеств dom(A) для каждого атрибута А из U; В переменные кортежи - хь х2,..., х„ ...;

в элементы множества 0 бинарных знаков сравнения в доменах; В элементы множества имен явных и неявных унарных звеньев (г,, т2,... гр); В элементы множества имен бинарных звеньев {qb q2,... qs};

■ логические связки-л, v,-I;

■ кванторы - V, Э;

В разделители -[,],(,),,;

■ символ перемычки -1.

Аксиомы матрично-реляционного исчисления кортежей бывают трех типов: И г(х) - слово, означающее что переменный кортеж х унарного или бинарного звена г

принадлежит этому звену; В х(А)8у(В) - слово, где х и у переменные кортежи; 060 - знак сравнения; А и В -

атрибуты из U, которые 9-сравнимы; В х(А)9с, d9y(B) - слова, где х и у переменные кортежи; Ое© - знак сравнения; А и В -атрибуты из U, с - константа из dom(A); d - константа из dom(B).

Правильно построенные формулы матрично-реляционного исчисления кортежей определены рекурсивно следующими правилами вывода: В каждое слово - формула; В если f - формула, то -.f - формула; В если fug формулы, то f л g и f v g - формулы;

В если х - переменный кортеж унарного звена, f - формула, включающая х, a R -

подмножество U, то 3x(R)f и Vx(R)f - формулы; В если z - переменный кортеж бинарного звена, g - формула, включающая z, а Р и Q -

подмножества U, то 3z(PJLQ)g и Vz(P_LQ)g - формулы; В если f - формула, го (f) - формула.

Проведена доработка правил вывода, что позволило выделить множество разрешенных формул. Введена интерпретация J и придан смысл разрешенным формулам матрично-реляционного исчисления кортежей. Пусть F = -(x(R) | h(x)} и F' = (z(PJ-Q) ! g(z)} " разрешенные формулы. Значением F на текущем состоянии модели данных Model называется унарное звено F(Model) со схемой R, содержащее все кортежи tedom(R), такие что J(h(t)) = истина, а значением F' - бинарное звено F'(ModeI) со схемой P-LQ, содержащее все кортежи s e dom(PlQ), такие что J(g(s)) = истина.

Согласно определению языка реляционного исчисления кортежей данного Мейером, язык матрично-реляционного исчисления кортежей является его расширением.

■ Выделено подмножество безопасных выражений • матрично-реляционного исчисления кортежей, которые позволяют сформулировать практически все необходимые запросы к базе отношений. В качестве примера рассмотрен кортежеориентированный язык SQL. Установлено, что запросы к матрично-редяционным БД на SQL более просты, чем к реляционным. Приведены примеры.

Проведена доработка матрично-реляционного исчисления кортежей для применения в продукционных системах. Показано, как SQL может быть использован для формирования условий применимости продукций.

Разработано матрично-реляционное исчисление доменов.

Глава 4

Показано, что матрично-реляцио иная модель может служить формой представления сетевых и реляционных БД.

Обосновано утверждение о том, что для представления одной и той же информации матрично-реляционная модель требует меньше оперативной памяти, чем реляционная; либо в рамках реляционной модели прикладному программисту необходимо вкладывать дополнительные трудозатраты.

Обосновано утверждеше о том, что обработка целого ряда запросов в рамках матрично-реляциошюй модели может выполняться быстрее, чем в реляционной, так как в основу физической организации данных магрично-реляционной модели можно положить методы организации данных сетевых и иерархических моделей.

Рассмотрены методы организации текстовой и слабоструктурируемой информации в рамках матрично-реляциошюй модели.

Поставлена задача нахождения оптимального кол!гчества файлов и размеров кусков текстов непрерывной записи в них для эффективного хранения страниц переменных длин. Решение поставленной задачи сведено к известным.

Разработаны средства физической организации страниц переменных длин на внешних носителях, учитывающие результаты решения поставленной задачи и позволяющие использовать матрично-реляционную модель для представления текстовых БД. " ' '

Глава 5

Отмечено, что разработка организационно-производственных систем мониторинга и управления включает в себя три составные части:

■ разработка модели данных для органгоащш и обработки информации;

■ разработка программного и алгоритмического обеспечения;

■ разработка пользовательского интерфейса.

Установлено, что эти составляющие обозначенных систем не могут вестись раздельно. Более того, установлено, что именно структура данных определяет экранные формы и алгоритмы программ. Определены основные подходы к построению пользовательского интерфейса и обрабатывающих алгоритмов для матрично-реляционной модели, а также показано их применение на основе разработанных автором следующих организационно-производственных систем:

■ автоматизированной информационной системы «Вольница»; Ш экспертной продукционной системы управления «Продус»;

■ информационно-справочной системы «Репетитор».

Основные результаты

Достигнуты следующие результаты:

1. Разработано формальное описание основных структурных единиц матрично-реляционной модели данных - перемычек, связей, унарных и бинарных звеньев и операций над звеньями; а также доказана теорема о том, что бинарные звенья являются отношениями теории реляционных БД. Разработанные математические конструкции и доказанная теорема позволили положить совокупность унарных и бинарных звеньев в основу носителя, а совокупность разработанных операций и операций реляционной алгебры - в основу сигнатуры матрично-реляционной алгебры.

2. Формализовано определение матрично-реляционной алгебры, носитель которой может быть положен в основу матрично-реляционной модели и матрично-реляционных БД, а сигнатура служить основой процедурных языков запросов к матрично-реляционным БД.

3. Доказана теорема о том, что реляционная алгебра является подалгеброй матрично-реляционной, в которой отсутствуют операции разложения и соединения па перемычке. Данная теорема показывает связь (дальнейшее развитие) матрично-реляционной алгебры с реляционной. Выделен класс практических задач и приведены примеры, в которых применение матрично-реляционной алгебры предпочтительнее.

4. Разработаны формальные описания матрично-реляционной модели и матрично-реляционной БД, позволившие разработать способы группировки элементов данных в рамках матрично-реляционной модели, а также применить в качестве декларативных систем запросов к матрично-реляционным БД исчисление предикатов первого порядка.

5. Разработана система модификации матрично-реляционных баз данных, которая позволяет формировать более простые требования на изменение состояния базы, нежели система модификации реляционных БД. Выделен класс задач, где применение

системы модификации матрично-реляционных БД предпочтительнее. Приведены примеры.

6. Разработаны способы группировки данных в рамках матрично-реляционной модели, упрощающие сопровождение организационно-производственных систем. Выделен класс задач и приведены примеры, где очевидны преимущества матрично-реляционных форм представления перед реляционными.

7. Разработаны декларативные языки запросов к матрично-реляционным БД -матрично-реляционное исчислёние кортежей и матрично-реляционное исчисление доменов, а также доказаны теоремы о том, что по' своим выразительным возможностям они не уступают матрично-реляционной алгебре. Это позволило обосновать утверждения о том, что матрично-реляционные языки проще своих , аналогов, предназначенных для формирования запросов к реляционным БД.

8. Обосновано утверждение о том что кортежеориенгированные и доменоориентированные алгоритмические языки запросов, например SQL, могут быть применены к матрично-реляционным базам данных с незначительными доработками. Запросы при этом упрощаются. Приведены примеры.

9. Разработан формализм для применения матрично-реляционных БД в качестве Базы продукционных систем, а декларативных языков запросов к ним - в качестве основы продукционных алгоритмов обработки Базы, позволяющий использовать матрично-реляционную модель в экспертных продукционных системах управления. Доработаны основные конструкции SQL для его применения в таких системах. Приведены примеры.

10. Обоснована возможность применения матрично-реляционной модели для представления реляционных и сетевых БД, что позволяет использовать методы физической организации и обработки данных этих БД.

11. Определены основные подходы к построению пользовательского интерфейса и обрабатывающих алгоритмов для матрично-реляционной модели, что систематизирует разработку и создание организационно-прошводственных систем.

Литература

1. Ковтун И.И. «Разработка программно-информационного обеспечения гипертекстовой базы данных». - Стр. 167-168 в сб.: Международная студенческая школа-семинар «Новые информационные технологии в образовании». Гурзуф, май 1993.

2. Ковтун И.И. «Модели и программные средства гипертекстовой семантической БД». Стр.4 в сб. Тезисы докладов научно-технической конференции-конкурса студентов, аспирантов и молодых специалистов. 27-29 апреля 1994 г. Москва 1994.

3. Евсеев О.В. Ковтун И.И. «Модели и программные средства гипертекстовой емантической базы данных». Стр. 40-41 в сб. Новые информационные технологии, урзуф, май. 1994 г. • •

4. Кравченко В.А. Евсеев О.В. Нечаев А.М. Поневаж В.П. Титов В.И. Бураков :.Б. Ковтун И.И. Лисюткин Д.В. Олыпанников A3. «Математические модели и средства «строения интеллектуальных систем реального времени для мониторинга контроля и правления дискретными динамическими процессами». Стр. 258-262. в сб. Машиностроение, приборостроение, энергетика / Ред. кол. А.П. Тихонов. В.А. Садовничий и др. - М.: Изд-во Моск. ун-та, 1994. - 340 с. (Программа "Университеты 'оссии").

5. Евсеев О.В. Бураков С.Б. Ковтун И.И. «Объектно-продукционная модель и нструментальные средства для построения интеллектуальных систем управления еального времени». Труды Второго международного симпозиума «Интеллектуальные истемы». Том 1.- Москва. Издательство РУДН - ПАИМС, 1996 г. Стр. 28-33.

6. Ковтун И.И. «Матрично-реляционная модель данных в автоматизированных роизводственных системах». В журнале «Информатика-машиностроение». N3 1997 год. :тр. 2-il.

7. Ковтун И.И. Кузьмин И.В. «Матрично-реляционная модель данных в втоматизированных системах управления потоками процессуальных документов и рганами предварительного следствия». В материалах научно-практического семинара 1НИИ МВД «Персональный компьютер на службе криминальной милиции и следствия, возможности и перспективы». 1997 год. Стр. 54-61.