Главная » SQL, Базы данных » НЕКОТОРЫЕ СЛЕДСТВИЯ ИЗЛОЖЕННОЙ СХЕМЫ

0

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

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

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

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

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

■     Логическое выражение р OR NOT (p) не обязательно в результате даст true.

Здесь р — это некоторое логическое выражение. В двухзначной логике выражение р OR NOT(p) всегда имеет значение true (т.е. истинно), независимо от значения р. Но в трехзначной логике, если р равно unk, общее выражение сводится к unk OR NOT (unk), т.е. к выражению unk OR unk, что в свою очередь упрощается до зна чения unk, а не true. Этот частный пример демонстрирует хорошо известное, но сложное для понимания свойство трехзначной логики, которое можно описать следующим образом. Если выполнить два запроса, "Получить сведения обо всех поставщиках из Лондона" и "Получить сведения обо всех поставщиках не из Лон дона", а затем объединить результаты обоих запросов, то не обязательно будут по лучены сведения обо всех поставщиках. Чтобы получить список всех поставщиков, к двум запросам нужно добавить еще один: "Получить сведения обо всех постав щиках, которые, возможно (may be), находятся в Лондоне" (иными словами, в трехзначной логике выражением, которое всегда принимает значение true, т.е. яв ляется аналогом выражения р  OR NOT (p) двухзначной логики, служит выраже ние р OR NOT(p)  OR MAYBE (p)).

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

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

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

на равенство "в стиле выборки", а не проверку на равенство "в стиле исключения дубликатов кортежей" (именно так!?).

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

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

■     Из равенства А = В AND В = С вовсе не обязательно следует равенство А =  С. Развернутая иллюстрация этого следствия приведена в подразделе "Пример с ба зой данных отделов и сотрудников".

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

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

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

Рис. 19.1. База данных отделов и сотрудников Рассмотрим следующее выражение,

которое может являться частью некоторого запроса.

DEPT.DEPT# = EMP.DEPT# AND EMP.DEPT# = DEPT# (‘Dl’)

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

DEPT.DEPT# = EMP.DEPT# AND EMP.DEPT# = DEPT# (‘D1′) AND DEPT.DEPT# = DEPT# (‘Dl’)

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

ЕМР.ЕМР# WHERE EXISTS DEPT ( NOT ( DEPT.DEPT# = EMP.DEPT# AND EMP.DEPT# = DEPT# (‘D1′) ) )

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

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

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

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

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

DEPT.DEPT# = EMP.DEPT# AND EMP.DEPT# = DEPT# (‘Dl’)

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

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

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

Дополнительные сведения о предикатах

Предположим, что отношение, являющееся текущим значением переменной  отношения ЕМР, содержит только два кортежа: (E2,D2) и (Е1,UNK). Первое  соответствует утверждению: "В отделе с номером D2 есть сотрудник с  номером  Е2", а второе — "Существует сотрудник с номером Е1". (Напомним,  что утверждение "Кортеж включает величину UNK" означает, что на самом деле этот кортеж вообще не содержит никакого значения в данной позиции  кортежа. Таким образом, кортеж (E1,UNK), если такое сомнительное обозначение вообще можно назвать кортежем, на самом деле следует рассматривать  как кортеж (Е1).) Иначе говоря, эти два кортежа являются конкретизациями двух разных предикатов, а все "отношение" является не отношением, а лишь своего рода некоторым объединением (причем нереляционным объединением!) двух разных отношений с двумя разными заголовками (в данном частном случае).

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

"Существует сотрудник с номером Е#, работающий в отделе с номером D#"

ОД "Существует сотрудник с номером Её".

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

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

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

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

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

По теме:

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