Применение методов распространения ограничений для ускорения обработки запросов к онтологиям
Ключевые слова:
запрос к онтологии, задача удовлетворения ограничений, матричное представление ограничений, распространение ограниченийАннотация
В статье предлагается рассматривать задачу обработки SPARQL-запросов к онтологии как задачу удовлетворения ограничений. Кратко представлен формальный аппарат, служащий для описания задач удовлетворения ограничений с помощью специализированных матрицеподобных структур. Применение данного аппарата позволяет более эффективно по сравнению с табличным представлением описывать, хранить и обрабатывать нечисловые ограничения предметной области. Для ускорения обработки запросов к онтологиям большого объема предлагается применить ранее разработанный авторами метод распространения нечисловых ограничений. По сравнению с традиционным подходом к обработке SPARQL-запросов, базирующимся на динамическом программировании, предлагаемый метод позволяет ускорить их выполнение за счет «компактного» представления онтологии, а также применения оригинальных авторских правил редукции пространства поиска. На конкретном примере показано использование этого математического аппарата для снижения размерности пространства поиска при выполнении запроса к онтологии междисциплинарных знаний.Литература
1. Gangemi A. Ontology Design Patterns for Semantic Web Content // Proceedings of the Fourth International Semantic Web Conference. Galway. Ireland. Springer. 2005. pp. 262–276.
2. Олейник А.Г., Ломов П.А. О формировании единого пространства мультипредметных знаний Кольского научного центра РАН // Труды пятой международной конференции «Системный анализ и информационные технологии» САИТ-2013). 2013. Т.1. С. 258–265.
3. Nikolić N. et al. RDF Stores Performance Test on Servers with Average Specification // Proceedings of the 5th International Conference on Information Science and Technology (ICIST). 2015. pp. 67–72.
4. Neumann T., Weikum G. RDF3X: a RISCstyle engine for RDF // Proceedings of the 34th International Conference on Very Large Data Bases (VLDB). Auckland. New Zealand. 2008. pp. 647–659.
5. Зуенко А.А. Вывод на ограничениях с применением матричного представления конечных предикатов // Искусственный интеллект и принятие решений. 2014. № 3. C. 21–31.
6. Smith B. et al. IAO-Intel: An Ontology of Information Artifacts in the Intelligence Domain // Proceedings of the Eighth International Conference on Semantic Technologies for Intelligence, Defense and Security (STIDS), (CEUR 2013). 2013. vol. 1097. pp. 33–40.
7. Basic Formal Ontology. URL: http://ifomis.uni-saarland.de/bfo/ (дата обращения: 10.11.2016).
8. Lomov P., Shishaev M. Ad-hoc Synthesis of Composite Content Ontology Design Patterns // Proceedings of the 26th International Conference on Information Modelling and Knowledge Bases (EJC 2016). Tampere University of Technology. Pori. 2016. pp. 25–33.
9. Blomqvist E, Hammar K, Presutti V. Engineering Ontologies with Patterns: The eXtreme Design Methodology // Ontology Engineering with Ontology Design Patterns. IOS Press. 2016. vol. 25. pp. 23–50.
10. Blomqvist E., Presutti V., Daga E., Gangemi A. Experimenting with eXtreme Design // Proceedings of EKAW 2010. Springer. Berlin-Heidelberg-New York. 2010. LNCS 6317. pp. 120–134.
11. Ontology of Integrated Knowledge Space. URL: https://github.com/palandlom/ontology-of-integrated-knowledge-space. (дата обращения: 11.11.2016).
12. Schmidt M., Meier M., Lausen G. Foundations of SPARQL query optimization // Proceedings of the 13th International Conference on Database Theory. 2010. .pp. 4–33.
13. Tsialiamanis P. et al. Heuristics-based query optimisation for SPARQL // Proceedings of the 15th International Conference on Extending Database Technology (EDBT '12). ACM. 2012. pp. 324–335.
14. Aranda C., Arenas M., Corcho M. Semantics and Optimization of the SPARQL 1.1 Federation Extension The Semanic Web: Research and Applications // 8th Extended Semantic Web Conference. Springer Berlin Heidelberg. 2011. pp. 1–15.
15. Gubichev A., Neumann T. Exploiting the query structure for efficient join ordering in SPARQL queries // Proceedings of the 17th international conference on Extending Database Technology. 2014. pp. 439–450.
16. Bartak R. Constraint Programming: In Pursuit of the Holy Grail // Proceedings of the Week of Doctoral Students (WDS99). 1999. Part IV. pp. 555–564.
17. Ruttkay Zs. Constraint satisfaction a survey // CWI Quarterly. 1998. vol. 11. pp. 163‒214.
18. Russel S., Norvig P. Artificial Intelligence: A Modern Approach. 3rd edition // Prentice Hall. 2010. 1132 p.
19. Щербина О.А. Удовлетворение ограничений и программирование в ограничениях // Интеллектуальные системы. 2011. Т. 15. №. 1‒4. С. 54‒73.
20. Kulik B.A., Zuenko A.A., Friedman A.Ya. Deductive and Defeasible Reasoning on the Basis of a Unified Algebraic Approach // Scientific and Technical Information Processing. 2015. vol. 42. no. 6. pp. 8–16.
21. Zakrevskij A. Integrated Model of Inductive-Deductive Inference Based on Finite Predicates and Implicative Regularities // Diagnostic Test Approaches to Machine Learning and Commonsense Reasoning Systems. IGI Global. 2013. pp. 1–12.
22. Зуенко А.А. Качественное моделирование технических систем на основе методов распространения ограничений // Открытые семантические технологии проектирования интеллектуальных систем: мат. VI Междунар. научн.-техн. конф. Минск. БГУИР. 2016. С.573–578.
23. Neumann T., Moerkotte G. Characteristic sets: Accurate cardinality estimation for RDF queries with multiple joins // ICDE. 2011. pp. 984–994.
24. Smirnov A.V., Levashova T.V., Shilov N.G., Krizhanovsky A.A. Knowledge Fusion in Context-Aware Decision Support: Ontology-Based Modeling and Patterns // Studies in Fuzziness and Soft Computing. 2014. vol. 314. pp. 35–51.
25. Smirnov A., Levashova T., Shilov N. Knowledge Fusion in Context-Aware Decision Support Systems // KEOD 2014 — Proceedings of the International Conference on Knowledge Engineering and Ontology Development. 2014. pp. 186–194.
2. Олейник А.Г., Ломов П.А. О формировании единого пространства мультипредметных знаний Кольского научного центра РАН // Труды пятой международной конференции «Системный анализ и информационные технологии» САИТ-2013). 2013. Т.1. С. 258–265.
3. Nikolić N. et al. RDF Stores Performance Test on Servers with Average Specification // Proceedings of the 5th International Conference on Information Science and Technology (ICIST). 2015. pp. 67–72.
4. Neumann T., Weikum G. RDF3X: a RISCstyle engine for RDF // Proceedings of the 34th International Conference on Very Large Data Bases (VLDB). Auckland. New Zealand. 2008. pp. 647–659.
5. Зуенко А.А. Вывод на ограничениях с применением матричного представления конечных предикатов // Искусственный интеллект и принятие решений. 2014. № 3. C. 21–31.
6. Smith B. et al. IAO-Intel: An Ontology of Information Artifacts in the Intelligence Domain // Proceedings of the Eighth International Conference on Semantic Technologies for Intelligence, Defense and Security (STIDS), (CEUR 2013). 2013. vol. 1097. pp. 33–40.
7. Basic Formal Ontology. URL: http://ifomis.uni-saarland.de/bfo/ (дата обращения: 10.11.2016).
8. Lomov P., Shishaev M. Ad-hoc Synthesis of Composite Content Ontology Design Patterns // Proceedings of the 26th International Conference on Information Modelling and Knowledge Bases (EJC 2016). Tampere University of Technology. Pori. 2016. pp. 25–33.
9. Blomqvist E, Hammar K, Presutti V. Engineering Ontologies with Patterns: The eXtreme Design Methodology // Ontology Engineering with Ontology Design Patterns. IOS Press. 2016. vol. 25. pp. 23–50.
10. Blomqvist E., Presutti V., Daga E., Gangemi A. Experimenting with eXtreme Design // Proceedings of EKAW 2010. Springer. Berlin-Heidelberg-New York. 2010. LNCS 6317. pp. 120–134.
11. Ontology of Integrated Knowledge Space. URL: https://github.com/palandlom/ontology-of-integrated-knowledge-space. (дата обращения: 11.11.2016).
12. Schmidt M., Meier M., Lausen G. Foundations of SPARQL query optimization // Proceedings of the 13th International Conference on Database Theory. 2010. .pp. 4–33.
13. Tsialiamanis P. et al. Heuristics-based query optimisation for SPARQL // Proceedings of the 15th International Conference on Extending Database Technology (EDBT '12). ACM. 2012. pp. 324–335.
14. Aranda C., Arenas M., Corcho M. Semantics and Optimization of the SPARQL 1.1 Federation Extension The Semanic Web: Research and Applications // 8th Extended Semantic Web Conference. Springer Berlin Heidelberg. 2011. pp. 1–15.
15. Gubichev A., Neumann T. Exploiting the query structure for efficient join ordering in SPARQL queries // Proceedings of the 17th international conference on Extending Database Technology. 2014. pp. 439–450.
16. Bartak R. Constraint Programming: In Pursuit of the Holy Grail // Proceedings of the Week of Doctoral Students (WDS99). 1999. Part IV. pp. 555–564.
17. Ruttkay Zs. Constraint satisfaction a survey // CWI Quarterly. 1998. vol. 11. pp. 163‒214.
18. Russel S., Norvig P. Artificial Intelligence: A Modern Approach. 3rd edition // Prentice Hall. 2010. 1132 p.
19. Щербина О.А. Удовлетворение ограничений и программирование в ограничениях // Интеллектуальные системы. 2011. Т. 15. №. 1‒4. С. 54‒73.
20. Kulik B.A., Zuenko A.A., Friedman A.Ya. Deductive and Defeasible Reasoning on the Basis of a Unified Algebraic Approach // Scientific and Technical Information Processing. 2015. vol. 42. no. 6. pp. 8–16.
21. Zakrevskij A. Integrated Model of Inductive-Deductive Inference Based on Finite Predicates and Implicative Regularities // Diagnostic Test Approaches to Machine Learning and Commonsense Reasoning Systems. IGI Global. 2013. pp. 1–12.
22. Зуенко А.А. Качественное моделирование технических систем на основе методов распространения ограничений // Открытые семантические технологии проектирования интеллектуальных систем: мат. VI Междунар. научн.-техн. конф. Минск. БГУИР. 2016. С.573–578.
23. Neumann T., Moerkotte G. Characteristic sets: Accurate cardinality estimation for RDF queries with multiple joins // ICDE. 2011. pp. 984–994.
24. Smirnov A.V., Levashova T.V., Shilov N.G., Krizhanovsky A.A. Knowledge Fusion in Context-Aware Decision Support: Ontology-Based Modeling and Patterns // Studies in Fuzziness and Soft Computing. 2014. vol. 314. pp. 35–51.
25. Smirnov A., Levashova T., Shilov N. Knowledge Fusion in Context-Aware Decision Support Systems // KEOD 2014 — Proceedings of the International Conference on Knowledge Engineering and Ontology Development. 2014. pp. 186–194.
Опубликован
2017-02-02
Как цитировать
Зуенко, А. А., Ломов, П. А., & Олейник, А. Г. (2017). Применение методов распространения ограничений для ускорения обработки запросов к онтологиям. Труды СПИИРАН, 1(50), 112-136. https://doi.org/10.15622/sp.50.5
Раздел
Методы управления и обработки информации
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями:
Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале.
Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале.
Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).
