Оценки длин переформулировок запросов к снабженным логической теорией базам данных

В цикле работ В.В. Подольского был получен ряд результатов по приложению теории сложности булевых схем к так называемым базам данных с онтологическим доступом. На элементах такой базы данных задаются предикаты, а также некоторая логическая теория первого порядка. Запросом к такой базе данных является формула логики первого порядка, а ответом на запрос является набор элементов базы данных, удовлетворяющий этой формуле. Одним из основных вопросов в этой области является вопрос об алгоритмической сложности задачи поиска ответа на заданный запрос к базе данных. Стандартным подходом к решению этой задачи является переформулировка заданного запроса к базе данных в таком виде, чтобы поиск ответа на запрос зависел лишь от значения предикатов, заданных на элементах базы. В цикле из трех работ, совместных с разными соавторами, исследовался вопрос о том, насколько увеличивается длина запроса при такой переформулировке. Был получен ряд верхних и нижних оценок этой величины при различных ограничениях на виды рассматриваемых логических теорий, запросов и переформулировок запросов. Для получения этих оценок используются классические результаты из теории сложности булевых схем. Была введена новая модель вычисления булевых функций, так называемые гиперграфовые программы. Эта модель была использована как связующее звено между запросами к базам данных и булевыми схемами.

Список литературы

1. Georg Gottlob, Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Thomas Schwentick, Michael Zakharyaschev, “The price of query rewriting in ontology-based data access”, Artificial Intelligence, 213 (2014), 42–59            
2. Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Michael Zakharyaschev, “On the Succinctness of Query Rewriting over OWL 2 QL Ontologies with Bounded Chase”, Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), ACM Digital Library, 2014, 57:1–57:10 , arXiv: 1401.4420
3. Meghyn Bienvenu, Stanislav Kikot, Vladimir V. Podolskii, “Tree-like Queries in OWL 2 QL: Succinctness and Complexity Results”, 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), IEEE, 2015, 317–328 , arXiv: 1406.3047