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

2009 г.

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

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

2. РЕЛЯЦИОННАЯ МОДЕЛЬ

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

Чтобы помочь отличать реляционные системы от нереляционных, мы предлагаем следующие определения. Система базы данных является полностью реляционной (fully relational), если она поддерживает:

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

Система базы данных, которая поддерживает аспекты (i) и (ii), но не (iii), является полуреляционной (semirelational). Заметим, что полностью реляционная система не обязана поддерживать реляционную алгебру в буквальном смысле, но должна быть не менее мощной. Реляционная алгебра не только является мерилом функциональных возможностей; она призвана также быть точным интеллектуальным инструментом, позволяющим иметь дело с такими вопросами, как проектирование модели, определение представлений и реструктуризация.

2.1. Структуры

Домен (domain) – это множество однотипных значений: например, все возможные серийные номера деталей в данной инвентарной ведомости или все возможные даты для класса регистрируемых событий. Домен является простым (simple), если все его значения атомарны (не декомпозируются системой управления базой данных).

Пусть имеется n (n > 0) не обязательно различных доменов D₁, D₂, ..., D_n. Декартово произведение ×{D_i: i = 1, 2, ..., n} – это множество всех n-кортежей <t₁, t₂, ..., t_n> таких, что t_i D_i для всех i. Отношение R определяется на этих n доменах, если оно является подмножеством их декартового произведения. Говорят, что такое отношение имеет степень n.

Вместо множества индексов (1, 2, ..., n) мы можем использовать любое неупорядоченное множество , если мы ассоциируем с каждым компонентом кортежа не только его домен, но также и отличающий его индекс, который мы будем впредь называть его атрибутом. Соответственно, n различных атрибутов отношения степени n характеризуют n разных применений доменов, на которых определено данное отношение (напомним, что число различных доменов может быть меньшим, чем n). Тогда кортеж вместо последовательности <v₁, v₂, ..., v_n> становится множеством пар (A:v), где A – некоторый атрибут, а v – значение, взятое из домена атрибута A.

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

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

Обозначение R(A:a, B:b, C:c, ...) используется для представления изменяющегося во времени отношения R, имеющего атрибут A, который принимает значения из домена a, атрибут B, который принимает значения из домена b и т. д. Если в некотором контексте рассуждений домены могут игнорироваться, то такое отношение будет представляться как R(A, B, C, ...) или даже просто как R. Однако, что для корректной интерпретации выражения (и в особенности оператора присваивания) порядок перечисления атрибутов может быть существенным (см. THETA-JOIN ниже).

Реляционная база данных – это изменяющаяся во времени совокупность данных, допускающая доступ к ним всем и их обновление таким образом, как если бы они были организованы в виде совокупности изменяющихся во времени табличных (не иерархических) отношений соответствующих степеней, определенных на заданном наборе простых доменов. Базовые отношения (base relation) – это такие отношения, которые определяются независимо от других отношений в базе данных в том смысле, что никакое базовое отношение полностью не выводится (независимо от времени) из каких-либо других базовых отношений. Выводимые отношения (derived relation) – это такие отношения, которые могут полностью выводиться из базовых отношений. Это такой вид отношений, которые обычно служат для обеспечения пользователей прикладных программ их собственными представлениями (view) базы данных. Объявленные отношения включают все базовые отношения, а также могут включать выводимые отношения. Позднее, когда будут введены некоторые дополнительные понятия, мы определим полувыводимые отношения (semiderived relation) – некоторый класс отношений, включающий выводимые отношения.

Если U – некоторая совокупность атрибутов некоторого отношения, то U-компонентомкортежа t этого отношения назовем множество пар (A:v), полученных путем удаления из t тех пар, которые содержат атрибуты, не принадлежащие U.

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

С каждым отношением ассоциируется множество возможных ключей. Cовокупность атрибутов K отношения R называется возможным ключом (candidate key) R, если обладает следующими независимыми от времени свойствами.

Никакие две строки R не содержат один и тот же K-компонент.
Если какой-либо атрибут исключается из K, то свойство уникальности (i) утрачивается.

