Главная » SQL, Базы данных » ИСЧИСЛЕНИЕ ПРЕДИКАТОВ

0

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

Предикаты

Как было описано в главе 3, предикат представляет собой логическую функцию, т.е. функцию, которая после постановки соответствующих фактических параметров вместо формальных параметров возвращает либо TRUE, либо FALSE. Например, функция "> (х, у) " (которая чаще всего записывается как "х > у") представляет собой предикат с двумя формальными параметрами, х и у; она возвращает TRUE, если ее фактический

4  Точнее, имена переменных. Рассматриваемые переменные являются логическими  переменными, а не переменными языка программирования. Их можно рассматривать как переменные области значений в том смысле, который указан в главе 8.

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

Примем удобное предположение, что предикаты, соответствующие операторам  "=", ">", ">" и т.д., являются встроенными (т.е. что они входят в состав описываемой нами формальной системы) и что выражения, в которых они используются, разрешено записывать в общепринятой форме. Но, безусловно, пользователям должна быть также предоставлена возможность определять свои собственные предикаты. И действительно, весь смысл рассматриваемого нами подхода состоит в следующем: дело в том, что в терминах баз данных определяемый пользователем предикат соответствует определяемой пользователем переменной отношения (как уже было указано в предыдущих главах). Например, переменная отношения поставщиков S может рассматриваться как предикат с четырьмя формальными параметрами, S#, SNAME, STATUS И  CITY.  Более того, выражения S(S1, Smith, 20, London) и S ( S 6 , White, 45, Rome),  сформулированные с использованием наглядного сокращенного обозначения, представляют собой экземпляры, варианты конкретизации или вызовы этого  предиката, которые (при использовании обычно принятого в качестве примера множества значений) принимают значения, соответственно, TRUE и FALSE. Неформально такие предикаты (наряду со всеми применимыми ограничениями целостности, которые также являются предикатами) могут рассматриваться как определение того, что "означает" эта база данных, как было описано в предыдущих частях данной книги (особенно в главе 9).

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

Следующий этап состоит в том, что можно расширить определение понятия формулы. Для того чтобы избежать путаницы с формулами, рассматриваемыми в предыдущем разделе (которые фактически представляют собой частный случай), перейдем к использованию термина правильно построенная формула (Well-Formed Formula — WFF, произносится как "вэфф"), или сокращенно ППФ, который был определен в главе 8. Ниже приведен упрощенный синтаксис правильно построенных формул.

<wff>

::<term>

| NOT ( <wff> )

| ( <wff> ) AND ( <wff> )

j ( <wff> ) OR ( <wff> )

| ( <wff> ) ⇒  ( <wff> )

| EXISTS <var name> ( <wff> )

I FORALL <var name> (

<wff> )

<term>

::= [ NOT ] <pred name> [ ( <argument commalist> ) ]

Из этого определения следуют приведенные ниже выводы.

1.           В качестве терма <term> применяется просто экземпляр предиката или, возмож но, его отрицание (если предикат рассматривается как логическая функция, то экземпляр предиката представляет собой вызов этой функции). Каждый фактиче ский параметр <argument> должен представлять собой константу, имя перемен ной или вызов функции, где каждый фактический параметр в вызове функции, в свою очередь, является константой, именем переменной или вызовом функции. Разделенный запятыми список фактических параметров <argument   commalist> и (при желании) соответствующие круглые скобки в случае нуль-местного преди ката исключаются.

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

2.           Как описано в разделе 24.3, применяются обычные правила приоритета для логи ческих операторов (NOT, затем AND, затем OR, затем ⇒ ) для того, чтобы можно бы

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

3.           Предполагается, что читатель знаком с кванторами EXISTS и FORALL.

Примечание. Здесь нас интересует только исчисление предикатов первого порядка, а это по существу означает, во-первых, что нет предикативных переменных (т.е. переменных, допустимыми значениями которых  являются  предикаты), и поэтому, во-вторых, сами предикаты не могут  становиться объектом применения кванторов. См. упражнение 8.8 из главы 8.

4.           Законы де Моргана могут быть обобщены применительно к правильно построен ным формулам, содержащим кванторы, следующим образом:

NOT ( FORALL X ( f ) ) ≡  EXISTS X ( NOT ( f ) )

NOT ( EXISTS X ( f ) ) ≡  FORALL X ( NOT ( f ) )

Эта тема также обсуждалась в главе 8.

