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

Тогда PXY,YZ[X,Y,Z,YX,YZ] запишется в виде:

{(3,4)},{(2,3),(3,4),(4,5),(5,6),(6,7)},{(5,6)},{ },{ } .

Этот результат раскладываем в элементарные кортежи.

На шаге 4 выполняем конкретизацию бинарных отношений условной С-системы PXY,YZ[X,Y,Z,YX,YZ], т.е. вычисляем соответствующие операторы

([A, B]), ([A, B]), и ([A, B]). В итоге имеем:

{(3,4)},{(2,3)},{(5,6)},[{(2,3)},{(3,4)}],{(3,4)},{(3,4)},{(5,6)}, [{(3,4)},{(3,4)}],

$PXY,YZ = {(3,4)},{(4,5)},{(5,6)}, , = .{(3,4)},{(5,6)},{(5,6)}, , [{(5,6)},{(5,6)}]{(3,4)},{(6,7)},{(5,6)}, ,{[(6,7)},{(5,6)}]

Значит, исходная формула невыполнима.

Поставленную задачу также можно решить графически (см. рис. 5.4). Из рисунка видно, что после подстановки значений логических переменных в предикаты (x > y) и ( y> z) получим области (множества точек), выделенных темно-серым цветом, которые не имеют пересечения в проекции на ось Y.

Рис. 5.4. Декартовы произведения интервалов.

Таким образом, с помощью АУК появляется возможность автоматизировать анализ составляющих логической формулы [Зуенко, 2008 b], содержащей элементарные двуместные предикаты, и делать выводы относительно их совместимости, а в случаях, когда заданы области определения переменных (как в приведенном примере) – о выполнимости или невыполнимости формулы.

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

190

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

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

5.2.3. Дедуктивные СУБД

В дедуктивных СУБД активно применяется ТФС и доказательнотеоретический подход. Другими словами, дедуктивная СУБД есть результат интеграции СУБД с системами логического вывода. Выполнение запроса здесь представляет собой доказательство некоторой теоремы с помощью специализированных дедуктивных аксиом и правил вывода. Основные аксиомы, соответствующие элементам домена и кортежам базовых отношений, называются экстенсиональной базой данных (extensional database – EDB). Дополнительные дедуктивные аксиомы вместе с ограничениями целостности образуют интенсиональную базу данных (intensional database – IDB).

Разработке единого языка для таких комбинированных систем посвящено большое число работ. Среди них можно выделить два направления [Чери,

1992]:

1)работы, в которых предусматривается интеграция систем управления реляционными БД с Пролог-системами, т.е. CPR-системы (аббревиатура от

Coupling Prolog to Relational databases);

2)работы, в которых принят единый язык управления БД и системой логического вывода – Дейталог. Описание постановки задачи на этом языке называется Дейталог-программой, а часть Дейталог-программы, не содержащей факты, – Дейталог-правилами.

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

Графы. Как правило, граф определяется в математике "геометрическим" способом: на множестве вершин V задается множество E их упорядоченных пар, которые называются дугами графа и изображаются в виде линий со

191

стрелками, направленными от одних вершин к другим. Если в графе какая-либо пара вершин соединена прямой и обратной дугой, то такое "двунаправленное" соединение между вершинами называется ребром графа. Ребра изображаются с помощью линий без стрелок. Граф, у которого все связи представлены только ребрами, называется неориентированным графом (или просто графом), граф, не содержащий ребер, – ориентированным графом, а граф, включающий и ребра, и дуги – смешанным.

Путь в графе есть последовательность его вершин, в которой пары соседних вершин соединены дугой, для которой одна из вершин – начальная, а другая – конечная. Вершина y графа G называется достижимой из вершины x, если в G существует путь из вершины x в вершину y. Если в графе имеется путь с совпадающими начальной и конечной вершиной, такой путь именуется

циклом.

Транзитивное замыкание графа G, содержащего n вершин, – это граф G+, где каждая вершина соединена дугой со всеми достижимыми вершинами.

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

Рис. 5.5. Пример графа.

{a} {b,c,d,e}

Его можно записать как C-систему G[XY] = {b} {d} ,

{c} {a,b,d,e}

изоморфную матрице смежности графа.

На графах часто используется композиция G G, т.е. композиция графа с самим собой, сокращенно обозначаемая как G2. Применяется и более высокая "степень" композиции, например, G3 = G G G и т.д.

192

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

G+ = G G2 G3 … Gk, где k n.

Практически во всех случаях преобразование конечного графа G в граф G+ заканчивается прежде, чем будет получена последняя "степень" Gk. Критерием

Рекурсивные запросы. Для иллюстрации возможностей применения АК при решении задач, типичных для дедуктивных СУБД, рассмотрим пример из [Чери, 1992]. В базе данных содержится упрощенная коммерческая система, состоящая из 11 фирм. Каждая фирма занимает определенную долю рынка в процентах для каждого вида товаров. Эти сведения содержатся в таблице "Фирмы". В таблице "Отношения собственности" показаны пары фирм и проценты всех акций Фирмы2, являющиеся собственностью Фирмы1. В таблице "Трестовский лимит" находятся наименования товаров и квота рынка в

193

процентах для каждого товара (см. таблицы 5.5-5.7).

В[Чери, 1992] решается "Антитрестовская задача", состоящая в следующем. В законодательстве некоторых стран существуют законы, не позволяющие фирмам непосредственно или косвенно (через другие фирмы) контролировать долю рынка более заданной. Известно также, что если фирма владеет контрольным пакетом акций другой фирмы (51% и выше), то она имеет возможность контролировать деятельность дочерней фирмы. Таким образом, возможна ситуация, когда доля рынка товаров самой фирмы не выходит за рамки квоты, но при учете других участников рынка, контролируемых этой фирмой, суммарная доля может превысить квоту для определенного товара. В данном случае необходимо выявить фирмы, торгующие товаром T1 и нарушающие антитрестовский закон.

В[Чери, 1992] для постановки задачи используется язык логического программирования Пролог. Решим задачу в терминах АК и теории графов. Селектором для данной задачи являются фирмы, торгующие товаром T1 и имеющие контрольный пакет акций каких-либо других фирм.