AntiLogik Sep 24 2023 at 16:21

Приложения алгебры кортежей. Часть 2. Математическая модель вопроса

Medium

11 min

Semantics*Algorithms*ООP*Mathematics*Data compression*

Opinion

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

Об алгебре кортежей (АК) и ее использовании для логико-семантического анализа было рассказано в моей статье в Хабре. В комментариях к статье предлагалось обратить внимание на функцию SELECT в языке SQL, которая соответствует операции Selection (Выборка) в реляционной алгебре. Эта операцию можно рассматривать как один из вариантов математической модели вопроса.

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

Предлагаемый здесь вариант смысла вопроса заключается в том, что в вопросе заданы некоторые ограничения (область знания, ситуация, значения некоторых атрибутов и т.д.), которые требуется использовать для того, чтобы найти или вычислить значение определенного атрибута или проверить правильность заданных в вопросе соотношений. Эта семантика применима к восполняющим вопросам типа «Что?», «Где?», «Когда?», к уточняющим вопросам типа «Верно ли, что А?» и к ИЛИ-вопросам типа «Что правильно: А или Б?». Назовем такие вопросы ограничительными. Их можно считать вариантами известной в искусственном интеллекте задачи удовлетворения ограничений.

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

Особняком стоят ПОЧЕМУ-вопросы, в которых требуется узнать причину возникновения определенного события. Если в базах данных или знаний имеются сведения о событиях и причинах их возникновения (например, причины аварий на дорогах), то эти вопросы можно свести к ограничительным вопросам. Другой вариант математической модели ПОЧЕМУ-вопроса заключается в том, что задана математическая модель системы, в составе параметров которой присутствуют внешние воздействия U_i , в зависимости от которых сменяются состояния S_k системы. Тогда ответ на вопрос «Почему система перешла из состояния S_a в состояние S_b ?» в некоторых случаях может быть решен с помощью соответствующих вычислений. Примерами математических систем такого рада являются автоматы. Математическая модель ПОЧЕМУ-вопроса, по-видимому, может быть темой интересного исследования, но здесь мы ограничимся только постановкой задачи. Далее будут рассмотрены только ограничительные вопросы.

Оглавление

Кратко об алгебре кортежей
Типы данных в алгебре кортежей
Математическая модель ограничительного вопроса
Заключение

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

В основе алгебры кортежей (АК) лежат свойства декартова произведения множеств (ДП), которое по версии Н. Бурбаки было введено в математику Георгом Кантором в конце XIX века. Многие из этих свойств были впервые определены и обоснованы в публикациях по АК. С помощью этих свойств были исследованы связи и соотношения между структурами АК и формулами математической логики.

Рассмотрим, что такое ДП. Пусть заданы n множеств $S_1, S_2, \dots, S_n$ . Тогда их ДП $S_1 \times S_2 \times \dots \times S_n$ с помощью определенных вычислений преобразуется в n-местное отношение, которое можно записать в виде таблицы. В этой таблице будут содержаться все возможные кортежи длины n, у которых на первом месте стоит элемент из множества S_1 , на втором – элемент из множества S_2 и т.д.

Если известны «мощности» множеств (т.е. количество элементов для конечных множеств), формирующих ДП, то общее число кортежей в вычисленном отношении будет равно произведению «мощностей» этих множеств. Например, ДП

$R_1 = \{a, c, d, f\} \times \{B, C, D, F, G\}\times \{3, 5, 10\}$ ,

выраженное в виде таблицы, будет содержать 60 ( $4 \times 5 \times 3$ ) разных кортежей с тремя элементами. Примерами этих кортежей являются (a, B, 3), (c, C, 5), (d, G, 10) и т.д. Этот пример показывает, что степень «сжатия» отношений, выраженных с помощью ДП и их объединений, может быть немалой. Это свойство «сжатия» проявляется не только в объеме занимаемой памяти, но и в уменьшении трудоемкости вычислений, так как практически все операции и проверки соотношений включения и равенства в АК производятся со «сжатыми» структурами.

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

Определены две фиктивные компоненты:

полная компонента (обозначается символом $\ast$ ) равна домену соответствующего (по месту расположения в кортеже) атрибута;
пустая компонента ( $\varnothing$ ).

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

АК содержит 4 типа АК-объектов:

C-кортежи - отношения, представленные одиночными ДП;
C-системы - отношения, представленные объединениями ДП с одинаковыми схемами отношения, выраженными в виде матриц;
D-кортежи - отношения, представленные сжатыми выражениями для дополнений C-кортежей;
D-системы - отношения, представленные сжатыми выражениями для дополнений C-систем.

С-кортежи и матрицы С-систем ограничены квадратными скобками ( [,] ), а D-кортежи и матрицы D-систем – перевернутыми квадратными скобками ( ],[ ).

Например, показанное выше ДП R_1 можно выразить в АК как C-кортеж

$R_1[X_1X_2X_3]= [\{a, c, d, f\} \quad \{B, C, D, F, G\}\quad \{3, 5, 10\}]$ ,

где [X_1X_2X_3] - схема отношения, показывающая, что данный АК-объект задан в пространстве $U = X_1 \times X_2 \times X_3$ .

Если задан универсум для R_1 , например,

$U[X_1X_2X_3] = [\{a, b, c, d, e, f\} \quad \{A, B, C, D, E, F, G\}\quad \{3, 5, 7, 10\}]$ ,

то дополнением R_1 будет D-кортеж $\overline{R_1}[X_1X_2X_3] = ]\{b, e\} \quad \{A, E\}\quad \{7\}[$ .

Компоненты данного D-кортежа являются дополнениями соответствующих компонент в исходном C-кортеже R_1[X_1X_2X_3] .

D-кортеж $\overline{R_1}[X_1X_2X_3]$ можно с помощью определенных алгоритмов выразить как более удобную для расчетов и перечислений C-систему (ниже показаны 2 возможных варианта).

Диагональная C-система: $\overline{R_1}[X_1X_2X_3] =\begin{bmatrix} \{b, e \} & * & *\\ * & \{A, E\} & *\\ * & * & \{7\} \end{bmatrix}$ .
Ортогональная C-система: $\overline{R_1}[X_1X_2X_3] = \begin{bmatrix} \{b, e \} & * & *\\ \{a, c, d, f\} & \{A, E\} & *\\ \{a, c, d, f\} & \{B, C, D, F, G\} & \{7\} \end{bmatrix}$ .

В ортогональной C-системе пересечение всех возможных пар C-кортежей пусто.

Если кратко, то АК – это алгебраическая система <A, O, R>, в которой

носитель A - множество отношений, выраженных АК-объектами;
операции O - содержат операции алгебры множеств (дополнение ( $\overline{M_i}$ ), пересечение $(\cap)$ и объединение $(\cup)$ ) и операции с атрибутами (переименование, добавление фиктивного атрибута, элиминация атрибута);
отношения R – равенство (=) и включение ( $\subseteq, \subset$ ).

Помимо этого в АК разработаны алгоритмы преобразования D-кортежей и D-систем в эквивалентные им (если нужно, ортогональные) C-системы.

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

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

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

Например, пусть $R_k[XZ]= \begin{bmatrix} A_1 & A_3\\ B_1 & B_3 \end{bmatrix}$ .

Тогда после добавления фиктивного атрибута в R_k[XZ] получим АК-объект

$+Y(R_k[XZ]) = R_m[XYZ]=\begin{bmatrix} A_1 & * & A_3\\ B_1 & * & B_3 \end{bmatrix}$ .

При выполнении операции в C-структуры добавляются фиктивные компоненты « $\ast$ », а в D-структуры – фиктивные компоненты « $\varnothing$ ».

Операция соответствует правилу обобщения ( Gen ) в исчислении предикатов, которое в известной книге Э. Мендельсона формулируется так:

$(\forall x_i)A$ следует из .

Соответствие операции правилу обобщения имеет простое объяснение. Например, если отношение содержит фамилии и должности персонала, но в нем не указан возраст, то это означает, что возраст у каждой персоны может быть любым (в разумных пределах, разумеется), поэтому по правилам АК в отношение можно вставить фиктивный атрибут «Возраст» значением которого в каждой строке будет полная компонента « $\ast$ ». Эту компоненту в данном случае можно интерпретировать как значение атрибута "Возраст" неизвестно. Отсюда ясно, что добавление фиктивного атрибута в отношение не приводит к изменению его интерпретации.

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

Обобщенные операции пересечения ( $\cap _G$ ) и объединения ( $\cup _G$ ) – это операции АК, отличающиеся от обычных одноименных операций алгебры множеств тем, что перед их выполнением, если это необходимо, АК-объекты приводятся к одной схеме отношения с помощью операции .

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

Если же операция (-X) используется в D-кортежах или в D-системах, то ее интерпретация существенно изменяется. Если АК-объекту $R[\dots X \dots]$ соответствует логическая формула $F(\dots, x, \dots)$ , то

для C-кортежей или C-систем: $-X(R[\dots X \dots])$ соответствует формуле $\exists x (F(\dots, x, \dots))$ ;
для D-кортежей или D-систем: $-X(R[\dots X \dots])$ соответствует формуле $\forall x (F(\dots, x, \dots))$ ,

где $\exists x$ и $\forall x$ – кванторные выражения, обозначающие соответственно «существует x» и «для всех x».

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

Теорема 1 (проверка включения C-кортежей). Пусть даны два однотипных
C-кортежа $P = [P_1~P_2~ \cdots ~ P_N]$ и $Q = [Q_1~Q_2~ \cdots ~ Q_N]$ . Тогда $P \subseteq Q$ , если и только если $P_i \subseteq Q_i$ верно для всех соответствующих пар компонент сравниваемых C-кортежей.
Теорема 2 (пересечение C-кортежей). Пусть даны два однотипных
C-кортежа $P = [P_1~P_2~ \cdots ~ P_N]$ и $Q = [Q_1~Q_2~ \cdots ~ Q_N]$ . Тогда
$P\cap Q = [P_1 \cap Q_1~~P_2 \cap Q_2~\cdots~P_N \cap Q_N]$ .

Теорема 3 (пустое пересечение C-кортежей). Пусть даны два однотипных C-кортежа $P = [P_1~P_2~ \cdots ~ P_N]$ и $Q = [Q_1~Q_2~ \cdots ~ Q_N]$ ], и в них имеется, по крайней мере, одна пара и компонент, для которых $P_i \cap Q_i = \varnothing$ . Тогда $P \cap Q = \varnothing$ .

Теорема 4 (объединение C-кортежей). Для однотипных
C-кортежей $P = [P_1~P_2~ \cdots ~ P_N]$ и $Q = [Q_1~Q_2~ \cdots ~ Q_N]$ справеливо $P\cup Q \subseteq [P_1 \cup Q_1~~P_2 \cup Q_2~\cdots~P_N \cup Q_N]$ , а равенство соблюдается лишь в следующих случаях:
- $P \subseteq Q$ или $Q \subseteq P$ ;
- для всех пар () выполняется за исключением одной пары.
Теорема 5 (пересечение C-систем). Пусть даны однотипные C-системы и . Результатом их пересечения будет C-система, содержащая все непустые пересечения каждого C-кортежа из с каждым C-кортежем из .

Типы данных в алгебре кортежей

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

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

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

Однако для математической модели вопроса требуется другой подход. Этот подход позволяет представить интервалы как объекты, с которыми можно выполнять такие операции как объединение, пересечение, дополнение. Ссылки на алгоритмы и программные коды для этой системы представления интервалов можно найти на сайте Stack Overflow на русском в некоторых комментариях к вопросу о программировании интервалов.

Математическая модель ограничительного вопроса

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

$Q[XZ_1Z_2Z_3] = [\ast \quad \{a\} \quad \{b,c\} \quad \{d\}]$ ,

где $\ast$ означает множество всех значений атрибута (фиктивный атрибут), а атрибуты Z_1, Z_2, Z_3 заданы некоторыми небольшими множествами значений – во многих случаях это одноэлементные множества.

Если предположить, что является вопросом, то его интерпретация такова: «Чему равно значение атрибута , если заданы значения атрибутов Z_1, Z_2, Z_3 ?».

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

Более сложные случаи вопросов могут содержать более сложные АК-объекты, при этом может потребоваться найти значения более чем одного атрибута. Иногда для ответа на вопрос требуется вычислить не пересечение вопроса с определенным отношением , а проверить соотношение $Q \subseteq R$ . Такая проверка соответствует ответу на уточняющие вопросы.

Рассмотрим некоторые варианты ограничительных вопросов и соответствующие им формулы АК, с помощью которых вычисляется ответы на эти вопросы. Предполагается, что заданные в вопросах АК-объекты R[XYZ] , P[XYZ] и R[YV] являются C-кортежами или C-системами. В выражениях используется обобщенная операция $\cap_G$ , с помощью которой вычисляется пересечение АК-объектов, имеющих разные схемы отношения. Pr_Z и $Pr_{XV}$ обозначают операции вычисления проекций [Z] и [XV] соответственно, которые выполняются с помощью рассмотренной выше операции элиминации атрибута. Если проекция состоит из одного атрибута, то необходимо вычислить объединение содержащихся в ней компонент. Если в проекции число атрибутов 2 и более, то можно сократить число содержащихся в ней C-кортежей, используя приведенную выше Теорему 4.

Вариант 1: Каково значение атрибута в АК-объекте , если и заданы?
- Структура вопроса: $Q_1[XY] = [\{a\} \quad \{b\}]$ .
- Формула ответа на вопрос: $Pr_Z(R[XYZ] \cap_G Q_1[XY])$ .
Вариант 2: Каково значение атрибута в АК-объекте , если и , либо или , , а находится в диапазоне D?
- Структура вопроса: $Q_2[XYZ] =\begin{bmatrix} \{a\} & \{c\} & *\\ \{a, b\} & \{e\} & D \end{bmatrix}$ .
- Формула ответа на вопрос: $Pr_Z(R[XYZ] \cap Q_2[XYZ])$ .
Вариант 3: Каковы значения атрибутов и , если известно, что и даны АК-объекты и ?
- Структура вопроса: $Q_3[Z] =[\{a\}]$ .
- Формула ответа на вопрос: $Pr_{XV}(P[XYZ] \cap_G R[YV] \cap_G Q_3[Z])$ .
Вариант 4: Каковы значения атрибутов и , если известно, что значения атрибута не принадлежат множеству $\{a, c, d\}$ , значения атрибута не принадлежат множеству $\{c, f\}$ и даны АК-объекты и ?
- Структура вопроса: $Q_4[YZ] = \begin{bmatrix} Y \setminus \{a, c, d\}& \ast \\ \{a, c, d\}& Z \setminus \{c, f\}\end{bmatrix}$ .
- Формула ответа на вопрос: $Pr_{XV}(P[XYZ] \cap_G R[YV] \cap_G Q_4[YZ])$ .

Пояснение к Варианту 4. В формулировке вопроса выражен запрет использования всех кортежей элементов, содержащихся в C-кортеже $Q_{not}[YZ] = [\{a, c, d\} \quad \{c, f\}]$ . Поэтому допустимое множество кортежей элементов вычисляется как дополнение $Q_{not}[YZ]$ , т.е. $Q_4 = \overline{Q_{not}}[YZ]$ , выраженное как ортогональная C-система.

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

Заключение

В математической модели ограничительного вопроса АК по сравнению с реляционной алгеброй имеет следующие преимущества:

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

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

Надеюсь, что тема «Приложения алгебры кортежей» еще не закончена. Пока предполагаются следующие возможные темы для продолжения:

вероятностная логика на основе АК;
соотношения между АК и математической логикой
быстрые алгоритмы решения задачи выполнимость конъюнктивной нормальной формы (КНФ) в исчислении высказываний на основе ортогонализации АК-объектов;
общедоступное обоснование классической логики.

Буду признателен, если в комментариях читатели выберут наиболее предпочтительную тему.
Дизайн баннера выполнен Анной Горской

Tags:

Hubs: