Введение в системы БД (542480), страница 239
Текст из файла (страница 239)
Следует указать еще одну особенность, упомянутую в главе 7. Внутри некоторой %ГГ-формулы каждый экземпляр переменной является либо свободным, либо связанным. Переменная называется связанной, если сразу же за ней следует квантор (указывающий кваплщфиляруечую перечеляую) или если она находится в пределах квантора и обозначает соответствующую кваитифицируемую переменную. В противном случае переменная называется свободной. 6. Закрытая ЪУГГ-формула не содержит ни одной свободной переменной. В противном случае она называется открытой %ГГ-формулой. Интерпретации и модели Для того чтобы понять, чщо такое %ГГ-формула, следует ввести понятие интерпретации.
Интерпретация ФГГ-формулы или (в более общем смысле) набора %ГГ-формул определяется следующим образом. 2 > 1 2 > З ЕХ1БтБ х ( х > 2 ) ГОЕАЬЬ х ( х > 2 ) : истинно : ложно : истинно ложно 909 Глава 23. Логичвгкив сиапемыуправления базами данных ° Во-первых, необходимо опрелелить пространство рассуждений, на котором будут интерпретироваться %ГГ-формулы. Иначе говоря, следует задать отображение между допустимыми константами формальной системы (в терминах базы данных это доменные значения) и объектами "реального мира*'.
Каждая отдельная константа соответствует ровно одному объекту пространства рассуждений. ° Во-вторых, нужно запать значение для каждого предиката на основе объектов в пространстве рассуждений. ° В-третьих, следует также задать значение для каждой функции на основе объектов в пространстве рассуждений. Таким образом, интерпретация включает комбинацию пространства рассуждений, отображений отдельных констант на объекты этого пространства и заданных значений для предикатов и функций по отношению к этому пространству. Допустим, что пространством рассуждений является набор целых чисел (0,1,2,3,4,5); такие константы, как 2, соответствуют элементам этого пространства очевидным образом, а предикат х>у задан с тралиционным для данного символа значением.(Можно было бы определить и такие функции, как "+", "-" и т.д.) Теперь зададим истинностные значения для, например, таких %ГГ-формул.
Следует отметить, что возможны также другие интерпретации. Например, можно задать пространство рассуждений в виде классификации уровней безопасности. уничтожить перед прочтением (уровень 5) уничтожить после прочтения (уровень 4) совершенно секретно (уровень 3) секретно (уровень 2) для служебного пользования (уровень 1) несекретно (уровень 0) В этом случае предикат ">" будет означать "более секретно, чем" (т.е. более высокий уровень безопасности). Теперь ясно, что эти две интерпретации изамарфны, т.е.
между ними можно задать взаимно однозначное соответствие, а значит, по большому счету эти две интерпретации одинаковы. Однако следует четко понимать, что могут существовать совершенно разные интерпретации. Например, можно определить такое же пространство рассуждений иа основе целых чисел от О до 5, но задать предикат ">" со значением равно. (Зто вполне возможно осуществить, хотя на практике может возникнуть путаница.) В таком случае первое значение 5УГГ-формулы в приведенном выше перечне будет лажны.м, а не истинным. Другой важной особенностью является возможность совпадения истинностных значений 5УГГ-формул для совершенно разных интерпретаций.
В рассматриваемом примере такая ситуация возможна, если предикат ">" определен по-разному, а значение 5УГГ- формулы 2>1 опущено. Следует заметить, что все упомянутые выше в этом подразделе предикаты являются закрытыми %ГГ-формулами. Дело в том, что для данной интерпретации всегда можно задать однозначное логическое значение для закрытой %ГГ-формулы, но логическое значение открытой 5УГГ-формулы будет зависеть от значений, присвоенных свободным переменным.
Например, рассмотрим следующую открытую %ГГ-формулу. х> 3 Она будет (очевидно) истинной, если значение х больше, чем 3, и ложной в противном случае (при любых значениях "больше" и "3'* в интерпретации). Модель |АТГ-формулы илн, в более общем смысле, набора (закрытых) 5УГГ-формул является такой интерпретацией, лля которой все функции набора ФГГ-формул истинны. Рассмотрим в свете двух приведенных выше интерпретаций четыре следующие 5УГГ-формульь 2>1 2>3 ЕХ1БТБх( х> 2 ) ЕОЕЛЕЕ х ( х > г ) Указанные интерпретации в терминах целых чисел от О до 5 не являются моделями данных %ГГ-формул, потому что в каждом случае некоторые 5УГГ-формулы принимают ложные значения.
И наоборот, первая интерпретация (в которой предикат ">" определен "правильным" образом).иаева бы быть моделью набора следующих %ГГ-формул. 2>1 3>2 ЕХ1БТБ х ( х > 2 ) ЕОЕАьЬ х ( х > 2 ОЕ НОТ ( х > 2 ) ) 910 Часть К Дополнительные аспекты Наконец, стоит отметить, что если заданный набор %ГГ-формул может допускать несколько интерпретаций, в которых эти %ГЕ-формулы принимают истинные значения, то он (в обшем случае) может иметь несколько моделей. Таким образом, база данных в общем случае может иметь несколько различных моделей, так как с модельнотеоретической точки зрения она является просто набором %ГГ-формул.
Подробности приводятся в разделе 23.5. Стандартная форма Так же, как любая формула в исчислении высказываний может быть конвертирована в конъюнктивную нормальную форму, %ГГ-формула в исчислении предикатов может быть конвертирована в стандартную форму, которая може~ рассматриваться в качестве расширенной версии конъюнктивной нормальной формы. Как показано ниже, одним из побудительных мотивов выполнения такого конвертирования является возможность применения правила резолюции при конструировании или проверке доказательств. Ниже кратко изложен весь процесс конвертирования, а более подробное описание представлено в [23.!О).
Все этапы этого процесса демонстрируются на основе следуюшей %ЕГ-формулы. ГОВАЕЕ х ( р ( х ) ЛВО ЕХ1ЯТЯ у ( ГОВАЕЕ х ( а ( у, х ) ) ) ) В этой формуле р и д являются предикатами, а х, у и х — переменными. 1. Сначала следует, как это было сделано в разделе 23.3„исключить из записи символы "=ь". В рассматриваемом примере данная операция не оказывает никакого влияния на вид %ГЕ-формулы. 2. Далее нужно использовать законы Де Моргана, а также тот факт, что две смежные операции ВОТ нейтрализуют одна другую, но применять эти операции по отношению к термам, а не к общим %ЕГ-формулам.
В рассматриваемом примере эта операция не оказывает никакого влияния на вид %ГГ-формулы. 3. Теперь необходимо конвертировать %ГЕ-формулу в предваренную нормальную форму, перенося кванторы в начало формулы (н систематически переименовывая переменные в случае необходимости). ГОВАРДЕ х ( ЕХ1ЯТЯ У ( ГОВАЕЬ г ( Р( х ) АВР й( У, х ) ) ) ) 4. Обратите внимание, что если содержащая кванторы %ГГ-формула, такая как ЕХ1ЯТЯ ч ( г ( ч ) )* эквивалентна другой %ГГ-формуле, например г(а), с некоторой (неизвестной) константой а, то в исходной %ГГ-формуле утверждается, что такая константа существует, хотя ее значение неизвестно.
Точно так же %ЕЕ-формула ГОВА11 ц ( ЕХ1ЯТЯ ч ( в ( ц, ч ) ) ) эквивалентна %ГГ-формуле ГОВЛЕЕ ц ( а ( ц, 1 ( ц ) ) ) Глава 23. Логические сисгпемы управления базами данных 911 для некоторой неизвестной функции Г, универсально квантифицированной переменной и. Константа а и функция Г в этих примерах называются в честь ученого- логика Сколема (Жо!еш) соответственно константой Сколема (ЕКо)егп сопмапг) и функцией Сколема, где константа Сколема — это просто функция Сколема без аргументов. Таким образом, на следующем этапе необходимо исключить излишнюю квантификацию, заменяя соответствующие квантифицированные переменные произвольными функциями Сколема всех универсально квантифицированных переменных, которые предшествуют данному квантору в %ТГ-формуле.
ГОКИД. х ( ГОКАЕЬ х ( р ( х ) КМО г) ( Г ( х ), з ) ) ) 5. Теперь все переменные универсально квантифицированы; следовательно, можно принять соглашение, что все они неявно универсально квантифицированы, и опустить явные кванторы. р ( х ) КНО и ( Г ( х ), з ) 6. Далее необходимо конвертировать %ТЕ-формулу в конъюнктивную нормальную форму, т.е. в набор предложений, объединенных с помощью операции КМ0 и, вероятно, содержащих связки МОТ и ОК, но только не связку ай0. В рассматриваемом примере %ТЕ-формула уже находится в такой форме. 7. Разместим каждое предложение в отдельной строке и опустим все связки йй0. р(х) г) ( Г ( х ), г ) Это и есть стандартная форма, эквивалентная оригинальной %РГ-формуле. Запеканке.
Из описанной выше процедуры слелует, что общий вид ИГР-формулы в стандартной форме представляет собой набор предложений, размещенных в отдельных строках с приведенным ниже синтаксисом. МОТ А1 ОК НОТ АГ ОК ... ОК НОТ Ац ОК В1 ОК ВГ ОК ... ОК Вп Здесь все А и В являются неотрицаемыми термами. Тот же синтаксис можно представить в другом виде. А1 ВМО АГ КМО ... АМ0 Ац =а В1 ОК ВГ ОК ... ОК Вл Если в этой записи присутствует по крайней мере один член В (л = 0 или л = 1), то она в честь ученого-логика Альфреда Хорна (А)бед Ноги) называется предложением Хорна. Использование правила резолюции Теперь на основе примера из раздела 23.2 рассмотрим, как выполняются запросы в логических базах данных. Допустим, что у нас есть предикат МОТНЕК ОГ, который имеет два параметра, представляющих мать и дочь соответственно, а также два следующих терма (экземпляра предиката).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
