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

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

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

13. ПРЕДШЕСТВОВАНИЕ СОБЫТИЙ

Сущности типа событий – это такие сущности, частью описания которых является время возникновения либо время начала и/или время окончания. Заметим, что не все сущности с атрибутами времени являются событиями. Например, ассоциативная сущность, которая указывает, что поставщик x может поставить деталь y со сроком доставки, равным трем месяцам, сама по себе не является событием.

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

Событие e₁ следует за событием e₂, если e₁ возникло/началось является строго позже, чем возникло/окончилось e₂ (в соответствии с тем, воспринимаются ли эти события как мгновенные или нет). За некоторыми типами событий безусловно следуют один или несколько других типов событий. Такое следование обычно представляет собой частичный порядок. Оно представляется в RM/T отношением безусловного следования (unconditional successor relation, US-отношение) – графовым отношением на RN-домене. (SUB:m, SUP:n) принадлежит этому отношению, если событие типа e(m) должно следовать за событием типа e(n), и не существует какого-либо промежуточного типа событий e такого, что e является безусловным преемником e(m), а e(n) – безусловным преемником e.

Подобным же образом, некоторые типы событий являются альтернативными преемниками других событий, и это альтернативное следование представляется отношением альтернативного следования (alternative successor relation, AS-отношение) таким же образом, как и безусловное следование.

Если событие e₂ следует за событием e₁, то это, очевидно, означает, что e₁ является предшественником e₂, но это не означает, что e₁ обязательно является единственным предшественником e₂, даже если e₂ – единственный преемник e₁. Следовательно, нам необходимы два дополнительных графовых отношения для описания предшествования между типами событий: UP – для безусловного предшествования и AP – для альтернативного предшествования.

Для иллюстрации использования этих графовых отношений предположим, что имеется база данных, которая включает записи заказов, помещаемые поставщиками, и записи поставок, которые принимаются как входные данные для инвентарной ведомости (соответствующие типы сущностей-событий будут называться заказами и поставками). Предположим также, что мы запрещаем принятие записей поставок в инвентарную ведомость, если не отсутствует какой-либо невыполненный заказ соответствующих товаров. Тогда отношение UP должно содержать кортеж (SUB:orders, SUP:shipments), наличие которого интерпретируется как утверждение, что каждому принятию записи поставки должен безусловно предшествовать какой-либо заказ. Кроме того, отношение AS должно включать некоторый кортеж, соответствующий утверждению, что одним из возможных событий-преемников для помещения заказа является принятие записи поставки (поставки могут, конечно, отвергаться). Такая интенсиональная информация может использоваться системой базы данных для того, чтобы подвергать сомнению допустимость принятия конкретных записей поставок, не охваченных соответствующими заказами.

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

14. КАТАЛОГ RM/T

RM/T содержит свой собственный расширяемый каталог для облегчения трансформаций между различными способами организации общей информации, которые могут встретиться в процессе интеграции представлений (view). Cтруктуру этого каталога образуют cледующие отношения:

CATR (R RELNAME RELTYPE)

CATRA (RA R A)

CATA (A ATTNAME USERKEY)

CATAD (AD A D )

CATD (D DOMNAME VTYPE ORDERING)

CATC (C PERNAME)

CATRC (RC R C),

где CATR, CATA и CATD описывают отношения, атрибуты и домены соответственно; CATRA связывает атрибуты и их домены; CATRC связывает отношения и категории (см. подробнее ниже). Кроме того, атрибуты R, A, D и C определяются на E-домене и содержат суррогаты для сущностей типов отношений, атрибутов, доменов и меток категории соответственно. Наконец, атрибуты RA, AD и RC также определяются на E-домене и содержат суррогаты для ассоциативных сущностей типов отношение-атрибут, атрибут-домен и отношение-категория-метка, соответственно. Остальные атрибуты перечислены ниже с кратким пояснением:

RELNAME – имя отношения (атрибут определен на RN-домене);
ATTNAME – имя атрибута;
DOMNAME – имя домена;
PERNAME – метка категории (атрибут определен на домене PER);
RELTYPE – тип объекта, представляемого отношением;
USERKEY – указывает, принимает ли атрибут участие в определяемом пользователем ключе для соответствующего отношения;
VTYPE – семантический тип значения;
ORDERING – указывает, применима ли операция > для значений в соответствующем домене.

Для заданной категории c, тип сущностей называется вершиной категории c (top per c), если у него имеется, по крайней мере, один подчиненный тип сущностей в c, но сам он не подчинен какому-либо типу в c. Отношение CATRC содержит, по крайней мере, один кортеж для каждой категории. Для каждой категории в базе данных в нем регистрируются отношения, которые представляют типы сущностей – вершины этой категории. Смысл других отношений в каталоге модели RM/T должен быть очевиден.

Подходящие значения reltype специфицируются для отношения путем конкатенации соответствующих букв из следующего списка:

A – отношение ассоциативных типов сущностей;
C – отношение характеристических типов сущностей;
E – E-отношение;
G – графовое отношение;
I – отношение внутренних стержневых типов сущностей;
K – отношение стержневых типов сущностей;
L – граф с помеченными ребрами;
N – отношение несущностных ассоциаций;
P – отношение свойств;
T – отношение типов сущностей-событий.

Например, для отношения, представляющего стержневой тип сущностей-событий, значением reltype было бы TK; для отношения, которое представляет ориентированный граф с помеченными ребрами, значением reltype было бы TK.

15. ОПЕРАЦИИ RM/T

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

15.1. Операции над именами

Операция NOTE

Пусть имеется отношение R. Тогда NOTE(R) – это relname отношения R (т.е. представление имени relname в форме символьной строки), если такое имя было назначено отношению R пользователем; в противном случае NOTE(R) имеет неопределенное значение. Для наших целей сейчас нет необходимости распространять этот оператор на объекты, отличные от отношений. Многие отношения, являющиеся промежуточными результатами, не будут иметь имен. Однако каждому базовому отношению должно быть дано какое-либо relname.

Операция TAG

Пусть имеется отношение R. Тогда

TAG(R) = R × {NOTE(R)},

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

Операция DENOTE

Пусть r – это значение relname некоторого отношения. Тогда DENOTE(r) – это отношение, обозначаемое r. При применении к отношениям, которые имеют имена, операции NOTE и DENOTE являются обратными друг к другу.

Операция DENOTE может применяться также к унарному отношению, которое является множеством значений relname. Пусть R – такое отношение. Тогда DENOTE(R) представляет собой множество всех таких отношений, для которых значения relname принадлежат R.

15.2. Операции над множествами

Операция COMPRESS

Пусть f – это некоторая ассоциативная и коммутативная операция, которая отображает пару отношений в отношение (например, операция join). Пусть Z – это множество отношений такое, что операция f может быть законным образом применена к каждой паре отношений в Z. Тогда COMPRESS(f, Z) – это отношение, полученное путем многократного попарного применения f к отношениям в Z. Альтернативной записью вызова COMPRESS(f,Z) является f/Z.

Операция APPLY

Пусть f – это унарная операция, которая отображает отношения в отношения, а Z – множество отношений (не обязательно совместимых по объединению). Тогда результатом вызова APPLY(f, Z) является множество всех отношений f(z), где z – элемент Z. Для удобства мы принимаем то соглашение, что если некоторое множество отношений используется в одном или нескольких местах алгебраического выражения, в которых синтаксически допускается употребление имени отношения, то это выражение вычисляется для каждого элемента данного множества. Однако

• это выражение должно быть заключено в скобки с предшествующим словом APPLY;
• в области действия одного оператора APPLY может быть упомянуто не более одного множества отношений (но может быть упомянуто любое число отдельных отношений).

Операция PARTITION BY ATTRIBUTE: PATT

Пусть R – отношение с атрибутом A (возможно, составным), причем R может иметь и другие атрибуты. Тогда PATT(R, A) – это множество отношений, полученных разбиением R по всем различным значением A. Для всех отношений, имеющих атрибут A:

R = UNION/PATT(R, A).

Операция PARTITION BY TUPLE: PTUPLE

Пусть R – некоторое отношение. Тогда PTUPLE(R) – это множество отношений, полученных путем помещения каждого кортежа R в некоторое однокортежное отношение. Заметим, что R = UNION/PTUPLE(R).

Операция PARTITION BY RELATION: PREL

Пусть R – некоторое отношение. Тогда PREL(R) – это множество отношений, у которых единственным элементом является отношение R. Заметим, что R = UNION/PREL(R).

Операция SETREL

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

SETREL(R₁, R₂, ..., R_n).

15.3. Графовые операции

Для удобства манипулирования ориентированными графовыми отношениями (PG, CG, AG, UGI, AGI, US, AS, UP, AP, KG) в модель включаются специальные операции, описываемые в данном подразделе. Отношение R называется отношением-диграфом (digraph relation)⁴⁾, если оно имеет степень не менее двух и обладает следующими свойствами:

1. два его атрибута определены на общем домене;
2. один из них исполняет роль SUB, а другой – роль SUP;
3. никакие другие атрибуты отношения не исполняют роли SUB или SUP.

Отношение R является отношением-диграфом с помеченными ребрами (edge-labeled digraph relation), если:

1. оно является отношением-диграфом степени не менее трех;
2. в точности один из его атрибутов исполняет роль PER (пометка);
3. для каждого набора m, n, p никакие два кортежа R не имеют общих триплетов (SUB:m, SUP:n, PER:p).

Отношение-диграф, которое не является отношением с помеченными ребрами, называется непомеченным (unlabeled).

Операция OPEN

Случай 1. Пусть R – непомеченное отношение-диграф (т. е. никакой его атрибут не исполняет роли PER). Тогда OPEN(R) порождает копию R, в которой удалены все не непосредственные подчинения. Иначе говоря, это максимальное подмножество R₁ отношения R, обладающее следующим свойством: если (SUB:m, SUP:n) принадлежит R₁, то либо не существует какого-либо k, для которого как (SUB:m, SUP:k), так и (SUB:k, SUP:n) принадлежат R₁, либо, если такое k существует, имеет место k = m или k = n.

Случай 2. Пусть R – отношение-диграф с помеченными ребрами. В таком случае OPEN(R) порождает максимальное подмножество R₁ отношения R, обладающее следующим свойством: если (SUB:m, SUP:n, PER:p) принадлежит R₁, то либо не существует какого-либо k, для которого как (SUB:m, SUP:k, PER:p), так и (SUB:k, SUP:n, PER:p) принадлежат R₁1, либо, если такое k существует, имеет место k = m или k = n.

Операция CLOSE

Случай 1. Пусть R – непомеченное отношение-диграф. Тогда CLOSE(R) – это транзитивное замыкание R, т.е. минимальное надмножество R такое, что если (SUB:m, SUP:k) и (SUB:k, SUP:n) принадлежат R, то (SUB:m, SUP:n) также принадлежит CLOSE(R). Кортежи в CLOSE(R), которые не принадлежат также и R, содержат неопределенные значения для тех атрибутов, которые отличны от SUB и SUP.

Случай 2. Пусть R – отношение-диграф с помеченными ребрами. Тогда CLOSE(R) – минимальное надмножество R такое, что если SUB:m, SUP:k, PER:p) и (SUB:k, SUP:n, PER:p) принадлежат R, то (SUB:m, SUP:n, PER:p) также принадлежит CLOSE(R). Кортежи в CLOSE(R), которые не принадлежат также и R, имеют неопределенные значения для тех атрибутов, которые отличны от SUB, SUP и PER.

Заметим, что для всех отношений-диграфов R имеют место соотношения:

OPEN(OPEN(R)) = OPEN(R),
OPEN(CLOSE(R)) = OPEN(R),
CLOSE(CLOSE(R)) = CLOSE(R)

Для всех непомеченных отношений-диграфов R степени 2 и для всех отношений-диграфов R степени 3 с помеченными ребрами действует также соотношение:

CLOSE(OPEN(R)) = CLOSE(R).

Для отношений-диграфов более высокой степени OPEN может утрачивать информацию (содержащуюся в атрибутах, отличных от SUB, SUP и PER), которую CLOSE не может восстановить.

Операция STEP

Случай 1. Пусть R – непомеченное отношение-диграф, которое не имеет атрибута SEP, обозначающего отделение (separation). Пусть Z – это множество всех атрибутов R, отличных от SUB и SUP. Тогда STEP(R) – это множество всех кортежей вида

(SUB:x, SUP:y, Z:z, SEP:n),

где (SUB:x, SUP:y, Z:z) принадлежит R, а n – наименьшее число ребер графа, которые отделяют узел x от узла y.

Случай 2. Пусть R – отношение-диграф с помеченными ребрами, которое не имеет атрибута SEP. Пусть Z – множество всех атрибутов R, отличных от SUB, SUP и PER. Тогда STEP(R) – это множество всех кортежей вида

(SUB:x, SUP:y, PER:p, Z:z, SEP:n),

где (SUB:x, SUP:y, PER:p, Z:z) принадлежит R, а n – наименьшее число ребер графа с меткой p, которые отделяют узел x от узла y.

15.4. Примеры

Пример A. Скомбинировать все P-отношения для типа сущностей служащие (emp) в единое исчерпывающее P-отношение без потери информации, не опираясь на какие-либо предположения о количестве таких отношений.

Получим сначала имена всех P-отношений для типа сущностей служащие:

R₁ ← PG[SUP = emp] [SUB].

Вспомним, что PG – это графовое отношение свойств. Тогда мы получаем соответствующее множество отношений:

R₂ ← DENOTE(R1).

Наконец, многократно применяем внешнее естественное соединение по атрибуту EMP (общему для всех отношений в этом множестве):

R₃ ← ( EMP)/R₂,

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

