    Приложение в 

    Логические системы управления базами данных 

    8.1. Введение 

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

    8.2. Обзор 

    Исследования связей между базами данных и логикой начались еще в конце 
70-х годов и о них можно прочесть в [В.5, В.7, В. 13]. Однако интерес к этой 
теме значительно повысился после публикации в 1984 году работы Рейтера 
(Reiter) [В. 15]. В этой статье традиционное представление баз данных 
характеризуется как модель-но-теоретическое, т.е., попросту говоря, база 
данных рассматривается как набор явно заданных (т.е. базовых) отношений, 
каждое из которых включает набор кортежей, и выполнение запроса может 
рассматриваться как вычисление некоторой особой формулы — комбинации этих 
отношений и кортежей (т.е. выражения с истинным значением). (Подробнее и 
точнее смысл термина "модельно-теоретический" поясняется ниже.) 
    В работе Рейтера наряду с модельно-теоретическим подходом рассматривается 
более предпочтительная в некотором отношении альтернатива — 
доказательно-теоретическое представление. Согласно этому представлению база 
данных рассматривается как набор 

    Приложение В, Логические системы управления базами данных 731 

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

    SPX WHERE SPX.QTY > 250 

    В традиционной (т.е. моделыю-теоретической) интерпретации необходимо 
последовательно проверить все кортежи о поставках с оценкой формулы QTY > 250 
для каждого кортежа записей. В результате выполнения этого запроса извлекаются 
все кортежи с записями, для которых данное выражение будет истинным. В 
доказательно-теоретической интерпретации, наоборот, кортежи записей о 
поставках (а также некоторые дополнительные объекты) рассматриваются как 
аксиомы некой "логической теории". А затем доказательно-теоретический метод 
применяется для выяснения того, для каких значений переменной SPX формула 
зрх.оту>250 является логической последовательностью аксиом этой теории. 
Результатом выполнения запроса будут частные значения переменной SPX. 
    Конечно, данный пример настолько прост, что с его помощью трудно 
обнаружить существенные различия между двумя этими представлениями. Однако 
дело в том, что ход рассуждений, лежащих в основе этого доказательства (в 
доказательно-теоретической интерпретации), конечно же, гораздо сложнее, чем 
можно продемонстрировать данным примером. Как будет показано ниже, такой ход 
рассуждений поможет справиться с гораздо более сложными проблемами, которые не 
под силу решать на основе классических реляционных систем. Более того, 
доказательно-теоретический подход обладает целым рядом дополнительных 
преимуществ [В. 15]. 
    •   Единство представления. Становится возможным задать единый язык для 
всей базы данных, согласно которому доменные значения, кортежи базовых 
отношений, "дедуктивные аксиомы", запросы и ограничения целостности будут 
представлены одинаковым образом. 
    •   Единство действия. Обеспечивается единая основа для организации 
выполнения совершенно различных задач, включая оптимизацию запросов (особенно 
семантическую оптимизацию), усиление ограничений целостности, составление 
макета базы данных, проверку корректности выполнения программы и др. 
    •   Семантическое моделирование. Появляется возможность задавать различные 
конструкции семантического моделирования, например события, иерархии типов и 
некоторые типы агрегации целостности. 
    •   Расширенное применение. Наконец, обеспечивается основа для решения 
таких проблем, с которыми не могут справиться системы на основе классических 
подходов. Например, для работы с дизъюнктивной информацией типа "Поставщик S5 
поставляет либо деталь Р1, либо деталь Р2, но точно не известно какую". 

    Дедуктивные аксиомы 

    В этом подразделе подробно описано понятие дедуктивной аксиомы, которое 
также называется правилом вывода (или правилом заключения). В общем, 
дедуктивная аксиома — это правило, по которому на основе некоторых фактов 
можно вывести новые факты. Например, на основе фактов "Анна — мать Бетти" 
("Anne is the mother of Betty") и "Бетти — мать Сельи" ("Betty is the mother 
of Celia") согласно очевидной дедуктивной аксиоме можно вывести, что Анна — 
бабушка Сельи. Забегая вперед, можно представить структуру дедуктивной СУБД, в 
которой два данных факта оформлены в виде кортежей отношения MOTHEROF с 
атрибутами MOTHER (мать) и DAUGHTER (дочь). 

    732	Приложения 

    MOTHEROF 
    MOTHER	DAUGHTER 
    Anne Betty	Betty Celia 

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

    IF	MCTHEROF	(X, у) 
    AND	MOTHEROF	(у, 2) 
    THEN	GRANDMOTHEROF	(х,2) 

    Теперь это правило, выраженное в форме дедуктивной аксиомы, можно 
применить к данным, выраженным в форме основных аксиом (о конкретном способе 
применения речь идет ниже), для получения результата GRANDMOTHER (Anne, 
ceiia). Таким образом, пользователи СУБД могут создавать запросы типа "Кто 
является бабушкой Сельи?" или "Кто является внучкой Анны?" (точнее, можно 
спросить "Чьей бабушкой является Анна?", подробнее это описано ниже). 
    Теперь следует сравнить описанные идеи с традиционными концепциями баз 
данных. Согласно традиционной терминологии дедуктивная аксиома может быть 
задана на основе приведенного ниже определения представления: 

    CREATE VIEW GRANDMOTHEROF AS 
    (MX.MOTHER AS GRANDMOTHER, MY.DAUGHTER AS GRANDDAUGHTER) WHERE MX.DAUGHTER 
= MY.MOTHER ; 

    Здесь MX и MY — переменные кортежа, которые содержатся в MOTHEROF. Запросы 
такого типа могут быть оформлены на основе следующего представления: 

    GX.GRANDMOTHER WHERE GX.GRANDDAUGHTER = 'Celia1 GX.GRANDDAUGHTER WHERE 
GX.GRANDMOTHER = 'Anne' 

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

    В.З. Исчисление высказываний 

    Далее дается краткое и весьма упрощенное описание некоторых основных идей 
логики. Так, в данном разделе описывается исчисление высказываний 
(утверждений), а в следующем — исчисление предикатов (логических условий) 
[B.L-B.4]. Сразу же следует отметить, что описание исчисления высказываний 
дается лишь для понимания более важного материала, изложенного ниже. В 
последующих разделах излагаются основные сведения, необходимые для понимания 
дальнейшего материала данного приложения. 
    Исходя из предположения, что читатель знаком с основными понятиями булевой 
алгебры, в некоторых случаях используются приведенные ниже термины и законы 
булевой алгебры. 
    •  Дистрибутивные законы: 
    /'AND ( g OR h ) s ( f AND g ) OR ( f AND h ) f OR ( g AND h ) e ( f OR g 
) AND ( f OR Л ) 
    •  Законы Де Моргана: 
    NOT   (   f AND g }   s NOT  f OR NOT g NOT1   (   f OR g )   s NOT  f AND 
NOT'  g 
    Здесь /, gv\ h— произвольные истинные выражения. 

    Приложение В, Логические системы управления базами данных	733 

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

    Термы 

    Предположим для начала, что имеется некоторый набор объектов, констант, о 
которых делаются различного рода заключения. Согласно языку, принятому в 
области баз данных, эти константы являются элементами основных доменов. Тогда 
термом будет называться содержащее константы выражение, обладающее следующими свойствами: 
    •	Выражение не содержит кванторов (подробнее это описано ниже). 
    •	Выражения либо не содержат логических связок, либо заключены в скобки. 
    •	Выражения однозначно оцениваются либо как истинные, либо как ложные. 
    Например, выражения типа "Поставщик S1 находится в Лондоне", "Поставщик S2 
находится в Лондоне" и "Поставщик S1 поставляет деталь Р1" являются термами (в 
рассматриваемом примере они оцениваются соответственно как истинное, ложное и 
истинное). И наоборот, выражение типа "Поставщик S1 поставляет некоторую 
деталь р" не является термом, поскольку содержит квантор ("некоторая деталь 
р"). Также не является термом выражение типа "Поставщик S5 когда-нибудь в 
будущем будет поставлять деталь Р1", поскольку его нельзя однозначно оценить 
как истинное или ложное. 

    Формулы 

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

    formula 
    ::=    term I  NOT  term 
    I   NOT   term AND formula I   NOT  term OR formula I   term => formula term 
    ::=    atomic-formula I   {  formula ) 

    Формулы оцениваются в соответствии с истинными значениями их постоянных 
термов и обычных таблиц истинности для связок. Здесь следует отметить 
некоторые важные особенности. 
    1. Атомарная формула (atomic-formula) — это терм, который не содержит 
связок и не заключается в скобки, 

    734	Приложения 

    2.  Символом => обозначается связка типа логической импликации. По 
определению выражение /'=> gлогически эквивалентно выражению NOT .f OR д. (В 
других главах для этой связки использовалась конструкция типа "IF ... THEN ...".) 
    3.  Для связок применяется обычный приоритет исполнения (NOT, затем AND, 
затем OR, затем =>), что позволяет избежать многократного использования скобок, 

    Правила вывода 

    Правила вывода для исчисления высказываний имеют следующий синтаксис: 
    М => g 
    (Здесь символом " [=" обозначена фраза "Всегда верно, что". Обратите 
внимание, что такие символы необходимы для составления метаутверждений, т.е. 
утверждений об утверждениях.) Ниже приведено несколько примеров правил вывода. 
    1.	(=   (   f AND g )   =>  f 
    2.	h / =>   (   f OR g } 
    3.	(=   (   (   f => g )   AND   (   g г=> Л  )   )   =>   (   f => Л ) 
    4.	(=  (  f AND  {  fmDg))   => g 

    Замечание. Правило образа утверждений бывает чрезвычайно важным и 
неформально интерпретируется так: если /истинно и под истинностью f 
подразумевается истинность g, то g должно быть тоже истинным. Например, 
допустим, что каждый из приведенных ниже фактов является истинным: 

    а) у меня нет денег; 
    б) если у меня нет денег, я должен мыть посуду. 
    Исходя из этих фактов, можно вывести, что истинным является факт 
    в) я должен мыть посуду. 
    Вот еще примеры правил вывода: 
    5.  (=  (   f =>   (  д => Л )   )   =>  (   (   / AND д )   )   => Л ) 
    6.     (=  (   (   .f OR д )   AND   (  NOT д OR Л )   )   =>   (   f OR h } 
    Замечание. Правило резолюции также является чрезвычайно важным и более 
подробно описывается ниже. 

    Доказательства 

    Теперь известны все сведения, необходимые для создания формальных 
доказательств в контексте исчисления высказываний. Задача доказательства 
состоит в определении, будет ли некоторая данная формула g, т.е. заключение, 
логическим выводом некоторого набора формул//,/2,... fn, т.е. предпосылок. 
Ниже приведена символьная запись доказательства: 

    fl,   f2,   ...   fn  \ д 

    Такая форма записи с использованием символа метаутверждения " р' 
интерпретируется как "g следует из//,/2, ...fn". Такой способ исполнения 
называется от фактов к цели и заключается в последовательном применении правил 
вывода к предпосылкам, затем к формулам, выведенным из этих предпосылок, затем 
к формулам, выведенным из этих формул, и т.д., до тех пор пока не будет 
выведено заключение. Иначе говоря, процесс "от фактов к цели" состоит в 
переходе от предпосылок к заключению. Однако существует несколько вариантов 
этой основной схемы. 

    Приложение В. Логические системы управления базами данных	735 

    1.   Принятие предпосылки. Если заключение g имеет вид р => q, то р 
принимается как дополнительная предпосылка, a q выводится из заданных 
предпосылок плюс предпосылка/?. 
    2.  От цели к фактам. Вместо доказательства р => q, доказывается 
противоположное выражение NOT/? => NOT q. 
    3.   Приведение к абсурду. Вместо доказательства прямого утверждения р => 
q, доказывается обратное выражение, когда и />, и NOT g являются истинными. 
    4.  Резолюция. В этом методе вывода используется правило резолюции (п. 6 
из предыдущего списка). 
    Методику использования правила резолюции следует рассмотреть подробнее, 
поскольку она довольно часто используется на практике. 
    Прежде всего нужно отметить, что правило резолюции весьма эффективно для 
отмены подчиненных формул. Например, на основе двух заданных формул 

    f OR g     И     NOT g OR Л 

    можно вывести упрощенную формулу 

    Г OR Л 

    В частности, на основе заданных формул / OR g и NOT g (т.е. допуская, что 
Л является истинным) можно вывести f. 
    Таким образом, можно заметить, что данное правило применяется в общем 
случае к конъюнкции (AND) двух формул, каждая из которых является дизъюнкцией 
(OR) двух формул. Для применения правила резолюции нужно поступить следующим 
образом. (Для более конкретного обсуждения этого вопроса применение правила 
будет продемонстрировано на заданном ранее примере.) Допустим, что нужно 
определить, будет ли истинным следующее доказательство (где А, В, С и D 
являются формулами): 

    Л =>   (  В => С },   NOT D OR А,   В  }• D => С 

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

    А =>   ( Б => С ) 
    NOT D OR A 
    В 
    NOT   (  D => С } 

    Обратите внимание на то, что эти четыре строки неявным образом связаны 
друг с другом с помощью оператора AND. Теперь нужно конвертировать каждую 
отдельную строку в конъюнктивную нормальную форму, т.е. в форму, состоящую из 
нескольких объединенных оператором AND формул, каждая из которых может 
содержать операторы NOT и OR, но не оператор AND (подробнее это описано в 
главе 18). В рассматриваемом примере вторая и третья строки уже имеют 
требуемый вид. В двух других строках следует исключить все символы "=>", 
используя для этого его определение на основе операторов NOT и OR. В случае 
необходимости можно применить упомянутые выше дистрибутивные законы и законы 
Де Моргана. Кроме того, необходимо убрать лишние скобки и пары смежных 
операторов NOT, которые образуют двойное отрицание. После выполнения всех этих 
действий строки примут следующий вид: 

    NOT Л OR NOT В OR С 
    NOT D OR A 
    В 
    D AND NOT С 

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

    736	Приложения 

    NOT Л OR N00? В OR С 
    NOT D OR Л 
    В 
    D 
    NOT С 

    Теперь для совмещения строк можно применить правило резолюции. Для этого 
выберем пару "совмещаемых" строк, одна из которых содержит некоторую часть 
формулы, а другая ее отрицание. Например, выберем первые две строки, 
содержащие NOT лил соответственно. После их совмещения получится следующий результат: 

    NOT D OR NOT B OR С 
    В 
    D 
    NOT С 

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

    NOT D OR С 
    D 
    NOT С 

    После еще одного совмещения первых двух строк (NOT он д) получится 
следующий результат: 

    с 
    NOT С 

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

    В.4. Исчисление предикатов 

    Основным отличием исчисления предикатов от исчисления высказываний 
является использование кванторов в формулах исчисления предикатов. С помощью 
кванторов эффективность и диапазон применения формул значительно 
увеличиваются. Например, утверждение "Поставщик SI поставляет некоторую деталь 
р" нельзя использовать в исчислении высказываний, однако это вполне допустимо 
в исчислении предикатов. Таким образом, в исчислении предикатов можно 
составлять запросы типа "Какие детали поставляются поставщиком S1?", "Найти 
поставщиков, которые поставляют некоторые детали" или даже "Найти поставщиков, 
которые не поставляют никаких деталей вовсе". 

    Предикаты 

    Предикат — это логическая функция, которая для некоторого аргумента 
возвращает значение истинно или ложно. Например, оператор ">" является 
предикатом, а выражение ">(х,у)" (оно чаще записывается в виде "*>/') 
возвращает истинное значение, если х больше у, и ложное значение в обратном 
случае. Предикат, содержащий п аргументов, называется «-местным предикатом. 
Пустое утверждение (или формула) в изложенном выше смысле может 
рассматриваться как нуль-местный предикат, поскольку не имеет аргументов и 
оценивается либо как истинное, либо как ложное. 
    Для удобства предполагается, что предикаты типа "=", ">", ">" и т.д. — 
встроенные (т.е. являются частью данной формально определенной системы) и 
содержащие их выражения могут читаться обычным способом. Однако пользователи, 
конечно же, могут задавать предикаты самостоятельно. Действительно, вскоре 
станет ясно, что в терминах баз данных заданный пользователем предика! не что 
иное, как

    Приложение В. Логические системы управления базами данных	737 
    24 Введение в системы баз данных 


определенное пользователем отношение. Например, отношение поставщиков S может 
рассматриваться как предикат с четырьмя аргументами (S#, SNAME, STATUS, CITY). 
Более того, выражения типа S(S1, Smith, 20, London) и S(S6, White, 45, Rome) 
представляют собой примеры или вызовы такого предиката, который выполняет 
оценку с выдачей истинного и ложного результатов соответственно (в пределах 
рассматриваемой здесь базы данных). 

    Правильно построенные формулы 

    Далее во избежание путаницы с термином "формула" из предыдущего раздела 
(который имеет совершенно другой смысл) следует использовать термин правильно 
построенная формула (well-formed formula— WFF, произносится "вэфф"). Ниже 
приведен упрощенный синтаксис WFF-формулы: 

    wff     : :=      terra 
    I   NOT   (   wff ) 
    |    (   wff )  AND   (   wff ) 
    I   (  wff )  OR  (  wff ) 
    |    (   wff )   =>   {   wff ) 
    I  EXISTS  variable (  wff ) 
    I   PORALL variable  (   wff ) 
    term    : :=  [ NOT ] predicate [   ( argument-coimalist )   ] 

    Отметим некоторые особенности этого синтаксиса. (Раньше в этой книге 
подобный синтаксис уже использовался.) 
    1.  Под словом term подразумевается просто экземпляр предиката, который 
может быть отрицаемым. Каждый аргумент (argument) должен быть константой, 
переменной или указателем на функцию, каждый аргумент которой, в свою очередь, 
является константой, переменной или указателем на функцию. Для нуль-местного 
предиката Элемент argument-cormalist (и Окружающие СГО Скобки) Опускается. 

    Замечание. Использование функций допускается для того, чтобы позволить 
включать в состав WFF-формулы вычисляемые выражения типа "+(х,уУ, которые 
обычно записываются в виде "х+у". 

    2.  Как и выше, для сокращения числа необходимых скобок здесь применяется 
обычный приоритет исполнения операторов (NOT, затем AND, затем OR, затем =>). 
    3.  Кванторы EXISTS и PORALL уже описывались в этой книге. (Здесь 
подразумевается, что не существует предикатных переменных, т.е. переменных, 
значениями которых являются предикаты. Следовательно, имеется в виду, что 
предикаты сами по себе не могут быть подвергнуты квантованию. Эта тема также 
обсуждается в главе 7.) 
    4.  Законы Де Моргана можно обобщить на случай использования квантования 
WFF-формул следующим образом: 
    NOT   (  TORALL X  (  f )   )   s EXISTS x  (  NOT   (   f )   ) NOT   {  
EXISTS X  (   f )   )   = FORALL x  ( NOT   (   f )   ) 
    Эта тема также обсуждается в главе 7. 
    5.  Следует повторить еще одну особенность, упомянутую в главе 7. Внутри 
некоторой WFF-формулы каждый экземпляр переменной является либо свободным, 
либо связанным. Переменная называется связанной, если сразу же за ней следует 
квантор ("квантованная переменная") или она находится в пределах квантора и 
имеет такое же имя, что и применяемая квантованная переменная. В противном 
случае переменная называется свободной. 
    6. Закрытая WFF-формула не содержит ни одной свободной переменной. В 
противном случае она называется открытой WFF-формулой. 

    738	Приложения 


    Интерпретации и модели 

    Для того чтобы понять, что такое WFF-формула, следует ввести понятие 
интерпретации. Интерпретация WFF-формулы или (в более общем смысле) набора 
WFF-фор-мул определяется следующим образом. 
    •   Во-первых, необходимо определить пространство рассуждений, на котором 
будут интерпретироваться WFF-формулы. Иначе говоря, следует задать отображение 
между допустимыми константами формальной системы (в терминах базы данных это 
доменные значения) и объектами "реального мира". Каждая индивидуальная 
константа соответствует одному элементу пространства рассуждений. 
    •  Во-вторых, нужно задать значение для каждого предиката на основе 
объектов в пространстве рассуждений. 
    •   В-третьих, следует также задать значение для каждой функции на основе 
объектов в пространстве рассуждений. 
    Таким образом, интерпретация заключается в комбинации пространства 
рассуждений, отображения индивидуальных констант на объекты этого 
пространства, заданных значений для предикатов и функций по отношению к этому пространству. 
    Допустим, что пространством рассуждений является набор целых чисел 
{0,1,2,3,4,5}, такие константы, как "2", соответствуют элементам этого 
пространства очевидным образом, а предикат ">" задан с традиционным для этого 
символа значением. (Можно было бы также определить такие функции, как "+", "-" 
и т.д.) Теперь можно задать истинностные значения для WFF-формул, например такие: 

    2 > 1	— истинно 
    2 > 3	— ложно 
    EXISTS х	( х > 2 )    — истинно 
    FORALL х	( х > 2 )    — ложно 

    Следует отметить, что возможны также некоторые другие интерпретации. 
Например, можно задать пространство рассуждений в виде классификации уровней безопасности: 
    уничтожить перед прочтением	(уровень 5) 
    уничтожить после прочтения	(уровень 4) 
    совершенно секретно	(уровень 3) 
    секретно	(уровень 2) 
    конфиденциально	(уровень 1) 
    неклассифицировано	(уровень 0) 
    В этом случае предикат ">" будет означать "более секретно чем" (т.е. более 
высокий уровень безопасности). 
    Теперь ясно, что эти две интерпретации изоморфны, т.е. между ними можно 
задать взаимно однозначное соответствие, а значит, по большому счету, эти две 
интерпретации одинаковы. Однако следует четко понимать, что могут существовать 
совершенно разные интерпретации. Например, можно определить такое же 
пространство рассуждений на основе целых чисел от 0 до 5, но задать предикат 
">" со значением "равно". (Это вполне возможно осуществить, хотя на практике 
это может привести к путанице.) В таком случае первое значение WFF-формулы в 
приведенном выше перечне будет ложным, а не истинным. 
    Другой важной особенностью является возможность совпадения истинностных 
значений WFF-формул для совершенно разных интерпретаций. В рассматриваемом 
примере такая ситуация возможна, если предикат ">" определен по-разному, а 
значение WFF-формулы "2>1" опущено. 
    Следует заметить, что все упомянутые до сих пор в этом подразделе 
предикаты являются закрытыми WFF-формулами. Дело в том, что для данной 
интерпретации всегда можно задать истинное значение для закрытой WFF-формулы, 
но истинное значение открытой WFF-формулы будет зависеть от значений, 
присвоенных свободным переменным. Например, открытая WFF-формула 

    х > 3 

    Приложение В. Логические системы управления базами данных	739 

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

    2 > 1 
    2 > 3 
    EXISTS л- ( л- > 2  ) 
    FORALL х ( х > 2  ) 

    на основе целых чисел от 0 до 5 не являются моделями для этих WFF-формул, 
потому что в этой интерпретации некоторые WFF-формулы принимают ложные 
значения. Наоборот, первая интерпретация (в которой предикат ">" определен 
"соответствующим" образом) могла бы быть моделью набора следующих WFF-формул: 

    2 > 1 
    3 > 2 
    EXISTS х ( х > 2  ) 
    TORALL х ( х > 2 OR NOT   ( х > 2  )   ) 

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

    Стандартная форма 

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

    FORALL х ( р ( х ) AND EXISTS у ( FOFALL z ( q ( у, z ) ) ) ). 

    В этой формуле р и q являются предикатами, ах, у HZ — переменными. 
    1. Сначала следует исключить символы "=>". В рассматриваемом примере эта 
операция не оказывает никакого влияния на вид WFF-формулы. 
    2.  Далее нужно использовать законы Де Моргана, а также тот факт, что два 
смежных оператора NOT нейтрализуют друг друга, для того чтобы применять эти 
операторы только по отношению к термам, а не к WFF-формулам. (В 
рассматриваемом примере эта операция не оказывает никакого влияния на вид WFF-формулы.) 
    3.  Теперь необходимо конвертировать WFF-формулу в предваренную нормальную 
форму, перенося кванторы в начало формулы (систематически переименовывая 
переменные в случае необходимости). 
    4.  Обратите внимание, что если содержащая множество кванторов WFF-формула 

    EXISTS v ( г (  v )   ) 

    эквивалентна другой WFF-формуле 

    г { а ) 

    740	Приложения 

с некоторой (неизвестной) константой а, то в исходной WFF-формуле 
утверждается, что такая константа существует, хотя ее значение не известно. 
Точно так же WFF-формула 

    PORALL u  (  EXISTS   v (  s  (   и,   v )   )   ) 

    эквивалентна WFF-формуле 

    FORALL и (  s (   и,   f (   и )   )   ) 

    для некоторой (неизвестной) функции/универсально квантованной переменной 
и. Константа а и функция/в этих примерах называются в честь ученого-логика 
Ско-лема (Skolem) соответственно константой Сколема (Skolem constant) и 
функцией Сколема (Skolem function), где константа Сколема — это просто функция 
Сколема без аргументов. Таким образом, на следующем этапе необходимо исключить 
излишнее квантование, заменяя соответствующие квантованные переменные 
(произвольными) функциями Сколема всех универсально квантованных переменных, 
которые предшествуют данному квантору в WFF-формуле. 

    FORALL х  (  FORAIi z   ( р  (   X )   AND q (   f (  х },   z )   )   ) 

    5.  Теперь все переменные универсально квантованы и, следовательно, можно 
допустить, что все они неявно универсально квантованы, и опустить явные кванторы. 

    р  (  х )  то q (  f (  х ),   z ) 

    6.  Теперь необходимо конвертировать WFF-формулу к конъюнктивной 
нормальной форме, т.е. к набору предложений, объединенных с помощью оператора 
AND и, вероятно, содержащих операторы NOT и OR, но только не оператор AND. В 
рассматриваемом примере WFF-формула уже находится в такой форме. 
    7.   Разместим каждое предложение на отдельной строке и опустим все 
операторы AND. 

    Р ( х ) 
    д (  f ( х),   z ) 

    Это и есть стандартная форма, эквивалентная оригинальной WFF-формуле. 
Замечание. Из описанной выше процедуры следует, что общий вид WFF-формулы в 
стандартной форме представляет собой набор предложений, размещенных на 
отдельных строках с приведенным ниже синтаксисом: 

    NOT Al OR NOT А2 OR ... OR NOT Am OR Bl OR B2 OR ... OR Bn 

    Здесь А и В являются неотрицаемыми термами. Тот же синтаксис можно 
представить в другом виде: 

    Al AND А2 AND ... AND Am => Bl OR B2 OR ... OR Bn 

    Если в этой записи присутствует по крайней мере один член В (п = О или п- 
1), то она в честь ученого-логика Альфреда Хорна (Alfred Horn) называется 
предложением Хорна. 

    Использование правила резолюции 

    Теперь на основе представленного выше примера рассмотрим, как исполняются 
запросы в логических базах данных. Во-первых, допустим, что у нас есть 
предикат MOTHEROF, который имеет два аргумента, представляющих мать и дочь 
соответственно, а также два следующих терма (экземпляра предиката): 
    1. MOTHEROF (Anne, Betty) 
    2. MOTHEROF(Betty, Celia) 
    Кроме того, дана WFF-формула ("дедуктивная аксиома"), которая, по сути, 
является предложением Хорна: 
    3.    MCTHEROF(x,   у)   AND MOTH?ROF(y,   z)   => GRANEMOTHEROF(x,   z) 

    Приложение В. Логические системы управления базами данных	741 

    Для упрощения работы с правилом резолюции следует исключить из предложения 
символ "=>" и переписать его таким образом: 
    4.    NOT MOTHEROF U,   у)   OR NOT MOTHEROF (y,   z)   OR GRANEMOTHEROFU, 
  z) 
    Далее следует показать, как доказывается утверждение, что Анна является 
