Алгебра кортежей

Алгебра кортежей — математическая система моделирования и анализа многоместных отношений.

Использование термина

В математической литературе термин «алгебра кортежей» используется в двух значениях. В одном из них под алгеброй кортежей понимается класс логических формул, применяемых для преобразования булевых функций в арифметические полиномы (Малюгин В. Д. Параллельные логические вычисления посредством арифметических полиномов. Москва. Физматлит. 1997).

Иное значение термина рассматривается в работах Б. А. Кулика — этот вариант излагается в данной статье.

Определение

Алгебра кортежей (АК) — это алгебраическая система, носителем которой является произвольная совокупность многоместных отношений, выраженных в специфических структурах (элементарный кортеж, C-кортеж, C-система, D-кортеж, D-система), называемых АК-объектами. Операции и отношения в АК полностью соответствуют операциям (пересечение, объединение, дополнение) и отношениям (принадлежность, включение, равенство) алгебры множеств. Кроме того, в состав операций АК добавлены четыре операции с атрибутами:

• переименование атрибутов;
• перестановка атрибутов;
• добавление нового фиктивного атрибута;
• элиминация атрибута из АК-объекта.

На чем основана АК

Законы АК основаны на сочетании законов алгебры множеств и свойств прямого произведения множеств.

Структуры АК

Обозначения

Имена АК-объектов содержат собственно имя, в некоторых случаях к имени добавляется заключенная в прямые скобки последовательность имен атрибутов, определяющих схему отношения, в которой задан этот АК-объект. Например, $R [X Y Z]$ означает, что АК-объект $R$ задан в пространстве атрибутов $X,Y$ и $Z$.

АК-объекты, заданные в одном пространстве атрибутов, называются однотипными.

Элементарный кортеж

• Элементарный кортеж в АК соответствует кортежу элементов в многоместных отношениях. Например, запись $T[XYZ] = (a,\quad b,\quad c)$. означает, что $T$ — элементарный кортеж, при этом $a\in X, b\in Y, c\in Z$.

В АК элементарные кортежи являются элементами множеств (отношений), выраженных другими типами АК-объектов.

Компоненты

Остальные структуры формируются из множеств, являющихся подмножествами доменов атрибутов. Эти множества в АК называются компонентами. В их число входят две фиктивные компоненты:

полная компонента — $\ast$, равна домену соответствующего (по месту ее расположения в кортеже) атрибута (используется в C-кортежах и C-системах);

пустое множество — $\empty$, (используется в D-кортежах и D-системах).

C-кортеж

• C-кортеж — кортеж множеств, ограниченный прямыми скобками. Интерпретируется как множество элементарных кортежей, содержащихся в прямом произведении этих множеств. Например, $R[XYZ] = [A\quad B\quad C]$ означает, что $A\sube X,\quad B\sube Y,\quad C\sube Z$ и $R[XYZ] = A\times B\times C$.

C-система

• C-система — объединение однотипных C-кортежей, выраженное в виде матрицы, ограниченной прямыми скобками.
  Например, C-систему $Q[XYZ] = \left [\begin{array} {ccc} A_1& B_1& C_1\\ A_2& B_2& C_2 \end{array}\right ]$
  можно представить как множество элементарных кортежей, вычисляемое по формуле

$Q[XYZ] = (A_1\times B_1\times C_1)\cup (A_2\times B_2\times C_2)$.

D-кортеж

Прежде, чем определить D-кортеж, нужно определить диагональную C-систему.

• Диагональная C-система — C-система размерности $n \times n$, у которой все недиагональные компоненты равны $\ast.$

Пример: $\left [\begin{array} {ccc} \{a,f,g\}& \ast & \ast\\ \ast& \{b\}& \ast\\ \ast& \ast& \{r,s\} \end{array}\right ] .$

• D-кортеж — отношение, равное диагональной C-системе, записанное в виде кортежа диагональных компонент и ограниченное перевернутыми квадратными скобками.

