Finding New Diamonds: Temporal Minimal- World Query Answering over Sparse ABoxes (Extended Abstract) ?

Abstract

Temporal description logics (DLs) combine terminological and temporal knowledge representation capabilities and have been investigated in detail in the last decades [2, 16, 17]. To obtain tractable reasoning procedures, lightweight temporal DLs have been developed [3, 13]. The idea is to use temporal operators, often from the linear temporal logic LTL, inside DL axioms. For example, −∃diagnosis.BrokenLeg v ∃treatment.LegCast states that after breaking a leg one has to wear a cast. However, this basic approach cannot represent the distance of events, e.g. that the cast only has to be worn for a fixed amount of time. Recently, metric temporal ontology languages have been investigated [6, 11, 14], which allow to replace − in the above axiom with [−8,0], i.e. wearing the cast is required only if the leg was broken ≤ 8 time points (e.g. weeks) ago. Such knowledge representation capabilities are important for biomedical applications. For example, many clinical trials contain temporal eligibility criteria [12], such as: “type 1 diabetes with duration at least 12 months”1; “known history of heart disease or heart rhythm abnormalities”2; “CD4+ lymphocytes count > 250/mm3, for at least 6 months”3; or “symptomatic recurrent paroxysmal atrial fibrillation (PAF) (> 2 episodes in the last 6 months)”4. Moreover, measurements, diagnoses, and treatments in a patients' EHR are clearly valid only for a certain amount of time. To automatically screen patients according to the temporal criteria above, one needs a sufficiently powerful formalism that can reason about biomedical and temporal knowledge. This is an active area of current research [8, 12, 15]. For the atemporal part, one can use existing large biomedical ontologies that are based on lightweight (atemporal) DLs, e.g. SNOMED CT5, which is formulated using the DL ELH. Since EHRs only contain information for specific points in time, it is especially important to be able to infer what happened to the patient in the meantime. For example, if a patient is diagnosed with a (currently) incurable disease like

-

Diabetes, they will still have the disease at any future point in time. Similarly, if the EHR contains two entries of CD4Above250 four weeks apart, one may reasonably infer that this was true for the whole four weeks. Qualitative temporal DLs such as T ELinfl [ 13 ] over the integer timeline can express the former statement by declaring Diabetes as expanding via the axiom −Diabetes v Diabetes. Our Contribution We propose to extend this logic by adding a special kind of metric temporal operators [ 6, 14 ] to write c 4CD4Above250 v CD4Above250, making the measurement convex for a specified length of time n (e.g. 4 weeks). This means that information is interpolated between time points of distance less than n, thereby computing a (limited) convex closure of the available information. The threshold n, regardless of the encoding, allows us to distinguish the case where two mentions of CD4Above250 are years apart, and are therefore unrelated.

The distinguishing feature of T ELinfl is that -operators are only allowed on the left-hand side (lhs) of concept inclusions [ 13 ], which is also common for temporal DLs based on DL-Lite [ 1, 4 ]. By permitting convex and classical metric temporal operators on left-hand side of concept and role inclusions, we deal with the problem of having large gaps in the data, e.g. in patient records. We show c,lhs remains tractable. that reasoning in the extended logic T ELH⊥

Additionally, we consider the problem of answering temporal queries over c,lhs knowledge bases. As argued in [ 5, 9 ], evaluating clinical trial criteria T ELH⊥ over patient records requires both negated and temporal queries, but standard certain answer semantics is not suitable to deal with negation over patient records, which is why we adopt the minimal-world semantics from [ 9 ] for our purposes. Our query language extends the temporal conjunctive queries from [ 7 ] by metric temporal operators and negation. For example, we can use queries like [−12,0](∃y.diagnosedWith(x, y) ∧ Diabetes(y)) to detect whether the first criterion from above is satisfied.

Using a combined rewriting approach, we show that the data complexity of c,lhs without temporal role inclusions is not higher than query answering for T ELH⊥ for positive atemporal queries in ELH⊥, i.e. P-complete, and also provide a tight combined complexity result of ExpSpace. Unlike most research on temporal query answering [ 1, 7 ], we do not assume that input data is given for all time points in a certain interval, but rather at sporadic time points with arbitrarily large gaps. The main technical difficulty is to determine which additional time points are relevant for answering a query, and how to access these time points without having to fill all the gaps. The full version of the paper, including all proofs, can be found at https://tu-dresden.de/inf/lat/papers. Acknowledgements This work was supported by the DFG grant BA 1122/19-1 (GOASQ) and grant 389792660 (TRR 248) (see https://perspicuous-computing. science).

References

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

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

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

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

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

6. Baader , F. , Borgwardt , S. , Koopmann , P. , Ozaki , A. , Thost , V. : Metric temporal description logics with interval-rigid names . In: Proc. FroCoS . pp. 60 - 76 . Springer ( 2017 )

7. Baader , F. , Borgwardt , S. , Lippmann, M.: Temporal query entailment in the description logic SHQ . J. Web Sem . 33 , 71 - 93 ( 2015 )

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

9. Borgwardt , S. , Forkel , W. : Closed-world semantics for conjunctive queries with negation over ELH⊥ ontologies . In: Proc. JELIA . pp. 371 - 386 . Springer ( 2019 )

10. Borgwardt , S. , Forkel , W. , Kovtunova , A. : Finding new diamonds: Temporal minimal-world query answering over sparse ABoxes . In: Foder, P. , Montali , M. , Calvanese , D. , Roman , D . (eds.) Proc. of the 3rd Int. Joint Conf. on Rules and Reasoning (RuleML+RR'19). Lecture Notes in Computer Science , vol. 11784 , pp. 3 - 18 . Springer-Verlag ( 2019 ). https://doi.org/10.1007/978-3- 030 -31095- 0 _ 1

11. 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 )

12. 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 )

13. Gutiérrez-Basulto , V. , Jung , J.C. , Kontchakov , R.: Temporalized EL ontologies for accessing temporal data: Complexity of atomic queries . In: Proc. IJCAI . pp. 1102 - 1108 . AAAI Press ( 2016 )

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

15. 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 )

16. Lutz , C. , Wolter , F. , Zakharyaschev , M. : Temporal description logics: A survey . In: Proc. of the 15th Int. Symp. on Temporal Representation and Reasoning (TIME'08) . pp. 3 - 14 . IEEE Press ( 2008 )

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