Top

Published in:

2019 | OriginalPaper | Chapter

Finding New Diamonds: Temporal Minimal-World Query Answering over Sparse ABoxes

Authors : Stefan Borgwardt, Walter Forkel, Alisa Kovtunova

Published in: Rules and Reasoning

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Lightweight temporal ontology languages have become a very active field of research in recent years. Many real-world applications, like processing electronic health records (EHRs), inherently contain a temporal dimension, and require efficient reasoning algorithms. Moreover, since medical data is not recorded on a regular basis, reasoners must deal with sparse data with potentially large temporal gaps. In this paper, we introduce a temporal extension of the tractable language

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-31095-0_1/MediaObjects/483638_1_En_1_Figa_HTML.gif

, which features a new class of convex diamond operators that can be used to bridge temporal gaps. We develop a completion algorithm for our logic, which shows that entailment remains tractable. Based on this, we develop a minimal-world semantics for answering metric temporal conjunctive queries with negation. We show that query answering is combined first-order rewritable, and hence in polynomial time in data complexity.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

next chapter Reasoning on with Defeasibility in ASP

https://clinicaltrials.gov/ct2/show/NCT02280564.

https://clinicaltrials.gov/ct2/show/NCT02873052.

https://clinicaltrials.gov/ct2/show/NCT02157311.

https://clinicaltrials.gov/ct2/show/NCT00969735.

https://www.snomed.org/.

https://clinicaltrials.gov/ct2/show/NCT01198002.

Strictly speaking, \(\psi _\mathcal {T}\) in [12] is a set of first-order formulas, which is however equivalent to the disjunction of all these formulas.

Alur, R., Henzinger, T.A.: A really temporal logic. J. ACM 41(1), 181–204 (1994)MathSciNetCrossRef

Artale, A., Kontchakov, R., Kovtunova, A., Ryzhikov, V., Wolter, F., Zakharyaschev, M.: First-order rewritability of ontology-mediated temporal queries. In: Proceedings IJCAI, pp. 2706–2712. AAAI Press (2015)

Artale, A., Kontchakov, R., Kovtunova, A., Ryzhikov, V., Wolter, F., Zakharyaschev, M.: Ontology-mediated query answering over temporal data: a survey (invited talk). In: Proceedings TIME, pp. 1:1–1:37. Schloss Dagstuhl (2017)

Artale, A., Kontchakov, R., Lutz, C., Wolter, F., Zakharyaschev, M.: Temporalising tractable description logics. In: Proceedings TIME, pp. 11–22. IEEE Press (2007)

Artale, A., Kontchakov, R., Wolter, F., Zakharyaschev, M.: Temporal description logic for ontology-based data access. In: Proceedings IJCAI, pp. 711–717. AAAI Press (2013)

Baader, F., Borgwardt, S., Forkel, W.: Patient selection for clinical trials using temporalized ontology-mediated query answering. In: Proceedings HQA, pp. 1069–1074. ACM (2018)

Baader, F., Borgwardt, S., Koopmann, P., Ozaki, A., Thost, V.: Metric temporal description logics with interval-rigid names. In: Dixon, C., Finger, M. (eds.) FroCoS 2017. LNCS (LNAI), vol. 10483, pp. 60–76. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-66167-4_4CrossRef

Baader, F., Borgwardt, S., Lippmann, M.: Temporal query entailment in the description logic \(\cal{SHQ}\). J. Web Sem. 33, 71–93 (2015)CrossRef

Baader, F., Brandt, S., Lutz, C.: Pushing the \(\cal{EL}\) envelope. In: Proceedings IJCAI, pp. 364–369. Professional Book Center (2005)

10.

Basin, D., Klaedtke, F., Müller, S., Zălinescu, E.: Monitoring metric first-order temporal properties. J. ACM 62(2), 1–45 (2015)MathSciNetCrossRef

11.

Bonomi, L., Jiang, X.: Patient ranking with temporally annotated data. J. Biomed. Inf. 78, 43–53 (2018)CrossRef

12.

Borgwardt, S., Forkel, W.: Closed-world semantics for conjunctive queries with negation over \(\cal{ELH}_\bot \) ontologies. In: Calimeri, F., Leone, N., Manna, M. (eds.) JELIA 2019. LNCS (LNAI), vol. 11468, pp. 371–386. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-19570-0_24CrossRef

13.

Borgwardt, S., Lippmann, M., Thost, V.: Temporalizing rewritable query languages over knowledge bases. J. Web Sem. 33, 50–70 (2015)CrossRef

14.