Для каждого базового отношения один из возможных ключей выбирается в качестве первичного ключа (primary key). Для заданной базы данных те домены, на которых определяются простые (т.е. состоящие из одного атрибута) первичные ключи, называются первичными доменами (primary domain) этой базы данных. Заметим, что не все атрибуты компонента составного (т.е. состоящего из нескольких атрибутов) первичного ключа обязательно должны быть определены на первичных доменах. Первичные домены имеют важное значение для поддержки некоторых транзакций, например "удалить из базы данных поставщика 3". Мы хотим здесь удалять 3 всякий раз, когда это значение означает порядковый номер поставщика, а не что-либо другое.

Все операции вставки, обновления и удаления, выполняемые над базовыми отношениями, ограничиваются двумя следующими правилами:

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

Правило 2 (целостность по ссылкам): Допустим, что некоторый атрибут A составного (т.е. состоящего из нескольких атрибутов) первичного ключа отношения R определяется на первичном домене D. Тогда в любой момент времени для каждого значения v атрибута A в отношении R должно существовать базовое отношение (скажем, S) с простым первичным ключом (например, B) такое, что v является значением B в S.

Реляционная модель состоит из:

совокупности изменяющихся во времени табличных отношений (с указанными выше свойствами – особо отметим ключи и домены);
правил вставки-обновления-удаления (Правила 1 и 2, сформулированные выше);
реляционной алгебры, описываемой ниже в подразделах 2.2 и 2.3.

C реляционной моделью тесно связаны различные идеи декомпозиции, являющиеся семантическими по своей природе (как основанные на инвариантных во времени свойствах изменяющихся во времени отношений). Примерами таких идей являются (естественные) соединения без потерь и функциональные зависимости [6], многозначные зависимости [10, 44] и нормальные формы. Подробности можно найти в [3]; см. также [39]¹⁾.

2.2. Реляционная алгебра (без учета неопределенных значений)

Поскольку отношения являются множествами, здесь применимы обычные теоретико-множественные операции, такие как UNION (объединение), INTERSECTION (пересечение) и SET DIFFERENCE (вычисление разности множеств). Однако их применение ограничивается только парами отношений, совместимых по объединению (union-compatible), т.е. таких отношений, между атрибутами которых имеется взаимно-однозначное соответствие, причем соответствующие атрибуты определены на одном и том же домене. Благодаря этому ограничению гарантируется, что результат является отношением. Операция CARTESIAN PRODUCT (вычисление декартова произведение) применима без какого-либо ограничения.

Определим теперь операции специально для манипулирования n-арными отношениями. Далее R и S обозначают отношения; A, B₁, B₂ и C – совокупности атрибутов; c – кортеж соответствующей степени и с соответствующими доменами.

Операция THETA-SELECT (иногда называемая RESTRICT (ограничение))

Пусть θ – какое-либо из бинарных отношений <, ≤, =, ≥, >, ≠, применимое к атрибуту(-ам) A и кортежу c. Тогда R[A θ c] есть множество кортежей из R, A-компоненты каждого из которых находятся в отношении θ с кортежем c. Вместо кортежа c может использоваться другой атрибут или другая совокупность атрибутов B отношения R при условии, что A и B определены на общих доменах. Тогда R[A θ c] – это множество кортежей из R, каждый из которых удовлетворяет тому условию, что его A-компонент находится в отношении θ с его B-компонентом. Если θ представляет собой равенство (очень распространенный случай), операция THETA-SELECT называется просто SELECT (селекцией).

Примеры THETA-SELECT:

R ( A B C )     R[A ≠ r] ( A B C )
    p 1 2                  p 1 2
    p 2 1                  p 2 1
    q 1 2                  q 1 2
    r 2 5
    r 2 3       R[A = r] ( A B C )
                           r 2 5
                           r 2 3
R[B > C] ( A B C )
           p 2 1

Операция PROJECTION (проекция)

R[A₁, A₂, ... A_n] – это отношение, получаемое путем удаления из R всех столбцов за исключением тех, которые специфицируются атрибутами A₁, A₂, ... A_n, и последующего удаления избыточных строк-дубликатов.

Примеры PROJECTION:

R ( A B C )     R[A,B]  (A B)
    p 1 2                p 1
    p 2 1                p 2
    q 1 2                q 1
    r 2 5                r 2
    r 2 3
                R[B,C]  ( B C )