В частности, в формуле $\left [\begin{array} {ccc} \{a,f,g\}& \ast & \ast\\ \ast& \{b\}& \ast\\ \ast& \ast& \{r,s\} \end{array}\right ] = \left ]\begin{array} {ccc} \{a,f,g\}& \{b\}& \{r,s\}\end{array}\right [ .$

правая часть равенства — D-кортеж.

D-система

• D-система — ограниченная перевернутыми квадратными скобками матрица компонент, которая интерпретируется как пересечение содержащихся в ней однотипных D-кортежей.

Так

$\left ]\begin{array} {ccc} A_1& B_1& C_1\\ A_2& B_2& C_2 \end{array}\right [ = \left ]\begin{array} {ccc} A_1& B_1& C_1 \end{array}\right [ \quad \cap \quad \left ]\begin{array} {ccc} A_2& B_2& C_2 \end{array}\right [ =$

$= \left [\begin{array} {ccc} A_1& \ast & \ast\\ \ast & B_1 & \ast \\ \ast& \ast & C_1\end{array}\right ] \cap \left [\begin{array} {ccc} A_2& \ast & \ast\\ \ast & B_2 & \ast \\ \ast& \ast & C_2\end{array}\right ].$

Основные соотношения

Основные соотношения АК основаны на свойствах прямого произведения множеств.
Пусть заданы C-кортежи    $P = \left [\begin{array} {cccc} P_1& P_2 & \ldots & P_n \end{array}\right ]$     и     $Q = \left [\begin{array} {cccc} Q_1& Q_2 & \ldots & Q_n \end{array}\right ].$

Тогда

• $P \cap Q = \left [\begin{array} {cccc} P_1\cap Q_1 & P_2\cap Q_2 & \ldots & P_n\cap Q_n \end{array}\right ]$ ;

• для любого C-кортежа $\quad P \quad$ если хотя бы одна компонента равна $\empty$, то $P = \empty$ ;

• $P \cup Q \sube \left [\begin{array} {cccc} P_1\cup Q_1 & P_2\cup Q_2 & \ldots & P_n\cup Q_n \end{array}\right ]$ ;

• $P \cup Q = \left [\begin{array} {cccc} P_1 & P_2 & \ldots & P_n\\Q_1 & Q_2 & \ldots & Q_n\end{array}\right ]$;

• $\overline {P} = \left ]\begin{array} {cccc} \overline {P_1} & \overline {P_2}& \ldots & \overline {P_n}\end{array}\right [,$ где дополнение $\overline {P_i}$ компоненты $\quad P_i \quad$ в D-кортеже вычисляется относительно домена соответствующего атрибута;

• $P \sube Q$, если и только если $\quad P_i \sube Q_i$ для всех $i = 1, 2,\ldots, n$.

Операции с атрибутами

• Переименование атрибутов используется при замене переменных, в частности, в алгоритмах вычисления транзитивного замыкания бинарного отношения.
• Перестановка атрибутов — операция, при выполнении которой в матрице АК-объекта меняются местами столбцы. При этом в некоторых случаях (например, при обращении отношений) порядок атрибутов в схеме отношения остается неизменным.
• Добавление фиктивного атрибута осуществляется только в том случае, если добавляемый атрибут отсутствует в схеме отношения АК-объекта. При этом в C-кортежи и в C-системы в соответствующие столбцы добавляется фиктивные компоненты $\ast$, а в D-кортежи и D-системы — фиктивные компоненты $\empty$.

Если в АК-объект вводится фиктивный атрибут, то эта процедура соответствует известному в исчислении предикатов правилу вывода, которое называется правилом обобщения. Например, если D-система

$G[XZ] = \left ]\begin{array} {cc} \{a,c\}& \empty \\ \{a,c,d\}& \{b,c\} \end{array}\right [$

соответствует формуле $\quad F(x, z) \quad$ исчисления предикатов, то, добавив в этот АК-объект фиктивный атрибут $\quad Y \quad$, получим АК-объект

$G_1[XYZ] = +Y(G[XZ]) = \left ]\begin{array} {ccc} \{a,c\}& \empty & \empty \\ \{a,c,d\}& \empty & \{b,c\} \end{array}\right [ ,$

который соответствует формуле $\forall y F(x, z)$, выводимой из формулы $\quad F(x, z) \quad$ по правилу обобщения.

• Элиминация атрибута осуществляется так:

из АК-объекта удаляется столбец, а из его схемы отношения — соответствующий атрибут.

Доказано, что для C-кортежй и C-систем элиминация атрибута $\quad X \quad$ означает «навешивание» квантора $\exists x$ в соответствующую формулу, а для D-кортежй и D-систем — квантора $\forall x$.

Обобщенные операции

Использование операции «добавление фиктивного атрибута» позволяет снять ограничение на применение теоретико-множественных операций в отношениях. Считается, что эти операции применимы только на отношениях, заданных на одном декартовом произведении. В алгебре кортежей любые отношения могут быть приведены за счет добавления фиктивных атрибутов к одной схеме отношения, что позволяет выполнять над ними любые теоретико-множественные операции и сравнения (проверка включения, эквивалентности и т.д.).

С учётом этого предложено (см. книгу Б.А. Кулика, А.А. Зуенко и А.Я. Фридмана) ввести в алгебру кортежей обобщенные операции ($\cap_G$, $\cup_G$) и обобщенные отношения ($\sube_G$, $=_G$). Это те же операции алгебры множеств над отношениями с предварительным добавлением недостающих атрибутов. Доказано, что алгебраическая система с обобщенными операциями и отношениями изоморфна алгебре множеств .

Связь алгебры кортежей с исчислением предикатов

• C-кортежу в исчислении предикатов соответствует конъюнкция одноместных предикатов с разными переменными. Например,
  C-кортежу $P[XYZ] = \left [\begin{array} {ccc} P_1 \quad P_2 \quad P_3 \end{array}\right ]$
  соответствует логическая формула $F_1(x,y,z) = P_1(x) \land P_2(y) \land P_3(z)$, где

$\quad X, Y \quad$ и $\quad Z$ — области определения переменных $\quad x, y \quad$ и $\quad z$; $P_1 \subseteq X; P_2 \subseteq Y; P_3 \subseteq Z$.

• D-кортежу соответствует дизъюнкция одноместных предикатов с разными переменными. Например,
  D-кортежу $Q[XYZ] = \left ]\begin{array} {ccc} Q_1 \quad Q_2 \quad Q_3 \end{array}\right [$
  соответствует логическая формула $F_2(x,y,z) = Q_1(x) \lor Q_2(y) \lor Q_3(z)$, где

$Q_1 \subseteq X; Q_2 \subseteq Y; Q_3 \subseteq Z$.

• C-системе соответствует дизъюнкция C-кортежей, D-системе — конъюнкция D-кортежей.
• Элементарный кортеж, входящий в состав непустого АК объекта, соответствует выполняющей подстановке логической формулы.
• АК-объект, оказавшийся при проверке пустым, соответствует тождественно ложной формуле.
• АК-объект $P[XY \ldots Z]$, если он равен $X \times Y \times \ldots \times Z$, соответствует общезначимой формуле или тавтологии.
• Непустой АК-объект соответствует выполнимой формуле.
• Методы квантификации в АК с помощью операций с атрибутами приведены выше.
• Домены атрибутов в АК могут быть любыми не обязательно равными друг другу множествами. Это означает, что структуры АК соответствуют формулам многосортного исчисления предикатов.
• Логический вывод в АК основан на теореме.

Теорема. Пусть даны АК-объекты $F_1, F_2, \ldots , F_n, G$. Тогда $\quad G \quad$ есть следствие $F_1, F_2, \ldots , F_n$, если и только если $(F_1 \cap F_2 \cap \ldots \cap F_n) \sube G$.

Возможные применения

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

Логическая задача

По мотивам задач из книги известного логика Раймонда Смаллиана «Принцесса или тигр?».

Перед узником три комнаты, в одной из них принцесса, в другой — тигр, а третья — пустая. Узнику нужно войти в комнату с принцессой. Заданы всего две подсказки:

1. Во 2-й комнате нет тигра, а 3-я комната не пуста.
2. 1-я комната не пуста, а во второй нет тигра.

Одна из подсказок истинная (какая именно, неизвестно), другая — ложная. В какой комнате принцесса? Задачу можно, разумеется, решить и без алгебры кортежей.

Пояснение: пусть T — в комнате тигр, P — в комнате принцесса, E — комната пуста. Тогда в структурах АК подсказки можно записать так:

1. $\left [\begin{array} {ccc} \ast & \{P,E\} & \{P,T\} \end{array}\right ]$.
2. $\left [\begin{array} {ccc} \{P,T\} & \{P,E\} & \ast \end{array}\right ]$.

Литература

• Кулик Б. А. Система логического программирования на основе алгебры кортежей // Изв. РАН. Техн. кибернетика. 1993. № 3. С. 226—239.
• Кулик Б. А. Обобщенный подход к моделированию и анализу интеллектуальных систем на основе алгебры кортежей.
• Кулик Б. А. Курс лекций по логике и математике.
• Кулик Б.А., Зуенко А.А., Фридман А.Я. Алгебраический подход к интеллектуальной обработке данных и знаний – СПб.: Изд-во Политехнического ун-та, 2010. – 235 с.