    Глава     20 

    Отсутствующая информация 

    20.1. Введение 

    В главе 5 уже отмечалось, что проблема недостатка информации наиболее 
часто встречается в реальной жизни. Перефразируя суждения главы 5, можно 
сказать, что в реальном мире весьма типичны ситуации, когда, например, "дата 
рождения неизвестна", "имя оратора будет объявлено дополнительно", 
"местонахождение объекта в данный момент неизвестно". Поэтому должен 
существовать механизм обработки подобных ситуаций в формальных системах баз данных. 
    Согласно главе 5 наиболее типичные подходы, которые встречаются в 
литературе (и в коммерческих продуктах), базируются на неопределенных 
значениях (null-значениях) и трехзначной логике. Например, коротко можно 
сказать, что вес некоторой детали не определен. Конкретнее это выражение 
подразумевает следующее: известно, что деталь существует; эта деталь имеет 
вес; но не известно, сколько весит эта деталь. Другими словами, мы не знаем 
точного значения веса, которое можно обоснованно использовать в качестве 
значения для атрибута веса детали WEIGHT в кортеже, описывающем 
рассматриваемую деталь. Следовательно, значение этого атрибута помечается как 
неопределенное и эта отметка интерпретируется, как указание того, что нам не 
известно точное значение. 
    Замечание. Неформально можно говорить, что атрибут WEIGHT "содержит 
неопределенное значение" или что соответствующее значение "является 
неопределенным"; для краткости и удобства в этой книге будут использоваться 
подобные выражения. Но предыдущими рассуждениями мы стремились показать, что 
подобные выражения только неформальные, к тому же несколько неточные. Термин 
"неопределенное значение" не следует использовать потому, что такие значения 
на самом деле значениями не являются. (Далее для таких "неопределенных" 
значений будет использоваться термин null-значение.) 
    Исходя из материала главы 5, рассмотрим один достаточно важный аспект 
null-значений, а именно: ситуацию, когда в результате вычисления скалярного 
сравнения, в котором какой-либо из операндов не определен (содержит значение 
null), будет получено логическое значение unknown (неизвестное) вместо 
значений true (истина) или false (ложь). К такой ситуации привела 
интерпретация значений null как "неизвестных значений". Если значение А 
неизвестно, то неизвестен и результат, например, сравнения А > В, независимо 
от значения В (даже если предположить, что значение В также неизвестно). 
Поэтому следует заметить, что два значения null не рассматриваются как равные 
друг другу, следовательно, если А и В содержат значения null, то результатом 
сравнения А = В также будет значение unknown, а не true. Концепция 
null-значений (по крайней мере в общепринятом смысле) неизбежно приводит нас к 
необходимости использования логики с тремя логическими значениями: true 
(истина), false (ложь) и unknown (неизвестное). Исходя из того, что при 
использовании null-значений результат сравнения может принимать три логических 
значения, появился термин трехзначная логика (three-valued logic, в литературе 
трехзначная логика часто обозначается как 3VL). 

    Глава 20. Отсутсвующая информация 543 

    Как подчеркивалось в главе 5, автор данной книги разделяет мнение многих 
других авторов о том, что null-значения и трехзначная логика являются 
ошибочными понятиями и им нет места в чисто формальных системах, подобных 
реляционной модели. С другой стороны, автор согласен с тем, что проблема 
отсутствующей информации еще не полностью исследована и пока не существует 
удовлетворительного решения этой проблемы. Оставив все на своих местах, не 
хотелось бы лишать читателя возможности обсудить null-значения и трехзначную 
логику, поэтому в настоящее издание и включена данная глава. 
    План этой главы таков. Непосредственно после введения и без лишнего 
недоверия и критицизма описываются основные идеи, на которых базируется 
концепция null-значений и трехзначной логики. (Суть в том, что невозможно 
строго и справедливо критиковать любые идеи без предварительного описания 
самих идей.) Затем обсуждаются некоторые более важные следствия из изложенных 
идей и делается попытка обосновать мнения автора о том, что понятие 
null-значений является ошибочным. Далее сделано отступление для описания 
наиболее часто встречающихся операций с null-значениями — операций внешнего 
соединения. После этого кратко рассматриваются связанные с данной проблемой 
аспекты языка SQL. И наконец, подводится итог. 
    Еще одно предварительное замечание. Существует множество причин отсутствия 
некоторой части информации; "значение неизвестно" — это только одна из 
возможных причин. Среди других причин такие, как "значение неприменимо", 
"значение не существует" и т.д. [20.8]. Действительно, в [4.4] Кодд предложил 
использовать в реляционной модели не одно, а два вида null-значений: одно Из 
них — "значение неизвестно", а второе — "значение неприменимо". Как следствие 
этого, в реляционной модели, предложенной Коддом, используется не трех-, а 
четырехзначная логика. Автор данной книги протестует против подобных 
предложений в этой и во всех других своих работах (например, [20.8]). В данной 
главе мы сосредоточимся только на одном виде null-значений, а именно "значение 
неизвестно", на него мы достаточно часто, но не всегда, будем ссылаться с 
помощью аббревиатуры UNK (от unknown — неизвестно). 

    20.2. Обзор концепции трехзначной логики 

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

    Вычислительные скалярные выражения 

    Рассмотрим числовое выражение 

    WEIGHT *  454, 

    где WEIGHT представляет вес некоторой детали, например детали Рх. Что если 
вес детали Рх является величиной UNK? Каким будет значение всего выражения? 
Ответ состоит в том, что значением всего выражения также должна быть величина 
UNK. В общем, если хотя бы один из операндов скалярного выражения является 
величиной UNK, то результатом всего выражения также будет величина UNK. Таким 
образом, например, если WEIGHT содержит величину UNK, то результатом всех 
показанных ниже выражений также будет величина UNK. 

    WEIGHT + 454 WEIGHT - 454 WEIGHT * 454 WEIGHT / 454 454 + WEIGHT 454 - 
WEIGHT 454 * WEIGHT 454 / WEIGHT + WEIGHT - WEIGHT 

    544	Часть V. Дополнительные аспекты 

    (Возможно, следует сразу же заметить, что подобная трактовка числовых 
выражений служит почвой для некоторых аномалий. Например, выражение WEIGHT - 
WEIGHT, значением которого должен быть 0 (нуль), на самом деле будет иметь 
значение UNK, а результатом выражения WEIGHT/0 будет также величина UNK вместо 
обычного в данном случае сообщения об ошибке деления на нуль. Конечно, в обоих 
выражениях предполагается, что WEIGHT содержит величину UNK.) 
    В дополнение к приведенным выше скалярным операторам следует представить 
некоторые операторы, результатом которых не является величина LTNK, даже если 
операнд содержит такую величину. 
    Первый из операторов — это ISJJNK, который получает один операнд и 
возвращает значение true, если операнд является величиной UNK, и значение 
false в противном случае. Другими словами, это оператор "проверки на величину UNK". 
    Второй оператор — это IF_UNK. Этот оператор получает два операнда и 
возвращает значение первого операнда, если это не величина UNK. Если первый 
операнд является величиной UNK, то оператор IF_UNK возвращает значение второго 
операнда. Другими словами, это оператор преобразования величины UNK в 
некоторое значение, не являющееся величиной UNK. 
    Но следует заметить, что второй оператор (IFJJNK) можно определить в 
терминах первого оператора (ISJJNK). Точнее, выражение 

    IF_UNK   (  выражение!,   выражение2 ) 

    (где Выражения выражение! И выражение2 ДОЛЖНЫ быТЬ СОВМССТИМЫМИ ПО ТИГР/) 
ЭКВИВЗлентно выражению 

    ( IF ISJJNK (выражение!) THEN выражение2 ELSE выражение! ) 

    Пример. Предположим, что величины UNK запрещено использовать в качестве 
