Главная » SQL, Базы данных » ОБЗОР КОНЦЕПЦИИ ТРЕХЗНАЧНОЙ ЛОГИКИ

0

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

Логические операторы

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

2     Однако   следует   особо   отметить,   что   в   любом   из   перечисленных   выше   случаев   как   таковой "отсутствующей   информации"   нет.   Например,   если   к   сотруднику   ‘   Joe’   понятие    комиссионного   воз награждения  "не  применимо",  значит,  к   нему  не  применим  сам  принцип   выплаты  комиссионных  и, таким  образом,  здесь  нет  никакой  отсутствующей  информации.  (Тем   не   менее,  если  кортеж  с  описанием сотрудника    ‘Joe’    содержит    "неприменимое     неопределенное    значение"    в    атрибуте    комиссионного вознаграждения,  этот  кортеж  вообще   не  является  кортежем  с  описанием  сотрудника,  поскольку  он не   является   корректной   реализацией   предиката   "Описание   сотрудника".   В   действительности,   он   даже не является кортежем.)

логикой. Третьим логическим значением здесь является значение unknown, на которое мы достаточно часто, но не постоянно, будем ссылаться с помощью сокращения ипк. Ниже приведены таблицы истинности для операторов AND, OR и NOT в трехзначной логике (в таблицах используются следующие сокращения: t — true, f—false, и ипк).

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

А > В AND В > С :    false

А > В OR В > С : ипк

А < В OR В < С : true NOT ( A = С ) : ипк

, Тем не менее, для реализации трехзначной логики одних только операторов AND, OR и NOT недостаточно [19.11]. Еще одним важным оператором является  оператор MAYBE (возможно) [19.5]. Таблица истинности данного оператора показана ниже.

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

EMP WHERE MAYBE ( JOB = ‘Programmer’ AND

DOB < DATE (‘1971-1-18′) AND SALARY < 50000.00 )

(Здесь предполагается, что атрибуты JOB, DOB и SALARY переменной отношения ЕМР имеют типы CHAR, DATE и RATIONAL, соответственно.) Но без оператора MAYBE ЭТОТ же запрос будет выглядеть следующим образом.

ЕМР WHERE  ( JOB = ‘Programmer’ OR IS_UNK ( JOB ) )

AND    ( DOB < DATE (‘1971-1-18′) OR IS_UNK ( DOB ) )                                                                                 ( SALARY < 50000.00

OR IS_UNK ( SALARY ) )

AND NOT ( JOB = ‘Programmer’ AND

DOB < DATE (‘1971-1-18′) AND

SALARY < 50000.00 )

3 Чтобы составить примеры, приведенные в данной главе, необходимо было принять допущение, что язык Tutorial D включает средства поддержки значений UNK и трехзначной логики. Фактически такая поддержка, разумеется, не предусмотрена.

Здесь предполагается существование другого истинностного оператора IS_UNK, который принимает в качестве параметра единственный скалярный операнд и возвращает значение true, если этот операнд равен UNK, или значение false — в противном случае. (Кстати, следует отметить, что определенная версия оператора IS_DNK необходима и для операндов, отличных от скалярных. Но автор не предпринимает попытку определить здесь  подобную  конструкцию,  поскольку  решение  этой  задачи  связано  со  слишком большими сложностями, к тому же он вообще не испытывает доверия к утверждению о необходимости поддержки трехзначной логики.)

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

может оказаться оператор TRUE_OR_MAYBE (который возвращает true, если его операнд

равен true или ипк, а в противном случае возвращает false), как показано в [19.5].

См. также аннотацию к [ 19.11] в разделе "Дополнительная литература".

Кванторы

Вопреки тому несомненному факту, что для представления большинства примеров в этой книге используется реляционная алгебра, а не исчисление, нам все же следует рассмотреть влияние трехзначной логики на вычисление кванторов реляционного исчисления  EXISTS  и  FORALL.  Как  говорилось  в  главе  8,  кванторы  EXISTS  И  FORALL определяются как итерационные конструкции из операторов OR и AND, соответственно. Иначе говоря, если r —  отношение с кортежами tl, t2, …, tm, V — переменная области значений, которая принимает значения из данного отношения г , а р (V) — логическое выражение, в котором V используется как свободная переменная, то выражение

EXISTS   V   (   р   (   V   )    )

