l.MOTHER OF( Anne, Betty ) 2. MOTHER OF( Betty, Celia )

3.N0T MOTHER OF( x, у ) OR NOT MOTHER OF( y, z ) OR

GRANDMOTHER OF( x, Z )

Дополним его четвертой предпосылкой.

4. NOT GRANDMOTHER OF( Anne, г ) OR RESULT( г )

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

Сначала подставим значение Anne вместо х и г вместо z. Совместив строки в пп. 4 и 3, получим следующий результат.

5. NOT MOTHER OF( Anne, у ) OR NOT MOTHER OF( у, z ) OR RESULT( z )

Подставив значение Betty вместо у и совместив строки в пп. 5 и 1, получим следующее.

6. NOT MOTHER OF( Betty, z ) OR RESULT( z )

Наконец подставив значение Celia вместо z и совместив строки в пп. 6 и 2, получим такой результат.

7. RESULT( Celia )

Следовательно, Анна является бабушкой Селии.

Замечание. Рассмотрим случай, когда задан дополнительный терм, как, например, показано ниже.

MOTHER OF ( Betty, Delia )

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

RESULT ( Delia )

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

23.5. Базы данных с точки зрения

доказательно-теоретического подхода

Как говорилось в разделе 23.4, предложением является выражение следующего вида. А1 AND А2 AND ... AND Алг => Bi OR В2 OR ... OR Bn

Здесь все A и В являются термами указанного ниже вида, где г- предикат, а х1, х2, xt - его аргументы.

г { х1, х2, xt ), 914 Часть V. Дополнительные аспекты

в соответствии с [23.12] рассмотрим несколько важных типов этой общей конструкции.

Случай /. m = О, п = 1.

В данном случае предложение может быть сведено к следующему простому виду. => В1

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

г ( х1, х2, xt)

Если все аргументы являются константами, то предложение представляет собой основную аксиому, т.е. утверждение, которое однозначно является истинным. В терминах базы данных такое утверждение соответствует кортежу некоторой переменной-отношения ??. Как неоднократно отмечалось в этой книге, предикат г соответствует смысловому значению переменной-отношения R. Например, в базе данных поставщиков и деталей существует отношение SP, которое означает, что заданный поставщик (Sl) поставляет указанную деталь (Р) в определенном количестве (QTY). Обратите внимание, что это значение соответствует открытой WFF-формуле, так как содержит несколько свободных переменных (Si, Pi и QTY). И наоборот, кортеж (S1, Р1, 300), в котором все аргументы являются константами, представляет собой основную аксиому, или закрытую WFF-формулу, которая однозначно утверждает, что поставщик с номером S1 поставляет деталь с номером Р1 в количестве 300.

Случай 2. т > О, п = 1.

В этом случае предложение принимает вид А1 AND А2 AND ... AND Алг => В

и может рассматриваться как дедуктивная аксиома. Она дает, возможно, неполное определение предиката справа от знака следования в терминах, которые представлены слева (см. в качестве примера определение предиката GRANDMOTHER OF).

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

S ( S, cl ) Шд S ( S, с2 ) = cl = с2

Здесь следует обратить внимание на использование встроенного предиката = .

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

Или значению в некоторо.м до.мене.

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

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

Переменные-отношения (точнее, их заголовки) представляют набор предикатов, или открытых WFF-формул, которые должны быть интерпретированы в этом пространстве. Например, заголовок переменной-отношения SP представляет предикат Поставщик Si поставляет деталь Р в количестве QTY .

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

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

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

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

Для того чтобы применить правила вывода, описанные в разделах 23.3 и 23.4, необходимо использовать новую точку зрения, в соответствии с которой база данных явным образом рассматривается как некая логическая теория, т.е. как набор аксиом. Смыс-

Однако если предположить, что в базе данных не содержится явным образом никакой отрицаемой информации (например, утверждения наподобие NOT Si( } , где S9 не является номером поставщика), то возможно существование минимального или канонического значения, которое является пересечением всех возможных моделей [23.10]. Более того, как уже отмечалось, в данном случае это каноническое значение будет таким же, как и значение, которое приписывается базе данных доказательно-теоретическим представлением.