значений атрибута CITY в отношении Р, тогда после вычисления выражения 

    EXTEND Р ADD IFJJNK   (  CITY,   'City unknown')   AS PCY 

    будет получено отношение, в котором атрибут PCY содержит строку "City 
unknown" для каждого кортежа в отношении Р, в котором атрибут CITY содержит 
величину UNK. 

    Условия 

    Выше уже отмечалось, что результатом скалярных операций сравнения, в 
которых хотя бы один из операндов является величиной UNK, будет логическое 
значение unknown вместо значений true mw false. Поэтому приходится оперировать 
с тремя логическими значениями. Значение unknown, на которое мы достаточно 
часто, но не постоянно будем ссылаться с помощью сокращения unk, является 
"третьим логическим значением". Ниже приведены таблицы истинности для 
операторов AND, OR и NOT в трехзначной логике (в таблицах используются 
следующие сокращения: t — true, f—false, u — unk). 

    AND 
    t	u f	OR 
    t	u f	t 
    u	u f	u 
    f	f f	f 

    NOT 
    t	t t t 
    t	u u u 
    t	u f f 
    t 

    Предположим, что А = 3,В = 4иС — это величина UNK, тогда показанные ниже 
выражения будут иметь следующие (приведенные справа) результаты: 

    А > В AND В > С	:	false 
    А > В OR В > С	:	unk 
    А < В OR В < С	:	true 
    NOT  ( А - С  )	:	unk 
    
    Тем не менее, в трехзначной логике недостаточно операторов AND, OR и NOT 
[20.12]. Еще одним важным оператором является оператор MAYBE (возможно). 
Таблица истинности данного оператора показана ниже. 
    
    MAYBE 

    Глава 20, Отсутсвующая информация	545 
    18 Введение в системы баз данных 

    Чтобы продемонстрировать необходимость в операторе MAYBE, рассмотрим 
запрос "Получить сотрудников с годовой зарплатой менее 50 000 долларов, 
которые могут быть (но точно неизвестно) программистами и родились до 18 
января 1941 года". С помощью оператора MAYBE этот запрос можно достаточно 
кратко записать так: 

    ЕМР WHERE MAYBE { JOB = 'Programmer' AND 
    DOB < DATE ('1941-1-18') AND SALARY < 50000.00 ) 

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

    ЕМР WHERE   (   ISJJNK   (  JOB  )   AND 
    DOB < DATE   С1941-1-181)   AND 
    SALARY < 50000.00 ) OR ( JOB = ' Programmer' AND 
    IS_UNK   (  DOB  )   AND 
    SALARY < 50000.00 ) OR ( JOB = 'Programmer' AND 
    DOB < DATE ('1941-1-18') AND 
    ISJJNK ( SALARY ) ) OR	( ISJJNK ( JOB ) AND 
    ISJJNK   (  DOB  )   AND 
    SALARY < 50000.00 ) OR ( ISJJNK ( JOB ) AND 
    DOB < DATE   ('1941-1-18')  AND 
    ISJJNK ( SALARY ) ) OR ( JOB = 'Programmer' AND 
    ISJJNK ( DOB ) AND 
    ISJJNK ( SALARY ) ) OR ( ISJJNK ( JOB ) AND 
    ISJJNK ( DOB ) AND 
    ISJJNK ( SALARY ) ) 

    Замечание. Не следует воспринимать изложенное выше как подтверждение того, 
что оператор MAYBE является единственным дополнительным логическим оператором, 
который необходим в трехзначной логике. На практике, например, весьма полезным 
может оказаться оператор TKOEJDR_MAYBE (истина или может быть) [20.8]. (См. 
также [20.12], где этот вопрос обсуждается в контексте SQL.) 

    Кванторы EXISTS и FORALL 

    В главе 7 кванторы EXISTS и FORALL определяются как циклические операции 
