Р ( р, рл, р1, pw, рс ) = П ( р ) AND

NAME ( рл ) AND COLOR ( pi ) AND WEIGHT ( pp/ ) AND CITY ( pc )

и т.д.

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

S ( S, snl, stl, scl ) AND S ( s, sn2, st2, sc2 )

= snl = sn2 AND \

stl = st2 AND scl = sc2

и т.д.

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

SP ( S, р, g ) S ( S, 5Л, St, sc ) AND Р ( р, рл, pt, pw, pc )

И т.д.

Замечание. Для удобства представления здесь предполагается, что переменные, расположенные справа от символа импликации (sn, st и т.д.), связаны с квантором существования. (Все остальные, как отмечалось выше, в разделе 23.3, связаны с квантором всеобщности.) С технической точки зрения мы нуждаемся в некоторой функции Сколема. Например, переменная sл в действительности должна быть заменена, скажем, функцией SN( S), где SN является функцией Сколема.

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

Теперь следует добавить несколько дедуктивных аксиом.

S ( S, sл, St, sc ) AND st > 15

=> GOOD SUPPLIER ( s, st, sc )

(Сравните с определением представления GOOD SUPPLIER, данным в разделе 9.1 главы 9.)

S ( SX, sxn, sxt, sc ) AND S ( sy, syn, syt, sc )

rr SS COLOCATED ( sx, sy ) S ( s, sn, st, с ) AND P ( p, рл, pi, pw, с )

rr SP COLOCATED ( s, p )

И т.д.

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

PART STRUCTURE ( px, ру ) => P ( px, xn, xl, xw, xc ) AND

P ( py, yn, yl, yw, yc )

Затем необходимо определить некоторые значения ее данных.

PART STRUCTURE ( Pl, Р2 ) PART STRUCTURE ( РГ, РЗ ) PART STRUCTURE ( Р2, РЗ ) PART STRUCTURE ( Р2, Р4 ) и т.д.

(На практике определение PART STRUCTURE должно было бы также иметь аргумент количество , который указывал бы количество деталей ру, входящих в состав детали рх, но в данном случае он опускается из соображений простоты.)

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

PART STRUCTURE ( рх, ру ) => COMPONENT OF ( рх, ру ) PART STRUCTURE ( рх, pz ) AND COMPONENT OF { pz, ру )

=> COMPONENT OF ( px, ру )

Иначе говоря, деталь ру является компонентом детали рх на определенном уровне, если она является непосредственным компонентом либо детали рх, либо детали pz, которая, в свою очередь, является компонентом детали рх на определенном уровне. Обратите внимание, что вторая аксиома рекурсивна, поскольку предикат COMPONENT OF определяется в ней на основе самого этого предиката. В классических реляционных системах, наоборот, не допускается использование подобных рекурсивных определений представлений (а также запросов, офаничений целостности и т.п.). Эта способность поддерживать рекурсивные определения - одно из самых очевидных различий между дедуктивными СУБД и их классическими аналогами. Хотя, как уже упоминалось в разделе 23.5 и как было показано в главе 6, не существует фундаментального ограничения, из-за которого классическую реляционную алгебру нельзя было бы расширить для поддержки соответствующего набора рекурсивных операторов.

В разделе 23.7 возможность поддержки рекурсии обсуждается несколько подробнее.

Язык Datalog

Из сказанного можно сделать вывод, что наиболее ясно выраженной частью дедуктивной СУБД может быть язык, на котором будут формулироваться дедуктивные аксиомы (или правила). Самым известным языком такого типа является Datalog [23.9], названный так по аналогии с языком Prolog. Ниже приведено его краткое описание.

Замечание. Основное внимание при создании этого языка уделялось не его вычислительным (как это обычно бывает с традиционными реляционными моделями [5.1]), а описательным качествам. При этом основной целью было создание языка, гораздо более

Фактически было определено транзитивное замыкание - в любой мо.мент отношение, соответствующее предикату COMPONENT OF, является транзитивным замыканием отношения, соответствующего предикату PART STRUCTURE (см. главу 6).

выразительного, чем традиционные реляционные языки [23.9]. В результате в языке Datalog, как и во всех логических СУБД, был сделан акцент на операциях выполнения запросов, а не обновления данных, хотя можно и нужно расширить этот язык также для поддержки операций обновления (подробнее об этом будет сказано ниже).

в простейшей форме язык Datalog поддерживает формулировку правил в виде простых предложений Хорна без функций. В разделе 23.4 предложение Хорна было определено как WFF-формула одного из двух видов.

А1 AND А2 AND ... AND Ал

Al AND A2 AND ... AND Ал = В

в этих конструкциях все А и В являются неотрицаемыми экземплярами предикатов, которые содержат только константы и переменные. Однако в языке Datalog вторая из приведенных конструкций записывается в обратном порядке.

В ф= AJ AND А2 AND ... AND Ал

Для полного соответствия с другими публикациями на эту тему далее будет использоваться именно такая запись. В данном предложении В является заголовком правила, или заключением, а терм А- телом правила, или предпосылкой либо целью, в которой отдельные термы являются подчиненными целями (или подцелями). Для краткости связки AND часто заменяют запятыми. Следовательно, программа на языке Datalog представляет собой набор таких предложений, разделенных обычным образом, т.е. точкой с запятой (в этой книге, однако, вместо точки с запятой используется перенос на отдельную строку). При этом в такой про-фамме порядок расположения предложений не имеет никакого значения.

Заметим, что вся дедуктивная база данных может рассматриваться как профамма Datalog в указанном выше смысле. Можно, например, все аксиомы, заданные для поставщиков и деталей (основные аксиомы, офаничения целостности и дедуктивные аксиомы), записать в стиле программы Datalog, разделив их точкой с запятой или разместив в отдельных строках, и в результате получить профамму на языке Datalog. Однако, как уже указывалось, экстенсиональная часть базы данных обычно не определяется таким способом; она определяется так, как принято в традиционных базах данных. Основная функция языка Datalog заключается в формулировании дедуктивных аксиом. Как отмечалось выше, эту функцию следует рассматривать в качестве расширения механизма определений представлений, существующего в современных реляционных СУБД.

Язык Datalog может также использоваться в качестве языка запроса (точно так, как и язык Prolog). Для примера предположим, что на языке Datalog дано следующее определение хороших поставщиков GOOD SUPPLIER.

GOOD SUPPLIER ( s, st, sc ) <= S ( s, sn, st, sc )

AND st > 15

Ниже приведены примеры запросов на основе этого определения.

1. Найти всех хороших поставщиков.

? < GOODJUPPLIER ( s, st, sc )

2. Найти хороших поставщиков в Париже.

? <= GOOD SUPPLIER ( s, st, Paris )