5.           Повторим еще один фрагмент из главы 8: в любой конкретной правильно постро енной формуле каждая ссылка на переменную является либо свободной, либо свя занной. Ссылка является связанной тогда и только тогда, когда она, во-первых, находится непосредственно за ключевым словом EXISTS ИЛИ FORALL (т.е. обозна чает переменную, на которую распространяется действие квантора) или, вовторых, находится в области действия квантора и обозначает соответствующую квантифицированную переменную. Ссылка на переменную является свободной тогда и только тогда, когда она не связана.

6.           Закрытой правильно построенной формулой называется такая формула, которая не содержит ссылок на свободные переменные (фактически она является высказыва нием). Открытой правильно построенной формулой называется такая формула, ко торая не является замкнутой.

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

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

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

■     Во вторых, определим смысл каждого предиката в терминах объектов предметной области.

■     В-третьих, определим также смысл каждой функции в терминах объектов пред метной области.

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

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

2 > 1                                                                                   : TRUE

2 > 3                                             : FALSE EXISTS x ( х > 2 ) : TRUE FORALL X ( x > 2 ) : FALSE

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

уничтожить перед прочтением (уровень 5) уничтожить после прочтения  (уровень 4) совершенно секретно                                          (уровень 3) секретно                                                                                                                         (уровень 2) для служебного пользования  (уровень 1) несекретно                                                                                     (уровень 0)

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

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

по своему характеру. Например, можно снова взять в качестве предметной области целые числа от 0 до 5, но определить предикат ">" как обозначающий равенство. (Безусловно, это может стать причиной значительной путаницы, но, по крайней мере, мы имеем полное право принять подобное решение.) В таком случае  первая правильно построенная формула из списка ("2 > 1") будет иметь значение FALSE,,а не TRUE.

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

Кстати, следует отметить, что все правильно построенные формулы, которые  рассматривались до сих пор в этом подразделе, были замкнутыми ППФ. Причина этого состоит в том, что при наличии некоторой интерпретации  всегда возможно присвоить замкнутой ППФ конкретное истинностное значение, но истинностное значение открытой ППФ зависит от значений, присвоенных свободным переменным. Например, вполне очевидно, что приведенная ниже  открытая ППФ принимает значение TRUE, если х больше 3, и FALSE в противном случае (при любой трактовке понятий "больше чем" и "3" в данной интерпретации):

х > з

Теперь можно определить модель множества (обязательно замкнутых) правильно построенных формул как интерпретацию, при которой все ППФ в данном множестве принимают значение TRUE. Вторая из двух интерпретаций, которые были даны для четырех приведенных ниже ППФ в терминах целых чисел от 0 до 5, не была моделью для этих ППФ, поскольку некоторые из ППФ при этой интерпретации принимали значение

FALSE:

2   >   1

2   >  3

EXISTS   x   (   х   >   2   )

FORALL  x   (   х  >   2   )

В отличие от этого, первая интерпретация (в которой операция ">" была определена

"должным образом"), должна была быть моделью для следующего множества ППФ:

2 > 1

3 > 2

EXISTS х ( х > 2 )

FORALL x { х > 2 OR NOT ( x > 2 ) )

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

Клаузальная форма

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

Процесс преобразования осуществляется следующим образом (здесь он описан схематически; дополнительные сведения приведены в [24.6]). Этапы преобразования будут показаны на примере применения их к следующей ППФ:   ,

FORALL X ( р ( X ) AND EXISTS у ( FORALL z ( q ( у, z ) ) ) )

Здесь р и g — предикаты, а х, у и z — переменные.

1.  Удалить символы " ⇒ ", как показано в разделе 24.3. В данном примере этот пер

вый этап преобразования не требуется.

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

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

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

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

EXISTS  v  (  r  (  v   )   )

эквивалентна следующей правильно построенной формуле для некоторой  неизвестной константы а:

r   (   а   )

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

FORALL u ( EXISTS v ( s ( u, v ) ) )

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

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

Константа а и функция f в этих примерах известны, соответственно, под названием скулемовской константы и скулемовской функции,  которые названы в честь логика Т.А.Скулема (T.A.Skolem). {Примечание. Скулемовская константа в действительности   представляет   собой   просто   скулемовскую   функцию   без параметров.)   Поэтому   следующий   этап   состоит   в   устранении   кванторов существования путем

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

FORALL х ( FORALL z ( р ( X ) AND q ( f ( х ), 2 ) ) )

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