Cкомбинируем выражения для R₁, R₂, R₃ в единое выражение и заменим emp на r, где r – это relname для какого-либо типа сущностей. Пусть PROPERTY(r) обозначает результат. Тогда получаем:

PROPERTY(r) = ( r, '')/DENOTE(PG[SUP = r] [SUB]).

Таким образом, PROPERTY отображает relname типа сущностей в соответствующее исчерпывающее P-отношение.

Пример B. Получить имя служащего и должность для всех служащих с отличным (excellent) рейтингом в предположении, что:

1. имеются различные типы сущностей для каждого типа должности (например, секретарь, водитель грузовика, инженер и т.д.), и категория типа должности (jobtype) производит разбиение множества служащих;
2. непосредственным обобщением этих типов может быть тип сущностей служащие (emp);
3. имя и должность служащего записываются в одно или более P-отношений, ассоциированных с типом сущностей служащие;
4. рейтинг записывается отдельно в некоторое P-отношение для каждого типа должности.

Тогда:

R₁ ← UGI[SUP = emp, PER = jobtype][SUB].

Вспомним, что UGI – это отношение безусловного обобщения по включению. Следовательно, R₁ – это унарное отношение, в котором содержатся все имена всех E-отношений, которые являются непосредственно безусловно подчиненными отношению служащие.

R₂ ← APPLY(PROPERTY, R₁).

Здесь R₂ – это множество P-отношений, каждое из которых является исчерпывающим P-отношением для одного из relname в R₁.

R₃ ← APPLY(R₂[RATING = excelent]).

R₃ – это множество отношений, в точности похожее на R₂, за исключением того, что каждое отношение в R₃ является ограничением его двойника в R₂.

R₄ ← APPLY(R₃[EMP]).

R₄ – это множество отношений, полученных проекцией каждого отношения из R₃ на атрибут EMP.

R₅ ← (PROPERTY(emp))[EMP, NAME, JOBTYPE]

Здесь исчерпывающее P-отношение для типа сущностей служащие проецируется на его атрибуты – суррогат, имя и должность.

R₆ ← UNION/APPLY(R₄[EMP = EMP]R₅).

Каждое отношение из множества R₄ соединяется по сущности служащий с отношением R₅. Результат компрессируется путем многократного применения операции объединения для получения R₆ – требуемого результата.

Окончательное выражение является примером соединения по сущности, в отличие от соединения по свойству.

Пример C. Пусть некоторая база данных содержит информацию о служащих. Свойства и характеристики, относящиеся ко всем служащим, связываются через посредство PG и CG с типом сущностей служащие. Кроме того, служащие категоризируются по:

1. должности – инженер, секретарь, техник и т.д.
2. служебному статусу – постоянный и временный.

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

Требуется получить тернарное отношение R такое, что (E-домен:x, RN-домен:y, PER-домен:z) принадлежит R тогда и только тогда, когда x является суррогатом некоторого служащего, y – типом сущности x в категории z. Фактически, мы конвертируем информацию категории в новый атрибут отношения на родительском уровне.

R₁ ← UGI[SUP = emp] [SUB, PER].

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

R₂ ← DENOTE(R₁[SUB]).

R₂ – это соответствующее множество отношений.

R₃ ← APPLY(TAG, R₂).

Для получения множества R₃ берется каждое отношение в R₂, и к нему добавляется столбец, который содержит столько экземпляров relname для данного отношения, сколько имеется кортежей в этом отношении.

R₄ ← UNION/APPLY(R₃[RN * SUB]R₁).

Естественное соединение с отношением R₁ применяется к каждому отношению из R₃ с использованием атрибутов rename. Для получения желаемого отношения результирующее множество отношений компрессируется путем многократного применения объединения.

Пример D. Скомбинировать всю информацию из графовых отношений RM/T в одном отношении R, имеющем атрибуты SUB, SUP, PER и RN, где (SUB:m, SUP:n, PER:p, RN:q) принадлежит R тогда и только тогда, когда

1. q является значением relnamr для помеченного графового отношения, и (SUB:m, SUP:n, PER:p) принадлежит отношению с именем q; или
2. q является значением relnamr для непомеченного графового отношения, p – неопределенное значение, и (SUB:m, SUP:n) принадлежит отношению с именем q.

Предположим, что тип графового отношения есть G. Не будем делать каких-либо предположений о числе графовых отношений в RM/T или об их именах.

Тогда:

R₁ ← DENOTE(CATR[RELTYPE = G] [RN]),

R₂ ← APPLY(TAG, R₂),

R₂ ← /R2.

В последнем выражении требуется внешнее объединение, поскольку не все графовые отношения в RM/T имеют одну и ту же степень.

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