ПРЕПРИНТ
О результатах, изложенных в препринтах, не следует сообщать в СМИ как о проверенной информации.
В области компьютерных наук под названием “представление знаний” (knowledge representation) некоторое время назад одним из стандартов стала следующая парадигма. Под базой знаний (knowledge base) подразумевается архитектура, объединяющая в себе данные, знания общего характера и механизм логического вывода, позволяющий генерировать на основе базовых данных и знаний новую информацию и использовать ее для ответов на запросы к системе. В этом обзоре мы сосредоточимся на сценарии, когда под данными подразумевается набор замкнутых атомов, под знаниями — онтология в той или иной дескрипционной логике, а в качестве языка запросов выбраны конъюнктивные запросы (conjunctive queries). Цель настоящей работы — собрать воедино теоретические и практические результаты о трудоемкости процедур построения ответа в зависимости от семантики, то есть формального определения того, что считать ответом на запрос.
Кикоть С. П. 2024. Конъюнктивные запросы к базам знаний. Какую семантику выбрать ? PREPRINTS.RU. https://doi.org/10.24108/preprints-3113145
1. N. Antonioli, F. Castanò, S. Coletta, S. Grossi, D. Lembo, M. Lenzerini, A. Poggi, E. Virardi,
2. and P. Castracane. Ontology-based data management for the Italian public debt. In
3. P. Garbacz and O. Kutz, editors, Formal Ontology in Information Systems - Proceedings
4. of the Eighth International Conference, FOIS 2014, September, 22-25, 2014, Rio de
5. Janeiro, Brazil, volume 267 of Frontiers in Artificial Intelligence and Applications, pages
6. 372–385. IOS Press, 2014.
7. A. Artale, D. Calvanese, R. Kontchakov, and M. Zakharyaschev. The DL-Lite family and
8. relations. J. Artif. Intell. Res. (JAIR), 36:1–69, 2009.
9. M. Bienvenu, C. Bourgaux, and F. Goasdoué. Querying inconsistent description logic
10. knowledge bases under preferred repair semantics. In Brodley and Stone [9], pages
11. 996–1002.
12. M. Bienvenu, S. Kikot, and V. V. Podolskii. Tree-like queries in OWL 2 QL: succinctness
13. and complexity results. In 30th Annual ACM/IEEE Symposium on Logic in Computer
14. Science, LICS 2015, Kyoto, Japan, July 6-10, 2015, pages 317–328. IEEE, 2015.
15. M. Bienvenu and M. Ortiz. Ontology-mediated query answering with data-tractable
16. description logics. In W. Faber and A. Paschke, editors, Reasoning Web. Web Logic Rules
17. - 11th International Summer School 2015, Berlin, Germany, July 31 - August 4, 2015,
18. Tutorial Lectures, volume 9203 of Lecture Notes in Computer Science, pages 218–307.
19. Springer, 2015.
20. M. Bienvenu, M. Ortiz, M. Simkus, and G. Xiao. Tractable queries for lightweight
21. description logics. In F. Rossi, editor, IJCAI 2013, Proceedings of the 23rd International
22. Joint Conference on Artificial Intelligence, Beijing, China, August 3-9, 2013. IJCAI/AAAI,
23. M. Bienvenu and R. Rosati. New inconsistency-tolerant semantics for robust ontology-
24. based data access. In Eiter et al. [16], pages 53–64.
25. I. Boguslavsky, V. Dikonov, L. Iomdin, A. Lazursky, V. Sizov, and S. Timoshenko.
26. Semantic analysis and question answering : a system under development. In
27. Computational Linguistics and Intellectual Technologies, Papers from the Annual
28. International Conference “Dialogue” (2015), Issue 14, pages 62–79, 2015.
29. C. E. Brodley and P. Stone, editors. Proceedings of the Twenty-Eighth AAAI Conference
30. on Artificial Intelligence, July 27 -31, 2014, Québec City, Québec, Canada. AAAI Press,
31. D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, A. Poggi, M. Rodriguez-Muro,
32. R. Rosati, M. Ruzzi, and D. F. Savo. The MASTRO system for ontology-based data access.
33. Semantic Web, 2(1):43–53, 2011.
34. D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, and R. Rosati. EQL-Lite: Effective
35. first-order query processing in description logics. In M. M. Veloso, editor, IJCAI
36. 2007, Proceedings of the 20th International Joint Conference on Artificial Intelligence,
37. Hyderabad, India, January 6-12, 2007, pages 274–279, 2007.
38. D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, and R. Rosati. Tractable
39. reasoning and efficient query answering in description logics: The DL-Lite family. J.
40. Autom. Reasoning, 39(3):385–429, 2007.
41. D. Calvanese, E. Franconi, V. Haarslev, D. Lembo, B. Motik, A.-Y. Turhan, and S. Tessaris,
42. editors. Proceedings of the 20th International Workshop on Description Logics
43. (DL 2007), Brixen-Bressanone, near Bozen-Bolzano, Italy, 8–10 June, 2007, volume 250
44. of CEUR Workshop Proceedings. CEUR-WS.org, 2007.
45. D. Carral, C. Feier, B. C. Grau, P. Hitzler, and I. Horrocks. EL-ifying ontologies. In S. Demri,
46. D. Kapur, and C. Weidenbach, editors, Automated Reasoning - 7th International Joint
47. Conference, IJCAR 2014, Held as Part of the Vienna Summer of Logic, VSL 2014, Vienna,
48. Austria, July 19-22, 2014. Proceedings, volume 8562 of Lecture Notes in Computer
49. Science, pages 464–479. Springer, 2014.
50. S. Ceri, G. Gottlob, and L. Tanca. What you always wanted to know about datalog (and
51. never dared to ask). Knowledge and Data Engineering, IEEE Transactions on, 1(1):146–
52. 166, 1989.
53. T. Eiter, B. Glimm, Y. Kazakov, and M. Krötzsch, editors. Informal Proceedings of the
54. 26th International Workshop on Description Logics, Ulm, Germany, July 23 - 26, 2013,
55. volume 1014 of CEUR Workshop Proceedings. CEUR-WS.org, 2013.
56. T. Eiter, M. Ortiz, and M. Simkus. Conjunctive query answering in the description logic
57. SH using knots. J. Comput. Syst. Sci., 78(1):47–85, 2012.
58. T. Eiter, M. Ortiz, M. Simkus, T. Tran, and G. Xiao. Query rewriting for Horn-SHIQ plus
59. rules. In J. Hoffmann and B. Selman, editors, Proceedings of the Twenty-Sixth AAAI
60. Conference on Artificial Intelligence, July 22-26, 2012, Toronto, Ontario, Canada. AAAI
61. Press, 2012.
62. B. Glimm, Y. Kazakov, and C. Lutz. Status QIO: an update. In Proceedings of the 24th
63. International Workshop on Description Logics (DL 2011), Barcelona, Spain, July 13-16,
64. 2011, 2011.
65. B. Glimm, C. Lutz, I. Horrocks, and U. Sattler. Conjunctive query answering for the
66. description logic SHIQ. J. Artif. Intell. Res. (JAIR), 31:157–204, 2008.
67. B. Glimm and S. Rudolph. Status QIO: conjunctive query entailment is decidable. In
68. F. Lin, U. Sattler, and M. Truszczynski, editors, Principles of Knowledge Representation
69. and Reasoning: Proceedings of the Twelfth International Conference, KR 2010, Toronto,
70. Ontario, Canada, May 9-13, 2010. AAAI Press, 2010.
71. G. Gottlob, S. Kikot, R. Kontchakov, V. V. Podolskii, T. Schwentick, and M. Zakharyaschev.
72. The price of query rewriting in ontology-based data access. Artif. Intell., 213:42–59,
73. E. Jiménez-Ruiz, E. Kharlamov, D. Zheleznyakov, I. Horrocks, C. Pinkel, M. G. Skjæveland,
74. E. Thorstensen, and J. Mora. Bootox: Practical mapping of RDBs to OWL 2.
75. S. Kikot, R. Kontchakov, V. V. Podolskii, and M. Zakharyaschev. On the succinctness
76. of query rewriting over shallow ontologies. In T. A. Henzinger and D. Miller, editors,
77. Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic
78. (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science
79. (LICS), CSL-LICS ’14, Vienna, Austria, July 14 - 18, 2014, pages 57:1–57:10. ACM, 2014.
80. S. Kikot, R. Kontchakov, and M. Zakharyaschev. On (in)tractability of OBDA with OWL 2
81. QL. In Proceedings of the 24th International Workshop on Description Logics (DL 2011),
82. Barcelona, Spain, July 13-16, 2011, 2011.
83. S. Kikot, R. Kontchakov, and M. Zakharyaschev. Conjunctive query answering with
84. OWL 2 QL. In G. Brewka, T. Eiter, and S. A. McIlraith, editors, Principles of
85. Knowledge Representation and Reasoning: Proceedings of the Thirteenth International
86. Conference, KR 2012, Rome, Italy, June 10-14, 2012. AAAI Press, 2012.
87. S. Kikot, D. Tsarkov, M. Zakharyaschev, and E. Zolin. Query answering via modal
88. definability with fact++: First blood. In Eiter et al. [16], pages 328–340.
89. S. Kikot and E. Zolin. Modal definability of first-order formulas with free variables and
90. query answering. J. Applied Logic, 11(2):190–216, 2013.
91. I. Kollia and B. Glimm. Optimizing SPARQL query answering over OWL ontologies. J.
92. Artif. Intell. Res. (JAIR), 48:253–303, 2013.
93. I. Kollia, B. Glimm, and I. Horrocks. SPARQL query answering over OWL ontologies. In
94. G. Antoniou, M. Grobelnik, E. P. B. Simperl, B. Parsia, D. Plexousakis, P. D. Leenheer,
95. and J. Z. Pan, editors, The Semantic Web: Research and Applications - 8th Extended
96. Semantic Web Conference, ESWC 2011, Heraklion, Crete, Greece, May 29-June 2, 2011,
97. Proceedings, Part I, volume 6643 of Lecture Notes in Computer Science, pages 382–396.
98. Springer, 2011.
99. R. Kontchakov, C. Lutz, D. Toman, F. Wolter, and M. Zakharyaschev. The combined
100. approach to query answering in dl-lite. In KR, 2010.
101. R. Kontchakov and M. Zakharyaschev. An introduction to description logics and query
102. rewriting. In M. Koubarakis, G. B. Stamou, G. Stoilos, I. Horrocks, P. G. Kolaitis,
103. G. Lausen, and G. Weikum, editors, Reasoning Web. Reasoning on the Web in the Big
104. Data Era - 10th International Summer School 2014, Athens, Greece, September 8-13,
105. Proceedings, volume 8714 of Lecture Notes in Computer Science, pages 195–244.
106. Springer, 2014.
107. A. Krisnadhi and C. Lutz. Data complexity in the EL family of DLs. In Calvanese et al. [13].
108. M. Krötzsch, S. Rudolph, and P. Hitzler. Complexities of horn description logics. ACM
109. Transactions on Computational Logic (TOCL), 14(1):2, 2013.
110. D. Lembo, M. Lenzerini, R. Rosati, M. Ruzzi, and D. F. Savo. Inconsistency-
111. tolerant semantics for description logics. In P. Hitzler and T. Lukasiewicz, editors,
112. Web Reasoning and Rule Systems - Fourth International Conference, RR 2010,
113. Bressanone/Brixen, Italy, September 22-24, 2010. Proceedings, volume 6333 of Lecture
114. Notes in Computer Science, pages 103–117. Springer, 2010.
115. C. Lutz, I. Seylan, D. Toman, and F. Wolter. The combined approach to obda: Taming role
116. hierarchies using filters. In The Semantic Web–ISWC 2013, pages 314–330. Springer,
117. B. Motik, Y. Nenov, R. Piro, I. Horrocks, and D. Olteanu. Parallel materialisation of
118. Datalog programs in centralised, main-memory RDF systems. In Brodley and Stone [9],
119. pages 129–137.
120. M. Ortiz and M. Simkus. Reasoning and query answering in description logics. In T. Eiter
121. and T. Krennwallner, editors, Reasoning Web. Semantic Technologies for Advanced
122. Query Answering - 8th International Summer School 2012, Vienna, Austria, September
123. 3-8, 2012. Proceedings, volume 7487 of Lecture Notes in Computer Science, pages 1–
124. Springer, 2012.
125. H. Pérez-Urbina, B. Motik, and I. Horrocks. Tractable query answering and rewriting
126. under description logic constraints. J. Applied Logic, 8(2):186–209, 2010.
127. V. V. Podolskii. Circuit complexity meets ontology-based data access. In L. D.
128. Beklemishev and D. V. Musatov, editors, Computer Science - Theory and Applications
129. - 10th International Computer Science Symposium in Russia, CSR 2015, Listvyanka,
130. Russia, July 13-17, 2015, Proceedings, volume 9139 of Lecture Notes in Computer
131. Science, pages 7–26. Springer, 2015.
132. M. Rodriguez-Muro, R. Kontchakov, and M. Zakharyaschev. Ontology-based data
133. access: Ontop of databases. In H. Alani, L. Kagal, A. Fokoue, P. T. Groth, C. Biemann,
134. J. X. Parreira, L. Aroyo, N. F. Noy, C. Welty, and K. Janowicz, editors, The Semantic Web
135. - ISWC 2013 - 12th International Semantic Web Conference, Sydney, NSW, Australia,
136. October 21-25, 2013, Proceedings, Part I, volume 8218 of Lecture Notes in Computer
137. Science, pages 558–573. Springer, 2013.
138. A. A. Romero, B. C. Grau, and I. Horrocks. More: Modular combination of OWL
139. reasoners for ontology classification. In P. Cudré-Mauroux, J. Heflin, E. Sirin,
140. T. Tudorache, J. Euzenat, M. Hauswirth, J. X. Parreira, J. Hendler, G. Schreiber,
141. A. Bernstein, and E. Blomqvist, editors, The Semantic Web - ISWC 2012 - 11th
142. International Semantic Web Conference, Boston, MA, USA, November 11-15, 2012,
143. Proceedings, Part I, volume 7649 of Lecture Notes in Computer Science, pages 1–16.
144. Springer, 2012.
145. R. Rosati. On conjunctive query answering in EL. In Calvanese et al. [13].
146. D. Trivela, G. Stoilos, A. Chortaras, and G. B. Stamou. Optimising resolution-based
147. rewriting algorithms for OWL ontologies. J. Web Sem., 33:30–49, 2015.
148. T. Venetis, G. Stoilos, and G. B. Stamou. Incremental query rewriting for OWL 2 QL.
149. In Y. Kazakov, D. Lembo, and F. Wolter, editors, Proceedings of the 2012 International
150. Workshop on Description Logics, DL-2012, Rome, Italy, June 7-10, 2012, volume 846 of
151. CEUR Workshop Proceedings. CEUR-WS.org, 2012.
152. Y. Zhou, B. C. Grau, Y. Nenov, and I. Horrocks. Pagoda: Pay-as-you-go abox reasoning. In
153. D. Calvanese and B. Konev, editors, Proceedings of the 28th International Workshop on
154. Description Logics, Athens,Greece, June 7-10, 2015., volume 1350 of CEUR Workshop
155. Proceedings. CEUR-WS.org, 2015.
156. E. Zolin. Query answering based on modal correspondence theory. In Proc. of the 4th
157. “Methods for modalities” Workshop (M4M-4), pages 21–37. m4m.loria.fr, 2005.