по определению эквивалентно следующему выражению. false  OR  p   (   tl   )   OR   …   OR  p   (   tm   ) Аналогичным образом, выражение

FORALL V  (  р   (  V  )   )

по определению эквивалентно следующему выражению.

true AND  p   (   tl   )   AND   …   AND  p   (   tm   )

Что произойдет, если для некоторого i значение p(ti) будет равно unk? Например,

пусть отношение r содержит следующие кортежи.

(                                          1,                                        2,                                             3    )

(                                           1 ,    2 ,    U N K )

(   UNK,   UNK,   UNK   )

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

EXISTS  v  ( v.c > 1 )                                                                                                                                                                                                          :  true EXISTS V( V.B > 2 )                                             : unk EXISTS V( MAYBE ( V.A > 3 ) )  : true EXISTS V( IS_UNK ( V.C ) )    : true

FORALL V( V.A > 1 )                                            : false FORALL V( V.B > 1 )                                             : unk FORALL V ( MAYBE ( V.C > 1 ) )  : false

Другие скалярные операторы

Рассмотрим следующее числовое выражение.

WEIGHT *  454

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

■  WEIGHT + 454                                         ■ 454 + WEIGHT                                             ■ + WEIGHT

■  WEIGHT 454                                         ■ 454 WEIGHT                                             ■ WEIGHT

■  WEIGHT * 454                                        ■ 454 * WEIGHT

■  WEIGHT / 454     ■ 454 / WEIGHT

Примечание. Вероятно, следует сразу же отметить, что подобная трактовка числовых выражений может привести к появлению некоторых аномалий.  Например, выражение WEIGHT WEIGHT, значением которого должен быть нуль,  на самом деле будет иметь значение UNK, а результатом вычисления выражения  WEIGHT/0 будет также величина UNK  вместо  обычного  в  данном  случае  сообщения  об  ошибке  деления  на  нуль (безусловно, в обоих выражениях предполагается, что атрибут WEIGHT содержит величину UNK). Такие аномалии будут игнорироваться до особого упоминания.

Аналогичные рассуждения применимы ко всем другим скалярным типам и операторам, за исключением логических операторов (рассматриваемых в двух предыдущих подразделах), оператора IS_UNK, описанного выше, и  рассматриваемого ниже оператора

IF_UNK. Таким образом, для символьных строк выражение А | | в возвращает UNK, если

А равен UNK, либо в равен UNK, либо оба равны UNK. (Снова следует отметить существование аномальных случаев, рассмотрение которых мы здесь опустим.)

Оператор IF_UNK получает на входе два скалярных операнда и возвращает значение первого операнда, если это не величина UNK. Если первый операнд является величиной UNK, то оператор IF_UNK возвращает значение второго операнда. Другими словами,

это — оператор преобразования величины UNK в некоторое значение, отличное от UNK.

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

EXTEND S ADD IF_UNK ( CITY, ‘City unknown’ ) AS SCITY

В результате его вычисления будет получена переменная отношения, в которой значение  атрибута  SCITY   равно   ‘City  unknown’  для  каждого   поставщика,   город которого в переменной отношения s определен как UNK.

Следует отметить, что оператор IF_UNK можно определить с помощью  оператора

IS_UNK. Точнее говоря, выражение

IF_UNK ( exp1, exp2 )

где параметры expl и ехр2 должны иметь одинаковые типы, эквивалентно следующему выражению.

IF IS_UNK ( expl ) THEN exp2 ELSE expl END IF

UNK — это не ипк

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

Проблема принадлежности величины UNK к типу

Из того факта, что шгк не является значением, прямо следует заключение, что типы (т.е. множества значении) не могут содержать величину UNK. Действительно, если бы типы могли содержать неопределенные значения какого-либо вида, то проверка ограничений целостности для них всегда завершалась бы с положительным результатом! Но, поскольку типы фактически не могут содержать величину UNK, "отношения", допускающие присутствие величины UNK, являются чем угодно, но только не реляционными отношениями. Причем это верно как для отношений, определение которых дано в главе 6, так и для отношений,  отвечающих оригинальному определению Кодда [6.1]. К обсуждению этого важного вопроса мы еще вернемся позже.

Реляционные операторы

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

Прежде всего, отметим, что на операцию произведения величина UNK никакого влия ния не оказывает.

