Расширение реляционной модели для лучшего отражения семантики

2009 г.

Расширение реляционной модели для лучшего отражения семантики

Э. Ф. Кодд
Перевод: М.Р. Когаловский

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

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

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

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

 
AND|   F   ω   T        OR|   F   ω   T
   |                      |
 F |   F   F   F        F |   F   ω   T
 ω |   F   ω   ω        ω |   ω   ω   T
 T |   F   ω   T        T |   T   T   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:

ω TS VU UR.

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

RS SR TU UT TU UV.

Заметим, между прочим, что такая схема для неопределенных значений обладает некоторыми свойствами, которые могут, на первый взгляд, показаться парадоксальными. Возьмем, например, отношение 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

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

Операция OUTER UNION (внешнее объединение)

Пусть R, S – отношения, которые имеют в качестве общего(-их) атрибута(-ов) только B и никаких других. Пусть A – оставшийся(-еся) атрибут(ы) (атрибуты) в R, а C – в S. Наконец, пусть

R₁(A, B, C) = R × (C:ω)

S₁(A, B, C) = (A:ω) × S,

где × обозначает символ операции декартова произведения. Тогда внешнее объединение R и S определяется как

R S = R₁ ∪ S₁

Заметим, что в частном случае, когда R и S совместимы по объединению,

R S = R ∪ S

Пример применения оператора OUTER UNION:

R(A B C)     S(B D)
  p 1 2        2 u
  p 2 1        3 v
  q 1 2

  R  S (A B C D)
          p 1 2 ω
          p 2 1 ω
          q 1 2 ω
          ω 2 ω u
          ω 3 ω v

Подобным же образом мы можем также определить OUTER версии операций INTERSECTION и DIFFERENCE.

Как при естественном соединении, так и при эквисоединении, происходит потеря информации, если соединяемые отношения не имеют равных проекций на атрибуты соединения. Для того чтобы сохранить информацию независимо от равенства этих проекций, нам требуется операция соединения, которая может генерировать неопределенные значения всякий раз, когда это требуется. Такого рода операции были независимо предложены в [16, 20, 23, 44].

Операция OUTER THETA-JOIN (внешнее тета-соединение)

Пусть заданы отношения R = R(A, B₁) и S = S(B₂,C) с атрибутами B₁ и B₂, определенными на общем домене, и пусть:

T = R[B₁ θ B₂]S

R₁ = R – T[A, B₁]

S₁ = S – T[B₂, C].

Тогда внешнее тета-соединение определяется как

R[B₁ B₂]S = T ∪ (R₁ × (B₂:ω,C:ω)) ∪ ((A:ω,B₁:ω) × S₁),

где ∪ обозначает объединение, а × – декартово произведение.

Пример OUTER EQUI-JOIN (внешнего эквисоединения):