OR и AND соответственно. Другими словами, если R— отношение с кортежами 77, 
72, ..., Тт; Т— переменная-кортеж, которая принимает значения из данного 
отношения; f(T) — условие, в котором используется переменная Т, то условие 

    EXISTS  Т (  f (   Т )   ) 

    по определению эквивалентно условию 

    false OR  (  f (   Tl )   )   OR ... OR  (  f (   Tm )   ) . 

    Аналогично, условие 

    FORALL Т (  f (   Т )   ) 

    по определению эквивалентно условию 

    true AND   (   f (   Tl  )   )   AND ... AND   (   f (   Tm )   ) . 

    Например, пусть отношение R содержит следующие кортежи: 

    (       1,	2,	3	) 
    (       1,	2,	UNK	) 
    (  UNK,	UNK,	UNK	) 

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

    546	Часть V. Дополнительные аспекты 

    true unk true true 
    false 
    unk 
    false 
    EXISTS	Т (	T[3]   > 1  ) 
    EXISTS	Г (	Г[2]   > 2  ) 
    EXISTS	Т (	MAYBE   (   T[l]   > 3   )   ) 
    EXISTS	Т (	IS__UNK   (   T[3]   )   ) 
    FORALL Г ( Г[1] > 1 ) FORALL Г ( T(2] > 1 ) FORALL Г ( MAYBE ( Г[3] > 1 ) ) 
    UNK - это не unfc 

    Следует явно указать, что UNK (неопределенное значение вида "значение 
неизвестно") и ww? (логическое значение unknown) — это не одно и то же, 
Действительно, такое положение дел является прямым следствием того, что unk — 
это значение (точнее, логическое значение), в то время как UNK не является 
значением вообще. Но давайте более точно сформулируем сказанное выше. 
Предположим, что X является переменной типа данных "логические значения". 
Тогда X может принимать одно из значений: true, false или unk. Таким образом, 
выражение "X является unk" в точности подразумевает, что значение переменной X 
известно и составляет unk, В отличие от этого, выражение "А'является UNK" 
означает, что значение переменной Jf неизвестно. 

    Могут ли домены содержать UNK 

    Утверждение о том, что домены не могут содержать UNK, — прямое следствие 
того, что UNK не является значением. Действительно, если бы было возможно, 
чтобы домены содержали null-значения какого-либо вида, появилось бы множество 
различных проблем, например: 
    •  Для всех значений v выражение v e D будет возвращать unk или true (но 
никогда false}, если домен D на самом деле содержит LINK. 
    •  И как следствие, если домен содержит UNK, то проверки целостности 
атрибутов, определенных на домене D, будут всегда завершаться с положительным результатом! 
    С другой стороны, если домены не могут содержать UNK, то отношения, 
содержащие UNK, не могут быть подмножествами декартова произведения 
соответствующих доменов, исходя из оригинального определения отношения, 
данного Коддом в [4.1]. Другими словами, подобные "отношения" — чем бы они ни 
были — на самом деле отношениями не являются! К этому вопросу мы еще вернемся 
в конце главы. 

    Реляционные выражения 

    Теперь рассмотрим влияние UNK на операторы реляционной алгебры. Для 
простоты ограничимся пятью примитивными операторами: выборки, проекции, 
произведения, объединения и вычитания (воздействие LTNK на другие операторы 
можно получить из заключений о воздействии UNK на пять перечисленных операторов). 
    Прежде всего, заметим, что на произведение никакого влияния нет. 
    Далее, операция выборки несколько переформулирована, для того чтобы 
возвращать только те кортежи, для которых условие выборки имеет значение true, 
т.е. эта операция не включает в результат те кортежи, для которых условие 
выборки принимает значение false или unk. Наличие этой формулировки неявно 
предполагалось в приведенном выше примере оператора MAYBE. 
    Теперь рассмотрим оператор проецирования. Проецирование отношения 
подразумевает (кроме всего прочего) исключение дублирующихся кортежей. В 
двухзначной логике два кортежа называют дублирующимися тогда и только тогда, 
когда все соответствующие компоненты обоих кортежей равны (конечно, 
рассматриваемые кортежи должны

    Глава 20, Отсутсвующая информация	547 

быть совместимыми по типу). Тем не менее, в трехзначной логике 
некоторые компоненты кортежей могут содержать UNK, а величина UNK не равна 
никакой другой величине, даже самой себе. Следует ли из этого заключить, что 
кортеж, который содержит UNK, не может быть дублем другого кортежа и даже 
самого себя? 
    Согласно Кодду [20.1] ответ на этот вопрос отрицательный. Две величины 
UNK, даже если они не равны между собой, все же считаются дублями друг друга в 
целях исключения дублирующихся кортежей. Очевидное противоречие описано 
следующим образом: "...проверка в процессе исключения дублирующихся кортежей 
... выполняется на более низком уровне детализации по сравнению с 
тестированием на равенство в операциях выборки. Поэтому можно применять 
различные правила" [20.1]. 
    Автор предоставляет читателю право решить, является ли такое обоснование 
приемлемым. В любом случае, давайте согласимся сейчас с этим обоснованием, а 
заодно примем и следующее определение. 
    •   Кортежи // и t2 являются дублирующими друг друга тогда и только тогда, 
когда они совместимы по типу и каждая пара значений al и а2 соответствующих 
атрибутов в обоих кортежах либо состоит из двух "реальных" (не UNK) значений и 
al = а2, либо и al и а2 являются UNK. 
    Теперь можно определить, что проекция отношения R по набору атрибутов А 
является результатом исключения атрибутов, не входящих в А, а затем исключения 
дублирующихся кортежей из того, что осталось. 
    Объединение также подразумевает исключение избыточных дублирующихся 
кортежей. Объединение двух совместимых по типу отношений R1 и R2 можно 
определить как отношение, совместимое по типу с исходными и включающее все 
возможные кортежи /, такие что / является дублем некоторого кортежа в 
отношении R1 или в отношении R2 (или в обоих одновременно). 
    И наконец, операции пересечения и вычитания определяются аналогично (хотя 
эти операции не используют исключение дублирующихся кортежей). Таким образом, 
кортеж t попадает в Rl INTERSECT R2 тогда и только тогда, когда этот кортеж 
дублирует какой-либо кортеж в R1 и какой-либо кортеж в R2. Кортеж / попадает в 
Rl MINUS R2 тогда и только тогда, когда этот кортеж дублирует какой-либо 
кортеж в RI и не дублирует ни одного кортежа в R2. Важность данных определений 
состоит в том, что, например, если оба отношения R1 и R2 содержат кортеж (х, 
UNK), то этот кортеж попадет в результат пересечения Rl INTERSECT R2, но не 
попадет ни в один из результатов вычитаний Rl MINUS R2 или R2 MINOS Rl. 

    Операции обновления 

    Здесь следует упомянуть два основных вопроса. 
    1. Если атрибут А отношения R может содержать UNK и если кортеж, 
вставляемый в отношение R не содержит значения для атрибута А, то система 
автоматически ставит UN К на место опущенного значения. Если атрибут Л в 
отношении R не позволяет использовать UNK, то попытка создать кортеж (с 
помощью операции INSERT или UPDATE), в котором для атрибута А стоит UNK, 
приведет к ошибке. 
    2.  Попытка создать (с помощью операции INSERT или UPDATE) дублирующий 
кортеж в R является (как всегда) ошибкой. В данном случае определение 
"дублирующихся кортежей" взято из предыдущего подраздела. 

    548	Часть V. Дополнительные аспекты 


    20.3. Некоторые следствия изложенной схемы 

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

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

    Прежде всего, обнаружилось, что различные выражения, которые в двухзначной 
логике всегда имели значение true, в трехзначной логике не обязательно будут 
давать всегда тот же результат. Ниже приведено несколько примеров с 
комментариями. Пожалуйста, отметьте, что этот список далеко не исчерпывающий. 
    1.  х = х не обязательно true. 
    В двухзначной логике любая переменная х всегда равна самой себе. В 
трехзначной логике переменная х не равна самой себе, если содержит величину UNK. 
    2. р OR NOT(p) не обязательно true. 
    Здесь р — это условие. В двухзначной логике выражение "р OR NOT(?>)" 
всегда имеет значение true (т.е. истинно), независимо от значения р. Тем не 
менее, в трехзначной логике, если р имеет значение unk, то общее выражение 
сводится к unk OR NOT(H«?), т.е. к выражению unk OR unk, что, в свою очередь, 
упрощается до значения unk, а не true. 
    Этот частный пример демонстрирует одно интересное свойство трехзначной 
логики, которое можно описать так. Если выполнить два запроса: "Получить всех 
расположенных в Лондоне поставщиков" и "Получить всех расположенных не в 
Лондоне поставщиков", а затем выполнить объединение результатов обоих 
запросов, то мы не обязательно получим всех поставщиков. Чтобы получить всех 
поставщиков, к двум запросам нужно добавить еще один: "Получить всех 
поставщиков, которые, возможно (maybe), расположены в Лондоне". 
    Суть данного примера состоит в том, что, в то время как в реальном мире 
два состояния "расположен в Лондоне" и "расположен не в Лондоне" являются 
взаимоисключающими и покрывают весь спектр возможностей, в базе данных 
содержится не реальный мир, а знания о реальном мире. А для знаний характерно 
три, а не два состояния. В данном примере это следующие состояния: 
"расположение известно, и это Лондон", "расположение известно, и это не 
Лондон", "расположение неизвестно". Более того (как показано в [20.9]), 
очевидно, что систему нельзя спрашивать о реальном мире, можно только задавать 
вопросы о знаниях системы о реальном мире, которые представлены в базе данных 
в виде значений. Такое "противоестественное" свойство, приведенное в примере, 
порождено тем, что пользователь мыслит в терминах реального мира, а система 
оперирует в терминах своих знаний об этом реальном мире. 

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

    Между прочим, как подсказывает пример, выражение р OR NOT{/?) OR MAYBE</>) 
в трехзначной логике всегда принимает значение true и аналогично выражению р 
OR ыот(р) в двухзначной логике. 
    3.  R JOIN R не обязательно даст R. 
    В двухзначной логике естественное соединение отношения R всегда дает 
исходное отношение R (т.е. естественное соединение иде.мпотентно). Тем не 
менее, в 

    Глава 20, Отсутсвующая информация	549 

трехзначной логике кортеж, содержащий UNK в любой позиции, не будет соединен 
сам с собой, так как соединение, в отличие от объединения, базируется на 
проверке равенства, а не на исключении дублирующихся кортежей. 
    4.  Операция INTERSECT больше не является частным случаем операции JOIN. 
    Этот факт подобен следствию того, что соединение базируется на определении 
равенства, в то время как пересечение, подобно объединению, базируется на 
определении дублирующихся кортежей. 
    5.  ИзА=В то В = С не обязательно следует А = С. 
    Расширенная демонстрация этого следствия приведена ниже в главе. 
    Таким образом, эквивалентности, корректные в двухзначной логике, не 
