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

ЧШ GRANDMOTHER OF VIEW

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

Здесь умышленно используется стиль реляционного исчисления. MX и MY - переменные кортежа, которые изменяются на переменной-отношении MOTHER OF. Запросы такого типа могут быть оформлены на основе следующего представления.

GX.GRANDMOTHER WHERE GX.GRANDDAUGHTER = NAME ( Celia ) GX.GRANDDAUGHTER WHERE GX.GRANDMOTHER = NAME ( Anne )

Здесь GX - переменная кортежа, изменяющаяся на переменной-отношении GRANDMOTHER OF.

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

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

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

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

Дистрибутивные законы

f AND ( g OR h ) = ( f AND g ) OR ( f AND h ) f OR ( g AND h ) = ( f OR g ) AND ( f OR h )

Законы Де Моргана

NOT ( f AND g ) = NOT f OR NOT g NOT ( f OR g ) = NOT f AND NOT g Здесь f, g и h - произвольные булевы выражения.

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

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

Термы

Предположим для начала, что имеется набор объектов, называемых константами, о которых делаются различного рода утверждения (или заключения). Согласно языку, принятому в области баз данных, эти константы являются значениями из основных доменов, г. утверждением может быть, например, такое условное выражение, как 3 > 2 . Тогда термом мы будем называть утверждение, которое содержит такие константы и обладает следующими свойствами.

1. Утверждения либо не содержат логических связок (подробности приводятся ниже), либо заключены в скобки.

2. Утверждения однозначно оцениваются либо как истинные, либо как ложные.

Например, утверждения Поставщик с номером S1 находится в городе London , Поставщик с номером S2 находится в городе London и Поставщик с номером S1 поставляет деталь с номером Р1 являются термами (в рассматриваемом примере они оцениваются соответственно как истинное, ложное и истинное). И наоборот, утверждения Поставщик с номером S1 поставляет некоторую деталь с номером р , где р- переменная, и Поставщик с номером S5 когда-нибудь в будущем будет поставлять деталь с номером Р1 не являются термами, поскольку их нельзя однозначно оценить как истинные шш ложные.

Формулы

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

<Формула>

::= <терМ>

NOT <терМ>

<тери[> AND <формула> <терМ> OR <формула> <терьс> => <формула> <терм>

::= <атомарная формула> I ( <формула> )

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

1. Параметр <атомарная формула>- это логическое выражение, которое не содержит связок и не заключено в скобки.

2. Символом => обозначается связка типа логической импликации. По определению выражение f => g логически эквивалентно выражению NOT f OR g.

Замечание. В главе 7 и других главах для этой связки использовалась конструкция IF ... THEN

3. К связкам применяются обычные правила приоритета выполнения (NOT, затем AND, затем OR, затем =>), что позволяет избежать многократного использования скобок.

4. Высказывание - это просто элемент типа <формула>, как он определен выше. Термин формула употребляется просто для согласования с материалом следую-шего раздела.

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

Правила вывода для исчисления высказываний имеют следующий вид. h f => g

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

1. [= ( f AND gr ) => f

2. 1= f => ( f OR gr )

3. f=( (f=>gr)AND(gr= i3) )=>(=>Л)

4. [= ( f AND ( f => gr ) ) => gr

Замечание. Это чрезвычайно важное правило называется правило.м отделения (modus ponens). Неформально оно интерпретируется так: если f истинно и из f следует д, то д также должно быть истинны.м. Допустим, например, что каждый из приведенных ниже фактов является истинным.

а) У меня нет денег.

б) Если у меня нет денег, я должен мыть посуду.

Исходя из этих фактов можно заключить, что истинны.м является и следующий факт.

в) Я должен мыть посуду. Вот еще примеры правил вывода.

5. =(/=>(дг=>Л) )=>( (fANDgr)=>A)

6. [= ( ( f OR gr ) AND ( NOT gr OR Л ) ) => ( f OR Л )

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