Реализация быстрого логического вывода в среде Prolog

Набор базовых операций реляционной алгебры включает в себя пересечение X n Y (INTERSECT), вычитание X — Y (DIFFERENCE), объединение XuY (UNION), соединение (JOIN), проекцию, дополнение (NOT) и фильтрацию (WHERE)'. Реализация над двумя списками X = {х} и Y = {у} операций пересечения, разности и объеди;

п_хп_у

нения предполагает в среднем развертывание —-— вершин дерева поиска (список Y сканируется до первого появления искомого значения), где п_х и п_у — количество фактов в множествах X и Y соответственно. Для операции соединения развертывается п_хп_у вершин, поскольку соединение представляет собой декартово произведение с фильтрацией. Операции дополнения и фильтрации в языке SWRL являются простыми, поскольку здесь не допускается вложенный поиск, как SUBSELECT в СУБД, и требуют развертывания только п_х вершин.

Ниже приведен текст предиката intersection, входящего в состав библиотеки lists SWI-Prolog. Здесь и далее вместо множеств мы будем говорить о списках. Во-первых, список — это агрегат данных, с которым манипулирует Prolog, во-вторых, списки^[1]

допускают повторяющиеся значения, сохранение которых неооходимо в некоторых операциях:

intersection ([],_, []).

intersection ([Х|Т], L, Intersect) memberchk (X, L),!,.

Intersect = [X|R], intersection (T, L, R). intersection ([_|T], L, R) intersection (T, L, R) .

ⁿy

Предикат memberchk вызывает извлечение в среднем — эле;

менов списка Y для каждого элемента списка X, что и обусловливает низкую скорость работы данного предиката.

Отсортируем списки X = {д} и Y = {у} по возрастанию значений. В этом случае оба списка можно обрабатывать совместно, и дерево поиска будет состоять из п_х + п_у вершин. Таким образом, ожидаемое ускорение обусловлено переходом от квадратичной к линейной зависимости сложности поиска от числа фактов. Предикат нахождения пересечения отсортированных списков intersectSorted представлен ниже:

intersectSorted ([],_, []).

intersectSorted (_, [], []).

intersectSorted ([Y|Xs], [Y|Ys], [Y|XxY]).

intersectSorted (Xs, Ys, XxY),!. intersectSorted ([X|Xs], [Y|Ys], XxY) X>Y,.

intersectSorted ([X|Xs], Ys, XxY),!. intersectSorted ([_|Xs], [Y|Ys], XxY).

intersectSorted (Xs, [Y|Ys], XxY).

Похожим образом реализуется операция вычитания множеств X — YdifferenceSorted:

differenceSorted ([],_, []) :-!.

differenceSorted (R, [], R) :-!.

differenceSorted ([X|Xs], [X|Ys], XmY).

differenceSorted (Xs, [X|Ys], XmY),!.

differenceSorted ([X|Xs], [Y|Ys], [X|XmY]).

X.

differenceSorted ([X|Xs], Ys, XmY).

Операция объединения множеств состоит из суммы двух вычитаний множеств плюс их пересечение:

т.е. требует пяти операций. Создание отдельного предиката unionSorted для операции объединения позволит сократить размерность данной задачи:

unionSorted ([], R, R) unionSorted (R, [], R).

unionSorted ([H|Xs], [H|Ys], [H|XuY]).

unionSorted (Xs, Ys, XuY),!. unionSorted ([X|Xs], [Y|Ys], [X|XuY]).

X.

unionSorted ([X|Xs], [Y|Ys], [Y|XuY]).

unionSorted ([X|Xs], Ys, XuY).

Наиболее часто в процессе интерпретации условий правил требуется соединение двух множеств кортежей (x_v х₂, х_т) и (y_v у₂, …, у_к) по совпадению значений переменных x_i = у у В реляционной алгебре данной функции соответствует операция INNER JOIN. Количество развертываемых вершин дерева поиска для данной операции в случае наивного вывода составляет п_хп_у, а для соединения отсортированных списков.

где n_xi и п_у) — количество повторяющихся значений в первом и втором списках соответственно.

Если пренебречь возможностью повторения одних и тех же значений в обоих списках (n_xi > 1 л n_yj > 1), а также пренебречь случаями (n_xi > 1 л n_yj = 0) и (n_xi = 0 л п_у1 >1), то формулу (3.2) можно упростить:

где d_x и d_y — число дубликатов значений в списках X и Y соответственно.

Ниже представлен текст предиката, реализующего данную операцию над двумя множествами кортежей {(х^ х₂)} и {(у_{1 у₂)} по совпадению x_t = у_х:

innerJoinSorted ([],_, Final, Final) :-!.

innerJoinSorted ([t (XI, X2) IXresidue], Y, In,.

Final).

inner Join Sort edl (t (XI, X2), Y, YtoLookUp, XY), append (In, XY, Out) ,.

innerJoinSorted (Xresidue, YtoLookUp, Out, Final). innerJoinSortedl (_, [], [], []) :-!.

innerJoinSortedl (t (X1_/_X2)_/ [t (Yl, Y2) lYresidue], [t (Yl, Y2) lYresidue], []) X1.

innerJoinSortedl (t (XI, X2), [t (Yl,_) lYresidue], YlookUp, XY) X1>Y1, !,.

innerJoinSortedl (t (XI, X2), Yresidue, YlookUp, XY) .

innerJoinSortedl (t (XI, X2), [t (Yl, Y2).

|Yresidue],.

[t (Yl, Y2) | YlookUp], [t (XI, X2, Y2) |XY]).

innerJoinSortedl (t (XI, X2), Yresidue, YlookUp, XY) .

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

Таблица 33

Сложность реализации операций реляционной алгебры на языке Prolog

Операция.	Оператор в СУБД.	Встроенный предикат в Visual Prolog	Сложность встроенного предиката.	Сложность быстрого предиката.
Пересечение In Y	INTERSECT	list: : intersection.		пх + пу
Разность X- Y	MINUS	list: difference.		пх + пу
Объединение Xu Y=(XY) +. + (У-Х) + (ХпУ).	UNION	list: union.		пх + Пу
Соединение.	JOIN	Отсутствует.		пх + V. + dx+ dy

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

• [1] См.: Дейт К.Дж.

  Введение

  в системы баз данных. 8-е изд. М.: Вильямс, 2006.