Совместное применение методов распространения ограничений и структурной декомпозиции для априорного анализа запросов к онтологиям
Автор: Зуенко А.А., Ломов П.А.
Журнал: Онтология проектирования @ontology-of-designing
Рубрика: Инжиниринг онтологий
Статья в выпуске: 4 (30) т.8, 2018 года.
Бесплатный доступ
В отличие от реляционных СУБД, ориентированных на поддержку ссылочной целостности интенсивно меняющихся данных, при использовании RDF-репозиториев для хранения онтологий нет необходимости оперировать такими атомарными структурами, как элементарный кортеж таблицы, а можно использовать более подходящие структуры для группирования и обобщения информации. В статье онтология рассматривается как совокупность отношений (унарных и бинарных), выраженных с помощью специализированных матрицеподобных структур - С -систем, что позволяет ставить и решать задачи вывода на онтологии как задачи удовлетворения ограничений. Рассматриваемая в статье задача априорного анализа и упрощения SPARQL-запросов решается для онтологий, которые разработаны с применением онтологических паттернов содержания, что обеспечивает предсказуемость структуры потенциальных запросов. Каждому паттерну сопоставляется совокупность шаблонов SPARQL-запросов. Разработан метод априорного анализа и преобразования шаблонов SPARQL-запросов в форму, позволяющую ускорить последующее исполнение конкретизированных пользовательских запросов. Метод основан на совместном применении методов структурной декомпозиции и авторских методов удовлетворения нечисловых ограничений. Применение методов структурной декомпозиции дает возможность разбивать шаблон SPARQL-запроса на части, распараллеливать выполнение подзадач, что особенно актуально при обращении к RDF-репозиториям большого объёма. Для соединения отношений, выраженных в виде совокупности С -систем, применяются авторские методы удовлетворения нечисловых ограничений, которые представляют собой модификации известных методов достижения совместности в вершинах и по дугам. Предлагаемый подход к представлению онтологии, а также к организации процедур вывода на онтологиях, позволяет снизить потребный объём памяти на хранение онтологии и обеспечить приемлемую скорость выполнения SPARQL-запросов.
Короткий адрес: https://sciup.org/170178803
IDR: 170178803 | УДК: 004.89,
Combining of methods of constraint propagation and structural decomposition for the a priori analysis of queries to the ontologies
Unlike relational DBMS that focused on maintaining of the referential integrity of rapidly changing transactional data, while using of RDF repositories which are storages for ontologies, there is no need to operate with such atomic structures as a tuple and you can use more suitable structures for grouping and summarizing of information. The article considers ontology as a set of relations (unary and binary), which are represented by specialized matrix-like structures - C -systems. That allows us to consider tasks of inference on ontologies as constraint satisfaction problems. The problem of a priori analysis and simplification of the SPARQL queries, considered in the article, is solved for ontologies that are developed using content ontology design patterns, which ensures the predictability of the structure of potential queries. In fact, each pattern is associated with a set of patterns of SPARQL queries. A method of a priori analysis and transformation of SPARQL queries patterns into a form, which speeds up the subsequent execution of concrete user queries has been developed. The method is based on the combining of the methods of structural decomposition and the author's methods for non-numeric constraints satisfaction. The structural decomposition methods make it possible to split the SPARQL query pattern into parts and parallelize its execution, which is especially important when accessing large volume RDF repositories. Due to the low frequency of modifications of the RDF repository, it is possible, based on the analysis of templates, to prepare data structures for the subsequent execution of concrete queries. This allows you to avoid unnecessary overhead incurred by repeated execution of the operation of joining the same relations when processing user requests described by a common pattern. For the join of relations, expressed as a set of C -systems, author's methods of non-numeric constraints satisfaction are applied, which are modifications of the known methods of maintaining node and arc consistency. As a result, the proposed approach to the ontology presentation and organization of inference procedures on ontologies allows to reduce the memory consumption and to ensure an acceptable speed of execution of SPARQL queries even for RDF repositories containing large amounts of data.
Список литературы Совместное применение методов распространения ограничений и структурной декомпозиции для априорного анализа запросов к онтологиям
- Зуенко, А.А. Применение методов распространения ограничений для ускорения обработки запросов к онтологиям / А.А. Зуенко, П.А. Ломов, А.Г. Олейник // Труды СПИИРАН. - 2017. - №1(50). - С.112-136.
- Ontology of Integrated Knowledge Space. - https://github.com/palandlom/ontology-of-integrated-knowledge-space.
- Blomqvist, E. Experimenting with eXtreme Design / E. Blomqvist, V. Presutti, E. Daga, A. Gangemi // In proceedings of EKAW 2010, LNCS 6317. Springer 2010. Berlin/Heidelberg/New York. - P. 120-134.
- Russel, S. Artificial Intelligence: A Modern Approach. 3rd edition / S. Russel, P. Norvig / Prentice Hall, 2010. - 1132 p.
- Bartak, R. Constraint Programming: In Pursuit of the Holy Grail / R. Bartak // Proceedings of the Week of Doctoral Students (WDS99), Part IV. - Prague: MatFyzPress, 1999. - P. 555-564.
