Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-18T08:14:17.982Z Has data issue: false hasContentIssue false
  • English
  • Français

Temporal Minimal-World Query Answering over Sparse ABoxes

Published online by Cambridge University Press:  11 August 2021

STEFAN BORGWARDT ,
WALTER FORKEL Open the ORCID record for WALTER FORKEL [Opens in a new window]  and
ALISA KOVTUNOVA Open the ORCID record for ALISA KOVTUNOVA [Opens in a new window]
STEFAN BORGWARDT
Affiliation:
Chair for Automata Theory, Technische Universität Dresden, Germany (e-mails: [email protected], [email protected], [email protected])
WALTER FORKEL
Affiliation:
Chair for Automata Theory, Technische Universität Dresden, Germany (e-mails: [email protected], [email protected], [email protected])
ALISA KOVTUNOVA
Affiliation:
Chair for Automata Theory, Technische Universität Dresden, Germany (e-mails: [email protected], [email protected], [email protected])
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Ontology-mediated query answering is a popular paradigm for enriching answers to user queries with background knowledge. For querying the absence of information, however, there exist only few ontology-based approaches. Moreover, these proposals conflate the closed-domain and closed-world assumption and, therefore, are not suited to deal with the anonymous objects that are common in ontological reasoning. Many real-world applications, like processing electronic health records, also contain a temporal dimension and require efficient reasoning algorithms. Moreover, since medical data are not recorded on a regular basis, reasoners must deal with sparse data with potentially large temporal gaps. Our contribution consists of two main parts: In the first part, we introduce a new closed-world semantics for answering conjunctive queries (CQs) with negation over ontologies formulated in the description logic $${\mathcal E}{\mathcal L}{{\mathcal H}_ \bot }$$ , which is based on the minimal canonical model. We propose a rewriting strategy for dealing with negated query atoms, which shows that query answering is possible in polynomial time in data complexity. In the second part, we extend this minimal-world semantics for answering metric temporal CQs with negation over the lightweight temporal logic and obtain similar rewritability and complexity results.

Keywords

knowledge representation and nonmonotonic reasoning
Type
Original Article
Information
Theory and Practice of Logic Programming , Volume 22 , Issue 2: Special Issue on the International Joint Conference on Rules and Reasoning, RuleML+RR 2019 , March 2022 , pp. 193 - 228
Check for updates
Creative Commons
Creative Common License - CCCreative Common License - BY
This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.
Copyright
© The Author(s), 2021. Published by Cambridge University Press

References

Ahmetaj, S., Ortiz, M. and Simkus, M. 2016. Polynomial datalog rewritings for expressive description logics with closed predicates. In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI’16), S. Kambhampati, Ed. AAAI Press, 878–885.Google Scholar
Alur, R., Feder, T. and Henzinger, T. A. 1996. The benefits of relaxing punctuality. Journal of the ACM 43, 1, 116–146.CrossRefGoogle Scholar
Alur, R. and Henzinger, T. A. 1994. A really temporal logic. Journal of the ACM 41, 1, 181–204.CrossRefGoogle Scholar
Arenas, M., Gottlob, G. and Pieris, A. 2014. Expressive languages for querying the semantic web. In Proceedings of the 33rd Symposium on Principles of Database Systems (PODS 2014), Hull, R. and Grohe, M., Eds. ACM, 14–26.Google Scholar
Aronson, A. R. 2001. Effective mapping of biomedical text to the UMLS Metathesaurus: The MetaMap program. In Proceedings of the AMIA Symposium. American Medical Informatics Association, 17–21.Google Scholar
Artale, A. and Franconi, E. 2005. Temporal description logics. In Handbook of Temporal Reasoning in Artificial Intelligence. Foundations of Artificial Intelligence, vol. 1. Elsevier, 375–388.Google Scholar
Artale, A., Kontchakov, R., Kovtunova, A., Ryzhikov, V., Wolter, F. and Zakharyaschev, M. 2015. First-order rewritability of ontology-mediated temporal queries. In Proceedings of IJCAI. AAAI Press, 2706–2712.Google Scholar
Artale, A., Kontchakov, R., Kovtunova, A., Ryzhikov, V., Wolter, F. and Zakharyaschev, M. 2017. Ontology-mediated query answering over temporal data: A survey (invited talk). In Proceedings of the 24th International Symposium on Temporal Representation and Reasoning (TIME 2017). Leibniz International Proceedings in Informatics, vol. 90. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 1:1–1:37.Google Scholar
Artale, A., Kontchakov, R., Lutz, C., Wolter, F. and Zakharyaschev, M. 2007. Temporalising tractable description logics. In Proceedings of TIME. IEEE Press, 11–22.Google Scholar
Artale, A., Kontchakov, R., Ryzhikov, V. and Zakharyaschev, M. 2014. A cookbook for temporal conceptual data modelling with description logics. ACM Transactions on Computational Logic 15, 3, 25:1–25:50.Google Scholar
Artale, A., Kontchakov, R., Wolter, F. and Zakharyaschev, M. 2013. Temporal description logic for ontology-based data access. In Proceedings of IJCAI. AAAI Press, 711–717.Google Scholar
Baader, F., Borgwardt, S., Koopmann, P., Ozaki, A. and Thost, V. 2017. Metric temporal description logics with interval-rigid names. In Proceedings of the 11th International Symposium on Frontiers of Combining Systems (FroCoS 2017). Springer, 60–76.Google Scholar
Baader, F., Borgwardt, S. and Lippmann, M. 2013. Temporalizing ontology-based data access. In Proceedings of the 24th International Conference on Automated Deduction (CADE 2013). Springer, 330–344.Google Scholar
Baader, F., Borgwardt, S. and Lippmann, M. 2015a. Temporal conjunctive queries in expressive description logics with transitive roles. In Proceedings of the 28th Australasian Joint Conference on Advances in Artificial Intelligence, AI 2015. LNCS, vol. 9457. Springer, 21–33.Google Scholar
Baader, F., Borgwardt, S. and Lippmann, M. 2015b. Temporal query entailment in the description logic $${\mathcal S}{\mathcal H}{\mathcal Q}$$ . Journal of Web Semantics 33, 71–93.Google Scholar
Baader, F., Brandt, S. and Lutz, C. 2005. Pushing the $${\mathcal E}{\mathcal L}$$ envelope. In Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI 2005). Professional Book Center, 364–369.Google Scholar
Baader, F., Calvanese, D., McGuinness, D. L., Nardi, D. and Patel-Schneider, P. F., Eds. 2007. The Description Logic Handbook: Theory, Implementation, and Applications, 2nd ed. Cambridge University Press.CrossRefGoogle Scholar
Baader, F., Ghilardi, S. and Lutz, C. 2012. LTL over description logic axioms. ACM Transactions on Computational Logic 13, 3, 21:1–21:32.Google Scholar
Baader, F., Horrocks, I., Lutz, C. and Sattler, U. 2017. An Introduction to Description Logic. Cambridge University Press.Google Scholar
Baader, F., Küsters, R. and Wolter, F. 2003. Extensions to description logics. In The Description Logic Handbook. Cambridge University Press, 219–261.Google Scholar
Bárány, V., ten Cate, B. and Otto, M. 2012. Queries with guarded negation. Proceedings of the VLDB Endowment 5, 11, 1328–1339.Google Scholar
Basin, D., Klaedtke, F., Müller, S. and Zălinescu, E. 2015. Monitoring metric first-order temporal properties. Journal of the ACM 62, 2, 15:1–15:45.Google Scholar
Bauslaugh, B. 1995. Core-like properties of infinite graphs and structures. Discrete Mathematics 138, 1–3, 101–111.Google Scholar
Besana, P., Cuggia, M., Zekri, O., Bourde, A. and Burgun, A. 2010. Using semantic web technologies for clinical trial recruitment. In Proceedings of the 9th International Semantic Web Conference (ISWC 2010), P. F. Patel-Schneider, Y. Pan, P. Hitzler, P. Mika, L. Zhang, J. Z. Pan, I. Horrocks, and B. Glimm, Eds. Lecture Notes in Computer Science, vol. 6497. Springer, 34–49.Google Scholar
Bienvenu, M. and Ortiz, M. 2015. Ontology-mediated query answering with data-tractable description logics. In Reasoning Web 11th International Summer School, W. Faber and A. Paschke, Eds. Lecture Notes in Computer Science, vol. 9203. Springer, 218–307.Google Scholar
Bonomi, L. and Jiang, X. 2018. Patient ranking with temporally annotated data. Journal of Biomedical Informatics 78, 43–53.CrossRefGoogle ScholarPubMed
Borgwardt, S. and Forkel, W. 2019. Closed-world semantics for conjunctive queries with negation over $${\mathcal E}{\mathcal L}{{\mathcal H}_ \bot }$$ ontologies. In Proceedings of the 16th European Conference on Logics in Artificial Intelligence (JELIA 2019). Springer, Rende, Italy, 371–386. To appear.CrossRefGoogle Scholar
Borgwardt, S., Forkel, W. and Kovtunova, A. 2019. Finding new diamonds: Temporal minimal- world query answering over sparse aboxes. In Proceedings of the 3rd International Joint Conference on Rules and Reasoning (RuleML+RR 2019), P. Foder, M. Montali, D. Calvanese, and D. Roman, Eds. Springer, Bolzano, Italy. To appear.Google Scholar
Borgwardt, S., Lippmann, M. and Thost, V. 2013. Temporal query answering in the description logic DL-Lite. In Proceedings of the 9th International Symposium on Frontiers of Combining Systems, FroCoS 2013. LNCS, vol. 8152. Springer, 165–180.Google Scholar
Borgwardt, S., Lippmann, M. and Thost, V. 2015. Temporalizing rewritable query languages over knowledge bases. Web Semantics: Science, Services and Agents on the World Wide Web 33, 50–70.Google Scholar
Borgwardt, S. and Thost, V. 2015a. Temporal query answering in DL-Lite with negation. In Proceedings of the 1st Global Conference on Artificial Intelligence (GCAI 2015). EasyChair, 51–65.Google Scholar
Borgwardt, S. and Thost, V. 2015b. Temporal query answering in the description logic $${\mathcal E}{\mathcal L}$$ . In Proceedings of the 24h International Joint Conference on Artificial Intelligence, IJCAI 2015. AAAI Press, 2819–2825.Google Scholar
Borgwardt, S. and Thost, V. 2020. Temporal conjunctive query answering in the extended DL-Lite family. In arXiv:2003.09508.Google Scholar
Brandt, S., Kalayc, E. G., Ryzhikov, V., Xiao, G., and Zakharyaschev, M. 2018. Querying log data with metric temporal logic. Journal of Artificial Intelligence Research 62, 829–877.Google Scholar
Calvanese, D., Cogrel, B., Komla-Ebri, S., Kontchakov, R., Lanti, D., Rezk, M., Rodriguez-Muro, M. and Xiao, G. 2017. Ontop: Answering SPARQL queries over relational databases. Semantic Web 8, 471–487.Google Scholar
Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M. and Rosati, R. 2006. Epistemic first-order queries over description logic knowledge bases. In Proceedings of the 19th International Workshop on Description Logics (DL 2006), B. Parsia, U. Sattler, and D. Toman, Eds. CEUR Workshop Proceedings, vol. 189. 51–61.Google Scholar
Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M. and Rosati, R. 2013. Data complexity of query answering in description logics. Artificial Intelligence 195, 335–360.Google Scholar
Cresswell, K. M. and Sheikh, A. 2017. Inpatient clinical information systems. In Key Advances in Clinical Informatics, A. Sheikh, K. M. Cresswell, A. Wright, and D. W. Bates, Eds. Academic Press, Chapter 2, 13–29.Google Scholar
Crowe, C. L. and Tao, C. 2015. Designing ontology-based patterns for the representation of the time-relevant eligibility criteria of clinical protocols. AMIA Joint Summits on Translational Science Proceedings 2015, 173–177.Google Scholar
Deutsch, A., Nash, A. and Remmel, J. B. 2008. The chase revisited. In Proceedings of the 27th ACM Symposium on Principles of Database Systems (PODS 2008). ACM, 149–158.Google Scholar
Eiter, T., Ortiz, M., Šimkus, M., Tran, T.-K. and Xiao, G. 2012. Query rewriting for Horn- $${\mathcal S}{\mathcal H}{\mathcal I}{\mathcal Q}$$ plus rules. In Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI 2012), J. Hoffmann and B. Selman, Eds. AAAI Press, 726–733.Google Scholar
Fagin, R., Kolaitis, P. G., Miller, R. J. and Popa, L. 2005. Data exchange: Semantics and query answering. Theoretical Computer Science 336, 1, 89–124.Google Scholar
Forkel, W. 2020. Closed-world semantics for query answering in temporal description logics. Ph.D. thesis, Technische Universität Dresden, Germany.Google Scholar
Furia, C. A. and Spoletini, P. 2008. Tomorrow and all our yesterdays: MTL satisfiability over the integers. In Proceedings ICTAC. Springer, 126–140.Google Scholar
Gutiérrez-Basulto, V., Ibáñez-Garca, Y., Kontchakov, R. and Kostylev, E. V. 2015. Queries with negation and inequalities over lightweight ontologies. Journal of Web Semantics 35, 184–202.Google Scholar
Gutiérrez-Basulto, V., Jung, J. C. and Kontchakov, R. 2016. Temporalized $${\mathcal E}{\mathcal L}$$ ontologies for accessing temporal data: Complexity of atomic queries. In Proc. IJCAI. AAAI Press, 1102–1108.Google Scholar
Gutiérrez-Basulto, V., Jung, J. C. and Ozaki, A. 2016. On metric temporal description logics. In Proceedings ECAI. IOS Press, 837–845.Google Scholar
Hernich, A., Kupke, C., Lukasiewicz, T. and Gottlob, G. 2013. Well-founded semantics for extended datalog and ontological reasoning. In Proceedings of the 32nd Symposium on Principles of Database Systems (PODS 2013), R. Hull and W. Fan, Eds. ACM, 225–236.Google Scholar
Johnson, A. E. W., Pollard, T. J., Shen, L., Lehman, L.-w. H., Feng, M., Ghassemi, M., Moody, B., Szolovits, P., Celi, L. A. and Mark, R. G. 2016. MIMIC-III, a freely accessible critical care database. Scientific Data 3, 160035, 1–9.Google Scholar
Kharlamov, E., Hovland, D., Skjæveland, M. G., Bilidas, D., Jiménez-Ruiz, E., Xiao, G., Soylu, A., Lanti, D., Rezk, M., Zheleznyakov, D., Giese, M., Lie, H., Ioannidis, Y., Kotidis, Y., Koubarakis, M. and Waaler, A. 2017. Ontology based data access in Statoil. Journal of Web Semantics 44, 3–36.Google Scholar
Kontchakov, R., Lutz, C., Toman, D., Wolter, F. and Zakharyaschev, M. 2011. The combined approach to ontology-based data access. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011), T. Walsh, Ed. AAAI Press, 2656–2661.Google Scholar
Kontchakov, R., Pandolfo, L., Pulina, L., Ryzhikov, V. and Zakharyaschev, M. 2016. Temporal and spatial OBDA with many-dimensional Halpern-Shoham logic. In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI 2016). AAAI Press, 1160–1166.Google Scholar
Köpcke, F. and Prokosch, H.-U. 2014. Employing computers for the recruitment into clinical trials: A comprehensive systematic review. Journal of Medical Internet Research 16, 7, e161.CrossRefGoogle Scholar
Krötzsch, M. 2020. Computing cores for existential rules with the standard chase and ASP. In Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning (KR 2020). IJCAI.CrossRefGoogle Scholar
Lindell, S. 1992. A purely logical characterization of circuit uniformity. In Proceedings of the 7th Annual Structure in Complexity Theory Conference, 185–192.Google Scholar
Lutz, C., Seylan, I. and Wolter, F. 2013. Ontology-based data access with closed predicates is inherently intractable (sometimes). In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI 2013), F. Rossi, Ed. AAAI Press, 1024–1030.Google Scholar
Lutz, C., Toman, D. and Wolter, F. 2009. Conjunctive query answering in the description logic $${\mathcal E}{\mathcal L}$$ using a relational database system. In Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI 2009). AAAI Press, 2070–2075.Google Scholar
Lutz, C., Wolter, F. and Zakharyaschev, M. 2008. Temporal description logics: A survey. In Proceedings of the 15th International Symposium on Temporal Representation and Reasoning (TIME 2008). IEEE Press, 3–14.Google Scholar
Marnette, B. 2009. Generalized schema mappings: From termination to tractability. In Proceedings of the 28th Symposium on Principles of Database Systems (PODS 2009), J. Paredaens and J. Su, Eds. ACM, 13–22.Google Scholar
Mugnier, M.-L. and Thomazo, M. 2014. An introduction to ontology-based query answering with existential rules. In Reasoning Web International Summer School, 245–278.Google Scholar
Ni, Y., Wright, J., Perentesis, J., Lingren, T., Deleger, L., Kaiser, M., Kohane, I. and Solti, I. 2015. Increasing the efficiency of trial-patient matching: Automated clinical trial eligibility pre-screening for pediatric oncology patients. BMC Medical Informatics and Decision Making 15, 1–10.Google Scholar
Patel, C., Cimino, J., Dolby, J., Fokoue, A., Kalyanpur, A., Kershenbaum, A., Ma, L., Schonberg, E., and Srinivas, K. 2007. Matching patient records to clinical trials using ontologies. In Proceedings of the 6th International Semantic Web Conference (ISWC 2007), K. Aberer, K.-S. Choi, N. Noy, D. Allemang, K.-I. Lee, L. Nixon, J. Goldbeck, P. Mika, D. Maynard, R. Mizoguchi, G. Schreiber, and P. Cudré-Mauroux, Eds. Lecture Notes in Computer Science, vol. 4825. Springer, 816–829.Google Scholar
Rosati, R. 2007a. The limits of querying ontologies. In Proceedings of the 11th International Conference on Database Theory (ICDT 2007), T. Schwentick and D. Suciu, Eds. 164–178.Google Scholar
Rosati, R. 2007b. On conjunctive query answering in $${\mathcal E}{\mathcal L}$$ . In Proceedings of DL. 451–458.Google Scholar
Ryzhikov, V., Walega, P. A. and Zakharyaschev, M. 2019. Data complexity and rewritability of ontology-mediated queries in metric temporal logic under the event-based semantics. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, S. Kraus, Ed. ijcai.org, 1851–1857.Google Scholar
Savova, G. K., Masanz, J. J., Ogren, P. V., Zheng, J., Sohn, S., Kipper-Schuler, K. C. and Chute, C. G. 2010. Mayo clinical text analysis and knowledge extraction system (cTAKES): Architecture, component evaluation and applications. Journal of the American Medical Informatics Association 17, 5, 507–513.CrossRefGoogle Scholar
Tagaris, A., Andronikou, V., Chondrogiannis, E., Tsatsaronis, G., Schroeder, M., Varvarigou, T. and Koutsouris, D.-D. 2014. Exploiting Ontology Based Search and EHR Interoperability to Facilitate Clinical Trial Design. Springer, 21–42.Google Scholar
Thost, V. 2018. Metric temporal extensions of DL-Lite and interval-rigid names. In Proceedings of KR. AAAI Press, 665–666.Google Scholar
Vardi, M. Y. 1982. The complexity of relational query languages (extended abstract). In Proceedings of STOC. ACM, 137–146.Google Scholar
Wolter, F. 2000. First order common knowledge logics. Studia Logica 65, 2, 249–271.CrossRefGoogle Scholar
Wolter, F. and Zakharyaschev, M. 2000. Temporalizing description logics. In Frontiers of Combining Systems 2. Research Studies Press/Wiley, 379–402.Google Scholar
Xu, C., Forkel, W., Borgwardt, S., Baader, F. and Zhou, B. 2019. Automatic translation of clinical trial eligibility criteria into formal queries. In Proceedings of the 9th Workshop on Ontologies and Data in Life Sciencs (ODLS 2019), part of The Joint Ontology Workshops (JOWO 2019), M. Boeker, L. Jansen, F. Loebe, and S. Schulz, Eds. CEUR Workshop Proceedings.Google Scholar