Автор неизвестен - Бионика интелекта информация язык интеллект№ 3 (77) 2011научно-технический журналоснован в октябре 1967 г - страница 68

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77 

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

3. Отображение компонентов реляционной модели данных в компоненты дедуктивной

Рассмотрение приведенных моделей данных показало, что реляционная модель данных (1) со­стоит из компонентов, описывающих структуру данных (2), целостную часть (3), представленную ограничениями целостности, и языков определе­ния и манипулирования данными (4).

В то же время дедуктивная модель данных пред­ставляется в виде множества фактов EDB, и ло­гической программы (5), состоящей из множеств правил вывода и ограничений целостности (8).

Проведенный выше анализ моделей данных по­зволяет сделать вывод о возможности отображения составных частей реляционной модели данных в компоненты дедуктивной (рис. 1).

Рис. 1. Отображение компонентов реляционной модели данных в компоненты дедуктивной

Для структурной части реляционной модели можно построить отображение в множество фак­тов экстенсионала EDB дедуктивной модели:

р :SMr EDB

Md

(10)

Множество ограничений целостности реля­ционной модели можно представить множеством правил вывода логической программы, являющей­ся частью дедуктивной модели:

в: ICMr IC

Md

(11)

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

9 :0Mr L

Md

(12)

Рассмотрим более подробно отображение каж­дого компонента реляционной модели. 3.1. Отображение структурной части

Структурная часть реляционной модели опре­деляет отношение как средство хранения данных.

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

Определение: Пусть r реляционное отношение со схемой R(A1,A2,—,An), которое содержит конеч­ное множество кортежей {t1,t2,—,tk}. Каждый кор­теж t{ (A1, A2,—, An) представляется в виде литерала p;-(a1,a2,—,an), где каждый атрибут Aj кортежа t t отображается в аргумент aj предиката p :

ф : Aj ap. (13)

Поскольку предикат является функцией, выше­сказанное можно переформулировать следующим образом: предикат р будет принимать значения "истина" лишь в том случае, если его аргументы будут отображением значений некоторого кортежа tt из отношения r.

Рассмотрим пример: пусть дано отношение r (рис.2), состоящее из двух кортежей {a , b1, c1} и {a1, b2, c2}. Представим данное отношение в тер­минах дедуктивной модели с помощью предиката p. Тогда предикат p будет возвращать значение "ис­тина" лишь при подстановке в качестве его аргу­ментов {a1, b , c1} и {a1, b2, c2}.

Рис. 2. Отображение реляционного отношения в множество фактов

Кортеж отношения r, представленный в виде n-арного предикатного символа p(a1, a2,—, an), где n арность исходного отношения r, а at констан­та, называют фактом. Множество всех фактов де­дуктивной базы данных принято называть экстен-сионалом.

В реляционной модели данных понятие отно­шения непосредственно связано с понятием доме­на [2]. В связи с этим рассмотрим соответствующие домену понятия дедуктивной модели и построим отображение.

Определение: пусть D = {D1,D2,—,Dn} — мно­жество доменов, где Д = {d[,d2 ..,d\}, где dj - значение домена (1 < j < k). Определим пре­дикат p(a1,a2,—,an) и множество значений aj = {a\,a\,.--,alk} его аргумента a . Тогда, можно по­строить отображение у множества элементов до­мена Д- в множество значений аргумента a :

у: dj aj. (14)

Представим систему отображений структурной части реляционной модели в экстенсионал дедук­тивной при помощи диаграммы (рис. 3).

Пусть SMr множество отношений, опреде­ленных в реляционной модели MR, а EDBMd —множество фактов экстенсионала MD . Простран­ство допустимых состояний, выразимых в MR и MD , обозначим, соответственно BR и BD. Тогда р отображение вида (10), ю : BR BD отобра­жение пространства состояний MR в пространство состояний MD , а \x.Def семантическая функция модели языка определения данных.

EDBM° М°е/(Р(5М«))

Рис. 3. Диаграмма отображения компонент MR в MD

3.2. Отображение манипуляционной части

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

Наиболее распространенным языком, приме­няемым в ДБД, является Datalog.

Семантика Datalog определена на алфавитах Var,Const8Pred , обозначающих переменные, кон­станты и предикаты.

Переменные обозначают строками буквенно-цифровых символов конечной длины, начинаю­щихся с прописной буквы. Следует отметить, что существует специальная переменная «_», назы­ваемая анонимной. Ею обозначают любую неиме­нованную переменную. Анонимные переменные используют для отсечения, некоторых аргументов предиката, что аналогично операции проекции в реляционной алгебре.

Константой является текстовая строка или чис­ло. Например: "строковая константа" или "12".

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

К функциям Datalog, помимо формулирования дедуктивных правил вывода, относят описание за­просов. Для выражения запросов, называемых в логическом программировании целями, на языке Datalog используют дизъюнкты вида (15). Голова цели состоит из символа "?", а тело из предиката, над которым выполняют запрос и условий отбора:

?p(A1, A2,—,Ak,, An), Ak £2C, (15)

где, p предикат, определенный на множестве фактов EDBmd ; A переменные, связанные с значениями аргументов предиката; Ak QC условие выборки; Q, множество логических функций сравнения (>,<,=,^); C константа. Следователь­но, результатом запроса будут являться все факты p, у которых аргумент Ak будет отвечать заданному условию отбора.

Цели, как и любые дизъюнкты, не содержат сво­бодных переменных. Т.е. все появляющиеся в цели переменные связаны квантором всеобщности. Из этого следует, что переменная, появляющаяся в некоторой цели G, имеет смысл только в этой цели и ее значение не распространяется на другие со­ставляющие логической программы.

Синтаксис логического программирования основан на использовании операций булевой ал­гебры, к которым относятся отрицание, имплика­ция, конъюнкция и дизъюнкция. В Datalog для вы­ражения булевых операций используются символы и соглашения, определенные в табл. 1.

Таблица 1

Выражение булевых операций в Datalog

Дизъюнкция

«;»

Конъюнкции

«,»

Отрицание

«not»

Импликация

« — »

Синтаксис языка Datalog является более выра­зительным чем, языки реляционных систем, и все операции реляционной алгебры и реляционного исчисления можно выразить с помощью эквива­лентных логические операций и конструкций ло­гического программирования. Рассмотрим их под­робно (табл. 2).

Таблица 2

Соответствие формул Datalog операциям реляционной алгебры

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77 


Похожие статьи

Автор неизвестен - 13 самых важных уроков библии

Автор неизвестен - Беседы на книгу бытие

Автор неизвестен - Беседы на шестоднев

Автор неизвестен - Богословие

Автор неизвестен - Божественность христа