Главная » SQL, Базы данных » ДЕДУКТИВНЫЕ СИСТЕМЫ БАЗ ДАННЫХ

0

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

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

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

Примечание. В приведенном ниже описании для удобства чтения применяются по существу такие же соглашения о представлении значений, как и на рис. 3.8 (см. стр. 119) и в других главах данной книги. Таким образом, в качестве удобного  сокращения для QTY ( 300 ) используется 3 0 0 и т.д.

S# ( SI ) NAME ( Smith)   INTEGER ( 5 )     CHAR ( London )

S# ( S2 ) NAME( Jones )    INTEGER ( 10 )    CHAR ( Paris ) S# ( S3 ) NAME ( Blake)    INTEGER ( 15 )    CHAR ( Rome ) S# ( S4 ) NAME( Clark )    и т.д.                                                                                CHAR ( Athens ) S# ( S5 ) NAME( Adams)                                                                                                                          и т.д.

S# ( S6 ) NAME( White ) S# ( S7 ) NAME( Nut )

и т.д.    NAME( Bolt )

NAME ( Scre)

и т.д.

7  Это также предусмотрено в стандарте SQL [4.23]. См. упр. 4.6 из главы 4.

8  В этой связи следует отметить, что Кодд еще в 1974 году заявил, что одна из задач внедрения реля ционной модели состоит именно в том, "чтобы добиться интеграции средств выборки фактов и управле ния файлами для подготовки к введению в дальнейшем средств логического вывода, применимых в программных продуктах производственного назначения" [12.2], [26.12].

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

S ( SI, Smith, 20, London ) S ( S2, Jones, 10, Paris )

и т.д.

P     (     P i,     Nut,  Re d,     12,  Lon don  )

и т . д .                                                                                :

SP   (   SI,   PI,   300   )

и  т . д .

Примечание. Безусловно, на основании этого примера не следует делать вывод о том, что экстенсиональная база данных создается путем явного перечисления всех основных аксиом, как показано в этом примере; скорее, для этого должны применяться традиционные методы определения данных и ввода данных.  Иными словами, дедуктивные СУБД, как правило, должны применять свои  дедуктивные средства к обычным базам данных, которые уже существуют, и были сформированы обычным образом. Но следует отметить, что теперь становится еще более важным требование, чтобы в экстенсиональной базе данных не нарушалось ни одно из объявленных ограничений целостности! Это связано с тем, что база данных, в которой нарушается хотя бы одно из таких ограничений, представляет собой (с точки зрения логики) несовместимое множество аксиом, но широко известно, что, исходя из такой начальной позиции, можно доказать, что истинным, вообще говоря, является абсолютно любое высказывание (иными словами, как описано в аннотации [9.16], из несовместимого множества аксиом могут быть выведены взаимно противоречивые утверждения).  Именно по той же причине важно также, чтобы было совместимым заданное множество ограничений целостности.

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

S ( S, sn, St, SC ) ⇒ S# ( S ) AND

NAME ( sn ) AND

INTEGER { st ) AND CHAR ( sc )

P ( p, pn, p1, pw, pc ) ⇒ P# ( p ) AND NAME ( pn ) AND COLOR ( p1 ) AND WEIGHT ( pw )

AND CHAR ( pc )

Рассмотрим ограничения потенциального ключа.

S ( s, sn1, st1, sc1 ) AND S ( s, sn2, st2, sc2 )

⇒ snl = sn2 AND

stl = St2 AND

scl =

sc2 и т.д.

Ограничения внешнего ключа представлены следующим образом.

SP  (  s,  p,  q  )   ⇒ S   (  s,   sn,   st,   sc  ) AND P   (   p,   pn,   pi,   pw,   pc   )

Остальная часть базы данных определяется аналогично.

Примечание. Для более полной демонстрации рассматриваемого подхода  предположим, что переменные, появляющиеся справа, а не слева от символа импликации (в данном примере sn, st и т.д.), квантифицированы экзистенциально. (Как было описано в разделе 24.4, все остальные переменные  квантифицированы универсально.) Поэтому, говоря формально, потребуется  применение определенных скулемовских функций; например, переменная sn фактически должна быть заменена (скажем) термом SN(s), где SN — скулемовская функция.

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

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

S    (   s,    sn,   st,    sc  )  AND   st   >  15

⇒ GOOD_SUPPLIER   (  s,   st,   SC  )

Рекомендуем сравнить эту аксиому с определением представления GOOD_SUPPLIER (Добросовестный поставщик), которое приведено в разделе 10.1 главы 10).

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

⇒ SS_COLOCATED ( SX, sy

) S ( s, sn, st, с ) AND P ( p, pn, p1, pw,

с )

⇒ SP_COLOCATED ( s, p )

Могут быть также дополнительно введены другие дедуктивные аксиомы.

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

PART_STRUCTURE   (  рх,  ру  )   ⇒ Р  (  рх,  xn,  xl,  xw,  xc  )  AND

Р   (   ру,   yn,   yl,   yw,   ус   )

