Выделение общих с точностью до имен переменных подформул из базы данных для решения задачи «Конъюнктивный булевский запрос»

Введение 3
Многоуровневое описание классов 6
Многоуровневое описание базы данных для решения зада­чи «Конъюнктивный булевский запрос» 10
Алгоритм выделения общих подформул 14
Список литературы 19
Приложение А: Код программы 20
Приложение B: Пример работы алгоритма 40
Купить

В данной работе предлагается подход для выделения общих с точ­ностью до имен переменных подформул из базы данных для решения задачи «Конъюнктивный булевский запрос» и описывается его реали­зация.
При использовании баз данных время выполнения запроса - очень важ­ная характеристика, особенно если учитывать объемы данных, храня­щихся в современных базах. «Конъюнктивный булевский запрос» - NP- полная задача, касающаяся баз данных. Далее приведена ее формули­ровка, как она дана в [2]:
Конъюнктивный булевский запрос
ДАНО. Домен D, набор отношений R = {R1, R2,..., Rm](где Ri есть подмножество множества Ddi), конъюнктивный булевский запрос Q над R и D, т.е. запрос вида
(Эу1;У2; ...;Ут ^^l Л Л ... Л Ar
где Ai имеет вид Ri(u1,u2, ...,Udl), а переменные и принадлежат множе­ству ({У1,У2,...,У1} и D).
ВОПРОС. Верно ли, что Q истинен при интерпретации его как утвер­ждения об R и D?
Данную задачу можно переформулировать следующим образом:
Конъюнктивный булевский запрос
ДАНО. Множество объектов D, предикаты p1,p2, ...pm, задающие отно­шения на D. Множество истинных на D постоянных атомарных фор­мул S(D). Элементарная конъюнкция Q вида A1 & А2 & ... & Ar, где Ai = pi(u1,u2, ...,Ukl), ut - переменные или константы из D.
ВОПРОС. Верно ли, что Q выполняется на D?
S(D) ЗУ1,У2,...,Ут (A1 & A2 & ... & Ar)?
В этом виде задача получается весьма схожей с задачей «Выполни­мость в конечной интерпретации» [4, 5], которая возникает при распо­знавании объектов в рамках логико-предметного подхода к распозна­ванию образов. Данная задача формулируется следующим образом:
Выполнимость в конечной интерпретации
ДАНО. Множество ш = {ш1, ш2,..., шг}, набор предикатов {p1,p2, ...,pn}, задающих свойства элементов из ш и отношения между ними, набор S(ш) истинных постоянных атомарных формул видаPi(T), где i = 1,..., n, т С ш, бескванторная формула A (у), представленная в виде дизъюнк­ции элементарных конъюнкций атомарных формул (у = (у1,...,уа) - список предметных переменных, входящих в формулу).
ВОПРОС. Существует ли набор значений для у из ша, для которого формула A(y) истинна? Или другими словами
S(ш) ЗуА(у)?
Алгоритм полного перебора всех возможных подстановок, как было доказано в [4], имеет число шагов
O(tmS ||),
где t - число элементов в ш, m - количество переменных в A(x), ||S|| - число атомарных формул в описании S(ш).
Алгоритмы, основанные на построении вывода в исчислении предика­тов, имеют число шагов
О( £ Ц),
i:pi is in A(x)
где si и ai - количество вхождений предиката pi в описание S(ш) и в формулу A(x) соответственно. Очевидно, те же оценки будут и у алго­ритмов решения задачи «Конъюнктивный булевский запрос».
Важное различие данных задач состоит в следующем:
- база данных, как правило, меняется довольно редко или вообще по­стоянна, а запросы, наоборот, каждый раз различные (S(D) неизменна, а запрос Q сильно изменчив);
- в распознавании образов множество формул может либо не меняться совсем, либо меняться, но очень редко, а распознаваемые объекты мо­гут появляться различные (A(y) неизменна, а объект ш и его описание S(ш) часто меняются).
Для уменьшения числа шагов решения задачи выполнимости существу­ет алгоритм построения многоуровневого описания классов, который будет рассмотрен далее. Однако тот же алгоритм не может быть эф­фективно использован для решения задачи «Конъюнктивный булев­ский запрос» из-за различий между данными задачами, в связи с чем предлагается его модификация.
Купить