являются эквивалентностями в трехзначной логике. Одно из наиболее серьезных 
следствий подобных несоответствий таково. Как правило, в основе различных 
законов преобразования, которые используются для преобразования запросов в 
более эффективную форму, лежит простая эквивалентность R JOIN R=R. Более того, 
эти законы используются не только системой (в процессе оптимизации), но и 
пользователями (когда они пытаются отыскать "наилучший" способ записи 
конкретного запроса). И если эквивалентность таковой не является, то законы 
преобразования некорректны. А если законы преобразования некорректны, то 
преобразования также некорректны. В свою очередь, некорректные преобразования 
запросов приводят к получению неправильных ответов системы. 

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

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

    DEPT		ЕМР 
    DEPT*		ЕМР#	DEPT# 
    D2		Е1	UNK 
    
    Рис. 20.1. База данных отделов и сотрудников Рассмотрим условие 

    DEPT.DEPT# = EMP.DEPTt AND EMP.DEPT# = ' Dl' 

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

    DEPT.DEPT# = ЕМР.ОЕШ    AND    ЕМР.ОЕШ =   'Dl' AND    DEPT.DEPTtt =   'Dl' 

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

    ЕМР.ЕМР* WHERE EXISTS DEPT 
    ( NOT ( DEPT.DEPT# = EMP.DEPT# AND EMP.DEPT# = 'Dl' ) ) 

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

    550	Часть V. Дополнительные аспекты 

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

    Вопрос интерпретации 

    Теперь давайте исследуем пример базы данных отделов и сотрудников более 
тщательно. Так как сотрудник EJ не привязан к какому-то конкретному отделу 
(вместо реального значения в кортеже присутствует UNK). Пусть d является 
значением атрибута DEPT# в этом кортеже. Теперь вычисление исходного выражения 

    DEPT.DEPT* = EMP.DEPT* AND EMP.DEPT# =   'D1' 

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

    Замечание. Эта проблема интерпретации возникла не только из-за наличия 
null-значений и трехзначной логики, но эти факторы являются наиболее 
фундаментальными (см. [20.2-20.12] для более детального обсуждения других факторов). 

    20.4. Внешнее соединение 

    В этом разделе делается отступление от основной темы главы для обсуждения 
часто используемой операции внешнего соединения (см. [20.6, 20.7, 20.14, 
20.15]). Внешнее соединение — это расширенная форма обычного или "внутреннего" 
соединения. От внутреннего соединения внешнее отличается тем, что кортежи в 
одном отношении, которые не имеют соответствующих кортежей во втором 
отношении, появляются в результате со значениями null в позициях атрибутов 
второго отношения, вместо того чтобы быть просто проигнорированными, как это 
делается в обычном соединении. Это не примитивный оператор. Например, 
приведенное ниже выражение можно использовать для построения внешнего 
естественного соединения поставщиков и партий товаров по номеру поставщика (в 
демонстрационных целях предположим, что NULL является корректным скалярным выражением). 

    ( S JOIN SP ) 
    UNION 
    ( EXTEND ( ( S [ S# ] MINUS SP [ S# ] ) JOIN S ) ADD NULL AS P#, NULL AS 
QTY ) 

    Результат содержит кортежи поставщиков, не поставляющих ни одной детали. 
Эти кортежи заполнены значениями null в позициях атрибутов Р# и QTY. 
    Давайте более детально исследуем этот пример. Взгляните на рис. 20.2. На 
этом рисунке вверху показаны пробные значения данных, ниже — результат 
внутреннего естественного соединения, а еще ниже — результат соответствующего 
внешнего естественного соединения. Как видно из рис. 20.2, внутреннее 
соединение, коротко говоря, "теряет информацию" о поставщиках, не поставляющих 
ни одной детали (поставщик S5 в данном примере), в то время как внешнее 
соединение "сохраняет" эту информацию. Действительно, это различие и является 
сутью внешнего соединения. 

    Глава 20, Отсутсвующая информация	551 

    s 
    S#		SNAME		STATUS		CITY				SP S#	Р#    CTY 
    32 S5		Jones Adams		10 30		Paris Athens				S2 S2	Р1    300 Р2    400 
    
    
    Обычное (внутреннее) естественное соединение: 

    S#		SNAME		STATUS		CITY		P#		QTY	Информация 
    S2 S2		Jones Jones		10 10		Paris Paris		PI P2		300 400	для поставщика S5 "теряется" 
    
    
    Внешнее естественное соединение: 

    S#		SNAME		STATUS		CITY		P#		QTY	Информация 
    S2 S2 S5		Jones Jones Adams		10 10 30		Paris Paris Athens		PI P2 UNK		300 
400 UNK	для поставщика 35 "сохраняется" 
    
    
    Рис. 20.2. Внутреннее и внешнее соединение (пример) 

    Таким образом, внешнему соединению суждено решить весьма важную проблему 
"потери информации" внутренним соединением. Некоторые авторы высказывают 
мнение, что система должна обеспечивать прямую и явную поддержку внешних 
соединений, вместо того чтобы требовать от пользователя нескольких 
перефразировок запроса для достижения желаемого результата. В частности, Кодд 
рассматривает внешнее соединение как внутреннюю часть реляционной модели 
[4.4]. Тем не менее, в этой книге мы не будем высказываться за явную поддержку 
внешних соединений и вот почему. 
    •  Прежде всего, конечно, операция внешнего соединения использует 
null-значения, а автор настоящей книги всегда выступает против null-значений 
по целому ряду описанных ранее причин. 
    •  Далее, уже было высказано мнение о том, что атрибуты, значениями 
которых .могут быть отношения, представляют собой альтернативный подход к 
решению проблемы с помощью внешних связей (глава 19). Кроме того, атрибуты, 
значениями которых могут быть отношения, не требуют использования 
null-значений и внешних связей и, по мнению автора, являются "более 
элегантным" решением проблемы [19.3]. 
    •  Заметьте, что существует несколько разновидностей внешнего соединения — 
левое, правое и полное внешнее 6-соединение, а также левое, правое и полное 
внешнее естественное соединение (левое соединение "сохраняет" информацию из 
левого операнда, правое — из правого операнда, а полное — с обеих сторон). На 
рис. 20.2 показано левое соединение, точнее, левое внешнее естественное 
соединение. Кроме того, заметьте, что не существует достаточно простого 
способа порождения внешнего естественного соединения из внешнего 6-соединения 
[20.7]. В результате неясно, какой из операторов внешнего соединения нужно 
явно поддерживать. 
    •  Далее, вопрос о внешнем соединении весьма далек от тривиальности, 
которая присутствует в примере на рис. 20.2. На практике, как показано в 
[20.7], внешнее соединение страдает от набора "отвратительных свойств", 
элегантно реализовать которые в существующих языках, в частности в SQL, 
довольно трудно. (См. [20.7], где этот вопрос описан подробнее.) 
    •   И наконец, существует проблема интерпретации null-значений, которые 
появляются в результате внешнего соединения. Например, что представляют собой 
эти значения 

    552 Часть V. Дополнительные аспекты 

    UNK на рис. 20.2? Определенно, они не означают "значение неизвестно" или 
"значение неприменимо". Более глубоко эта проблема обсуждается в [20.7]. 
(Читатель, возможно, заметил, что в этом разделе мы вернулись к исходному 
термину "null-значение" вместо UNK. Это как раз и есть одна из проблем 
внешнего соединения — не совсем ясно, null-значения какого вида должны 
появляться в результате.) 
    Кроме того, внешнее соединение иногда создает отношение, которое содержит 
null-значения в первичном ключе, и поэтому подобные отношения нельзя 
преобразовать в базовые отношения без нарушения правил целостности. 
Действительно, этот комментарий применим и к примеру на рис. 20.2. 

    Замечание. Существует возможность определить "внешние" версии некоторых 
других операторов реляционной алгебры, в частности операторов объединения, 
пересечения и вычитания [20.1], и Кодд опять рассматривает по крайней мере 
один из таких операторов, как внутреннюю часть реляционной модели [4.4]. 
Подобные версии операторов позволяют выполнять объединение (и т.п.) двух 
отношений, даже если данные отношения несовместимы по типу. В основном такие 
операторы работают, расширяя каждый из операндов атрибутами, свойственными 
другому операнду, посредством вставки null-значений в каждый такой атрибут 
каждого кортежа (после этого операнды становятся совместимыми по типу). Затем 
выполняется обычное объединение, пересечение или вычитание. Тем не менее, мы 
не будем детально обсуждать эти операции по следующим причинам: 
    •   Внешнее пересечение гарантированно возвращает пустое отношение, за 
исключением специального случая, когда исходные отношения совместимы по типу. 
В этом случае внешнее пересечение вырождается до обычного пересечения. 
    •   Внешнее вычитание гарантированно возвращает первый операнд, за 
исключением специального случая, когда исходные отношения совместимы по типу. 
В этом случае внешнее вычитание вырождается до обычного вычитания. 
    •   Основными проблемами внешнего объединения являются проблемы 
интерпретации (эти проблемы даже сложнее проблем интерпретации внешнего 
соединения). См. [20.2] для более детального изучения. 

    20.5. Поддержка SQL 

    Поддержка null-значений и трехзначной логики в языке SQL отражает широкий 
набор подходов, описанных в предыдущих разделах. Так, например, когда в языке 
SQL применяется условие WHERE к таблице Т, то это исключает из рассмотрения 
все строки таблицы Т, для которых условие WHERE принимает значение false или 
unk (т.е. не true). Аналогично, когда к некоторой сгруппированной таблице G 
применяется оператор HAVING, то из дальнейшего рассмотрения исключаются все 
группы кортежей, для которых условие оператора HAVING принимает значение false 
или unk. Из этого следует, что мы просто обратили внимание читателя на 
некоторые возможности, специфические для языка SQL и не являющиеся частью 
концепции трехзначной логики, которая обсуждалась в предыдущем разделе. 
    Замечание. Очень сложно оценить все последствия поддержки null-значений в 
языке SQL. Дополнительную информацию можно найти в официальных документах 
стандарта SQL [8.1] ив учебном издании [8.5]. 

    Определение данных 

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

    Глава 20, Отсутсвующая информация	553 

    NOT NOLL) не запрещает использование таких значений. Представление 
null-значений зависит от реализации, но оно должно быть таким, чтобы система 
смогла отличить это значение от других, которые null-значениями не являются. 

    Табличные выражения 

    Вспомните главу 8: большинство современных версий стандарта SQL (SQL/92) 
обладает явной поддержкой операции JOIN. Более того, если ключевое слово JOIN 
предварено одним из слов LEET, RIGHT или FULL (с необязательной добавкой OUTER 
в каждом случае), то рассматриваемое соединение является внешним соединением, например: 

    S LEFT	[ OUTER ]	JOIN SP ON S.S# = SP.S# 
    S LEFT	[ OUTER ]	JOIN SP USING ( Stt ) 
    S LEFT	[ OUTER ]	NATURAL JOIN SP 

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

    Условия 

    Ни для кого не является неожиданностью, что условия стали той частью языка 
SQL, которая больше всего затронута null-значениями и трехзначной логикой. 
Приведенное ниже описание весьма выборочно и поверхностно. 
    •  Проверки на null. SQL обладает двумя специальными операторами— is NULL 
и is NOT NULL— для проверки наличия и отсутствия null-значений. Синтаксис 
операторов показан ниже. конструктор-строки IS   [  NOT  ]   NULL 
    Для неосторожных пользователей здесь существует одна ловушка. Два 
выражения г is NOT NULL и NOT (r is NULL) не являются эквивалентными! Более 
подробное описание можно найти в [8.5]. 
    •  Проверки на true, false и unknown. Если р — это условие, заключенное в 
скобки, то следующие выражения также являются условиями: 

    р IS	[	NOT ]	TRUE 
    р IS	[	NOT ]	FALSE 
    p IS	[	NOT ]	UNKNOWN 

    Значения этих выражений показаны ниже в таблице истинности. 

    р	true	false	unk 
    р IS TRUE	true	false	false 
    р IS NOT TRUE	false	true	true 
    p IS FALSE	false	true	false 
    p IS NOT FALSE	true	false	true 
    p IS UNKNOWN	false	false	true 
    p IS NOT UNKNOWN	true	true	false 

    Заметьте, что выражения/? is NOT TRUE и NOT p не являются эквивалентными! 
Замечание. Выражение р is UNKNOWN соответствует описанной выше инструкции 
    MAYBE (р}. 
    Условия MATCH. Синтаксис условий MATCH включает опцию "PARTIAL или FULL", 
которая не обсуждалась в главе 8. Эта опция может повлиять на результат, если 
используются null-значения. 
    конструктор-строки MATCH   [  UNIQUE ] 

    [  PARTIAL  |   FULL ]   (   табличное выражение ) 

    554 Часть V. Дополнительные аспекты 

    Существует шесть возможных случаев, зависящих от того, опущена или нет 
опция UNIQUE, а также опущена или нет опция "PARTIAL или FULL" (и если нет, то 
какой из кванторов использован). Детальное обсуждение этого вопроса достаточно 
сложное и выходит за рамки настоящей главы. Дополнительную информацию можно 
найти в [8.5]. 
    •   Условия EXISTS, См. комментарий к [20.9]. 
    Скалярные выражения 
    •   "Литералы". Ключевое слово NULL может быть использовано как отдельный 
вид строкового представления null-значений (например, в выражениях INSERT), 
Тем не менее, следует заметить, что данное ключевое слово не может появляться 
во всех контекстах, в которых можно использовать литералы. Как гласит 
стандарт, "не существует <литерала> для null-значения, хотя в некоторых 
случаях используется ключевое слово NULL, чтобы указать, что в данном случае 
желательно null-значение" [8.1]. Таким образом, например, ключевое слово NULL 
нельзя явно использовать в качестве операнда в простых операциях сравнения, 
т.е. выражение "WHERE x = NULL" некорректно. 
    •   COALESCE. Это SQL-аналог определенной выше в данной главе функции IF UNK. 
    •  Агрегативные функции. Эти функции языка SQL, например SUM, AVG и т.п., 
не ведут себя в соответствии с правилами для скалярных операторов, изложенными 
выше в этой главе. Вместо этого они просто игнорируют любое null-значение в 
своих аргументах (исключение составляет выражение COUNT<*), при вычислении 
которого null-значение трактуется как реальное значение). Кроме того, если 
подобные функции получают в качестве аргумента пустое множество, то они 
возвращают null-значение. Исключение составляет функция COUNT, которая в 
случае пустого множества возвращает нуль, являющийся корректным результатом. 
(Сравните с трактовкой пустых множеств, изложенной в главе 6.) 
    •   Табличные выражения в скобках. Если скалярное выражение фактически 
является заключенным в скобки табличным выражением, например (SELECT S.CITY 
FRCM s WHERE s.s#='si'), то вполне естественно, что результатом табличного 
выражения должна быть таблица, содержащая единственный столбец и единственную 
строку. Тогда значением скалярного выражения будет тот единственный скаляр, 
который содержит результирующая таблица. Но если результатом табличного 
выражения является таблица, не содержащая ни одной строки, то SQL, определяет 
значение рассматриваемого скалярного выражения как null. 

    Ограничения целостности 

    В SQL ограничения (условия) целостности в основном представляют собой 
условия, которые не должны принимать значение false. Другими словами, условие 
SQL не рассматривается как нарушенное, если оно принимает значение unk. 
Конечно, с технической точки зрения в данном случае следует говорить, что 
неизвестно, нарушается ограничение или нет, но так как стандарт SQL 
рассматривает unk как false в случае оператора WHERE, то вполне допустимо 
рассматривать значение unk как true в случае ограничений целостности (если 
говорить коротко). 
    Изложенные соображения применимы к ограничениям доменов, основным 
ограничениям ("утверждениям") и проверочным ограничениям и распространяются 
без изменений на все три перечисленных вида ограничений. Потенциальные и 
внешние ключи требуют дополнительного рассмотрения. 
    •  Потенциальные ключи. Пусть С — это столбец, являющийся частью 
потенциального ключа К некоторой таблицы. Если К является первичным ключом, то 
SQL не разрешает использовать null-значения в столбце С (так как необходимо соблюдать 

    Глава 20. Отсутсвующая информация	555 

ограничение целостности). Тем не менее, если К не является первичным 
ключом, то SQL разрешает использовать в С любое количество null-значений 
(конечно, вместе с любым количеством значений, не являющихся null-значениями). 
    •  Внешние ключи. Правила, определяющие соответствие значения конкретного 
внешнего ключа значению какого-либо потенциального ключа (при наличии 
null-значений), очень сложные. В данной дискуссии детальное обсуждение этих 
правил опускается. Следует только заметить, что они в основном совпадают с 
правилами для условий MATCH (см. выше). 
    Null-значения также влияют на ссылочные операции (CASCADE, SET NULL и 
т.д.), использующиеся в операторах ON DELETE и да UPDATE. Для простоты 
изложения детальное обсуждение этой проблемы опущено. Более подробно она 
изложена в [8.5]. 

    Встроенные выражения SQL 

    •  Переменные-индикаторы. Рассмотрим пример встроенного выражения SQL. 
(Этот пример уже приводился в главе 8 при описании "единичного SELECT".). 

    ЕХЕС SQL SELECT STATUS, CITY INTO  :RANK, :CITY FROM  S WHERE S# = 
:GIVENS# ; 

    Предположим, что для некоторых поставщиков атрибут STATUS может содержать 
null-значение. Тогда приведенное выше выражение SELECT завершится неудачей, 
если в выбранном кортеже атрибут STATUS содержит null-значение (переменная 
SQLSTATE будет содержать код ошибки 22002). В общем смысле, если существует 
возможность того, что полученное значение может быть null-значением, 
пользователь должен указать переменную-индикатор для целевой переменной. 
Пример указания переменной-индикатора приведен ниже. 

    ЕХЕС SQL SELECT STATUS, CITY 
    INTO  :RANK INDICATOR :RANKIND, :CITY 
    FROM  S 
    WHERE S# = :GIVENS# ; IF RANKIND = -1 THEN ... /* атрибут STATUS содержал 
null-значение */; 

    Если значение, которое нужно выбрать, является null-значением и указана 
переменная-индикатор, то эта переменная примет значение -1 (значение целевой 
переменной зависит от реализации). 
    •   Упорядочение. Для упорядочения строк, полученных в результате 
вычисления табличного выражения, используется инструкция ORDER BY. Возникает 
вопрос: "Каков относительный порядок двух скаляров А и В, если А является 
null-значением или В является null-значением (или они оба одновременно 
являются null-значениями)?" Стандарт SQL подразумевает следующие ответы: 
    1.  В процессе упорядочения все null-значения считаются равными друг другу. 
    2.   В процессе упорядочения все null-значения считаются либо большими 
всех остальных значений, либо меньшими (выбор каждой из этих возможностей 
зависит от конкретной реализации). 

    20.6. Резюме 

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

    556	Часть V. Дополнительные аспекты 

хотя так принято считать (например, когда некоторый атрибут "является 
null"). Результатом любых операций сравнения, в которых один из операндов 
содержит null-значение, служит третье логическое значение unknown (сокращенно 
unk), поэтому логика называется трехзначной. Также отмечалось, что по целому 
ряду причин информация может отсутствовать, поэтому существуют различные виды 
null-величин. Для одного из видов null-величины — "значение не определено" — 
рассматривалось удобное (и явное) сокращение UNK. 
    Далее исследовалось влияние UNK и трехзначной логики на вычислительные 
выражения, условия, кванторы FORALL и EXISTS и реляционные операторы (в 
частности, на операторы выборки, проекции, объединения, пересечения и 
вычитания, а также на операторы INSERT и DELETE). В этой главе был представлен 
оператор IS_UNK (выполняющий проверку на UNK), оператор IFJJNK (для 
преобразования UNK в значение, не являющееся LINK) и оператор MAYBE (для 
преобразования значения unk в true). Обсуждалась проблема дублирующихся 
кортежей с учетом наличия UNK. Кроме того, особо подчеркивалось, что UNK и unk 
— это не одно и то же. 
    Далее рассматривались некоторые следствия изложенных идей. Во-первых, было 
показано, что некоторые эквивалентности двухзначной логики не являются 
эквива-лентностями в трехзначной логике. В результате пользователи и 
оптимизаторы могут совершать ошибки в процессе преобразования выражений. Но 
даже без учета названных ошибок трехзначная логика обладает одним очень 
серьезным недостатком — она не соответствует реальному миру, т.е. результаты 
операций в трехзначной логике не всегда корректны в понятиях реального мира. 
    После этого было сделано отступление для описания внешнего соединения. 
Отмечалось, что автор не является сторонником прямой поддержки этой операции 
(по крайней мере в ее обычном смысле), так как считает, что существует лучшее 
решение проблемы, которую призвано решать внешнее соединение. Подчеркивалась 
возможность существования и других "внешних" операций, в частности внешнего объединения. 
    В данной главе также проанализирована поддержка изложенных идей стандартом 
SQL. В трактовке проблемы отсутствующей информации в стандарте SQL широко 
используется трехзначная логика, но эта трактовка вносит множество других 
осложнений, описание которых выходит за рамки этой книги. Действительно, в 
дополнение к недостаткам трехзначной логики [20.9, 20.11] стандарт SQL вносит 
новые недостатки. Более того, эти недостатки служат дополнительными причинами, 
замедляющими процесс оптимизации. 
    В заключение попытаемся сформулировать некоторые размышления. 
    •   Читатель будет благодарен за то, что в книге кратко описана проблема 
null-значений и трехзначной логики. Тем не менее, изложено достаточно 
материала, чтобы утверждать, что "преимущества" трехзначной логики более чем сомнительны. 
    •  Следует также заметить, что, даже если читатель не слишком озабочен 
проблемой трехзначной логики, было бы желательно избегать соответствующих 
возможностей языка SQL из-за "дополнительных недостатков", описанных выше. 
    •  Таким образом, пользователям СУБД автор рекомендует полностью 
игнорировать средства поддержки трехзначной логики выбранного производителя 
СУБД и использовать более строгую схему "значений по умолчанию" (из-за 
строгости остающуюся в рамках двухзначной логики). Подобная схема детально 
описана в [20.13]. 
    •  И наконец, повторим важное утверждение, сформулированное выше в этой 
главе. Если значение данного атрибута некоторого отношения "является 
null-значением", то такие атрибуты не содержат ничего, подтверждающего, что 
"отношение" (чем бы оно ни было) уже не является отношением, соответственно 
основа того, что мы рассматриваем (что бы это ни было), уже не является 
математической реляционной теорией. Другими словами, автор считает, что 
трехзначная логика и null-значения разрушают весь базис реляционной модели. 

    Глава 20. Отсутсвующая информация	557 


    Упражнения 

    20.1. Укажите логические результаты следующих выражений, если А = 6, В = 
5, С = 4, a D содержит UNK: 
    а)	А = В OR ( В > С AND A > D ) 
    б)	А > В AND ( В < С OR IS_UNK ( A - D ) ) 
    В)	А < С OR В < С OR NOT ( А = С ) 
    Г)	B>DORD>BORD = B 
    Д)	MAYBE ( А > В AND В > С ) 
    б)	MAYBE ( IS_UNK ( D ) ) 
    Ж)	MAYBE ( ISJJNK ( A 4- В ) ) 
    3)	IF_UNK ( D, A ) > В AND IFJJNK ( C, D ) < В 
    20.2. Отношение R содержит следующие кортежи: 
    (       6,	Ь,       4  ) 
    (  UNK,	Ъ,       4   ) 
    (       6,	UNK,       4   ) 
    (  UNK,	UNK,        4   ) 
    (  UNK,	UNK,   UNK  ) 
    и Т— это переменная-кортеж, которая принимает значения из R. Укажите 