Brandt, S., Kalaycı, E.G., Ryzhikov, V., Xiao, G., Zakharyaschev, M.: Querying log data with metric temporal logic. J. Artif. Intell. Res. 62, 829–877 (2018)MathSciNetCrossRef

15.

Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Rosati, R.: Data complexity of query answering in description logics. Art. Intell. 195, 335–360 (2013)MathSciNetCrossRef

16.

Crowe, C.L., Tao, C.: Designing ontology-based patterns for the representation of the time-relevant eligibility criteria of clinical protocols. AMIA Jt. Summits Transl. Sci. Proc. 2015, 173–177 (2015)

17.

Deutsch, A., Nash, A., Remmel, J.B.: The chase revisited. In: Proceedings of the Twenty-Seventh ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2008, 9–11 June 2008, Vancouver, BC, Canada, pp. 149–158 (2008)

18.

Furia, C.A., Spoletini, P.: Tomorrow and all our yesterdays: MTL satisfiability over the integers. In: Fitzgerald, J.S., Haxthausen, A.E., Yenigun, H. (eds.) ICTAC 2008. LNCS, vol. 5160, pp. 126–140. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85762-4_9CrossRef

19.

Gutiérrez-Basulto, V., Ibáñez-García, Y., Kontchakov, R., Kostylev, E.V.: Queries with negation and inequalities over lightweight ontologies. J. Web Sem. 35, 184–202 (2015)CrossRef

20.

Gutiérrez-Basulto, V., Jung, J.C., Kontchakov, R.: Temporalized \(\cal{EL}\) ontologies for accessing temporal data: complexity of atomic queries. In: Proceedings IJCAI, pp. 1102–1108. AAAI Press (2016)

21.

Gutiérrez-Basulto, V., Jung, J.C., Ozaki, A.: On metric temporal description logics. In: Proceedings ECAI, pp. 837–845. IOS Press (2016)

22.

Hripcsak, G., Zhou, L., Parsons, S., Das, A.K., Johnson, S.B.: Modeling electronic discharge summaries as a simple temporal constraint satisfaction problem. J. Am. Med. Inform. Assn. 12(1), 55–63 (2005)CrossRef

23.

Jones, N.D., Laaser, W.T.: Complete problems for deterministic polynomial time. Theore. Comput. Sci. 3(1), 105–117 (1976)MathSciNetCrossRef

24.

Krisnadhi, A., Lutz, C.: Data complexity in the \(\cal{EL}\) family of description logics. In: Dershowitz, N., Voronkov, A. (eds.) LPAR 2007. LNCS (LNAI), vol. 4790, pp. 333–347. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-75560-9_25CrossRef

25.

Krötzsch, M., Rudolph, S.: Conjunctive queries for \(\cal{EL}\) with role composition. In: Proceedings DL, pp. 355–362 (2007)

26.

Lindell, S.: A purely logical characterization of circuit uniformity. In: Proceedings of the 7th Annual Structure in Complexity Theory Conference, pp. 185–192 (1992)

27.

Lutz, C., Toman, D., Wolter, F.: Conjunctive query answering in the description logic \(\cal{EL}\) using a relational database system. In: Proceedings IJCAI, pp. 2070–2075. AAAI Press (2009)

28.

Lutz, C., Wolter, F., Zakharyaschev, M.: Temporal description logics: a survey. In: Proceedings of the 15th International Symposium on Temporal Representation and Reasoning (TIME 2008), pp. 3–14. IEEE Press (2008)

29.

Rosati, R.: On conjunctive query answering in \(\cal{EL}\). In: Proceedings DL, pp. 451–458 (2007)

30.

Thost, V.: Metric temporal extensions of DL-Lite and interval-rigid names. In: Proceedings KR, pp. 665–666. AAAI Press (2018)

31.

Vardi, M.Y.: The complexity of relational query languages (extended abstract). In: Proceedings STOC, pp. 137–146. ACM (1982)

32.

Wolter, F., Zakharyaschev, M.: Temporalizing description logics. In: Frontiers of Combining Systems 2, pp. 379–402. Research Studies Press/Wiley (2000)

Title: Finding New Diamonds: Temporal Minimal-World Query Answering over Sparse ABoxes
Authors: Stefan Borgwardt
Walter Forkel
Alisa Kovtunova
Publisher: Springer International Publishing
Book: Rules and Reasoning
Print ISBN: 978-3-030-31094-3

Electronic ISBN: 978-3-030-31095-0

Copyright Year: 2019
DOI: https://doi.org/10.1007/978-3-030-31095-0_1

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner