Материал: Алгебра_кортежей

индивидные константы, множества слотов (другие фреймы) или правила

[Искусственный интеллект, 1990; Смолин, 2004; Представление знаний, 1989].

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

Если значение некоторого слота есть множество слотов, то это отношение (фрейм) имеет атрибут (слот), являющийся многоместным отношением, и этот фрейм представляет собой суперпозицию многоместных отношений. Во многих случаях фреймы можно отобразить как сеть взаимосвязанных многоместных отношений. Правила или продукции, которые во фреймах присутствуют в качестве значений некоторых слотов или используются в продукционных системах, эквивалентны логическим формулам (см. п. 1.3), представимым (по крайней мере, теоретически) как многоместные отношения.

Задачи семантического анализа текста, перевода текстов с одного языка на другой и т.д. практически невозможны без преобразования предложений в отношения. Например, предложение "Ракета "Союз-ФГ" стартовала в воскресенье в 11.01 мск с космодрома Байконур" можно выразить как элемент отношения

СТАРТОВАТЬ (Объект действия, время действия, место действия).

Одна из основных задач искусственного интеллекта заключается в автоматизации работы со знаниями, представленными в виде текстов [Башмаков, 2005; Искусственный интеллект, 1990]. С этой проблемой тесно переплетается задача перевода текстов с одного языка на другой [Башмаков, 2005]. Решение такой задачи состоит из следующих этапов: 1) лексический анализ; 2) морфологический анализ; 3) синтаксический анализ и 4) семантический анализ. Для выполнения семантического анализа необходимо перевести текст во "внутреннее представление", т.е. представить в виде семантической сети [Башмаков, 2005], которая, как было сказано выше, есть взаимосвязанная совокупность бинарных отношений.

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

70

Глава 2. Теоретические основы алгебры кортежей

Чтобы разобраться в бесконечном, надо сперва различать, а затем связывать.

И.В. фон Гете, "Фауст"

Из обзора, приведенного в главе 1, следует, что общая теория отношений пока полностью не разработана. В теории бинарных отношений и реляционной алгебре многоместное отношение трактуется как подмножество элементарных кортежей, входящих в некоторое декартово произведение. Это классическое определение позволяет оперировать с отношениями как с обычными множествами при условии, что отношения сформированы в одном и том же декартовом произведении D. Но соответствие алгебры многоместных отношений алгебре множеств теряется при переходе к совокупностям отношений, заданных в различных декартовых произведениях, поскольку для них не удается определить операции объединения и пересечения. Также в алгебре многоместных отношений существуют операции соединения и композиции, для которых нет эквивалента в алгебре множеств.

Рассматриваемая в этой и последующих главах алгебра кортежей реализует общую теорию многоместных отношений, пригодную для задач логического анализа. В качестве основной структуры АК выступает не элементарный кортеж, а декартово произведение множеств, которому в исчислении предикатов соответствует конъюнкция предикатов или формул, попарно не содержащих совпадающих переменных. По сути, алгебра кортежей представляет собой алгебру декартовых произведений и их дополнений: каждый кортеж, в зависимости от его принадлежности к определенному классу АК-объектов, интерпретируется либо как декартово произведение множеств, либо как дополнение некоторого декартова произведения множеств.

2.1 Основные термины и структуры

Алгебра кортежей была разработана для моделирования и анализа многоместных отношений [Кулик, 1993; 2008]. В отличие от реляционной алгебры, применяющейся для формализации БД, АК позволяет использовать все средства логического моделирования и анализа систем, которые входят в

71

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

В математике кортежем называется последовательность некоторых объектов.

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

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

Кроме операций, типичных для алгебры множеств, в АК добавлено 5 операций с атрибутами:

1)переименование атрибутов;

2)перестановка атрибутов и соответствующих им столбцов;

3)обращение АК-объектов;

4)добавление нового фиктивного атрибута (+Atr);

5)элиминация атрибута из АК-объекта (–Atr).

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

72

Если задано некое отношение, то его определяющий признак – совокупность присущих ему атрибутов. Последовательность этих атрибутов в АК называется схемой отношения. Универсум отношения есть декартово произведение доменов атрибутов, представленных в его схеме.

АК-объекты, сформированные в одной и той же схеме отношения, называются однотипными. Универсум для совокупности однотипных отношений называется частным универсумом.

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

Размерность АК-объекта определяется как размерность его матричного отображения (т.е. число строк и столбцов) независимо от мощности компонент, из которых он сформирован.

Эквивалентными являются АК-объекты, у которых совпадают множества содержащихся в них элементарных кортежей. Другими словами, два АК-объекта P и Q эквивалентны, если выполняется как P Q, так и Q P.

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

Например, если задан элементарный кортеж T[XYZ] = (a, b, c), то подразумевается, что a X, b Y и c Z. В АК элементарные кортежи принадлежат множествам (отношениям), выраженных другими типами АК-объектов.

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

1)полная компонента – " " – равна домену соответствующего (по месту

еерасположения в кортеже) атрибута, используется в C-кортежах и C-системах;

2)пустое множество – " " – используется в D-кортежах и D-системах.

Далее будет показано, что за счет использования фиктивных компонент (фиктивных атрибутов) в АК имеется возможность приводить отношения с различными схемами к одному типу, что позволяет применять к ним теоретико-

73

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

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

Определение 2.3. C-кортежем называется заданный в определенной схеме отношения кортеж компонент.

Префиксы "C" и "D" в названиях структурных типов АК-объектов выбраны не случайно. Это сокращенные обозначения логических понятий "конъюнкция" (conjunction) и "дизъюнкция" (disjunction), которые отображают структуры, соединенные логическими связками "И" (конъюнкция) и "ИЛИ" (дизъюнкция). При сопоставлении со структурами математической логики можно обосновать (см. п. 2.4), что C-кортежи соответствуют конъюнкции некоторых структур, а D-кортежи – дизъюнкции.

C-кортеж эквивалентен некоторому множеству элементарных кортежей – это множество можно перечислить, если вычислить декартово произведение компонент C-кортежа. Для изображения C-кортежей используются прямые скобки. Например, R[XYZ] = [A B C] означает, что A X, B Y, C Z и R[XYZ] = A B C.

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

R[XYZ] = {b, d} {f, h} {a, b} и Q[YZ] = {f, g} {a, c}.

Эти отношения можно записать как C-кортежи:

R[XYZ] = [{b, d} {f, h} {a, b}], Q[YZ] = [{f, g} {a, c}].

Поскольку каждый C-кортеж есть декартово произведение множеств, он содержит некоторое множество элементарных кортежей. Например,

( f ,a)

( f ,c)

Q[YZ] = [{f, g} {a, c}] = {f, g} {a, c} = (g,a) .

(g,c)

C-кортеж, у которого имеется хотя бы одна пустая компонента, пуст. C-кортеж со всеми полными компонентами эквивалентен некоторому частному

74