РЕАЛІЗАЦІЯ ШВИДКОГО ЛОГІЧНОГО ВИСНОВКУ В СЕРЕДОВИЩІ 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).

n 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 - Y differenceSorted:

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 х 2 , х т ) і (y v у 2 , ..., у до ) за випадковим збігом значень змінних x i = у у В реляційній алгебрі даної функції відповідає операція INNER JOIN. Кількість розгорнутих вершин дерева пошуку для даної операції в разі наявного виведення становить п х п у , а для з'єднання відсортованих списків

де n xi і п о) - кількість значень, що повторюються в першому і другому списках відповідно.

Якщо знехтувати можливістю повторення одних і тих же значень в обох списках (n xi > 1 л n yj > 1), а також знехтувати випадками (n xi > 1 л n y j = 0) і (n xi = 0 л п у 1 > 1), то формулу (3.2) можна спростити:

де d x і d y - число дублікатів значень в списках X і Y відповідно.

Нижче представлений текст предиката, що реалізує дану операцію над двома множинами кортежів {(х ^ х 2 )} і {(у {1 у 2 )} за випадковим збігом 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 = (X- Y) +

+ (У-Х) + (ХПУ)

UNION

list :: union

п х + П у

з'єднання

JOIN

Відсутнє

п х + V

+ D x + d y

Таким чином, використання реляційних операцій над відсортованими списками забезпечує поліноміальних складність логічного висновку. На жаль, цей метод не охоплює всі можливі запити до бази знань. Зокрема, він працює ефективно тільки при з'єднанні декількох умов правила по рівності значень аргументів. Якщо аргументи кількох умов зіставляються за умовами «більше», «менше» або «не дорівнює», ефективність методу істотно знижується.

  • [1] Див .: Дейт К.Дж. Введення в системи баз даних. 8-е изд. М .: Вільямс, 2006.
 
Переглянути оригінал
< Попер   ЗМІСТ   ОРИГІНАЛ   Наст >