бабушкой Сейли, т.е. как ответить на запрос "Является ли Анна бабушкой 
Сейли?". Для этого нужно начать с отрицания заключения, которое требуется 
доказать, и принять его как дополнительную предпосылку: 
    5. NOT GRANDMOTHEROF(Anne, Celia) 
    Теперь для применения правила резолюции нужно систематически подставлять 
значения для переменных таким образом, чтобы можно было найти два предложения, 
содержащих WFF-формулу и ее отрицание. Такая подстановка вполне законна, 
поскольку все переменные неявно универсально квантованы. Следовательно, 
индивидуальные (неотрицаемые) WFF-формулы должны быть истинны для всех и для 
каждой допустимой комбинации значений этих переменных. 

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

    Для того чтобы проиллюстрировать описанный выше процесс, обратимся к 
примеру. Прежде всего следует обратить внимание на то, что строки в пп. 4 и 5 содержат 
    ТерМЫ GRANEMCTHEROFU,   z)  И NOT GRANmOTHEROF(Anne,   Celia) 
СООТВСТСТВСННО. ТЗКИМ образом, в строке п. 4 нужно подставить значение йппе 
вместо х и значение ceiia вместо z. После совмещения получится такой результат: 
    6.   NOT MOTHEROF(Anne,  у)   OR NOT MOTHEROF (y,   Celia) 
    Строка п. 2 содержит выражение NOT MOTHEROF(Anne, у), поэтому можно 
подставить значение Betty вместо ув строке п. 6 и после совмещения получить 
новое выражение 
    7.   NOT MOTHEROF(Anne,   Betty) 
    Совмещая строки в пп. 7 и 1, можно получить пустое утверждение п, т.е. 
противоречие. Следовательно, результатом исходного запроса будет ответ "Да, 
Анна является бабушкой Сейли". 
    Теперь можно выяснить, как будет выполняться запрос "Кто является внучкой 
Анны?". Сложность этой задачи прежде всего состоит в том, что системе ничего 
не известно о внучках, она обладает информацией только о бабушках. В этом 
случае можно было бы добавить еще одну дедуктивную аксиому, согласно которой z 
является внучкой х тогда и только тогда, когда х является бабушкой z 
(предполагается, что в рассматриваемой базе данных не содержатся сведения о 
мужчинах). Тогда исходный запрос можно перефразировать — "Чьей бабушкой 
является Анна?" — и использовать тот же набор предпосылок, что и прежде: 
    1.	MOTHEROF(Anne,  Betty) 
    2.	MOTHEROF(Betty,  Celia) 
    3.	NOT MOTHEROF (x,  y)   OR NOT MOTHEROF (y,   z)   OR GRANDMOTHEROFU,   z) 
    Дополним его четвертой предпосылкой: 
    4.    NOT GRANEMOTHEROF(Anne,   r)   OR RESULT (r) 
    Эта предпосылка может рассматриваться как утверждение о том, что либо Анна 
не является ничьей бабушкой, либо, наоборот, она является бабушкой некоторой 
особы г. Предполагая, что такая особа существует, далее следует ее найти. 
    Сначала подставим Anne вместо хи г вместо z. Совместив строки в пп. 4 и 3, 
получим следующий результат: 
    5.    NOT MOTHEROF (Anne,   у)   OR NOT MOTHEROF(y,   z)   OR RESULT(z) 

    742	Приложения 

    Подставив Betty вместо уи совместив строки в пп. 5 и 1, получим: 
    6.   NOT MOTHEROF(Betty,   z)   OR RESULT (г) 
    Наконец, подставив ceiia вместо ги совместив строки в пп. 6 и 2, получим: 
    7.    RESULT(Celia) 
    Следовательно, Анна является бабушкой Сельи, 
    Замечание, Если бы был задан дополнительный терм, например: 

    MOTHEROF (Betty,   Delia), 

    то на последнем этапе можно было бы подставить Delia вместо г и получить в 
результате выражение 

    RESULT(Delia) 

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

    Al AND А2 AND ,., AND Am => Bl OR B2 OR ... OR Bn 

    Здесь А и В являются термами вида 

    г  ( xl,   х2,   ... xt), 

    где г— предикат, a xl, х2, ... xt— аргументы этого предиката. В 
соответствии с [В. 12] рассмотрим несколько важных типов этой общей конструкции. 
    Случай 1: т = 0, п- 1. 
    В этом случае предложение может быть сведено к следующему простому виду: 

    => В1 

    Его можно также записать в другом виде без символа импликации для 
некоторого предиката г с набором аргументов xl, х2,... xt: 

    г ( xl,   x2,   ... xt) 

    Если все аргументы являются константами, то предложение представляет собой 
основную аксиому, т.е. утверждение, которое однозначно является истинным. В 
терминах базы данных такое утверждение соответствует кортежу некоторого 
отношения R (или элементу некоторого домена). Как неоднократно отмечалось в 
этой книге, предикат г соответствует "смысловому значению" отношения R. 
Например, в базе данных поставщиков и деталей существует отношение SP, которое 
означает, что заданный поставщик (S#) поставляет указанную деталь (Р#) в 
определенном количестве (QTY). Обратите внимание, что это значение 
соответствует открытой WFF-формуле, так как содержит несколько свободных 
переменных (S#, P#, QTY). И наоборот, кортеж (SI, P1, 300), в котором все 
аргументы являются константами, представляет собой основную аксиому или 
закрытую WFF-формулу, которая однозначно утверждает, что поставщик S1 
поставляет деталь Р1 в количестве 300. 
    Случай 2: т > 0, п = 1. 
    В этом случае утверждение принимает вид 

    Al AND A2 AND ... AND Am => В 

    и может рассматриваться как дедуктивная аксиома. 

    Приложение В, Логические системы управления базами данных	743 

    Также такое предложение может рассматриваться как ограничение целостности. 
Предположим, что в рассматриваемом примере отношение S содержит только два 
атрибута, S# и CITY. Тогда приведенное ниже предложение выражает ограничение: 
атрибут CITY функционально зависим от атрибута S#. 

    5(  s,   cl )  ШО S( s,   с2 )   => cl = с2 

    Здесь следует обратить внимание на использование встроенного предиката "=". 
    Из вышеизложенного можно заключить, что кортежи в отношениях ("основные 
аксиомы"), выведенные отношения ("дедуктивные аксиомы") и ограничения 
целостности могут рассматриваться как особые случаи общей конструкции 
предложения. Теперь следует рассмотреть, как эти идеи могут привести к 
упомянутому ранее "доказательно-теоретическому" представлению. 
    Традиционное представление базы данных может считаться 
"модельно-теорети-ческим". Согласно этой точке зрения база данных 
рассматривается как набор явных именованных (базовых) отношений, каждое из 
которых содержит явные кортежи и явный набор ограничений целостности, 
накладываемых на эти кортежи. 
    •  Используемые домены содержат переменные значения или константы, которые 
используются для представления объектов "реального мира" (точнее, в некоторой 
интерпретации, описанной выше в этом приложении). Таким образом, они 
соответствуют "пространству рассуждений". 
    •  Базовые отношения (точнее, заголовки базовых отношений) представляют 
набор предикатов, или открытых WFF-формул, которые должны быть 
интерпретированы в этом пространстве. Например, заголовок отношения SP 
представляет предикат "Поставщик S# поставляет деталь Р# в количестве QTY". 
    •  Каждый кортеж данного отношения представляет собой экземпляр 
соответствующего предиката, т.е. однозначно истинное в пространстве 
рассуждений утверждение (закрытую WFF-формулу, которая не содержит никаких переменных). 
    •  Ограничения целостности также являются закрытыми WFF-формулами и 
интерпретируются в том же пространстве. Поскольку данные не нарушают (т.е. не 
должны нарушать!) ограничений целостности, эти ограничения также всегда 
являются истинными. 
    •  Кортежи и ограничения целостности вместе могут рассматриваться как 
набор аксиом, задающих определенную логическую теорию (попросту говоря, под 
термином "теория" в логике подразумевается набор аксиом). Поскольку в данной 
интерпретации все аксиомы истинны, такая интерпретация по определению является 
моделью этой логической теории. Следует заметить, что, как уже отмечалось в 
этом разделе, модель может быть не уникальной, т.е. база данных может иметь 
несколько возможных интерпретаций, каждая из которых допустима с логической 
точки зрения. 
    Следовательно, с модельно-теоретической точки зрения "смысловым значением" 
базы данных является модель в изложенном выше смысле термина "модель". А 
поскольку существует несколько возможных моделей, в принципе существует и 
несколько возможных смысловых значений. (Однако если предположить, что в базе 
данных не содержится явным образом никакой отрицаемой информации (например, 
утверждение типа "NOT S#(S9)", где S9 не является номером поставщика), то 
возможно существование "минимального" или канонического значения, которое 
является пересечением всех возможных моделей [В. 10].) 
    Для того чтобы применить правила вывода, описанные выше в этом приложении, 
необходимо использовать новую перспективу, в которой база данных явным образом 
рассматривается как некая логическая теория, т.е. как набор аксиом. "Смысловым 
значением" этой базы данных становится набор истинных утверждений, которые 
могут быть выведены из аксиом и их различных комбинаций, т.е. набора теорем, 
дока

    744	Приложения 

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

    Замечание. Из сказанного следует, что отличие между модельно-теоретическим 
и доказательно-теоретическим подходами состоит в том, что, в то время как с 
мо-дельно-теоретической точки зрения база данных может иметь несколько 
"смысловых значений", с доказательно-теоретической точки зрения она обычно 
обладает в точности одним "смысловым значением". Это верно за исключением двух 
случаев: когда, как уже упоминалось ранее, единственное значение является 
каноническим с модель-но-теоретической точки зрения, а также когда 
единственное значение с доказательно-теоретической точки зрения прекращает 
быть истинным, если в базе данных содержатся какие-либо отрицаемые аксиомы 
[В.9, В. 10]. 

    Ниже в неформальном виде перечислены аксиомы базы данных, рассматриваемой 
в данном примере с доказательно-теоретической точки зрения [В. 15]. 
    1. Основные аксиомы, соответствующие элементам домена и кортежам базовых 
отношений, которые называются экстенсиональной базой данных (extensional 
database — EDB). 
    2.  "Аксиома дополнения" для каждого отношения, которая утверждает, что 
никаких кортежей данного отношения не существует, помимо явно указанных в 
отношении. Эти аксиомы называются замкнутым миром допущений (Closed World 
Assumption — CWA). Таким образом, при удалении заданного кортежа из данного 
отношения предполагается, что утверждение, относящееся к этому кортежу, 
становится ложным. Например, если в отношение поставщиков S не включен кортеж 
(S6, White, 45, Rome), то утверждение "Существует поставщик S6 по имени White, 
который имеет статус 45 и проживает в Риме (Rome)" является ложным. 
    3.  Аксиома "уникального имени", которая утверждает, что каждая константа 
отлична от других (т.е. обладает уникальным именем). 
    4.  Аксиома "замкнутости доменов", которая утверждает, что не существует 
никаких других констант, кроме упомянутых в доменах базы данных. 
    5.  Набор аксиом (совершенно стандартных) для определения встроенного 
предиката "=". Эти аксиомы обязательны, поскольку в аксиомах 2-4 используется 
предикат равенства. 
    В заключение следует перечислить принципиальные различия между двумя 
точками зрения — модельно-теоретической и доказательно-теоретической. Но 
прежде всего следует отметить, что с чисто практической точки зрения между 
ними нет существенной разницы, по крайней мере в понятиях современных систем. 
    •   Аксиомы 2-5 из приведенного выше списка согласно 
доказательно-теоретическому подходу указывают, что некоторые допущения 
являются явными, хотя с точки зрения модельно-теоретического подхода они 
неявные [В. 15]. Вообще, явное задание аксиом довольно удобно и, более того, 
даже необходимо для явного задания дополнительных аксиом, используемых для 
таких общих методов доказательства, как описанный выше метод резолюции. 
    •   Следует отметить, что в аксиомах не упоминаются ограничения 
целостности. Дело в том, что с доказательно-теоретической точки зрения при 
добавлении таких офаничений СУБД становится дедуктивной. Подробнее это описано ниже. 
    •  Доказательно-теоретический подход, в отличие от 
модельно-теоретического, обладает некоторой элегантностью, состоящей в едином 
представлении нескольких конструкций, которые обычно рассматриваются как 
совершенно разные: базовые 

    Приложение В. Логические системы управления базами данных	745 

данные, запросы, ограничения целостности (несмотря на сказанное в 
предыдущем пункте), виртуальные данные и т.д. Это позволяет создавать более 
стандартизованные интерфейсы и приложения. 
    С помощью доказательно-теоретического подхода можно решать проблемы, 
которые не под силу решить на основе реляционных систем, например обрабатывать 
дизъюнктивную информацию типа "Поставщик S6 проживает либо в Париже, либо в 
Риме". Эта информация — результат отрицаемой информации типа "Кто не является 
поставщиком?" и рекурсивных запросов, которые будут описаны ниже. Причем в 
этом случае нет никаких принципиальных ограничений для соответствующего 
расширения классической реляционной системы и выполнения таких запросов (один 
из вариантов такого расширения можно найти в [В. 14]). Более детально эти 
вопросы описаны ниже. 
    Наконец, цитируя Рейтера (Reiter) [В. 15], можно сказать, что 
доказательно-теоретический подход "обеспечивает корректную обработку 
расширений реляционной модели для более широкого включения семантики реального 
мира" (включая события, иерархии типов и некоторые виды агрегации целостности). 

    В.6. Дедуктивные СУБД 

    Дедуктивная СУБД — это СУБД, в которой поддерживается 
доказательно-теоретический подход к базам данных и в которой, в частности, 
можно вывести дополнительные факты из экстенсиональной базы данных с помощью 
специализированных дедуктивных аксиом, или правил вывода. Дедуктивные аксиомы 
вместе с ограничениями целостности (они будут описаны ниже) образуют 
интенсиональную базу данных (intensional database — IDB). Экстенсиональная и 
интенсиональная базы данных вместе составляют дедуктивную базу данных (это не 
совсем удачное название, поскольку на самом деле это СУБД, а не база данных, 
которая делает выводы). 
    Как сказано выше, часть дедуктивных аксиом образует экстенсиональную базу 
данных, а другая часть состоит из дополнительных аксиом, которые представляют 
ограничения целостности (т.е. правила, используемые прежде всего для 
ограничения обновлений, хотя в действительности такие правила могут также 
использоваться в процессе дедукции для генерирования новых фактов). 
    Рассмотрим, как будет выглядеть база данных поставщиков и деталей в форме 
"дедуктивной СУБД". Прежде всего следует определить набор основных аксиом, 
которые задают допустимые значения домена. (Далее для лучшей читабельности все 
кавычки вокруг символьных констант будут опущены.) 

    s#	( SI )	NAME (	Smith )	STATUS	( 5 )	CITY (	London ) 
    s#	( S2 )	NAME (	Jones )	STATUS	( 10 )	CITY (	Paris ) 
    s#	( S3 )	NAME (	Blake )	STATUS	( 15 )	CITY (	Rome ) 
    s#	( S4 )	NAME (	Clark )	и т.д.		CITY (	Athens ) 
    s#	( S5 )	NAME (	Adams )			и т.д. 
    s#	( S6 )	NAME (	White ) 
    s#	( S7 )	NAME {	Nut ) 
    и т	.Д.	NAME (	Bolt ) 
    NAME (	Screw ) 

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

    S ( SI, Smith, 20, London ) S ( S2, Jones, 10, Paris ) и т.д. 
    P ( PI, Nut, Red, 12, London ) и т.д. 
    SP ( SI, PI, 300 ) 

    и т.д. 

    746	Приложения 


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

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

    S ( s, sn, st, sc ) =* S# ( s ) AND 
    NAME ( sn } AND STATUS ( st ) AND CITY ( sc ) 
    P ( p, pn, pi, pa, pc ) => P# ( p } AND 
    NAME ( pn ) AND 
    COLOR ( pi ) AND 
    WEIGHT ( pw } AND 
    CITY ( pc } и т.д. 

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

    S ( s, snl, stl, scl ) 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, pt, pw, pc )  AND QTY   (   q ) 

    И так далее. 

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

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

    S   (  s,   sn,   st,   sc )  AND st > 15 
    => GOOD_SUPPLIERS   {   s,   st,   sc ) 

    (Сравните с определением представления, данным в начале главы 17.) 

    S ( sx, sxn, sxt, sc ) AND S ( sy, syn, syt, sc ) 
    => SS_COLCCATED ( sx, sy ) S ( s, sn, st, sc ) AND P ( p, pn, pi, pw, с ) 
    => SS_COLCCATED { s, p ) 

    И так далее. 

    Приложение В. Логические системы управления базами данных	747 

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

    PART__STRUCTORE   ( рх,  ру )   ==> Р   ( рх,   хп,   xl,   xw,   xc )   AND 
    Р   ( ру,   уп,   yl,   yv,   ус ) 

    Затем следует указать данные 

    PART_STRUCTURE ( PI, P2 ) PARTJ3TRUCTURE ( PI, РЗ ) PART_STRUCTURE ( Р2, 
РЗ ) PART_STRUCTURE ( Р2, Р4 ) и т.д. 
    (На самом деле определение PART STRUCTURE должно также иметь аргумент 
"количество", который указывал бы количество деталей ру, необходимое для 
создания детали рх, но в данном случае для простоты это опускается.) 
    Теперь можно добавить пару дедуктивных аксиом для объяснения, каким 
образом деталь/?* содержит деталь/ту в качестве компонента любого уровня: 

    PARTJSTKUCTUPE   ( рх,  ру )   => CCMPONENTOF   (  рх,   ру  ) 
    PART_STRUCTURE   ( рх,  pz )   AND CCMPONENTOF   ( pz,   py ) => 
CCMPONENTOF   (  рх,   ру  ) 

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

    Язык Datalog 

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

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

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

    Al AND A2 AND . .. AND An 
    Al AND A2 AND ... AND An => В 

    748	Приложения 

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

    В <= Al AND A2 AND  . . .  AND An 

    Для полного соответствия с другими публикациями на эту тему далее будет 
использоваться именно такая запись. В таком предложении В является заголовком 
правила, или заключением, а терм А — телом правила, или предпосылкой либо 
целью, в которой отдельные термы являются подчиненными целями (или подцелями). 
Для краткости операторы AND часто заменяют запятыми. Таким образом, программа 
на языке Datalog представляет собой набор таких предложений, разделенных 
обычным образом, т.е. точкой с запятой (в этой книге, однако, вместо точки с 
запятой используется перенос на отдельную строку). При этом в такой программе 
порядок расположения предложений не имеет никакого значения. 
    Заметим, что целая "дедуктивная база данных" может рассматриваться как 
программа Datalog в указанном выше смысле. Можно, например, все аксиомы, 
заданные для поставщиков и деталей (основные аксиомы, ограничения целостности 
и дедуктивные аксиомы), записать в стиле программы Datalog, разделить точкой с 
запятой или разместить на отдельных строках и в результате получить программу 
на языке Datalog. Основная функция языка Datalog заключается в формулировании 
дедуктивных аксиом. Как уже отмечалось выше, эту функцию следует рассматривать 
как расширение механизма определений представлений, существующего в 
современных реляционных СУБД. 
    Язык Datalog может также использоваться в качестве языка запроса (точно 
так же, как язык Prolog). Для примера предположим, что на языке Datalog дано 
следующее определение хороших поставщиков GOOD_SUPPLIERS: 

    GOOD_SUPPLIERS   (  s,   st,   sc )   <= S   (  s,   sfi,   st,   sc )  
AND st > 15 

    Ниже приведены примеры запросов на основе этого определения. 
    1.  Найти всех хороших поставщиков: 

    ? <= GOOD_SUPPLIERS   (  s,   st,   sc ) 

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

    ? <= GOOD_SUPPLIERS   (  s,   st,   Paris ) 

    3.  Является ли поставщик SI хорошим поставщиком: 

    ? <= GOODJSUPPLIERS   (  SI,   st,   sc ) 

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

    Приложение В. Логические системы управления базами данных	749 

    •   Отрицаемые предпосылки: 

    SS_COLOCATED ( sx, sy ) <= S ( sx, sxn, sxt, sc ) AND 
    S ( sy, syn, syt, sc ) AND NOT ( sx = sy ) 

    •  Скалярные функции (встроенные и определенные пользователем): 

    P_WT_IN_GRAMS   ( р,  рп,  pi,  pg,   рс )   <= 
    Р   ( р,  рп,  pi,  fw,  рс )   AND pg = pw *   454 

    В данном примере предполагается, что встроенная функция "*" (умножение) 
может быть записана в представленном виде. Более ортодоксальное представление 
терма, следующего за оператором AND, выглядело бы как = (рд, * (ри, 454)). 
    •   Функции подведения итогов и группировки (в некотором смысле эта тема 
касается отдельных особенностей оператора SUMMARIZE; подробнее это описано в 
главе 6). Такие операторы необходимы для того, чтобы разрешить проблему так 
называемых грубых требований. Она заключается не только в поиске деталей ру, 
которые являются компонентами некоторых деталей рх на любом уровне, но также и 
в выяснении, сколько деталей ру (на всех уровнях) требуется для создания 
детали рх (при этом, естественно, предполагается, что PART_STRUCTURE содержит 
атрибут QTY). 
    •  Операции обновления. Один из подходов в реализации этих операций [В. 
10], и не только их, основан на наблюдении, что в языке Datalog любой предикат 
в заголовке правила должен быть неотрицаемым и каждый кортеж, генерируемый 
этим правилом, может рассматриваться как "вставленный" в результирующее 
отношение. Возможное расширение, таким образом, должно допускать использование 
отрицаемых предикатов в заголовке правила и рассматривать отрицание как запрос 
на удаление (соответствующих кортежей). 
    •  Предложения "не-хорновского" типа в теле правила. Иначе говоря, в 
определении правил допускается использование WFF-формул самого общего вида. 
    Обзор этих расширений вместе с примерами и обсуждением приложений языка 
Datalog можно найти в [В. 10]. 

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

    Как отмечалось в предыдущем разделе, одна из наиболее замечательных 
особенностей дедуктивных СУБД — способность поддерживать рекурсию. Именно 
поэтому изучению технологий применения рекурсии в последние годы уделялось 
значительное внимание. Действительно, с 1986 года на каждой научной 
конференции по базам данных один или несколько докладов посвящаются этой теме. 
Ниже в краткой форме обсуждается поддержка рекурсивных запросов, которая 
обычно не характерна для традиционных СУБД. 
    В качестве примера повторим приведенное выше рекурсивное определение 
отношения "структуры деталей" (для краткости вместо полного названия 
PART_STRUCTURE используется сокращение PS, а вместо COMPONENTOF — СОМР, кроме 
того, используется запись, принятая в языке Datalog). 

    ССМР ( рх, ру ) <= PS ( рх, ру ) 
    ССМР ( рх, ру ) <= PS ( рх, pz ) AND ССМР ( pz, ру ) 

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

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

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

    750	Приложения 


    ССМР ( рх, ру ) <= PS ( рх, ру ) 
    ССМР ( рх, ру ) <= ССМР ( рх, pz ) AND ССМР ( pz, ру ) 

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

    Р   (  х,   у )   <= Q   (  х,   z )   AND R   (   z,   у ) Q   (  х,  у ) 
  <= Р   (   х,   z )   AND S   (   z,   у ) 

    Для краткости изложения эти особенности будут опущены, а более подробную 
информацию о них можно найти в [В. 16]. 
    Так же как и при обработке классического (нерекурсивного) запроса, вся 
задача воплощения заданного рекурсивного запроса может быть разбита на две 
отдельные части, а именно: преобразование исходного запроса в эквивалентную, 
но более эффективную форму и собственно выполнение преобразованного таким 
образом запроса. В литературе содержатся описания нескольких попыток 
разрешения этих проблем. Например, в [В. 16] предлагается прекрасный обзор, 
анализ и сравнение опубликованных данных о таких технологиях по состоянию на 
1988 год. Ниже кратко описаны некоторые простейшие из этих технологий. Они 
будут проиллюстрированы на примере запроса "Найти все компоненты детали Р1" с 
использованием приведенного ниже набора значений для отношения PS (они 
построены на основе рис. 4.4 из главы 4, но для упрощения изложения здесь 
опущена переменная QTY). 

    PS 
    РХ	PY 
    Р1	Р2 
    Р1	РЗ 
    Р2	РЗ 
    Р2	Р4 
    РЗ	Р5 
    Р4	Р5 
    Р5	Р6 


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

    Одним из возможных подходов, конечно, является использование стандартных 
для языка Prolog методов унификации и резолюции, описанных выше. В данном 
примере этот подход будет реализован следующим образом. Прежде всего следует 
указать первичные предпосылки, которые являются дедуктивными аксиомами и в 
конъюнктивной нормальной форме выглядят так: 
    1.    NOT PS   ( рх,  ру )   OR ССМР   ( рх,  ру ) 
    2.    NOT PS   ( рх,  pz )   OR NOT ССМР   ( pz,  ру )   OR ССМР   ( рх,  
ру ) 
    Еще одна предпосылка создана на основе искомого заключения: 
    3.    NOT ССМР   (  Р1,  ру )   OR RESULT   ( ру ) 
    Основные аксиомы образуют оставшиеся предпосылки. Ниже приведен пример 
одной из таких аксиом: 
    4.    PS   (  Р1,   Р2  ) 
    Подставляя Р1 вместо рх и Р2 вместо ру в строке п. 1 и совмещая строки пп. 
1 и 4, получим следующий результат: 
    5.    ССМР   (  Р1,   Р2  ) 
    Теперь, подставляя Р2 вместо ру в строке п. 3 и совмещая строки пп. 3 и 5, 
получим окончательный результат: 
    6.    RESULT   {   Р2   ) 

    Приложение В. Логические системы управления базами данных 751 

    Таким образом, деталь Р2 является компонентом детали Р1. Аналогично можно 
показать, что деталь РЗ также является компонентом детали Р1. Теперь, обладая 
дополнительными аксиомами сомр(р!,р2) и сомр(р!,РЗ), можно рекурсивно 
выполнить поиск всех остальных компонентов. Эта задача предлагается читателю в 
качестве упражнения. 
    Однако на практике унификация и резолюция могут в значительной степени 
понизить производительность системы. Поэтому желательно найти и использовать 
более эффективную стратегию. Несколько таких стратегий описано ниже. 

    Наивное оценивание 

    Наивное оценивание [В.25], судя по названию, является, вероятно, 
простейшим подходом. Его можно продемонстрировать (на основе рассматриваемого 
примера с запросом) с помощью приведенного ниже псевдокода. 

    ССМР := PS ; 
    do until ССМР reaches a "fixpoint" ; /* выполнять, пока ССМР не достигнет 
"точки неизменчивости" */ 
    ССМР := ССМР UNION ( ССМР и PS ) ; end ; DISPLAY := ССМР WHERE PX = 'PI' ; 

    Каждое из отношений СОМР и DISPLAY (подобно отношению PS) имеет по два 
атрибута, РХ и PY. Попросту говоря, выполнение этого алгоритма с получением 
промежуточного результата, состоящего из объединения соединения отношения PS и 
предыдущего промежуточного результата, повторяется до тех пор, пока 
промежуточный результат не достигнет "точки неизменчивости", т.е. пока не 
прекратится рост (изменение) промежуточного результата. 

    Замечание. Выражение "СОМР « PS" является сокращенной формой записи 
выражения "соединить СОМР и PS по атрибутам COMP.PY и PS.PX с выводом 
результатов по атрибутам СОМР.РХ и PS.PY". Для краткости здесь игнорируются 
операции переименования атрибута, соответствующие рассматриваемому диалекту 
данной алгебры (подробнее это описано в главе 6). 

    Теперь попробуем применить этот алгоритм к рассматриваемому набору данных. 
Ниже показаны результаты выполнения первой итерации цикла: слева приведены 
значения выражения СОМР & PS, а справа — значения величины СОМР (кортежи, 
добавленные в ходе этой итерации, отмечены звездочкой). 

    ССМР и PS 
    РХ  |  PY Р1     РЗ PI     P4 PI     P5 Р2     Р5 РЗ     Р6 Р4     Р6 
    ССМР 
    РХ	PY 
    Р1	Р2 
    Р1	РЗ 
    Р2	РЗ 
    Р2	Р4 
    РЗ	Р5 
    Р4	Р5 
    Р5	Р6 
    Р1	Р4 
    Р1	Р5 
    Р2	Р5 
    РЗ	Р6 
    Р4	Р6 

    Далее приведены результаты, полученные после второй итерации. 
    При внимательном просмотре этих результатов можно заметить, что на второй 
итерации повторяется вычисление кортежей СОМР & PS, полученных во время первой 
итерации, а также вычисляется несколько дополнительных кортежей (в данном 
случае это два кортежа (Р1, Р6) и (Р2, Р6)). Это делает методику наивного 
оценивания не очень удачной. 

    752 Приложения 

    ССМР и PS 
    РХ    РУ PI    РЗ PI     Р4 PI     P5 Р2     Р5 РЗ    Р6 Р4     Р6 PI     
P6 PI     P6 
    ССМР 
    РХ	PY 
    Р1	Р2 
    Р1	РЗ 
    Р2	РЗ 
    Р2	Р4 
    РЗ	Р5 
    Р4	Р5 
    Р5	Р6 
    Р1	Р4 
    Р1	Р5 
    Р2	Р5 
    РЗ	Р6 
    Р4	Р6 
    Р1	Р6 
    Р1	Р6 

    После третьей итерации и повторения всех необходимых вычислений 
извлекаемые значения выражения СОМР s PS остаются теми же, что и на предыдущей 
итерации. Таким образом, точка неизменчивости для СОМР достигается и 
выполнение цикла завершается. Выполнив выборку СОМР по всем РХ, равным Р1, 
получим окончательный результат. 

    ССМР 
    РХ	PY 
    Р1	Р2 
    Р1	РЗ 
    Р1	Р4 
    Р1	Р5 
    Р1	Р6 

    Неэффективность этого алгоритма проявляется еще и в том, что он выполняет 
огромную работу по поиску компонентов каждой детали, фактически вычисляя 
транзитивное замыкание отношения PS (ниже это описано более подробно), и 
оставляет в виде конечного результата лишь небольшую часть вычисленных 
кортежей. Иначе говоря, при этом выполняется большой объем ненужной работы. 
    Замечание в отношении транзитивного замыкания. Транзитивное замыкание 
бинарного отношения R{X, Y} — это супермножество кортежей (х, у), которые 
принадлежат этому транзитивному замыканию тогда и только тогда, когда они 
принадлежат R или существует такая последовательность значений zl, z2,... zn, 
при которой все кортежи (х, zl), (zl, z2),... (zn, у) принадлежат R. 
    В заключение следует отметить, что наивное оценивание можно рассматривать 
как практическое воплощение метода "от фактов к цели". В самом деле, оно 
начинается с использования экстенсиональной базы данных (т.е. с действительных 
значений данных), а затем продолжается в виде повторного использования 
предпосылок определения (т.е. тела правила) вплоть до получения желаемого 
результата. Фактически этот алгоритм позволяет вычислить .минимальную модель 
для программы на языке Datalog. 

    Полунаивное оценивание 

    Первым очевидным усовершенствованием алгоритма наивного оценивания 
является возможность избежать повторных вычислений результатов, полученных во 
время предыдущей итерации. Такой усовершенствованный алгоритм называется 
полунаивным оцениванием [В.28]. Иначе говоря, на каждом шаге итерации 
вычисляются только новые кортежи, которые добавляются к полученным ранее 
результатам. Эта идея вновь будет проиллюстрирована на примере запроса "Найти 
все компоненты детали Р1" с приведенным ниже псевдокодом. 
    NEW := PS ; ССМР := NEW ; do until NEW is enpty ; /* выполнять, пока NEW 
не будет пусто */ 

    NEW := ( NEW % PS ) MINUS CCMP ; 
    CCMP := CCMP UNION NEW ; end ; DISPLAY := CCMP WHERE PX = 'PI1 ; 

    Приложение В. Логические системы управления базами данных 753 
    25 Введение в системы баз данных 

    Теперь стоит просмотреть, как выполняется этот алгоритм, на примере 
используемых ранее данных. Перед выполнением цикла отношения NEW и СОМР 
идентичны PS, 

    РХ | PY               CCMP  РХ	PY 
    Р1   РЗ                     Р1	Р2 
    Р1   Р5                     Р1	РЗ 
    Р2   Р5                     Р2	РЗ 
    РЗ   Р6                     Р2	Р4 
    Р4   Р6                     РЗ	Р5 
    Р4	Р5 
    Р5	Р6 
    Р1	Р4 
    Р1	Р5 
    Р2	Р5 
    РЗ	Р6 
    Р4	Р6 

    Данные для СОМР такие же, как и при использовании алгоритма наивного 
оценивания, а данные для NEW содержат только те кортежи, которые были 
добавлены для СОМР на этой итерации. Обратите внимание, что данные для NEW не 
содержат кортеж (Р1, РЗ) (сравните с данными, полученными при наивном оценивании). 
    Ниже приведены данные, которые будут получены после выполнения следующей итерации. 

    NEW   РХ | PY                CQMP   РХ | PY 
    Р1   Р6                       Р1	Р2 
    Р2   Р6                      Р1	РЗ 
    Р2	РЗ 
    Р2	Р4 
    РЗ	Р5 
    Р4	Р5 
    Р5	Р6 
    Р1	Р4 
    Р1	Р5 
    Р2	Р5 
    РЗ	Р6 
    Р4	Р6 
    Р1	Р6 
    Р2	Р6 

    На следующей итерации для NEW никаких данных получено не будет и цикл 
будет завершен. 

    Статическое фильтрование 

    Статическое фильтрование базируется на основной идее классической теории — 
налагать ограничения на самых ранних этапах вычислений. Его можно 
рассматривать как воплощение методики "от цели к фактам", поскольку в нем 
самым эффективным образом используется информация запроса (заключения) для 
модификации правил (предпосылок). Иногда этот способ называется сокращением 
набора уместных фактов, поскольку в нем для исключения ненужных кортежей сразу 
на выходе экстенсиональной базы данных вновь используется информация запроса. 
Эффективность этого способа демонстрируется с помощью следующего кода: 

    NEW    := PS WHERE РХ =  'PI'   ; CCMP  := NEW ; 
    
    РХ	PY          семе  РХ | PY 
    Р1	Р2                     PI   P2 
    Р1	РЗ                     Р1   РЗ 
    Р2	РЗ                     Р2   РЗ 
    Р2	Р4                     Р2   Р4 
    РЗ	Р5                     РЗ   Р5 
    Р4	Р5                     Р4   Р5 
    Р5	Р6                     Р5   Р6 


    754 Приложения 

    do until NEW is empty ; /* выполнять,  пока NEW не будет пусто */ 
NEW  :=  (NEW » PS)  MINUS CCMP ; 
CCMP   := CCMP UNION NEW  ; 
end ; 
DISPLAY  := CCMP ; 

Ниже дается последовательное описание этого алгоритма. Перед началом 
выполнения цикла NEW и ССМР выглядят так: 

NEW       РХ   1    PY               
                       CCMP       PX   1    PY 
    NEW       РХ   |    PY                                      ССМР       РХ  
 |    PY PI         P2                                                      PI 
        P2 Р1         РЗ                                                      
Р1         РЗ 

    После первой итерации эти переменные примут следующий вид 

NEW    

   PX   |    PY                                      CCMP       PX   J    PY 
PI         P4                                                       PI         
P2 Р1         Р5                                                      Р1       
  РЗ PI         P4        * PI         P5       * 

    А в конце следующей итерации будет получен результат: 

NEW        
PX        
  PY                                          ССМР        РХ    1    Fl 
    РХ	PY 
    Р1	Рб 
    РХ | PY PI   P2 Р1   РЗ PI   P4 PI   P5 PI   P6 

    На следующей итерации переменная NEW опустошается и выполнение цикла 
завершается. На этом заканчивается краткий обзор стратегий рекурсивного 
выполнения запросов. В опубликованной литературе можно найти множество более 
сложных подходов, однако их описание явно выходит за рамки этой книги, в 
которой преследуется совсем другая цель. Более детально познакомиться с этими 
подходами и получить все необходимые для их понимания основные сведения можно 
в [В.16-В.43]. В. 8. Резюме На этом завершается краткое введение в СУБД, 
основанные на логике. Некоторые потенциальные преимущества этой сравнительно 
новой идеи, представляющей значительный интерес, описаны в различных разделах 
данного приложения. Однако здесь не было упомянуто еще одно преимущество: 
логика может сформировать поистине полную интеграцию между языками 
программирования общего назначения и базой данных. Другими словами, вместо не 
совсем элегантного подхода на основе "подъязыка для внедренных данных", 
который используется во многих со временных СУБД, в данной системе 
предлагается единый язык, основанный на логике. Причем в такой системе "данные 
являются данными" независимо от того, хранятся ли они в совместно используемой 
базе данных или локально по отношению к некоторому приложению. (Конечно, на 
пути к этой цели потребуется преодолеть множество препятствий; например, 
весьма важно убедить специалистов в области информационных технологий в том, 
что логика может быть прежде всего основой языков программирования общего 
назначения.) Помимо рассмотренного выше примера, в некоторых приложениях 
требуется обеспечить доступ к данным в базе данных совместного использования в 
стиле языка Catalog. В таком случае возникает вопрос, как обеспечить подобный 
доступ. На этот вопрос существует два разных ответа, основанных на подходах 
слабой и сшьной связи [В. 1 1 ]. •   Подход на основе слабой связи состоит в 
необходимости наладить интерфейс вызовов между уже существующей СУБД и 
существующей системой логического программирования. Пр и таком подходе 
пользователь осознает, что работа ведется 

    Приложение В. Логические системы управления базами данных 755 

в двух совершенно различных системах. Причем сначала для извлечения данных 
должны быть выполнены операции базы данных (например, SQL-выражения), а затем 
с этими данными будут выполнены логические операции (например, правила языка 
Prolog). При таком подходе не обеспечивается упомянутая выше "полная интеграция". 
    •  Подход на основе сильной связи, наоборот, построен на истинной 
интеграции СУБД и системы логического программирования. Иначе говоря, в языке 
запросов такой СУБД предусмотрена прямая поддержка логических операций. Таким 
образом, пользователь имеет дело только с одним языком программирования, а не 
с двумя. 
    Достоинства и недостатки этих подходов очевидны: слабую связь легче 
воплотить, но она не столь привлекательна для пользователя. И наоборот, 
сильную связь труднее воплотить, но она более привлекательна. Кроме того, 
система на основе сильной связи обладает большей производительностью 
(возможности для оптимизации логических запросов весьма ограничены в слабо 
связанных системах). Однако по очевидным причинам первые коммерческие продукты 
(некоторые из них существуют до сих пор) были выполнены на основе слабой связи. 
    Подытожим представленные в данном приложении сведения. Оно начиналось с 
краткого обзора исчисления высказываний и исчисления предикатов с описанием 
некоторых основных понятий. 
    •   Интерпретация набора WFF-формул —• это комбинация пространства 
рассуждений, отображения индивидуальных констант из этих WFF-формул на объекты 
в этом пространстве и набора заданных значений для предикатов и функций, 
находящихся в этих WFF-формулах. 
    •   Модель для набора WFF-формул — это интерпретация, для которой все 
WFF-формулы в наборе истинны. В общем случае для данного набора WFF-формул 
может существовать любое количество моделей. 
    • Доказательство — это демонстрация того, что данная WFF-формула g 
(заключение) является логической последовательностью некоторого заданного 
набора WFF-формул //, /2,... fn (предпосылки). В качестве примера 
рассматривался один из методов доказательства под названием резолюция и унификация. 
    Затем обсуждался доказательно-теоретический подход к базам данных. При 
таком подходе база данных рассматривается как комбинация экстенсиональной и 
интенсиональной баз данных. Экстенсиональная база данных содержит основные 
аксиомы, т.е. базовые данные (попросту говоря), а интенсиональная — 
ограничения целостности и дедуктивные аксиомы, т.е. представления (попросту 
говоря). В таком случае "смысловое значение" базы данных определяется набором 
теорем, которые должны быть выведены из аксиом, а выполнение запроса 
становится (по крайней мере концептуально) процессом доказательства теоремы. 
Дедуктивной СУБД называется СУБД, в которой поддерживается 
доказательно-теоретический подход. 
    Одно совершенно очевидное отличие языка Catalog от традиционных 
реляционных языков — возможность поддержки рекурсивных аксиом, а значит, и 
рекурсивных запросов. При этом никаких принципиальных ограничений на 
расширение соответствующим образом традиционной реляционной алгебры и 
исчисления не существует. (В этой связи интересно отметить, что в реляционных 
СУБД все же необходимо (хоть и неявно) выполнять рекурсивную обработку, 
поскольку каталог будет содержать рекурсивно структурированную информацию. 
Например, определения доменов выражаются на основе других определений доменов, 
определения представлений выражаются на основе других определений 
представлений и т.д.). Здесь также рассматриваются некоторые простые 
технологии выполнения таких запросов. 
    В заключение отметим, что приложение начиналось с перечисления терминов 
типа логическая СУБД, дедуктивная СУБД и т.д., которые часто встречаются в 

    756	Приложения 

современной научной литературе (а также в рекламных материалах). Для прояснения 
смысла этих терминов ниже приводится их краткое описание. Хотя следует 
заметить, что единого мнения по этому поводу не существует и в разных 
публикациях можно встретить совершенно разные определения. 
    •  Рекурсивная обработка запросов. Такой тип обработки относится к 
оцениванию (и отчасти к оптимизации) запросов, которые по определению являются рекурсивными. 
    •  База знаний. Этот термин порой используется для так называемой 
интенсиональной базы данных, которая состоит из правил (ограничений 
целостности и дедуктивных аксиом), тогда как экстенсиональная база данных 
состоит из базовых данных. Однако многими авторами термин "база знаний" 
используется для обозначения комбинации экстенсиональной и интенсиональной 
базы данных, за исключением случая, когда (как, например, утверждается в [В. 
10]) база знаний часто содержит сложные объекты, такие как классические 
отношения. Наконец, в системах на основе естественных языков этот термин имеет 
совсем другое специфическое значение, поэтому, вероятно, лучше вообще избегать 
использования этого термина. 
    •  Знания. Знания — это то, что содержится в базе знаний. Исходя из такого 
определения, для объяснения термина "знания" необходимо вернуться к 
предыдущему пункту. 
    •   Система управления базой знаний. Это программное обеспечение, которое 
управляет базой знаний. Этот термин обычно используется как синоним для 
дедуктивной СУБД (см. ниже). 
    • Дедуктивная СУБД. Это СУБД, в которой предусмотрена поддержка 
доказательно-теоретического подхода, в частности в таких СУБД можно вывести 
дополнительную информацию из экстенсиональной базы данных с помощью 
инференци-альных (т.е. дедуктивных) правил, которые хранятся в интенсиональной 
базе данных. В дедуктивной СУБД почти всегда поддерживаются рекурсивные 
правила, а это значит, что возможно выполнение рекурсивных запросов. 
    • Дедуктивная база данных. Спорный термин, который означает базу данных, 
управляемую дедуктивной СУБД. 
    •   Экспертная СУБД. Синоним дедуктивной СУБД. 
    •   Экспертная база данных. База данных, которая находится под управлением 
экспертной СУБД. 
    •   Инференциальная СУБД. Синоним дедуктивной СУБД. 
    •   Система, основанная на логике. Синоним дедуктивной СУБД. 
    •  Логическая база данных. Спорный термин, который является синонимом 
дедуктивной базы данных. 
    •  Логика как модель данных. Модель данных состоит из объектов, правил 
целостности и операторов. В дедуктивной СУБД все они представлены в одной и 
той же форме: как аксиомы логического языка типа Datalog. Действительно, как 
объясняется в этом приложении, база данных в такой системе может 
рассматриваться как логическая программа, содержащая аксиомы всех трех видов. 
Следовательно, можно утверждать, что в такой системе абстрактная модель данных 
логична сама по себе. 

    Упражнения 

    В.1. Используя метод резолюции, определите, являются ли приведенные 
утверждения истинными в исчислении высказываний: 
    а) А => В,   С => В,   D=>   (A OR С ),   D \ В 

    Приложение В. Логические системы управления базами данных	757 

    б) ( /3 => В )AND(  С => ? ),(В =>E AND D => F ), NOT( E AND F ), A => С [ NOT A 
    B) (  A OR В )=> D, D => NOT(  ?' OR F ), NOT ( Я AND С AND ?• ) )-NOT( G => NOT(С AND #)  
    B.2. Преобразуйте следующие WFF-формулы в стандартную форму: 
    а) FORALL х ( FORALL у ( р (	х,	у } => EXISTS z	( д ( х,	z )	)	)	) 
    б) EXISTS х ( EXISTS у ( р (	х,	у ) => FORALL г	( д ( х,	z )	)	)	) 
    B) EXISTS х ( EXISTS у ( р (	х,	у ) => EXISTS z	( q ( х,	г )	)	)	) 
    8.3. Ниже приводится достаточно стандартный пример логической базы данных: 

    MAN	(	Adam ) 
    WOMAN	(	Eve ) 
    MAN	(	Cain ) 
    MAN	(	Abel ) 
    MAN	(	Enoch ) 
    PARENT	( Adam, Cain ) 
    PARENT	( Adam, Abel ) 
    PARENT	( Eve, Cain ) 
    PARENT	( Eve, Abel ) 
    PARENT	( Cain, Enoch ) 
    FATHER ( X, у ) <= PARENT ( X, у ) AND MAN ( x ) MOTHER ( X, у ) <= PARENT 
( X, у ) AND WOMAN ( x ) 
    SIBLING { x, у ) <= PARENT ( z, X ) AND PARENT ( z, у ) BROTHER ( X, у ) 
<= SIBLING ( X, у ) AND MAN ( X ) SISTER ( X, у ) <= SIBLING ( x, у ) AND 
WOMAN { x ) 
    ANCESTOR ( x, у ) c= PARENT { X, у ) 
    ANCESTOR ( x, у ) <= PARENT ( x, z ) AND ANCESTOR ( z, у ) 

    Используйте метод резолюции для ответа на следующие запросы: 
    а) "Кто является матерью Каина (Cain)?" 
    б) "Кто является братом или сестрой Каина?" 
    в) "Кто является братом Каина?" 
    г) "Кто является сестрой Каина?" 
    д) "Кто является наследником Еноха (Enoch)?" 
    8.4. Дайте определение терминам "интерпретация" и "модель". 
    8.5. Напишите набор аксиом языка Datalog только для той части определений 
базы данных поставщиков и деталей. 
    8.6. Запишите на языке Datalog ответы для упр. 6.13-6.48 там, где это возможно. 

    758	Приложения 

    Список литературы 

    В течение нескольких последних лет число публикаций в области логических 
СУБД весьма возросло, а приведенный ниже список представляет собой лишь малую 
часть всей имеющейся на сегодня литературы. Список включает следующие 
тематические группы. Книги [В.1-В.9] посвящены логике в целом (отчасти в 
контексте вычислений, отчасти в контексте баз данных) или представляют собой 
сборники статей по логическим СУБД. Работы [В.10-В.12] являются учебными 
пособиями, как и [В.46, В.47], а [В.14, В.17-В.20, В.ЗО, В.49, В.50] посвящены 
операции транзитивного замыкания и ее применению. В [В.21-В.24] описана важная 
методика выполнения рекурсивного запроса — "магические множества", а также ее 
варианты. Остальные публикации демонстрируют масштабность исследований, 
которые ведутся в этой области. Они описывают дополнительные аспекты этой темы 
и в основном представлены без комментариев. 
    B.I. Stoll R.R. Sets, Logic and Axiomatic Theories. — San Francisco, 
