Расширения алгебры, допускающие неопределенные значения

Смысл двух наиболее важных типов неопределенного значения заключается в том, что "значение неизвестно в настоящее время" или "свойство неприменимо". Подход, при котором допускаются оба типа неопределенных значений, описан в работе [40]. Попытка достаточно общего решения проблемы оперирования неполной информацией описывается в [22]. Здесь мы ограничимся только первым типом неопределенного значения – "значение неизвестно в настоящее время" – и обозначим его ω (см. более подробное обсуждение в [5]). Следующую трактовку следует рассматривать как предварительную и нуждающуюся в дальнейшем исследовании.

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

Первый возникающий вопрос заключается в том, каково истинностное значение выражения x = y, если x или y, или то и другое является неопределенным значением? Уместным результатом в каждом из этих случаев является неизвестное истинностное значение, а не истина или ложь. В соответствии с этим, для использования при выборке данных из баз данных, которые могут содержать неопределенные значения, мы выбираем трехзначную логику. Будем использовать для обозначения неизвестного истинностного значения тот же самый символ "ω", поскольку истинностные значения могут храниться в базах данных, а мы хотели бы, чтобы интерпретация всех неизвестных и неопределенных значений была однородной. Трехзначная логика базируется на следующих таблицах истинности:

AND| F ω T OR| F ω T

NOT(F) = T; NOT(ω) = ω; NOT(T) = F

Кванторы существования и всеобщности ведут себя подобно многократно применяемым OR и AND соответственно.

Что касается принадлежности множеству

и включения множеств

, то мы будем назначать истинностное значение ω выражениям: ω

S и {ω}

S

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

Каждое вхождение ω в выражении может быть замещено некоторым значением, отличным от неопределенного (возможно, разными значениями для разных вхождений) таким образом, чтобы значением выражения становится T.

Каждое вхождение ω в выражении может быть замещено некоторым значением, отличным от неопределенного (возможно, разными значениями для разных вхождений) таким образом, чтобы значением выражения становится F.

Будем называть это принципом подстановки неопределенного значения (null substitution principle). Описанная выше трехзначная логика совместима с этим принципом. Следующие примеры иллюстрируют применение этого принципа к принадлежности множеству и к включению множеств. Пусть

обозначает пустое множество, а R, S, T, U, V – следующие отношения:

R S T U V

ω ω ω 1 x ω x ω

1 1 y ω ω 3 y 3 2 z 1

Следующие выражения имеют истинностное значение F:

ω

S V

U U

R.

Следующие выражения имеют значение истинности ω:

R

S S

R T

U U

T T

U U

V.

Заметим, между прочим, что такая схема для неопределенных значений обладает некоторыми свойствами, которые могут, на первый взгляд, показаться парадоксальными. Возьмем, например, отношение EMP (служащие) c атрибутами NAME (фамилия) и AGE (возраст). Выражение

(EMP[AGE≤50] ∪ EMP[AGE>50])[NAME]

не обязательно пропроизводит множество всех имен служащих. Однако, если мы интерпретируем EMP[AGE≤50] как множество кортежей EMP, об AGE-компонентах которых в базе данных известно, что они меньше чем или равны 50, а EMP[AGE>50] – как множество кортежей, об AGE-компонентах которых известно, что они больше 50, то впечатление парадоксальности исчезает. В такого рода интерпретации не требуется, чтобы все тавтологии двузначной логики были сохранены в трехзначной логике (в противоположность [40]).

Применяя принцип подстановки неопределенного значения для проверки неравенств, мы можем избежать задания ω какого-либо места в числовом или лексикографическом упорядочении. В соответствии с этим принципом, мы назначаем истинностное значение ω выражениям вида x θ y, где θ – какое-либо из отношений <, ≤, ≥, >, всякий раз, когда x или y является неопределенным значением.

Для каждого положительного целого n кортеж длины n, состоящий из неопределенных значений (каждое из которых, конечно, сопровождается его атрибутом), является допустимым кортежем. Но небазовое n-арное отношение может содержать не более одного такого кортежа, а базовое отношение не может содержать таких кортежей вовсе. Как обычно, никакое отношение не может содержать кортежей-дубликатов. При применении этого правила отсутствия дубликатов (nonduplication rule) неопределенное значение в одном кортеже считается таким же, как и неопределенное значение в другом кортеже. Может показаться, что такое отождествление одного неопределенного значения с другим противоречит нашему назначению истинностного значения сравнения ω = ω.

