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

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

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

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

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

Определение

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

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

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

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

Структуры АК

Обозначения

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

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

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

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

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

Компоненты

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

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

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

C-кортеж

• C-кортеж — кортеж множеств, ограниченный прямыми скобками. Интерпретируется как множество элементарных кортежей, содержащихся в прямом произведении этих множеств. Например, $R[XYZ]=[A\quad B\quad C]$ означает, что $A\subseteq X,\quad B\subseteq Y,\quad C\subseteq 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$ если хотя бы одна компонента равна $\emptyset$, то $P=\emptyset$ ;
• $P\cup Q\subseteq \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\subseteq Q$, тогда и только тогда, когда $\quad P_{i}\subseteq Q_{i}$ для всех $i=1,2,\ldots ,n$.

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

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

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

$G[XZ]=\left]{\begin{array}{cc}\{a,c\}&\emptyset \\\{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\}&\emptyset &\emptyset \\\{a,c,d\}&\emptyset &\{b,c\}\end{array}}\right[,$

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

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

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

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

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

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

С учётом этого предложено (см. книгу Б. А. Кулика, А. А. Зуенко и А. Я. Фридмана) ввести в алгебру кортежей обобщённые операции ($\cap _{G}$, $\cup _{G}$) и обобщённые отношения ($\subseteq _{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})\subseteq 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 с.