R[B] ( B )                1 2
       1                  2 1
       2                  2 5
                          2 3

Теперь мы можем определить третий класс отношений. Полувыводимые отношения – это такие отношения, у которых некоторая проекция (по крайней мере, с одним атрибутом) является выводимым отношением (см. о слабой избыточности в [5]). Если, например, R(A, B) является базовым отношением, S(A, C) – это такое отношение, что S[A] = (R[B = b])[A], и атрибут C определен на некотором домене, не используемом в каком-либо из базовых отношений (следовательно, отношение S не является выводимым), то S является полувыводимым отношением. Как мы увидим, существует много применений полувыводимых отношений. Заметим, что требование обеспечения минимальной избыточности при проектировании реляционных баз данных ничем не обусловлено, хотя это один из возможных вариантов. Таким образом, объявленные отношения наряду с базовыми отношениями могут включать полувыводимые и даже выводимые отношения.

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

Пусть заданы отношения R(A, B₁) и S(B₂, C) такие, что B₁ и B₂ определены на общем домене, и пусть θ – какое-либо из бинарных отношений =, <, <, ≤, ≥, >, ≠, которое применимо к домену атрибутов B₁, B₂. Тета-соединение R по B₁с S по B₂ обозначается как R[B₁ θ B₂]S. Это – конкатенация строк отношения R со строками отношения S, формируемая всякий раз, когда компонент B₁ строки R находится в отношении θ с компонентом B₂ строки S. Если отношение θ является равенством, операция THETA-JOIN называется EQUI-JOIN (эквисоединением). Из всех операций THETA-JOIN только EQUI-JOIN дает результат, который обязательно содержит два идентичных столбца (один продуцированный из B₁, а другой – из B₂). В общем случае допускается использование в качестве θ произвольного бинарного отношения, которое применимо к домену атрибутов B₁и B₂.

Примеры THETA-JOIN:

R ( A B C )             S ( D E )
    p 1 2                   2 u
    p 2 1                   3 v
    q 1 2                   4 u
    r 2 5
    r 3 3
	
R[C = D]S ( A B C D E )
            p 1 2 2 u
            q 1 2 2 u
            r 3 3 3 v
			
R[C > D]S ( A B C D E )
            r 3 3 2 u
            r 2 5 2 u
            r 2 5 3 v
            r 2 5 4 u

Если отношения, к которым применяется оператор THETA-JOIN, имеют какие-либо общие имена атрибутов, то должны быть заданы имена атрибутов результирующего отношения. Например, если у обоих отношений R и S имеются атрибуты A, B, и все эти четыре атрибута определяются на некотором общем домене, мы можем определить несколько возможных θ-соединений R с S. Одно из таких определений:

T(D, E, F, G) = R(A, B)[B > B]S(A, B).

При использовании соглашения о порядке перечисления атрибутов это означает, что источником значений для атрибута D отношения T является атрибут A отношения R. Подобным же образом, источниками значений атрибутов E, F и G отношения T являются, соответственно, атрибут B отношения R, а также атрибуты A и B отношения S.

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

Такое соединение ничем не отличается от EQUI-JOIN за исключением того, что в этом случае удаляются избыточные столбцы, сгенерированные при выполнении соединения. Естественное соединение – это соединение, используемое при нормализации совокупности отношений.

Пример NATURAL JOIN: Пусть отношения R и S заданы приведенными выше таблицами. Тогда:

R[C*D]S ( A B C E )
          p 1 2 u
          q 1 2 u
          r 3 3 v

Операция DIVIDE (деление)

Пусть заданы отношения R(A, B₁) и S(B₂, C) такие, что B₁ и B₂ определены на одном и том же домене (доменах). Тогда R[B₁÷B₂]S – это максимальное подмножество R[A] такое, что его декартово произведение с S[B₂] включается в R. Этот оператор является алгебраическим двойником квантора всеобщности.

Пример DIVIDE:

R ( A B )       S ( C )
    p 1             1
    p 2             3
    p 3
    q 1       R[B÷C]S ( A )
    r 1                 p
    r 3                 r

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