Ниже приведены некоторые значения данных.

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

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

PART_STRUCTURE ( рх, ру ) ⇒ COMPONENT_OF ( рх,

ру ) PART_STRUCTURE ( рх, pz ) AND COMPONENT_OF (

pz, py )

⇒ COMPONENT_OF ( рх, ру )

Иными словами, деталь ру является компонентом детали рх (на некотором уровне), если она является либо непосредственным компонентом детали рх, либо непосредственным компонентом некоторой детали pz, которая, в свою очередь, является компонентом (на некотором уровне) детали рх. Заслуживает особого  внимания то, что здесь вторая аксиома рекурсивна — она определяет предикат COMPONENT_OF в терминах самого этого предиката. Отметим, что первоначально в реляционных системах не допускалось использование определений таких представлений (или запросов, или ограничений целостности, или других конструкций), которые были бы заданы как рекурсивные в указанной форме. Поэтому рассматриваемая здесь способность поддерживать рекурсию является одним из наиболее очевидных непосредственных различий между дедуктивными СУБД и их классическими реляционными аналогами. Хотя, как было указано в разделе 24.5 (и описано в главе 7, при обсуждении оператора TCLOSE), фактически не существует таких причин, по которым нельзя было бы расширить классические реляционные системы для поддержки такой рекурсии, и в некоторых системах  указанная задача уже была решена. Дополнительные сведения, касающиеся рекурсии, приведены в разделе 24.7.

Язык Datalog

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

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

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

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

Al AND A2 AND . . . AND An

Al AND A2 AND … AND An ⇒ В

Здесь все термы А и терм в представляют собой неотрицаемые экземпляры предикатов, которые включают только константы и переменные. Но в соответствии со стилем, принятым в языке Prolog, в Datalog второе из этих выражений фактически записывается с обратным размещением правой и левой частей, следующим образом.

В   ⇐  A1   AND  A2   AND   . . .   AND  An

Поэтому для согласования с другими публикациями в этой области в последующем изложении будет применяться такая же форма записи.

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

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

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

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

Datalog может также использоваться как язык запросов (опять-таки, во многом аналогично языку Prolog). Например, предположим, что дано следующее олределение  предиката GOOD_SUPPLIER на языке Datalog.

GOOD_SUPPLIER   (   s,    st,    sc   )   ⇐  S   (   s,   sn,    st,    sc   ) AND st  >  15

Ниже приведено несколько типичных запросов к пpeдикaтy GOOD_SUPPLlER.

1.  Определить всех добросовестных поставщиков.

?   ⇐ GOOD_SUPPLIER  (  s,   st,   sc  )

2.  Определить всех добросовестных поставщиков из Парижа.

?   ⇐  GOOD_SUPPLIER   (   s,    st,    Paris   )

3.  Является ли поставщик si добросовестным?

?   ⇐  GOOD_SUPPLIER  (  S1,   st,   sc  )

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

Следует отметить, что язык Datalog, в том виде, в котором он был определен первоначально, не поддерживает весьма многих средств обычных реляционных языков: простые вычислительные операторы ("+", "*" и т.д.), операторы агрегирования (COUNT, SUM и т.д.), операцию разности множеств (поскольку нельзя применять операцию отрицания к выражениям), группирования и разгруппирования и т.д.  (хотя этот язык поддерживает рекурсию). Кроме того, в языке Datalog не предусмотрена поддержка именования атрибутов (назначение фактического параметра предиката зависит от его порядковой позиции), а также не предусмотрена полная поддержка доменов (т.е. определяемых пользователем типов, в том смысле, который указан в главе 5). К тому же как было отмечено выше в данном разделе, в этом языке не предусмотрены какие-либо операции обновления, а также (как следствие из данного факта) в нем не поддерживаются декларативные спецификации правил удаления и обновления внешних ключей (ON 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   (   р,   pn,   pl,   рg,   рс   )   <=

Р   (   р,   pn,   pl,   pw,   рс   )   AND  рд   =  pw   *   454

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

■     Операторы группирования и агрегирования (во многом соответствующие требовани ям к обычному реляционному оператору SUMMARIZE, который описан в главе 7). Такие операторы необходимы для решения (например) задач, иногда называемых задачами определения необходимого количества (gross requirements problem). Для решения этих задач требуется не только узнать, какие детали ру являются ком понентом некоторой детали рх на любом уровне, но также определить, какое количество различных деталей ру (на всех уровнях) потребуется для изготовле ния детали рх. (Безусловно, при этом предполагается, что переменная отноше ния PART_STRUCTURE включает атрибут QTY.)

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

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

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

Краткий обзор описанных выше дополнений с примерами можно найти в  книге Гардарена (Gardarin) и Валдуриса (Valduriez) [24.6], где также рассматривается целый ряд методов реализации языка Datalog.

Источник: Дейт К. Дж., Введение в системы баз данных, 8-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — 1328 с.: ил. — Парал. тит. англ.

По теме:

  • Комментарии