📄Работа №125007
Тема: Выделение общих с точностью до имен переменных подформул из базы данных для решения задачи «Конъюнктивный булевский запрос»
Характеристики работы
Тип работы
Дипломные работы, ВКР
Предмет
Информационные системы
Объем:
77 листов
Год:
2018
Просмотров:
52
4800
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
Введение 3
Многоуровневое описание классов 6
Многоуровневое описание базы данных для решения задачи «Конъюнктивный булевский запрос» 10
Алгоритм выделения общих подформул 14
Список литературы 19
Приложение А: Код программы 20
Приложение B: Пример работы алгоритма 40
Многоуровневое описание классов 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(ш) часто меняются).
Для уменьшения числа шагов решения задачи выполнимости существует алгоритм построения многоуровневого описания классов, который будет рассмотрен далее. Однако тот же алгоритм не может быть эффективно использован для решения задачи «Конъюнктивный булевский запрос» из-за различий между данными задачами, в связи с чем предлагается его модификация.
При использовании баз данных время выполнения запроса - очень важная характеристика, особенно если учитывать объемы данных, хранящихся в современных базах. «Конъюнктивный булевский запрос» - 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(ш) часто меняются).
Для уменьшения числа шагов решения задачи выполнимости существует алгоритм построения многоуровневого описания классов, который будет рассмотрен далее. Однако тот же алгоритм не может быть эффективно использован для решения задачи «Конъюнктивный булевский запрос» из-за различий между данными задачами, в связи с чем предлагается его модификация.
✅ Заключение
В данной работе разработан подход с целью выделения общих с точностью до имен переменных подформул из базы данных для решения задачи «Конъюнктивный булевский запрос», рассмотрена его реализация.
При использовании баз данных время выполнения запроса - очень важная характеристика, особенно если учитывать объемы данных, хранящихся в современных базах. «Конъюнктивный булевский запрос» - NP-полная задача, касающаяся баз данных. Для уменьшения числа шагов решения задачи выполнимости существует алгоритм построения многоуровневого описания классов, который и модифицирован в работе, поскольку не может быть эффективно использован для конъюнктивного булевского запроса из-за существующих различий в самих задачах.
При использовании баз данных время выполнения запроса - очень важная характеристика, особенно если учитывать объемы данных, хранящихся в современных базах. «Конъюнктивный булевский запрос» - NP-полная задача, касающаяся баз данных. Для уменьшения числа шагов решения задачи выполнимости существует алгоритм построения многоуровневого описания классов, который и модифицирован в работе, поскольку не может быть эффективно использован для конъюнктивного булевского запроса из-за существующих различий в самих задачах.
ИЛИ
Поиск аналога
📕 Список литературы
🖼 Скриншоты
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.