S ( S# SCITY )    J ( J# JCITY )
    s1  c4            j1  c1
    s2  c2            j2  c2
    s4  c1            j3  c2
    s6  c1            j4  c5
    s7  c3

Пусть SJ = S[SCITY JCITY]J. Тогда:

SJ ( S# SCITY JCITY J# )
     s1  c4    ω    ω
     s2  c2    c2   j2
     s2  c2    c2   j3
     s4  c1    c1   j1
     s6  c1    c1   j1
     s7  c3    ω    ω
     ω   ω     c5   j4

Операция OUTER NATURAL JOIN (внешнее естественное соединение)

Пусть, как и ранее, заданы отношения R = R(A, B₁) и S = S(B₂, C), а также отношения T, R₁ и S₁, определенные так же, как выше, но с заменой "тета" на "=". Тогда внешнее естественное соединение R по B₁ с S по B₂ определяется как

R[B₁ B₂]S = T[A,B₁,C] ∪ (R₁ × (C:ω)) ∪ ((A:ω) × S₁).

Пример операции OUTER NATURAL JOIN.

Пусть T(S#,CITY,J#) = S[SCITY JCITY]J, где отношения S и J представлены приведенными выше таблицами. Тогда:

T ( S# CITY J# )
    s1  c4  ω
    s2  c2  j2
    s2  c2  j3
    s4  c1  j1
    s6  c1  j1
    s7  c3  ω
    ω   c5  j4

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

3. СВЯЗЬ С ЛОГИКОЙ ПРЕДИКАТОВ

Опишем два различных способа, с помощью которых реляционная модель может быть связана с логикой предикатов. Предположим, что мы рассматриваем первоначально базу данных как некоторое множество формул логики предикатов первого порядка. Предположим также, что каждая такая формула не имеет свободных переменных и находится в максимально возможной атомарной форме (например в A & B были бы замещены составляющие формулы A и B). Допустим теперь, что большинство формул является простыми утверждениями вида Pab ... z (где P – предикат, а a, b, .., z – константы), и что количество различных предикатов в базе данных мало по сравнению с количеством простых утверждений. Такую базу данных называют обычно форматированной, поскольку ее основная часть поддается вполне регулярной структуризации. Один из очевидных способов состоит в том, чтобы факторизовать предикат, общий для некоторого множества простых утверждений, и затем интерпретировать это множество как экземпляр n-арного отношения, а предикат – как имя этого отношения. Структурированная таким образом база данных будет далее состоять из двух частей: регулярной части, состоящей из совокупности изменяющихся во времени отношений соответствующей степени (которая иногда называется экстенсионалом (extension)), и нерегулярной части, состоящей из формул логики предикатов, которые являются относительно устойчивыми во времени (ее называют иногда интенсионалом (intension), хотя это, возможно, и не то, что логики Рассел (Russell) и Уайтхед (Whitehead) первоначально подразумевали под этим термином). Можно также рассматривать интенсионал как множество ограничений целостности (т. е. условий, которые определяют все допустимые экстенсионалы) и таким образом отделить эти понятия от изменчивости во времени.

Возможны альтернативы при интерпретации отсутствия некоторого кортежа в базовом отношении, которое может рассматриваться как утверждение о том, что истинностное значение соответствующей атомарной формулы является (1) неизвестным или (2) ложным. Если принимается альтернатива (1), мы имеем интерпретацию, соответствующую гипотезе открытого мира. Если же принимается альтернатива (2), то мы имеем интерпретацию, соответствующую гипотезе замкнутого мира (см. [28]). Хотя интерпретация, соответствующая гипотезе замкнутого мира, обычно принимается для коммерческих баз данных, существует случай, когда следует допустить, чтобы некоторые отношения (например P-отношения из разд. 7) имели интерпретацию, соответствующую гипотезе открытого мира, в то время как другие отношения (скажем E-отношения для стержневых типов сущностей, обсуждаемых в разд. 5 и 6) имеют интерпретацию, соответствующую гипотезе замкнутого мира.

Независимо от того, принимается ли интепретация открытого или замкнутого мира, реляционная модель весьма близка к логике предикатов. Эта близость является причиной существования большого числа реляционных подъязыков данных, основанных на логике предикатов. Исследование и основательное сравнение таких языков можно найти в работах [20, 27].

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

Можем ли мы более точно определить, из чего образуется простое утверждение?
Какие другие виды регулярности могут быть полезными в форматированной базе данных?
В какой степени эти дополнительные виды регулярности могут быть представлены в легко анализируемых структурах данных, а не в процедурах?

Пытаясь дать ответы на эти вопросы, мы будем использовать для мотивации расширений реляционной модели такие популярные неформальные термины, как "сущность", "свойство" и "ассоциация". В конце концов, мы приходим к формальной системе, названной RM/T (здесь T означает "Тасманию", где эти идеи впервые были представлены [9]). Эта система может интерпретироваться многими различными способами. Некоторые интерпретации должны удовлетворять так называемой школе двух концепций в семантическом моделировании, в то время как другие должны удовлетворять школе трех концепций (см. [25, стр. 27]).

Назад Содержание Вперёд