Calif: W.H. Freeman and Company, 1961. 
    Представляет собой весьма неплохое введение в логику. 
    В.2. Manna Z., Waldinger R. The Logical Basis for Computer Programming. 
Vol. I. Deductive Reasoning (1985); Vol. II. Deductive Techniques (1990). — 
Reading, Mass.: Addison-Wesley, 1985-1990. 
    B.3. Gray P.M.D. Logic, Algebra and Databases. — Chichester, England: 
Ellis HorwoodLtd., 1984. 
    Книга является прекрасным введением в исчисление высказываний и исчисление 
предикатов с точки зрения базы данных, в ней также изложены другие темы, 
имеющие непосредственное отношение к данной. 
    8.4. Walker A., McCord M., Sowa J.F., Wilson W.G. Knowledge Systems and 
Prolog (2nd ed.). — Reading, Mass.: Addison-Wesley, 1990. 
    Хотя книга и посвящена логическому программированию в целом, в ней 
достаточно материала, касающегося логических СУБД в частности. 
    8.5. Gallaire H., Minker J. Logic and Data Bases.— New York, N.Y.: Plenum 
Publishing Corp., 1978. 
    Один из первых (если не самый первый) сборников статей по данной теме. 
    8.6. Kershberg L. (ed.). Expert Database Systems // Proc. 1st Intern. 
