Преобразование выражений

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

Сравнение х = X не обязательно в результате даст true.

В двухзначной логике любая переменная х всегда равна самой себе. В трехзначной логике переменная х не равна самой себе, если она содержит величину UNK.

Логическое выражение р OR NOT(p) не обязательно в результате даст true. Здесь р - это некоторое логическое выражение. В двухзначной логике выражение р OR NOT(p) всегда имеет значение true (т.е. истинно), независимо от значения р. Однако в трехзначной логике, если р равно ипк, общее выражение сводится к ипк OR NOT(uiiic), т.е. к выражению ипк OR ипк, что, в свою очередь, упрощается до значения ипк, а не true.

Этот частный пример демонстрирует одно интересное свойство трехзначной логики, которое можно описать так. Если выполнить два запроса, Получить сведения обо всех поставщиках из Лондона и Получить сведения обо всех поставщиках не из Лондона , а затем объединить результаты обоих запросов, то не обязательно будут получены сведения обо всех поставщиках. Чтобы получить список всех поставщиков, к двум запросам нужно добавить еще один: Получить сведения обо всех поставщиках, которые, воз.можно (may be), находятся в Лондоне .

Суть данного примера, безусловно, состоит в том, что в реальном мире состояния находится в Лондоне и находится не в Лондоне являются взаимоисключающими и покрывают весь спектр возможностей. Однако в базе данных содержится не сам реальный мир, а лищь знания о реальном мире, и эти знания характеризуются тремя, а не двумя возможными состояниями. В рассматриваемом здесь примере это следующие состояния: место нахождения известно, и это Лондон , место нахождения известно, и это не Лондон , место нахождения неизвестно . Более того, как показано в [18.6], очевидно, что систему базы данных нельзя оп-ращивать о состоянии реального мира, ей можно задавать вопросы только о тех знаниях о реальном мире, которые представлены в базе данных в виде значений. Такое противоестественное свойство, приведенное в примере, порождено тем, что пользователь мыслит в терминах реального мира, а система функционирует, опираясь исключительно на свои знания об этом реальном мире.

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

Как следует из этих рассуждений, выражением, которое в трехзначной логике всегда будет давать в результате true (т.е. будет аналогом выражения р OR NOT(p) в двухзначной логике), является р OR ЮТ(р) OR MAYBE(р).

Вычисление логического выражения г JOIN г не обязательно в результате даст г.

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

Операция INTERSECT больше не является частным случаем операции JOIN.

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

Из равенства А = В AND В = С вовсе не обязательно следует равенство А = С. Развернутая иллюстрация этого следствия приведена в следующем разделе.

Таким образом, эквивалентности, корректные в двухзначной логике, не являются эквивалентностями в трехзначной логике. Одно из наиболее серьезных следствий подобных несоответствий таково. Как правило, в основе различных законов преобразования, которые используются для преобразования запросов в более эффективную форму, лежит простая эквивалентность вида г JOIN г = г (см. главу 17). Более того, эти законы используются не только системой (в процессе оптимизации), но и пользователями (когда они пытаются отыскать наилучший способ записи конкретного запроса). Если же исходная эквивалентность таковой не является, то построенные на ней законы преобразования, очевидно, являются некорректными. А если законы преобразования некорректны, то и выполняемые на их основе преобразования некорректны. В свою очередь, некорректные преобразования запросов приводят к неправильным ответам со стороны системы.

Пример с базой данных отделов и сотрудников

Для иллюстрации проблемы некорректных преобразований мы подробно обсудим специальный пример, взятый из [18.9] (по некоторым важным для данного случая причинам он построен на использовании реляционного исчисления, а не реляционной алгебры). Предположим, что имеется простая база данных отделов и сотрудников, показанная на рис. 18.1.

dept

dept#

Рис. 18.1. База данных отделов и сотрудников

Рассмотрим следующее условие, которое может являться частью некоторого запроса. DEPT.DEPT* = EMP.DEPT* AND EMP.DEPT* = DEPT# ( Dl )

Здесь DEPT и ЕМР являются переменными диапазона. Для всех кортежей в базе данных приведенное условие сводится к выражению ипк AND ипк, т.е. просто к значению ипк. Тем не менее хороший оптимизатор, исходя из того, что если А = В и В = С, то А = С, добавит к исходному условию дополнительную выборку А = С (как описано в главе 17.4). В результате получится следующее выражение.

DEPT.DEPTI = ЕМР.DEPTI AND ЕМР.DEPTi = DEPTi ( Dl )

AND DEPT.DEPTI = DEPTI ( Dl )

Это измененное выражение теперь сведется к выражению ипк AND ипк AND false или просто к значению false (для двух рассматриваемых кортежей в базе данных). В этом свете рассмотрим следующее выражение.

ЕМР.EMPI WHERE EXISTS DEPT ( NOT

( DEPT.DEPTI = EMP.DEPTI AND EMP.DEPTi = DEPTi ( Dl ) ) )

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

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

Проблема интерпретации

Теперь исследуем приведенный выше пример базы данных отделов и сотрудников более тщательно. Так как сотрудник с номером Е1 в действительности приписан к конкретному отделу, величина UNK представляет некоторое реальное значение d. В данном случае значение d либо равно D1, либо нет. Проанализируем значение следующего выражения.

DEPT.DEPTI = ЕМР.DEPTI AND ЕМР.DEPTI = DEPTt ( Dl )

Если d равно Dl, то для приведенного выше примера данных все выражение имеет значение false, поскольку именно это значение дает вычисление первого терма выражения. Если d не равно D1, то все выражение также будет иметь значение false, так как именно это значение будет получено при вычислении второго терма выражения - ЕМР.DEPTI = DEPTI ( Dl ). Иначе говоря, в реальном мире исходное выражение всегда имеет значение false, независимо от того, какое реальное значение представлено величиной UNK. Отсюда следует вывод, что результат, корректный в контексте реального мира, и результат, корректный в трехзначной логике, - это не одно и то же! Иначе говоря, трехзначная логика отражает поведение реального мира некорректно, т.е. можно считать, что трехзначная логика не является адекватным инструментом для интерпретации поведения реального мира!