логические результаты выражений 
    а)    EXISTS т ( т[2] > 5 ) 
    б)	EXISTS Т ( Л2] > 2 AND Г[3] > 5 ) 
    B)	EXISTS Т ( MAYBE ( ЛЗ] > 3 ) ) 
    г)	EXISTS Т ( MAYBE ( ISJJNK ( Т(3] ) ) ) 
    д)	FORALL Т ( Т[1] > 1 ) 
    е)	FORALL  Т (   Т(2]   >  1 OR IS__UNK   {   T[2]   )   } 
    ж)	FORALL  Т ( MAYBE   (   ЛИ   >  Л2]   )   ) 
    (Индексирование T[i] используется для ссылок на компоненты кортежа.) 
    20.3. Говоря коротко, оператор ISJJNK не нужен. Почему? 
    20.4. В [20.1] предложены версии "mayby" ("возможно") для некоторых 
операторов реляционной алгебры. Например, "mayby-выборка" отличается от 
обычного оператора выборки тем, что возвращает те кортежи, для которых условие 
выборки принимает значение unk, а не true. Тем не менее, подобные операторы не 
нужны. Почему? 
    20.5. В двухзначной логике существует только два логических значения — 
true и false. Следствием этого является существование ровно четырех возможных 
унарных логических операторов: один преобразует оба значения в true, второй 
преобразует оба значения Е false, третий преобразует true в false и наоборот и 
четвертый принимает значение операнда. Кроме того, существует ровно 16 
возможных бинарных логических операторов (см. таблицу истинности ниже). 

    А	В 

    t	t	ttttttttffffffff 
    t	f	ttttffffttttffff 
    f	t	ttffttffttffttff 
    f	f	tftftftftftftftf 


    558	Часть V. Дополнительные аспекты 

    Докажите, что все четыре унарных и все 16 бинарных операторов можно 
