Для удобства предполагается, что предикаты, соответствующие операщ1Ям = , > , > и т.д., - встроенные (т.е. являются частью данной формально определенной системы) и выражения, которые их включают, могут записываться обычным образом. Однако пользователи, безусловно, могут определять предикаты самостоятельно. Как известно из предыдущих глав, в терминах баз данных заданный пользователем предикат фактически представляет собой определенную пользователем переменную-отношение. Например, переменная-отношение поставщиков S может рассматриваться как предикат с четырьмя параметрами, а именно: SI, SNAME, STATUS, CITY. Более того, выражения типа S ( S1, Smith, 20, London) и S ( S6, White, 45, Rome) представляют собой экземпляры или вызовы такого предиката, который вычисляется в результате со значением соответственно истина или ложь (в контексте рассматриваемой здесь базы данньпс). Неформально говоря, такие предикаты (вместе с любыми ограничениями цечостности, которые также являются предикатами) можно рассматривать в качестве определения того, что подразумевает база данных, как уже объяснялось в предыдущих частях книги, в частности в главе 8.

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

Во избежание путаницы с термином формула из предыдущего раздела (термин, который фактически относится к частному случаю) будем употреблять термин правильно построенная формула (well-formed formula; произносится как вэфф ), определение которого было дано в главе 7. Ниже приведен упрощенный синтаксис WFF-формулы.

<wff> ::= <тери[>

NOT ( <\fff> ) ( <wff> ) AND ( <wff> ) ( <wff> ) OR ( <wff> ) ( <wff> ) => ( <wff> ) EXISTS <имя переменной> ( <wff> ) FORALL <имя переменной> ( <wft> )

<терМ> ::= [ NOT ] <имя предиката> [ ( <список аргументов> ) ] Отметим некоторые особенности этого синтаксиса.

1. Под словом терм подразумевается просто экземпляр предиката, который может быть отрицаемым. Если рассматривать предикат как логическую функцию, то экземпляр предиката - вызов такой функции. Каждый аргумент в параметре <список аргументов> должен быть константой, именем переменной или обращением к функции, а каждый аргумент функции, в свою очередь, - константой, именем переменной или обращением к функции. Для нуль-местного предиката параметр <список аргументов> и окружающие его скобки опускаются.

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

2. Как и в разделе 23.3, для сокращения числа необходимых скобок здесь применяется обычный приоритет выполнения операций (NOT, затем AND, затем OR, затем =>).

3. Кванторы EXISTS и FORALL уже описывались в этой книге.

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

4. Законы Де Моргана можно обобщить на случай использования квантификации WFF-формул следующим образом.

NOT ( FORALL х ( f ) ) = EXISTS х ( NOT ( f ) ) NOT ( EXISTS X ( f ) ) = FORALL x ( NOT ( f ) )

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

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

6. Закрытая WFF-формула не содержит ни одной свободной переменной. В противном случае она называется открытой WFF-формулой.

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

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

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

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

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

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

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

2 > 1 : истинно

2 > 3 . ложно

EXISTS X { X > 2 ) : истинно

FORALL X ( X > 2 ) : ложно

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

уничтожить перед прочтением (уровень 5) уничтожить после прочтения (уровень 4)

совершенно секретно (уровень 3)

секретно (уровень 2)

для служебного пользования (уровень 1)

несекретно (уровень 0)

В этом случае предикат > будет означать более секретно, чем (т.е. более высокий уровень безопасности).

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

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

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

X > 3

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

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

2 > 1 2 > 3

EXISTS X ( X > 2 ) FORALL X ( X > 2 )

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

2 > 1

3 > 2

EXISTS X ( X > 2 )

FORALL X ( X > 2 OR NOT ( X > 2 ) )