Workshop on Expert Database Systems (Kiawah Island, S.C.). — Menlo Park, 
Calif: Benjamin/Cummings, 1986. 
    Прекрасный сборник статей, располагающих к размышлениям. Однако не все из 
них непосредственно связаны с темой данного приложения. 
    8.7. Minker J. (ed.). Foundations of Deductive Databases and Logic 
Programming. — San Mateo, Calif: Morgan Kaufmann, 1988. 
    B.8. Mylopoulos J., Brodie M.L. (eds). Readings in Artificial Intelligence 
and Databases. — San Mateo, Calif: Morgan Kaufmann, 1988. 
    B.9. Ullman J.D. Database and Knowledge-Base Systems. В 2-х т. — 
Rockville, Md: Computer Science Press, 1988-1989. 
    Одна из десяти глав первого тома целиком посвящена логическим методам. В 
этой большой по объему главе (в которой впервые был представлен язык Datalog) 
обсуждается связь между логической и реляционной алгеброй, а также реляционное 
исчисление в виде особого случая логического подхода — версии как для доменов, 
так и для кортежей. Второй том состоит из семи глав, пять из которых посвящены 
различным аспектам логических СУБД. 

    Приложение В, Логические системы управления базами данных	759 

    В.10. Gardarin G., Valduriez P. Relational Databases and Knowledge Bases.— 
Reading, Mass.: Addison-Wesley, 1989. 
    В книге есть глава, посвященная дедуктивным системам, которая (несмотря на 
вводный характер изложения) содержит сведения о теории таких систем, об 
алгоритмах оптимизации и т.д. в гораздо большем объеме, чем данное приложение. 
    В. 11, Stonebraker M. Introduction to "Integration of Knowledge and Data 
Management" // M. Stonebraker (ed.). Readings in Database Systems. — San 
Mateo, Calif.: Morgan Kaufrnann, 1988. 
    B.12. Gallaire H., Minker J., Nicolas J.-M. Logic and Databases: A 
Deductive Approach // ACM Сотр. Surv. — 1984. — 16, № 2. 
    B.13. Dahl V. On Database Systems Development through Logic // ACM TODS.— 
1982. —7, № 1. 
    Хорошее и ясное описание идей, лежащих в основе логических СУБД, с 
примерами, созданными автором на базе языка Prolog в 1977. 
    В. 14. Agrawal R. Alpha: An Extension of Relational Algebra to Express a 
Class of Recursive Queries // IEEE Trans. on Software Engineering. — 1988. — 
14, № 7. 
    Здесь предлагается новый оператор alpha, с помощью которого в рамках 
традиционной реляционной алгебры поддерживается формулировка "большого класса 
рекурсивных запросов" (в действительности множество линейных рекурсивных 
запросов). (Хотя это верно только в некоторой степени, поскольку данный 
оператор действительно приводит к отношению не в 1НФ. Один из атрибутов 
полученного отношения является, в свою очередь, отношением. Затем для таких 
ненормализованных отношений накладываются ограничения на характер 
использования результата.) Существует мнение, что оператор alpha достаточно 
мощный для решения многих практических проблем, включая рекурсию, и более 
легкий в применении по сравнению с другими общими механизмами рекурсии. В 
книге приводится несколько примеров использования этого оператора. 
    Кроме того, материал по этой теме содержится также в [В. 18, В. 19]. 
    В. 15. Reiter R. Towards a Logical Reconstruction of Relational Database 
Theory // On Conceptual Modelling: Perspectives from Artificial Intelligence, 
Databases, and Programming Languages (eds. M.L. Brodie, J. Mylopoulos, J.W. 
Schmidt). — New York, N.Y.: Springer-Verlag, 1984. 
    Как уже отмечалось, хотя работа Рейтера и является первоисточником в этой 
области, многие исследователи до него изучали связь между логикой и базами 
данных (см., например, [В.5, В.7, В. 13]). Однако, по всей вероятности, именно 
"логическая реконструкция реляционной теории" значительно повысила интерес и 
побудила к активным исследованиям в этой области. 
    В. 16. Bancilhon F., Ramakrishnan R. An Amateur's Introduction to 
Recursive Query Processing Strategies // Proc. 1986 ACM SIGMOD Intern. Conf. 
on Management of Data. — Washington, D.C., 1986. (В переработанном виде 
опубликована в сборнике M. Stonebraker (ed.). Readings in Database Systems. — 
San Mateo, Calif.: Morgan Kaufrnann, 1988; а также в [В.8].) 
    Прекрасный обзор положительных и отрицательных сторон методов решения 
проблемы воплощения рекурсивного запроса. Положительно оценивается наличие 
множества технологий, разработанных для решения этой проблемы, а отрицательно 
— трудности выбора технологии, наиболее подходящей для конкретной ситуации (в 
частности, многие технологии представлены без описания характеристик 
производительности). После описания

    760	Приложения 

основных идей логических баз данных в статье предлагается множество 
алгоритмов. Сравниваются различные подходы на основе домена приложения (т.е. 
класса проблем, для которых применяется данный алгоритм), производительности и 
легкости их воплощения. В статье также приводятся цифры производительности (со 
сравнительным анализом), полученные в результате тестирования различных 
алгоритмов на основе простого теста. 
    В.17. loannidis Y.E. On the Computation of the Transitive Closure of 
Relational Operators // Proc. 12th Intern. Conf. on Very Large Data Bases. — 
Kyoto, Japan, 1986. 
    Транзитивное замыкание является операцией фундаментального значения при 
обработке рекурсивного запроса [В. 18]. В статье предлагается новый алгоритм 
воплощения этой операции (основанный на подходе типа "разделяй и властвуй"). 
Об этом также речь идет в работах [В. 14, В.18-В.20, В.49, В.50]. 
    В. 18. Jagadish H.V., Agrawal R., Ness L. A Study of Transitive Closure as 
a Recursion Mechanism // Proc. 1987 ACM SIGMOD Intern. Conf. on Management of 
Data. — San Francisco, Calif., 1987. 
    Немного переработанная цитата из аннотации: "В этой статье показано, что 
каждый линейный рекурсивный запрос может быть выражен в виде транзитивного 
замыкания, которое начинается и завершается операциями, уже существующими в 
реляционной алгебре". В статье также делается предположение, что для 
эффективного воплощения линейной рекурсии в общем случае, а значит, и для 
создания эффективных дедуктивных СУБД для большого класса рекурсивных проблем 
достаточно обеспечить эффективное воплощение транзитивного замыкания. 
    8.19. Agrawal R., Jagadish H. Direct Algorithms for Computing the 
Transitive Closure of Database Relations // Proc 13th Intern. Conf. on Very 
Large Data Bases.— Brighton, England, 1987. 
    Предлагается набор алгоритмов для транзитивного замыкания. Статья также 
содержит полезное резюме предыдущих работ о других алгоритмах. 
    8.20. Lu H. New Strategies for Computing the Transitive Closure of a 
Database Relation // Ibid. 
    Приводится описание некоторых других алгоритмов транзитивного замыкания. 
Так же, как и [В.19], эта статья содержит полезный обзор разработанных ранее 
подходов к этой проблеме. 
    8.21. Bancilhon F., Maier D., Sagiv Y., Ullman J.D. Magic Sets and Other 
Strange Ways to Implement Logic Programs // Proc. 5th ACM SIGMOD-SIGFACT 
Symposium on Principles of Database Systems, 1986. 
    Основная идея "магических множеств" заключается в динамичном введении 
