видно, что преобразование АК-объекта в альтернативный класс во многих случаях весьма трудоемко. В главе 3 будут рассмотрены некоторые методы уменьшения этой трудоемкости.
Приведенные выше соотношения и преобразования позволяют получить полный спектр операций алгебры множеств и проверок включения и эквивалентности для любых пар АК-объектов в заданном универсуме. Отсюда следует фундаментальное предложение, сформулированное в теореме 2.1.
Итак, любая система отношений с одинаковыми схемами атрибутов представляет собой обычную алгебру множеств, в которой каждое отношение рассматривается как множество элементарных кортежей. В алгебре кортежей такой системе множеств соответствует совокупность однотипных АК-объектов. Ранее в главе были сформулированы в виде теорем, определений и предложений алгоритмы выполнения операций алгебры множеств с АК-объектами, а также алгоритмы проверки включения одного АК-объекта в другой. Эти алгоритмы систематизированы и приведены в Приложении.
Как уже упоминалось, в АК можно непосредственно выполнять операции алгебры множеств с АК-объектами, если они однотипны (т.е. имеют одну и ту же схему отношения). Однако АК также дает возможность производить аналогичные операции над многоместными отношениями, которые имеют разные типы. Предварительно отношения приводятся к одной схеме с помощью перечисленных ранее (см. определение 2.1) операций с атрибутами. Следующий подраздел показывает, как это реализуется.
2.3. Операции с атрибутами, операции соединения и композиции, обобщенные операции
Универсальный характер АК обусловлен тем, что в ней, помимо операций алгебры множеств с АК-объектами, дополнительно вводятся еще пять вышеупомянутых операций с атрибутами, которые существенно расширяют аналитические возможности АК. Рассмотрим эти операции более подробно, а также проиллюстрируем их применение при выполнении операций соединения и композиции отношений.
Переименование атрибутов допускается только для атрибутов, относящихся к одному сорту. Эта операция используется при замене
85
переменных, в частности, в алгоритмах вычисления транзитивного замыкания графа.
Перестановка атрибутов – операция, при выполнении которой в матрице АК-объекта меняются местами столбцы, а в схеме отношения соответственно изменяется порядок атрибутов.
При одновременной перестановке столбцов АК-объекта и соответствующих им атрибутов содержание отношения не изменяется. Эта операция необходима для того, чтобы привести АК-объекты с одинаковыми, но расположенными в разном порядке атрибутами, к такому виду, при котором можно выполнять операции алгебры множеств.
Например, C-система P[XYZ] = |
{a,b,d} |
{f ,h} |
{b} |
при перестановке |
|
|
{b,c} |
* |
|
||
|
|
{a,c} |
|
||
атрибутов |
|
преобразуется |
в |
эквивалентную |
C-систему |
||
|
{f ,h} |
{a,b,d} |
{b} |
|
|
|
|
P[YXZ] = |
|
|
{b,c} |
. |
|
|
|
|
|
{a,c} |
|
|
|
||
Обращение отношений. В случае бинарных отношений перестановка столбцов без перестановки атрибутов позволяет получить отношение, обратное
|
|
|
|
|
исходному. Так, отношение G[XY] = |
{a} {a,b} |
|
|
|
|
при перестановке столбцов |
|||
{b,c} |
{a,c} |
|
|
|
|
|
{a,b} {a} |
|
|
преобразуется в обратное отношение G-1[XY] = |
|
. При обращении |
||
|
|
{a,c} |
{b,c} |
|
АК-объекта все элементарные кортежи (s, t) исходного отношения преобразуются в обратные – (t, s). Если элементарный кортеж содержит одинаковые элементы (например, (b, b)), то при обращении он не изменяется.
Добавление фиктивного атрибута (+Atr) осуществляется, если добавляемый атрибут отсутствует в схеме отношения АК-объекта (АК-объекты с повторяющимися атрибутами допустимы, но здесь не рассматриваются). При выполнении этой операции одновременно в схему отношения добавляется имя нового атрибута, а в структуру вводится на соответствующем месте новый столбец с фиктивными компонентами, при этом в C-кортежи и в C-системы добавляется фиктивные компоненты “ ”, а в D-кортежи и D-системы – фиктивные компоненты “ ”.
Элиминация атрибута (–Atr) осуществляется так: из АК-объекта
86
удаляется столбец, а из его схемы отношения – соответствующий атрибут. Но, в отличие от предыдущей операции, логический смысл элиминации зависит от того, к какому классу объектов она применяется.
Семантика операций “+Atr” и “–Atr” будет изложена ниже в п. 2.4. Они применяются, в частности, при вычислении соединения и композиции двух разнотипных отношений, заданных АК-объектами. Эти операции часто используются при решении разнообразных задач на графах, в базах данных, в интеллектуальных системах [Кулик, 1996; 2007 b]. В логическом анализе операции соединения соответствует конъюнкция двух предикатов с отличающимся составом переменных, например, P(x, y) Q(x, z, v), а операции композиции – конъюнкция предикатов под квантором существования,
например, x(P(x, y) Q(x, z, v)).
Простейший пример применения этих операций приведен в следующей задаче. Пусть дано отношение РОДИТЕЛИ[X, Y], в котором первый элемент пары обозначает родителя, а второй – его (или ее) ребенка. В результате соединения отношения РОДИТЕЛИ с самим собой получается трехместное отношение "персоны – их дети – их внуки", а в результате композиции этого отношения с самим собой образуется двухместное отношение "персоны – их внуки".
В общем случае можно выполнять операции соединения и композиции отношений для любых пар АК-объектов. Пусть заданы две структуры R1[V] и R2[W], где V и W – множества атрибутов, причем V W. Эти множества можно разложить на непересекающиеся подмножества X, Y, Z с помощью таких преобразований:
X = W \ V; Y = W V; Z = V \ W.
Тогда получим V = Y Z и W = X Y, и заданные отношения можно переписать как R1[YZ] и R2[XY].
Операция соединения R1[YZ] R2[XY] отношений обычно выполняется с помощью попарного сравнения всех элементарных кортежей из разных отношений. Если при сравнении элементарных кортежей окажется, что в проекции [Y] они совпадают, то из двух кортежей формируется кортеж со схемой отношения [XYZ], который становится одним из элементов соединения отношений. Например, имеются два элементарных кортежа T1 R1 и T2 R2,
87
причем
T1[YZ] = (c, d, e, f, g); T2[XY] = (a, b, c, d, e), где T2[X] = (a, b); T1[Z] = (f, g); T1[Y] = T2[Y] = (c, d, e).
Тогда результат композиции этих кортежей – элементарный кортеж
T3[XYZ] = (a, b, c, d, e, f, g).
В АК операция соединения отношений существенно упрощается, ее можно выполнить без попарного сравнения всех элементарных кортежей по формуле:
R1[YZ] R2[XY] = +X(R1) +Z(R2) |
(2.1) |
Операция композиции R1[YZ] R2[XY] отношений вычисляется после вычисления соединения. Для этого нужно их каждого элементарного кортежа, принадлежащего соединению отношений, изъять проекцию [Y]. Например, композицией двух приведенных выше кортежей T1 и T2 – элементарный кортеж
T4[XZ] = (a, b, f, g).
В алгебре кортежей композиция отношений определяется по формуле:
R1[YZ] R2[XY] = –Y(+X(R1) +Z(R2)) = –Y(R1 |
R2), |
(2.2) |
||||
при условии, что (R1 R2) является C-кортежем или C-системой. |
|
|||||
Рассмотрим пример. Пусть в пространстве S заданы АК-объекты |
|
|||||
R1[YZ] = |
{f} {a,b} |
; R2[XY] = |
{a} {g,h} |
|
||
|
|
|
. |
|
||
{g,h} |
{a,c} |
{b,c} {f} |
|
|
||
По формуле (2.1) найдем их соединение. Для этого добавим фиктивный атрибут X в R1 и фиктивный атрибут Z в R2, после чего вычислим их пересечение:
|
{f} |
{a,b} |
{a} |
{g,h} |
|
{b,c} |
{f} {a,b} |
|
R1 R2 = |
|
|
|
|
|
= |
|
. |
|
{g,h} |
{a,c} |
{b,c} |
{f} |
|
{a} |
{g,h} {a,c} |
|
Далее ищем по формуле (2.2) их композицию. Для этого надо |
||||||||
элиминировать из R1 R2 |
атрибут Y: |
|
|
|
|
|||
|
{b,c} |
{a,b} |
|
|
|
|
|
|
R1 R2 = |
|
|
. |
|
|
|
|
|
|
{a} |
{a,c} |
|
|
|
|
|
|
В случаях, когда требуется найти соединение отношений, которые
выражены как D-системы, можно воспользоваться формулой (2.1). При этом
88
надо учесть особенности операции +Atr для D-систем (в добавляемом фиктивном атрибуте должны быть пустые компоненты) и операции пересечения D-систем. Однако для операции композиции в этом случае формула (2.2) не подходит, так как элиминация атрибута из D-системы означает навешивание квантора , но не (см. п. 2.4). Для вычисления композиции во всех случаях справедлива формула
R1[YZ] R2[XY] = y(+X(R1) +Z(R2)) = y(R1 R2), |
(2.3) |
Если при вычислении соединения АК-объектов получается D-система, то перед элиминацией атрибутов ее необходимо преобразовать в эквивалентную C-систему или использовать метод квантификации для D-систем, который рассматривается в главе 3.
Назовем операции и отношения алгебры множеств с АК-объектами с предварительным добавлением недостающих фиктивных атрибутов
обобщенными операциями и отношениями алгебры множеств в АК и обозначим их соответственно G , G , \G , G , G и т.д. С учетом этого формулу 2.1 можно записать как
R1[YZ] R2[XY] = R1[YZ] G R2[XY].
Операции G , и G полностью соответствуют логическим операциям и. Отношение G в АК эквивалентно отношению выводимости в исчислении предикатов. Отношение G означает, что структуры равны при условии, что они приведены к одной схеме отношения путем добавления атрибутов. Это обстоятельство позволяет использовать принципиально новый подход к построению процедур логического вывода и проверок выводимости, который рассматривается в главе 4.
Далее раскроем взаимосвязь АК с логическими исчислениями.
89