р   (   х   )   AND  q   (   f   (   X   ),    z   )

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

7.  Записать каждое выражение на отдельной строке и удалить операторы AND, сле дующим образом.

Р     (    X    )     q     (     f     (    X    ) ,     Z     )

Это и есть клаузальная форма, эквивалентная первоначальной правильно построенной формуле.

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

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

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

Al AND A2 AND . . . AND Am => Bl OR B2 OR … OR Bn

Если количество термов в не превышает одного (п = 0 или 1), такое выражение называют хорновским выражением в честь логика Альфреда Хорна (Alfred Horn).

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

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

1.         MOTHER_OF ( Anne, Betty )

2.         MOTHER_OF ( Betty, Celia )

Кроме того, дана приведенная ниже правильно построенная формула (дедуктивная аксиома).

3.          MOTHER_OF (X,у) AND MOTHER_OF (у,z) ⇒  GRANDMOTHER_OF (X,z) Обратите внимание на то, что это — хорновское выражение). Для того чтобы упростить применение правила резолюции, перепишем это  выражение для удаления

символа " ⇒ ", как показано ниже.

4.          NOT MOTHER_OF ( X, у ) OR NOT MOTHER_OF (у, z ) OR GRANDMOTHER_OF ( x, z )

Теперь мы можем перейти к доказательству того, что Анна — бабушка Селии. Таким образом, будет показано, как ответить на запрос: "Является ли Анна бабушкой Селии?" Начнем с отрицания того заключения, которое должно быть доказано, и принятия его в качестве дополнительной предпосылки, как показано ниже.

5.          NOT GRANDMOTHER_OF ( Anne, Celia )

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

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

Для того чтобы рассмотреть, как описанный выше процесс действует в данном конкретном случае, вначале следует отметить, что строки 4 и 5 содержат, соответственно, термы   GRANDMOTHER_OF   ( x , z )   И   NOT   GRANDMOTHER_OF   (Anne,Celia). Поэтому выполним подстановку в строке 4 значения "Anne" вместо х и "Celia" вместо z и применим правило резолюции для получения приведенного ниже выражения.

6.          NOT MOTHER_OF ( Anne, у ) OR NOT MOTHER_OF ( у, Celia )

Строка 2 содержит терм MOTHER_OF (Betty, Celia), поэтому можно выполнить подстановку значения "Betty" вместо у в строке 6 и применить правило резолюции для получения приведенного ниже выражения.

7.          NOT MOTHER_OF ( Anne, Betty )

Применив правило резолюции к строкам 7 и 1, получаем пустое множество выражений, [ ]. Это означает, что обнаружено противоречие. Поэтому ответ на первоначальный запрос состоит в следующем: "Да, Анна — бабушка Селии".

А теперь найдем ответ на запрос: "Кто является внучкой Анны?" Вначале отметим, что системе ничего не известно о внучках; она имеет информацию только о бабушках. Поэтому, чтобы выйти из положения, можно ввести еще  одну  дедуктивную аксиому, свидетельствующую о том, что z является внучкой х  тогда и только тогда, когда х — бабушка z (в этой базе данных нет информации о мужчинах). Еще один вариант состоит в том, что первоначальный вопрос может  быть перефразирован следующим образом: "Чьей бабушкой является Анна?" Рассмотрим последнюю формулировку. Применяемые предпосылки (еще раз) показаны ниже.

1.         MOTHER_OF ( Anne, Betty ) ,

2.         MOTHER_OF ( Betty, Celia )

3.         NOT MOTHER_OF ( X, у ) OR NOT MOTHER_OF ( y, z ) OR GRANDMOTHER_OF ( x, z )

Введем четвертую предпосылку, как показано ниже.

4.         NOT GRANDMOTHER_OF ( Anne, r ) OR RESULT ( r )

На интуитивном уровне ясно, что в этой новой предпосылке содержится  утверждение, что либо Анна не является бабушкой кого-либо, либо существует некоторое лицо r, данные о котором входят в состав желаемого результата (поскольку Анна является бабушкой этого лица r). Нам требуется определить имена всех таких  лиц  r.  Дальнейшие  действия  выполняются  следующим  образом.  Вначале выполним  подстановку  значения  "Anne"  вместо  х  и  переменной  r  вместо  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 )

то на последнем этапе (вместо значения "Celia") можно было бы подставить в качестве z значение "Delia" и получить следующий результат.

RESULT ( Delia )

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

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

По теме:

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