нового набора "магических" правил, которые гарантируют получение того же 
результата, что и оригинальный запрос, но гораздо эффективнее за счет 
сокращения числа "соответствующих фактов". Изложение подробностей несколько 
сложно для восприятия и выходит за рамки данного комментария. Читателю 
предлагается прочесть эту статью или обратиться к работам [В.9, В. 10, В. 16] 
для получения более подробных сведений. Однако следует отметить, что 
существуют также многочисленные варианты этой основной идеи [В.22-В.24]. 
    Кроме того, следует также учесть работу [18.22] из главы 18. 

    Приложение В. Логические системы управления базами данных	761 

    В.22. Beeri С., Ramakrishnan R. On the Power of Magic // Proc. 6th ACM 
SIGMOD-SIGFACT Symposium on Principles of Database Systems, 1987. 
    B.23. Sacca D., Zaniolo C. Magic Counting Methods // Proc, 1987 ACM SIGMOD 
Intern. Conf. on Management of Data. — San Francisco, Calif, 1987. 
    B.24, Gardarin G. Magic Functions: A Technique to Optimize Extended 
Datalog Recursive Programs // Proc. 13th Intern. Conf. on Very Large Data 
Bases.— Brighton, England, 1987. 
    B.25. Aho A., Ullman J.D. Universality of Data Retrieval Languages // 
Proc. 6th ACM Symposium on Principles of Programming Languages. — San Antonio, 
Texas, 1979. 
    Для данной последовательности отношений R, j(R), flflR)),... (где/— 
некоторая фиксированная функция) крайней точкой неизменчивости называется 
отношение R*, выведенное в соответствии со следующим алгоритмом наивного оценивания: 
    К* := Л ; do until R* stops growing ; 
    /* выполнять, пока Л* не достигнет "точки неизменчивости" */ 
    Я* := Я* UNION /{/?*) ; end ; 
    В этой статье описывается дополнение реляционной алгебры понятием "крайней 
точки неизменчивости". 
    8.26. Ullman J.D. Implementation of Logical Query Languages for Databases 
// ACM TODS.— 1985.—10, №3. 
    Описывается важный класс технологий воплощения возможных рекурсивных запросов. 
    8.27. Tsur S., Zaniolo С. LDL: A Logic-Based Data-Language // Proc. 12th 
Intern. Conf. on Very Large Data Bases. — Kyoto, Japan, 1986. 
    Язык LDL включает множества как примитивные объекты данных, отрицание 
(основанное на различиях множеств), операции определения данных и операции 
обновления (для определений данных, базовых отношений и выведенных отношений). 
Это язык логического типа, причем компилируемый, а не интерпретируемый. 
    Материал по этой теме можно также найти в [В .45]. 
    8.28. Bancilhon F. Naive Evaluation of Recursive Defined Relations // M. 
Brodie and J. Mylopoulos (eds): On Knowledge Base Management Systems: 
Integrating Database and AI Systems. — New York, N.Y.: Springer-Verlag, 1986. 
    B.29. Lozinskii E.L. A Problem-Oriented Inferential Database System // ACM 
TODS.— 1986. — 11, №3. 
    В статье описывается прототип системы, в которой применяется 
экстенсиональная база данных для компенсации очень быстрого расширения 
поискового пространства вследствие использования инференциальных технологий. 
    В.ЗО, Rosenthal A. et al. Traversal Recursion: A Practical Approach to 
Supporting Recursive Applications // Proc. 1986 ACM SIGMOD Intern. Conf. on 
Management of Data. — Washington, D.C., 1986. 
    B.31, Gardarin G., De Maindreville C. Evaluation of Database Recursive 
Logic Programs as Recurrent Function Series // Ibid. 
    B.32, Raschid L,, Su S.Y.W. A Parallel Processing Strategy for Evaluating 
Recursive Queries // Proc. 12th Intern. Conf. on Very Large Data Bases — 
Kyoto, Japan, 1986. 

    762	Приложения 

    В.ЗЗ. Spyratos N. The Partition Model: A Deductive Database Model // ACM 
TODS.—1987.— 12, № 1. 
    B.34. Han J., Henschen L.J. Handling Redundancy in the Processing of 
Recursive Queries // Proc. 1987 ACM SIGMOD Intern. Conf. on Management of 
Data. — San Francisco, Calif, 1987. 
    B.35. Zhang W., Yu C.T. A Necessary Condition for a Double Recursive Rule 
to be Equivalent to a Linear Recursive Rule // Ibid. 
    B.36. Nejdl W. Recursive Strategies for Answering Recursive Queries — The 
RQA/FQI Strategy // Proc. 13th Intern. Conf. on Very Large Data Bases.— 
Brighton, England, 1987. 
    B.37. Whang K.-Y., Navathe S.B. An Extended Disjunctive Normal Form 
Approach for Optimizing Recursive Logic Queries in Loosely Coupled 
Environments // Ibid. 
    B.38. Naughton J.F. Compiling Separable Recursions // Proc. 1988 ACM 
SIGMOD Intern. Conf. on Management of Data. — Chicago, 111., 1988. 
    B.39. Youn C., Henschen L.J., Han J. Classification of Recursive Formulas 
in Deductive Databases // Ibid. 
    B.40. Ceri S., Gottlob G., Lavazza L. Translation and Optimization of 
Logic Queries: The Algebraic Approach // Proc. 12th Intern. Conf. on Very 
Large Data Bases. — Kyoto, Japan, 1986. 
    B.41. Ceri S., Tanca L. Optimization of Systems of Algebraic Equations for 
Evaluating Datalog Queries // Proc. 13th Intern. Conf. on Very Large Data 
Bases.— Brighton, England, 1987. 
    B.42. Van Gelder A. A Message Passing Framework for Logical Query 
Evaluation // Proc. 1986 ACM SIGMOD Intern. Conf. on Management of Data.— 
Washington, D.C., 1986. 
    B.43. Wolfson O., Silberschatz A. Distributed Processing of Logic Programs 
// Proc. 1988 ACM SIGMOD Intern. Conf. on Management of Data. — Chicago, 111., 1988. 
    B.44. Naughton J.F. et al. Efficient Evaluation of Right-, Left-, and 
Multi-Linear Rules // Proc. 1989 ACM SIGMOD Intern. Conf. on Management of 
Data. — Portland, Ore., 1989. 
    B.45. Naqvi S., Tsur S. A Logical Language for Data and Knowledge Bases. — 
New York., N.Y.: Computer Science Press, 1989. Эта книга полностью посвящена 
описанию языка LDL [В.27]. 
    В.46. Ceri S., Gottlob G., Tanca L. Logic Programming and Databases — New York, 
    N.Y.: Springer-Verlag, 1990. B.47. Das S.K. Deductive Databases and Logic 
Programming. — Reading, Mass.: 
    Addison-Wesley, 1992. 
    B.48. Kifer M., Lozinskii E. On Compile-Time Query Optimization in 
Deductive Databases by Means of Static Filtering // ACM TODS. — 1990. — 15, № 3. 
    B.49. Agrawal R., Dar S., and Jagadish H.V. Direct Transitive Closure 
Algorithms: Design and Performance Evaluation // Ibid. 
    B.50. Jagadish H.V. A Compression Method to Materialize Transitive Closure 
// Ibid. — № 4. 
    Предлагается технология индексирования, которая позволяет сохранять 
транзитивное замыкание данного отношения в сжатой форме таким образом, чтобы 
можно было выполнить тестирование и узнать с помощью одной справочной таблицы 
с индексом, будет ли в замыкании находиться данный кортеж. 

    Приложение В. Логические системы управления базами данных	763 

    В.51, Abiteboul S., Grumbach S. A Rule-Based Language with Functions and 
Sets // ACM TODS, — 1991. — 16, № 1. 
    Описывается "язык комплексных объектов" ("complex object language" — COL), 
который является расширением языка Catalog с интеграцией идеи дедуктивных и 
объектно-ориентированных баз данных. 
    Ответы к некоторым упражнениям 
    8.1. а) Истинно; б) истинно; в) — ложно. 
    8.2. В приведенных ниже записях a, b и с являются константами Сколема, а/— 
функцией Сколема. 
    а) р ( х,	у }	=> q ( x,	f (  х,  у )   ) 
    б) р (  а,	Ь )	=> q {  a,	z ) 
    B) р  (  а,	Ь )	=> q (  а,	с ) 
    В.6. В соответствии с принятой формой перечисленные ниже решения 
обозначаются как В.б.п, где п — номер оригинального упражнения в главе 6, 
    8.6.13. ? <= J ( j, jn, jc ) 
    8.6.14. ? с.- j ( j, jn, London ) 
    B.6.15, RES ( s ) <^ SPJ ( s, р, Jl ) 
    ? <= RES ( s ) 
    B.6.16. ? <= SPJ ( s, p, j, q ) AND 300 < q AND q < 750 
    B.6.17, RES ( pi, pc ) <= P ( p, pn, pi, w, pc ) 
    ? <=--- RES ( pi, pc ) 
    B.6,18. RES ( s, p, j ) <= S ( s, sn, st, с ) AND 
    P ( p, pn, pi, w, с ) AND J ( j, jn, с ) ? ст RES ( s, p, 7 ) 
    B.6.19, B.6,20. He может быть выполнено без отрицания. 
    В.6.21. RES ( р ) <= SPJ ( s, p, j, q ) AND S ( s, sn, st, London ) ? <= RES ( p ) 
    B.6.22. RES ( p ) <= SPJ { s, p, j, q ) AND 
    S ( s, sn, st, London ) AND J ( j, jn, London ) ? <= RES ( p ) 
    B.6,23. RES ( cl, c2 ) <= SPJ ( s, p, j, q ) AND 
    S ( s, sn, st, cl ) AND J ( j, jn, c2 ) ? <= RES ( cl, c?. ) 
    B.6.24. RES ( p ) <= SPJ ( s, p, j, q ) AND 
    S ( s, sn, st, с ) AND J ( j, jn, с ) ? Cr RES ( p ) 
    B.6.25. He может быть выполнено без отрицания. 
    В.6.26. RES   ( pi, р2 }   <= SPJ   (   s,  pi,   jl,   ql  )   AND 
    S   {   s,   p2,   J2,   q2 ) ? <= RES   (  pi,  p2 ) 
    B.6.27-B.6.30. He может быть выполнено без функций группировки и функций 
подведения итогов. 

    764	Приложения 

    B.6.31. RES ( jn ) <= J ( j, jn, jc ) AND 
    SPJ ( SI, p, j, g ) ? <= RES ( jn ) 
    B.6.32. RES ( pi ) <= P ( p, рл, pj, w, pc ) AND 
    SPJ ( SI, p, j, q ) 
    ? <= RES ( pi ) 
    B.6.33. RES ( p ) <= P ( p, рл, p-Z, w, pc ) АЮ SPJ ( s, p, j, q ) AND J ( 
7f -7Л< London ) ? <= RES ( p ) 
    B.6.34. RES ( j ) <= SPJ ( S, p, j, q ) AND 
    S ( SI, p, j-.?, g? ) ? <= RES ( j ) 
    B.6.35. RES ( s ) <= SPJ ( s, p, J, q ) AND 
    SPJ ( s2, p, J2, q2 ) AND SPJ ( s2, p2, J3, q3 ) AND P ( p2, рл, Red, w, с ) 
    ? <= RES ( s ) 
    B.6.36. RES ( s ) <= S ( s, sn, st, с ) AND 
    S ( SI, snl, stl, cl ) AND st < stl ? <= RES ( s ) 
    B.6.37-B.6.39. He может быть выполнено без функций группировки и функций 
подведения итогов. 
    В.6.40-В.6.44. Не может быть выполнено без отрицания. 
    В.6.45. RES ( с ) <= S ( s, sn, st, с ) 
    RES ( с ) t= P ( p, рл, pi, w, с ) RES ( с ) <= J ( j, jn, с ) ? <= RES ( 
с ) 
    B.6.46. RES ( p ) <= SPJ ( s, p, j, q ) AND 
    S ( s, sn, st, London ) RES { p ) <= SPJ ( s, p, j, q ) AND 
    J ( ji Jn/ London ) ? <= RES ( p ) 
    B.6.47, B.6.48. He может быть выполнено без отрицания. 

    Приложение В. Логические системы управления базами данных	765 