записать с помощью комбинаций операторов NOT, AND и OR (следовательно, нет 
необходимости явно поддерживать все 20 операторов). 
    20.6. Сколько логических операторов может быть в трехзначной логике? А в 
четырехзначной? Для более общего случая — в и-значной логике? 
    20.7. (Взято из [20.8]) На рис. 20.3 показаны образцы данных для 
очередного варианта базы данных поставщиков и деталей. (Этот вариант 
отличается от предыдущих тем, что в отношение SP включен атрибут SHIP# 
(shipment number— номер партии), а атрибут Р# в этом отношении определен как 
разрешающий использование UNK. Отношение Р не относится к данному примеру и в 
упражнении не описывается.) 

    S					SP 

    s#	SNAME	STATUS	CITY		SHIPft	S#	P#	QTY 
    SI	Smith	20	London		SHIP1	SI	PI	300 
    S2	Jones	10	Paris		SHIP2	S2	P2	200 
    S3	Blake	30	Paris		SHIP3	S3	UNK	400 
    S4	Clark	20	London 
    
    
    Рис. 20.3. Вариант базы данных поставщиков и деталей Теперь рассмотрим выражение 

    S WHERE NOT EXISTS SP   (  SP.S# = S.S# AND SP.P# =   'P2'   ) 
    Какая из следующих интерпретаций запроса корректна: 
    а) получить поставщиков, которые не поставляют деталь Р2; 
    б) получить поставщиков, о поставках детали Р2 которых ничего не известно; 
    в) получить поставщиков, о которых известно, что они не поставляют деталь Р2; 
    г) получить поставщиков, о которых либо известно, либо не известно, что 
они поставщики детали Р2. 
    20.8. Спроектируйте схему физического представления базовых таблиц SQL, 
позволяющих использовать null-значения. 
    20.9. Предположим для простоты, что отношение с данными о деталях имеет 
только два атрибута, Р# и COLOR. Также предположим, что Р# объявлен как 
атрибут, не разрешающий использовать null-значения, a COLOR — как атрибут, 
разрешающий использовать null-значения. Сформулируйте предикат такого отношения. 

    Список литературы 

    20.1. Codd E.F. Extending the Database Relational Model to Capture More 
Meaning // ACM TODS. — 1979. — 4, № 4. 
    Это первая работа Кодда, в которой обсуждается проблема отсутствующей 
информации (хотя это не основная тема данной работы). В этой публикации автор 
предлагает несколько расширений алгебры, позволяющих оперировать с 
null-значениями и трехзначной логикой, а также с "внешними" версиями операций 
объединения, пересечения, вычитания, 9-соединения и естественного соединения. 

    Глава 20, Отсутсвующая информация 559 

    20.2. Darwen H. Into the Unknown // C.J. Date. Relational Database 
Writings 1985-1989. — Reading, Mass.; Addison-Wesley, 1990. 
    В работе поднимается ряд дополнительных вопросов в отношении null-значений 
и трехзначной логики, наиболее сложным из которых является следующий: "Если 
(как показано в главе 4) TABLE_DEE соответствует значению true, a TABLE_DUM — 
значению false и если TABLE_DEE и TABLE_DUM являются единственными возможными 
экземплярами отношения с null-значениями, то что же соответствует значению unk?" 
    20.3. Darwen H. Outer Join with No Nulls and Fewer Tears // C.J. Date and 
Hugh Darwen. Relational Database Writings 1989-1991.— Reading, Mass.: 
Addison-Wesley, 1992. 
    В работе предложен простой вариант "внешнего соединения"; в нем не 
используются null-значения и решается много других задач, которые призвано 
решать внешнее соединение. 
    20.4. Date C.J. Data Models // C.J. Date. An Introduction to Database 
Systems: Volume II. Chapter 5 — Reading, Mass.: Addison-Wesley, 1983. 
    Первый взгляд автора данной книги на проблему null-значений и трехзначной логики. 
    20.5. Date C.J. Null Values in Database Management // C.J. Date. 
Relational Database: Selected Writings. — Reading, Mass.: Addison-Wesley, 1986. 
    Пересмотрен и расширен материал работы [20.4]. 
    20.6. Date C.J. The Outer Join // Ibid. 
    Здесь детально обсуждается проблема внешнего соединения и представлены 
некоторые предложения по поддержке этой операции в реляционных языках, таких 
как SQL. 
    20.7. Date C.J. Watch Out for Outer Join // C.J. Date and Hugh Darwen. 
Relational Database Writings 1989-1991 —Reading, Mass.: Addison-Wesley, 1992. 
    В этой главе сделано утверждение о том, что внешнее соединение страдает от 
нескольких "отвратительных свойств". В работе предлагается список таких свойств. 
    1.   Внешнее 9-соединение не является выборкой декартова произведения. 
    2.   Выборка не распространяется на операции внешнего 6-соединения. 
    3.   В трехзначной логике "А<В" — это не то же самое, что "А<В OR А=В". 
    4.  Операции 9-сравнения не транзитивны. 
    5.  Внешнее естественное соединение не является проекцией внешнего 
соединения по эквивалентности. 
    В статье также рассматривается поддержка в SQL конструкции SELECT-FROM
    WHERE. 
    20.8. Date C.J. NOT Is Not "Not"! (Notes of Three-Valued Logic and Related 
Matters) // C.J. Date. Relational Database Writings 1985-1989.— Reading, 
Mass.: Addison-Wesley, 1990. 
    Положим, X— переменная данных типа "истинное значение". Тогда Л'принимает 
одно из значений — true, false или tink. Таким образом, утверждение "А'не 
является true (истиной)" подразумевает, что значением X является либо unk, 
либо false. Однако утверждение "X— NOT true (не истина)" означает, что 
значением X является false (ложь) (см. таблицу истинности для NOT). 
Получается, что NOT в трехзначной логике не соответствует отрицанию 

    560	Часть V. Дополнительные аспекты 

"не" в обычном разговорном языке... Некоторые уже столкнулись с данным 
фактом (включая и создателей стандарта SQL/92), и, несомненно, это будет 
происходить снова. 
    20.9. Date C.J. EXISTS Is Not "Exists"! (Some logical Flaws in SQL) // Ibid. 
    Здесь обращается внимание на то, что оператор SQL EXISTS — не то же самое, 
что квантор существования трехзначной логики, так как он оценивает true или 
false, но не unk, даже в том случае, когда unk является логически правильным ответом. 
    20.10. Date C.J. Three-Valued Logic and the Real World // C.J. Date and 
Hugh Darwen. Relational Database Writings 1989-1991. — Reading, Mass.: 
Addison-Wesley, 1992. 
    20.11. Date C.J. Oh No Not Nulls Again // Ibid. 
    20.12. Date C.J. A Note on the Logical Operators Of SQL, Part I // The 
Relational Journal. — 1993. — 5, № 1. 
    В трехзначной логике (3VL) используются три логических значения — true, 
false и неопределенность (обозначенные здесь как t, f и и соответственно). 
Следовательно, в трехзначной логике может быть 3 * 3 * 3 - 27 возможных 
унарных операторов (см. упр. 20.5), так как каждое из трех возможных входящих 
значений t,/или и может отображать любое из трех возможных выходящих значений 
t, f или и. Также в трехзначной логике может быть 39=19 683 возможных бинарных 
оператора (см. таблицу ниже). 

    t       u       f 
    t/u/f t/u/f t/u/f 
    t/u/f t/u/f t/u/f 
    t/u/f t/u/f t/u/f 

    Фактически, в более общем случае и-значная логика («VL) включает п в 
степени п унарных операторов и в степени п2 бинарных операторов (см. таблицу ниже). 
    Унарные операторы	Бинарные операторы 

    2VL	4	16 
    3VL	27	19 683 
    4VL	256	4 294 967 296 
    nVL	(л)** (л)	(л) **(//) 

    Для любой и-значной логики, где п > 2, возникают следующие вопросы: 
    • Каков подходящий набор примитивных операторов? (Например, как набор 
{NOT, AND}, так и набор {NOT, OR} являются подходящими примитивными наборами 
для двухзначной логики.) 
    • Каков подходящий набор полезных операторов? (Например, набор {NOT, AND, 
OR} — подходящий полезный набор для двухзначной логики.) 
    В части I данной статьи показано, что стандарт SQL/92 (при очень вольной 
интерпретации) по крайней мере прямо или косвенно поддерживает все унарные 
операторы трехзначной логики. В части II отмечается то же самое в отношении 
бинарных операторов. Тем не менее, необходимо обратить внимание на то, что в 
логике операторы оперируют с предикатами и с предложениями, в то время, как в 
SQL (даже при вольной интерпретации) операторы оперируют только с предложениями. 
    20.13. Date C.J. The Default Values Approach to Missing Information // 
C.J. Date and Hugh Darwen. Relational Database Writings 1989-1991.— Reading, 
Mass.: Addison-Wesley, 1992. 

    Глава 20, Отсутсвующая информация 561 

    Разработан систематический подход к проблеме отсутствия информации, 
основанной на значениях по умолчанию и на двухзначной логике, вместо 
null-значений и трехзначной логики. В статье аргументировано доказывается, что 
значения по умолчанию — это то, что мы используем в реальном мире (в реальном 
мире такая вещь, как null, не существует), таким образом желательно, чтобы 
системы баз данных были максимально приближены к реальному миру. 
    20.14. Heath IJ. IBM internal memo. — 1971. 
    В статье впервые вводится термин (и концепция) "внешнего соединения". 
    20.15. Lacroix M., Pirotte A. Generalized Joins //ACM SIGMOD. — 1976. — 8, 
№ 3. 
    20.16. Liu К.-С., Sunderraman R. Indefinite and Maybe Information in 
Relational Databases//ACM TODS. — 1990.— 15, № 1. 
    Содержит набор формальных предложений для расширения реляционной модели до 
работы с возможной информацией (например, "деталь Р7 может быть черной") и с 
неопределенной или дизъюнктивной информацией (например, "деталь Р8 или деталь 
Р9 красная"). Представлены таблицы истинности для нормальной (определенной), 
возможной и неопределенной информации. Для эксплуатации таблиц истинности 
расширены операторы выборки, проекции, произведения, объединения, пересечения 
и вычитания. 
    20.17. Maier D. The Theory of Relational Databases.— Rockville, Md.: 
Computer Science Press, 1983. 
    20.18. McGoveran D. Nothing from Nothing // Database Programming & 
Design.— 1993. — 6, № 12. — Part I; 1994. — 7, № 1. — Part II; № 2. — Part 
III; № 3 — Part IV. 
    Работа состоит из четырех частей. В части I показано определяющее значение 
логики в системах баз данных. В части II объясняется, почему эта логика должна 
быть двухзначной и почему попытки использовать трехзначную логику не 
приветствуются. В части III рассматривается, как можно "разрешить" проблемы 
трехзначной логики. И наконец, в части IV приводится ряд прагматических 
решений этих проблем. 
    20.19. RescherN. Many-Valued Logic. — New-York, N.Y.: McGraw-Hill, 1969. 

    Ответы к некоторым упражнениям 

    20.1. a) unk; б) true', в) true', г) unk; я) false', e) false (обратите 
внимание на то, что IS_UNK никогда не возвращает unk); ж) false; з) true. 
    20.2. a) unk; б) unk; в) true; г) false; д) unk; e) true; ж) false. 
    20.3. Потому что "isjJNKU)" возвращает true тогда и только тогда, когда 
"xQy" возвращает unk (для произвольных 9 и у), и возвращает false тогда и 
только тогда, когда "х =у <жх*у" возвращает true (для произвольного значения 
у, которое не является UNK-значением). 
    20.4. Потому что (например, "mayby-выборка") "MAYBE_RESTRICT л WHERE p" 
аналогично "R WHERE MAYBE (р)". 
    20.5. Четыре унарных оператора могут быть определены следующим образом (А 
— единственный операнд): 
    А 
    NCTW) 
    A OR NOT (A) 

    562	Часть V. Дополнительные аспекты 

    A AND NOT (A) 

    16 бинарных операторов могут быть определены следующим образом (А и В — 
два операнда): 

    A OR NOT (A)   OR В OR NOT (В) 
    A AND NOT (Л)   AND В AND NOT (В) 
    A 
    NOT (Л) 
    Я 
    NOT (В) 
    
    A OR В 
    A AND В 
    Л OR NOT (B) 
    A AND NOT (B) 
    ЫОТ(Л)   OR fl 
    NOT И)   AND В 
    
    NOT (Л)   OR NOT(B) 
    NOT'(^)   AND NOT(S) 
    ШОТ(Л)   OR B)   AND   (NOT(B)   OR Л) 
    даОТ(Л)   AND B)   OR   (NOT(B)   AND Л) 

    20.6. См. комментарий к [20.12]. 
    20.7. Корректен вариант (в). Для подробного обсуждения см. [20.8]. 
    20.8. Мы кратко опишем представление, используемое в DB2. В этом продукте 
фирмы IBM столбец таблицы, который может принимать null-значения, физически 
представлен в хранимой базе данных двумя столбцами — столбец непосредственно 
данных и скрытый столбец индикатора. Значение столбца индикатора, состоящее из 
двоичных единиц, указывает, что соответствующее значение столбца данных должно 
игнорироваться (т.е. приниматься как null-значение); значение столбца 
индикатора, состоящее из двоичных нулей, указывает, что соответствующее 
значение столбца данных должно быть принято как реальное значение. Конечно, 
столбец индикатора всегда скрывается от пользователя. 
    20.9. Скорее всего, данное отношение не имеет закономерного предиката 
вообще. Здесь можно сказать что-нибудь вроде того, что деталь с точно 
установленным номером ИЛИ имеет точно установленный цвет, ИЛИ не имеет 
никакого цвета. Но эта формулировка, по существу, бессмысленна! Это еще раз 
подтверждает, что использование null-значений подрывает основу реляционной модели. 

    Глава 20, Отсутсвующая информация	563 

