3. Является ли поставщик с номером S1 хорошим? ? <= GOOD SUPPLIER ( Sl, st, sc )

И так далее. Иначе говоря, запрос на языке Datalog состоит из специального правила с заголовком типа ? и телом, состоящим из одного терма, который обозначает результат запроса. Заголовок ? означает (по соглашению) Показать .

Следует отметить, что несмотря на поддержку рекурсии существует достаточное количество стандартных операций для традиционных реляционных систем, которые не поддерживаются в языке Datalog, например скалярные операции ( + , - и т.д.), операции обобщения (COUNT, SUM и др.), группирования и т.д. В этом языке также не поддерживается именование атрибутов (значение аргументов предиката зависит от его относительного расположения), не обеспечивается полная поддержка доменов (т.е. типов данных, определенных пользователем в смысле, изложенном в главе 5). Как уже отмечалось, в языке не предусмотрены операции обновления, а также не поддерживается декларативная спецификация удаления и обновления внешних ключей (DELETE CASCADE и т.д.).

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

Отрицаемые предпосылки, например такие, как показано ниже.

SS COLOCATED ( SX, sy ) S ( sx, sxn, sxt, sc ) AND

S ( sy, syn, syt, sc ) AND NOT ( SX = sy )

Скалярные операторы (встроенные и определенные пользователем), например такие, как показано ниже.

P WT IN GRAMS ( р, рл, р1, рд, рс ) ф=

Р ( Pl рп, р1, pw, рс ) AND рд = pw * 454 В данном примере предполагается, что встроенная функция * (умножение) может быть записана в обычном инфиксном представлении. Более ортодоксальное представление терма, следующего за оператором AND, выглядело бы как =(рд, * (pw, 454)).

Операторы обобщения и группирования (в некотором смысле эта тема касается отдельных особенностей оператора SUMMARIZE, что подробнее описано в главе 6). Эти операторы необходимы для того, чтобы разрешить проблему так называемых требований обобщения. Она заключается не только в поиске деталей ру, которые являются компонентами деталей рх на любом уровне, но также в выяснении, сколько деталей ру (на всех уровнях) требуется для изготовления детали рх (при этом, естественно, предполагается, что переменная-отношение PART STRUCTURE содержит атрибут QTY).

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

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

Обзор этих расширений вместе с примерами и обсуждением приложений языка Datalog можно найти в книге [23.10], где также обсуждается множество методов реализации языка Datalog.

23.7. Обработка рекурсивных запросов

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

В качестве примера повторим приведенное в разделе 23.6 рекурсивное определение переменной-отношения COMPONENT OF в терминах структуры состава деталей PART STRUCTURE (для краткости вместо полного названия PART STRUCTURE используется сокращение PS, а вместо COMPONENT OF - СОМР; кроме того, используется запись, принятая в языке Datalog).

СОМР ( рх, ру ) < PS ( рх, ру )

СОМР ( рх, ру ) Ф= PS ( рх, pz ) AND СОМР ( pz, PY )

А вот пример типичного рекурсивного запроса к базе данных ( Найти все компоненты, из которых состоит деталь с номером Р1 ).

? < СОМР ( Р1, ру )

Второе правило в приведенном выше рекурсивном определении является линейно рекурсивным, поскольку предикат из заголовка правила встречается в теле правила только один раз. На самом деле можно переопределить это правило таким образом, чтобы рекурсия не была линейной.

СОМР ( рх, ру ) < PS ( рх, ру )

СОМР ( рх, ру ) СОМР ( рх, pz ) AND СОМР ( pz, ру )

Однако с практической точки зрения линейная рекурсия представляет гораздо больший интерес, потому что чаще встречается на практике и для ее применения разработано несколько известных и эффективных методов [23.16]. Поэтому далее речь пойдет исключительно о линейной рекурсии.

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

Р ( X, у ) Ф= Q ( X, Z ) AND R ( Z, у ) Q ( X, у ) Р ( X, Z ) AND S ( Z, у )

Для краткости изложения эти особенности будут опущены. Более подробную информацию о них можно найти в [23.16].

Так же, как при обработке классических (нерекурсивных) запросов, в целом, проблема реализации заданного рекурсивного запроса может быть разбита на две отдельные части, а именно: преобразование исходного запроса в эквивалентную, но более эффективную форму и собственно выполнение преобразованного таким образом запроса. В литературе содержатся описания различных подходов к решению этих проблем. Ниже кратко описаны некоторые простейшие из предложенных технологий. Они будут проиллюстрированы на примере запроса Найти все компоненты детали с номером РГ с использованием приведенного ниже набора значений в переменной-отношении PS.

Унификация и резолюция

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

1. NOT PS ( рх, ру ) OR СОМР ( рх, ру )

2. NOT PS ( рх, pz ) OR NOT СОМР ( pz, ру ) OR СОМР ( px, ру ) Еще одна предпосылка создана на основе искомого заключения.

3. NOT СОМР ( РГ, ру ) OR RESULT ( ру )

Основные аксиомы образуют оставшиеся предпосылки. Ниже приведен пример одной из таких аксиом.

4. PS ( РГ, Р2 )

Подставив РГ вместо рх и Р2 вместо ру в строке из п. 1 и совместив строки из пп. 1 и 4, получим следующий результат.

5. СОМР ( РГ, Р2 )

Теперь, подставив значение Р2 вместо ру в строке из п. 3 и совместив строки из пп. 3 и 5, получим окончательный результат.

6. RESULT ( Р2 )

Таким образом, деталь с номером Р2 является компонентом детали с номером РГ. Аналогично можно показать, что деталь с номером РЗ также является компонентом детали с номером РГ. Теперь, обладая дополнительными аксиомами СОМР( РГ , Р2) и СОМР(РГ ,РЗ), можно рекурсивно выполнить поиск всех остальных компонентов. Эта задача предлагается читателю в качестве упражнения.