Далее, операцию сокращения следует несколько переформулировать,  потребовав, чтобы возвращались только кортежи, для которых условие сокращения имеет значение true, т.е. эта операция не должна включать в результат кортежи, для которых условие сокращения принимает значение false или ипк.

4 Тем не менее, в стандарте SQL они рассматриваются как эквивалентные понятия (см. раздел 19.7).

Примечание. Использование именно этой формулировки неявно  предполагалось в примере с оператором MAYBE, приведенном выше, в подразделе "Логические операторы" данного раздела.

Теперь рассмотрим операцию проекции. Для получения проекции отношения требуется, кроме всего прочего, исключить дубликаты кортежей. В двухзначной  логике два кортежа tl и t2 считаются дубликатами тогда и только тогда, когда они имеют одинаковые атрибуты А1, А2, . . .,  An и для всех i (i = 1, 2, . . . ,  п)  значение Ai в кортеже tl равно значению Ai в кортеже t2. Однако в трехзначной логике некоторые из этих значений атрибутов могут содержать величину UNK, а величина UNK (как было сказано выше) не равна никакой другой величине, даже самой себе. Следует ли из этого заключить, что кортеж, который содержит величину UNK, не может быть дубликатом другого кортежа и даже самого себя?

Согласно Кодду, ответ на этот вопрос отрицателен: две величины UNK, даже если они не равны между собой, считаются дубликатами одна другой в целях исключения дубликатов кортежей [14.7]5. Это очевидное противоречие объясняется следующим образом:

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

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

■     Кортежи tl и t2 являются дубликатами один другого тогда и только тогда, когда они имеют одинаковые атрибуты А1,   А2,    . . .,   An и для всех i (i   =   1,   2,

. . .,   п), либо значение Ai в кортеже tl равно значению Ai в кортеже t2, либо оба значения Ai в кортежах tl и t2 равны UNK.

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

■       tl  =  t2;

■     tl и t2 являются дубликатами друг друга.

Объединение также подразумевает исключение избыточных дубликатов кортежей, и для этой операции также может быть применено приведенное выше определение дубликатов кортежей. Таким образом, объединение отношений r1 и r2 одного и того же типа можно определить как отношение r того же типа, тело которого состоит из всех возможных кортежей t, таких что кортеж t является дубликатом некоторого кортежа в отношении rl или в отношении r2 (или в них обоих одновременно).

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

5   Работа  [14.7]  была  первой работой Кодда, в  которой проблема отсутствия информации  рассматривалась достаточно подробно, хотя описание этой проблемы не являлось основной задачей статьи (см. главу 14). Помимо всего прочего, в статье предлагаются версии "возможного" 9-соединения, 8-выборки (т.е. сокращения), операторы деления (см. упр. 19.4), а также "внешние" версии операций соединения, пересечения, вычитания, 8-соединения и естественного соединения (см. раздел 19.5).

операции r1 MINUS r2 тогда и только тогда, когда этот кортеж является  дубликатом какого-либо  кортежа  в  отношении  rl,  но  не  является   дубликатом   ни  одного  из кортежей в отношении r2. (Для полноты картины отметим, что операция пересечения определяется аналогично, хотя она, безусловно не относится к типу примитивных. Это означает, что кортеж t попадает в результат операции rl INTERSECT r2 тогда и только тогда, когда этот кортеж является дубликатом какого-либо кортежа в отношении rl и одновременно дубликатом какого-либо кортежа в отношении r2.)

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

Здесь следует упомянуть два описанных ниже основных момента.

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

2.         Попытка поместить в отношении R дубликат кортежа (с помощью операции INSERT или UPDATE) обычно является ошибкой. В данном случае определение дубликатов кортежей взято из предыдущего подраздела.

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

Как указывалось в главе 9, ограничение целостности неформально можно рассматривать как логическое выражение, результат вычисления которого не должен быть равен false. Следовательно, ограничение целостности не будет  нарушено, если результат его вычисления будет равен значению ипк (на самом деле, это неявно предполагалось в замечаниях, приведенных выше в настоящем разделе в отношении ограничений типов). Безусловно, в этом случае точнее было бы сказать, что нам ничего не известно о том, будет ли нарушено данное ограничение целостности. Но с известной долей приближения вполне можно утверждать, что если в конструкции WHERE значение ипк рассматривается как false, то в ограничениях целостности оно рассматривается как true (и здесь в обоих случаях применяются несколько неформальные утверждения).

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

По теме:

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