Однако отождествление кортежей для удаления дубликатов является операцией более низкого уровня детализации, чем сравнение по равенству при вычислении условий выборки. Поэтому здесь можно принять иное правило. Следствия для UNION, INTERSECTION и DIFFERENCE иллюстрируются ниже.

R S R ∪ S R ∩ S R – S

ω ω ω ω ω ω ω ω u ω u ω u ω u ω u 1 u 1 u 1 u 1 ω 1 ω 1 ω 1

Рассмотрим теперь влияние этого типа неопределенного значения на остальные операции реляционной алгебры. Операция CARTESIAN PRODUCT (декартово произведение) этому влиянию не подвержена. Операция PROJECTION (проекция ) ведет себя, как и ожидалось, если помнить, как применяется правило отсутствия дубликатов к кортежам с компонентами, имеющими неопределенное значение. Следующие примеры иллюстрируют операцию проекции:

R R[B, C] R[C] A B C   B C     C

u ω ω ω ω ω

v 1 ω 1 ω

ω ω 1 ω 1 1 x 1 ω

y ω 1

Операция THETA-JOIN (тета-соединение) производит конкатенацию пар кортежей при условии, что удовлетворяется некоторое заданное условие θ, налагаемое на некоторые компоненты этих кортежей. При вычислении этого условие для любой возможной пары кортежей вырабатывается истинностное значение F, ω или T. Мы оставляем лишь операцию соединения, конкатенирующую только такие пары кортежей, для которых при вычислении условия вырабатывается значение T и называем его TRUE THETA JOIN (тета-соединение по "истине"). Кроме того, мы вводим операцию MAYBE THETA JOIN (тета-соединение "может быть"), конкатенирующую только те пары кортежей, для которых при вычислении заданного условия вырабатывается ω.

Версия MAYBE ("может быть") некоторой операции обозначается путем помещения символа ω после тета-символа (например, =ω) или символа операции (например, ÷ω).

Следующие примеры иллюстрируют операторы TRUE EQUI-JOIN и MAYBE EQUI-JOIN, а также TRUE LESS-THAN JOIN и MAYBE LESS-THAN JOIN.

R S R[B=C]S R[B =ω C]S

A B C A B C A B C

u ω ω ω 2 2 u ω ω

ω 2 2 u ω 2 w 1 ω 2 ω

w 1 ω

R[B<C]S R[B <ω C]S

A B C A B C

ω 1 2 то же, что и R[B =ω C]S

Если нужно выбрать только те строки из R, компонент B которых содержит ω, мы можем выполнить операцию MAYBE EQUI-JOIN над отношением R и отношением T, единственным элементом которого является некоторое значение, отличное от неопределенного (годится любое такое значение при условии, что оно выбрано из того же самого домена, на котором определен атрибут B), а затем применить к результату операцию проекции PROJECT на атрибуты A, B. Для приведенного выше случая читатель может проверить, что окончательный результат представляет собой отношение, единственным элементом которого является пара (A:u, B:w). Обработка неопределенных значений операцией THETA-SELECT (тета-селекция) для версий TRUE и MAYBE следует тому же принципу, что и в случае операций THETA-JOIN.

Подобным же образом выполняется операция деления (DIVISION). Исходная операция, основанная на истинном включении (проверке включения, которая дает значение T), сохраняется и называется TRUE DIVISION. Вводится также новая операция ÷ω, основанная только на включении "может быть" (проверке включения, вырабатывающей ω) и называемая MAYBE DIVISION. Следующие примеры иллюстрируют эти два вида деления.

R S T R[B ÷ C]S R[B ÷ C]T

A B C C     A         A

u 1 2 2 u пусто u 2 3 ω

u 3 R[B ÷ω C]S R[B ÷ω C]T

w 2     A          A

w ω w u

z 3 w

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

Содержание раздела