Материал: Алгебра_кортежей
универсуму. В АК, если речь идет о моделях исчисления высказываний или предикатов, эти утверждения приняты в качестве аксиомы, для которой имеется соответствующая интерпретация, основанная на свойствах декартовых произведений.
Определение 2.4. C-системой называется множество однотипных C-кортежей, которые записываются в виде матрицы, ограниченной прямыми скобками. Строки этой матрицы содержат C-кортежи.
C-система эквивалентна множеству элементарных кортежей. Это множество равно объединению множеств элементарных кортежей, принадлежащих соответствующим C-кортежам. Например, C-систему
A1 |
B1 |
C1 |
|
можно представить как множество элементарных |
Q[XYZ] = |
B2 |
|
|
|
A2 |
C2 |
|
||
кортежей, вычисляемое по формуле
Q[XYZ] = (A1 B1 C1) (A2 B2 C2).
Здесь и далее в этом подразделе будем рассматривать примеры АК-объектов, заданные в пространстве S = X Y Z, где X = {a, b, c, d}, Y = {f, g, h}, Z = {a, b, c}. Например, для S можно определить некоторое отношение R[XYZ] как C-систему
|
|
|
|
{a,d} |
* |
{b,c} |
|
R[XYZ] = {b,d} |
{f ,h} |
{a,c} . |
|
{b,c} |
{g} |
{b} |
|
|
|
|
|
Компонента " " в первом C-кортеже соответствует атрибуту Y и в силу этого равна множеству {f, g, h}. Полученную структуру можно представить как множество элементарных кортежей, если последовательно "разворачивать" каждый из C-кортежей, содержащихся в C-системе, во множество элементарных кортежей. При этом надо учитывать, что одинаковые элементарные кортежи могут содержаться в разных C-кортежах, подобное дублирование надо исключать. В C-системе Q такими "неудобными" являются первый и второй C-кортежи, так как результатом их пересечения является непустой C-кортеж [{d} {f, h} {c}]. Это означает, что элементарные кортежи (d, f, c) и (d, h, c) содержатся в каждом из этих C-кортежей.
Теорема 2.1. Алгебра кортежей для однотипных АК-объектов изоморфна алгебре множеств.
75
Для обоснования этого положения в данном разделе рассмотрены особенности реализации операций (пересечение, объединение, дополнение) и отношений (включения и равенства) сначала для С-объектов (С-кортежей, С-систем), а затем для D-объектов (D-кортежей, D-систем). После чего, в подразделе 2.2 показаны способы преобразования С-объектов в D-объекты и наоборот.
Операции с однотипными АК-объектами, а также проверка соотношений включения или равенства осуществляется на основании теорем 2.2-2.8 (для С-объектов) и 2.9-2.15 (для D-объектов). Многие теоремы приводятся здесь без доказательств, так как их формулировка в терминах АК соответствует известным свойствам декартовых произведений.
Пусть заданы однотипные C-кортежи
P = [P1 P2 … Pn] и Q = [Q1 Q2 … Qn].
Теорема 2.2. P Q = [P1 Q1 P2 Q2 … Pn Qn].
Примеры: [{b, d} {f, h} {a, b}] [ {f, g} {a, c}] = [{b, d} {f} {a}]; [{b, d} {f, h} {a, b}] [ {g} {a, c}] = [{b, d} {a}] = .
Теорема 2.3. P Q, если и только если Pi Qi для всех i = 1, 2, …, n. Теорема 2.4. P Q [P1 Q1 P2 Q2 … Pn Qn], причем равенство
возможно лишь в двух случаях:
(i)P Q или Q P;
(ii)Pi = Qi для всех соответствующих пар компонент, за исключением одной пары.
Заметим, что в алгебре кортежей в соответствии с определением 2.4 во
P1 |
P2 |
... |
Pn |
всех случаях справедливо равенство P Q = |
Q2 |
... |
. |
Q1 |
Qn |
Теорема 2.5. Пересечение двух однотипных C-систем равно C-системе, содержащей все непустые пересечения каждого C-кортежа первой C-системы с каждым C-кортежем второй C-системы.
Пример. Пусть в пространстве S заданы C-системы:
|
{a,b,d} {f ,h} |
{b} |
|
|
{a,d} |
* |
{b,c} |
||
|
|
|
|
|
|
||||
R [XYZ] = |
|
|
|
|
, R [XYZ] = |
{b,d} |
{f ,h} |
{a,c} . |
|
1 |
|
|
|
|
|
2 |
|
|
|
|
|
{b,c} |
* |
{a,c} |
|
{b,c} |
{g} |
{b} |
|
|
|
|
|
|
|
|
|
|
|
Нужно вычислить их пересечение. Сначала вычисляем пересечение всех
76
пар C-кортежей, содержащихся в разных C-системах:
[{a, b, d} {f, h} {b}] [{a, d} {b, c}] = [{a, d} {f, h} {b}]; [{a, b, d} {f, h} {b}] [{b, d} {f, h} {a, c}] = ;
[{a, b, d} {f, h} {b}] [{b, c} {g} {b}] = ; [{b, c} {a, c}] [{a, d} {b, c}] = ;
[{b, c} {a, c}] [{b, d} {f, h} {a, c}] = [{b} {f, h} {a, c}]; [{b, c} {a, c}] [{b, c} {g} {b}] = .
Затем из непустых C-кортежей формируем C-систему:
R1 R2 |
= |
|
|
. |
|
{a,d} {f ,h} |
{b} |
||
|
|
{b} |
{f ,h} |
{a,c} |
Даже этот сравнительно несложный пример показывает некоторые возможности уменьшения трудоемкости алгоритмов за счет использования АК: тот же результат можно получить, если предварительно перевести исходные C-системы в множества элементарных кортежей. Но при этом трудоемкость вычислений значительно увеличится, так как C-система P содержит 24 элементарных кортежа, C-система Q – 20, а C-система P Q – 8.
Теорема 2.6. Объединение двух однотипных C-систем равно C-системе, содержащей все C-кортежи операндов.
Например,
{a,b,d}
|
|
|
|
|
|
|
|
|
|
|
|
{b,c} |
{a,b,d} {f ,h} {b} |
|
|
{a,d} {f ,h} {b} |
|
|
|||||||
|
|
|
= |
|
|
|||||||
|
{b,c} |
* |
|
|
|
{b} |
|
|
{a,d} |
|||
|
{a,c} |
|
|
{f ,h} {a,c} |
|
|
||||||
|
|
|
|
|
|
|
|
|
|
{b} |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
{f ,h}
{f ,h}
{f.h}
{b} {a,c}
{b} .
{a,c}
В некоторых случаях после вычисления объединения C-систем можно сократить общее число кортежей в полученной C-системе, если использовать условия (i) или (ii) теоремы 2.4. Можно убедиться, что в последней C-системе третий C-кортеж включен в первый, а четвертый – во второй. Значит, результат будет равен первой C-системе из левой части равенства.
Для операций пересечения и объединения отношений можно было бы ограничиться тремя определенными ранее типами АК-объектов. Но для использования операции дополнения этого недостаточно. Поэтому требуется определить еще три структуры.
77
Определение 2.5. Диагональная C-система – C-система размерности n n, у которой все недиагональные компоненты равны полной компоненте.
{a,c} |
|
|
|
|
Например, |
|
{f ,g} |
|
– диагональная C-система. |
|
|
|
{b,c} |
|
|
|
|
|
|
Определение 2.6. D-кортеж – это отношение, равное диагональной C-системе, записанное в виде кортежа диагональных компонент и ограниченное перевернутыми квадратными скобками.
{a,c} |
|
|
|
|
Например, |
|
{f ,g} |
|
= ]{a, c} {f, g} {b, c}[, |
|
|
|
{b,c} |
|
|
|
|
|
|
где в правой части равенства D-кортеж. Отсюда ясно, что любой D-кортеж можно при необходимости "развернуть" в диагональную C-систему.
D-кортеж с хотя бы одной полной компонентой равен некоторому частному универсуму. D-кортеж со всеми пустыми компонентами эквивалентен пустому множеству
Чтобы вычислить дополнение C-кортежей и C-систем, необходимо найти дополнение каждой компоненты. Дополнение Pj любой компоненты Pj
АК-объекта определяется как дополнение относительно домена соответствующего ей атрибута. Например, если задан C-кортеж
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
R[XYZ] = [A B C], то A = X \ A, B = Y \ B и |
C |
|
= Z \ C. |
|
||||||||||
Теорема 2.7. Для произвольного C-кортежа |
P = [P1 P2 … Pn] его |
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|||||
дополнение равно D-кортежу P = ] |
P1 |
|
P2 |
… Pn [. |
|
|||||||||
Формулировка данной теоремы |
соответствует |
операции разности |
||||||||||||
декартовых произведений, выраженной в структурах АК (см. подраздел 1.4).
Рассмотрим примеры. Пусть в пространстве |
S = X Y Z задан C-кортеж |
||||
T = [{b, d} {f, h} {a, b}]. Тогда |
|
|
|
||
|
|
{a,c} |
|
|
|
|
|
= ]X \ {b, d} Y \ {f, h} Z \ {a, b}[ = |
|
{g} . |
|
T |
|||||
|
|
|
|
|
{c} |
|
|
|
|
|
|
Вычислим дополнение для случая, когда в C-кортеже имеются фиктивные
компоненты. Пусть T1 = [{b, d} {a, b}]. Тогда |
T1 |
= ]{a, c} {c}[. Здесь в |
78 |
|
|
D-кортеже появилась фиктивная компонента “ ”. При преобразовании D-кортежа с фиктивными компонентами в диагональную C-систему C-кортежи, содержащие эти фиктивные компоненты, будут пустыми и поэтому могут быть удалены из C-системы. Например,
|
|
|
|
|
|
|
|
{a,c} |
|
|
|
|
|
|
{a,c} |
|
|
|
|
|
|
. |
|||
|
= ]{a, c} {c}[ = |
|
|
|
|
|
|
|
|
|
||
T |
= |
|
|
|
||||||||
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
{c} |
|
|
{c} |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
Оказывается, D-кортеж не только позволяет компактно отобразить диагональные C-системы, но самостоятельно используется во многих операциях АК.
Используя D-кортежи, можно сформировать еще одну структуру АК – D-систему.
Определение 2.7. D-система – структура, состоящая из множества однотипных D-кортежей, равная пересечению множеств элементарных кортежей, содержащихся в этих D-кортежах.
Изображение D-системы аналогично изображению C-системы, только вместо обычных прямых скобок используются перевернутые.
Теорема 2.8. Дополнение C-системы есть D-система той же размерности, в которой каждая компонента равна дополнению соответствующей компоненты в
исходной C-системе. |
|
|
|
|
|
|
Доказательство. Пусть |
дана C-система |
P, |
содержащая |
множество |
||
{P1, P2, …, Pn} |
C-кортежей. |
Это |
означает, что |
P = P1 P2 … Pn. При |
||
вычислении |
дополнения |
по |
закону |
де |
Моргана |
получим |
|
P |
= |
P1 |
|
P2 |
… |
Pn |
. Тогда справедливость |
|
данной |
теоремы следует из |
||
теоремы 2.7. Конец доказательства. |
|
|
|
|
|
||||||||
|
|
Например, дополнение C-системы F[XYZ] = |
{a,b,d} |
{f ,h} |
{b} |
, |
|||||||
|
|
|
{b,c} |
* |
|
||||||||
|
|
|
|
|
|
|
|
|
|
{a,c} |
|
||
заданной в пространстве S, можно вычислить как D-систему
|
X \{a,b,d} Y \{f ,h} |
Z \{b} |
|
{c} |
{g} {a,c} |
|||
F |
= |
X \{b,c} |
Y \ |
|
= |
|
|
. |
|
|
Z \{a,c} |
{a,d} |
{b} |
||||
Теперь опишем возможные операции и соотношения для D-объектов. Пусть заданы однотипные D-кортежи P = ]P1 P2 … Pn[ и Q = ]Q1 Q2 … Qn[.
79