Temporalising Unique Characterisability and Learnability of Ontology-Mediated Queries (Extended Abstract)

Abstract

Recently, the study of the unique characterisability and learnability of database queries by means of examples has been extended to ontology-mediated queries. Here, we study in how far the obtained results can be lifted to temporalised ontology-mediated queries. We provide a systematic introduction to the relevant approaches in the non-temporal case and then show general transfer results pinpointing under which conditions existing results can be lifted to temporalised queries.

Keywords

• eol>Ontology-mediated query
• temporal data
• query-by-example
• unique characterisability
• learnability

-

1. Introduction Motivated by the challenge of constructing logical expressions from data examples, the unique characterisability and learnability of queries, formulas, and concepts has been studied extensively by the database, logic, and KR communities [ 1, 2, 3, 4, 5, 6 ]. Recently, significant progress has been made for ontology-mediated queries, where one aims to characterise or learn a database query under background knowledge, both in the passive sense (where sets of positive and negative examples are given), see, e.g., [ 7 ], and in Dana Angluin’s sense of exact learning with membership and/or equivalence queries [ 8 ], see, e.g., [ 9 ]. Also, rather general results have been obtained about the characterisation and learnability of temporal queries, but so far without ontologies [ 10 ]. Our aim here is to combine these two directions and study the temporalisation of unique characterisability and learnability under description logic (DL) ontologies.

Let be an ontology and a class of conjunctive queries (CQs), which we assume for simplicity to have a single answer variable. We say that a query ∈ fits a pair = (+, − ) of finite sets + and − of pointed data instances (, ) wrt if , |= () for all (, ) ∈ +, and , ̸|= () for all (, ) ∈ − . Then uniquely characterises wrt within if is the only (up to equivalence modulo ) query in that fits wrt . An ontology language ℒ admits (polysize) characterisations within if every ∈ has a (polysize) characterisation wrt to any ℒ-ontology within . Unique characterisations can be used to illustrate, explain, and construct queries. They are also a ‘non-procedural’ necessary condition for (polynomial) learnability using membership queries in Angluin’s framework of exact learning, where membership queries to the oracle take the form ‘does , |= () hold?’ We focus our investigation on the class ELIQ of CQs that are equivalent to ℰ ℒℐ-concepts.

Examples, proofs, and further context can be found in the full version [ 11 ].

Non-temporal case. We begin by summarising the relevant results that will be used as a black box in our investigation of temporalised queries. Let be an FO-ontology (typically in some DL). Given queries 1, 2, we write 1 |= 2 and say that 1 is contained in 2 wrt if , |= 1() implies , |= 2(), for any pointed data instance (, ). We utilise a well-known reduction of containment to query entailment. An ontology admits containment reduction if, for any CQ (), there is a pointed data instance (ˆ, ) such that the following conditions hold: () is satisfiable wrt if and ˆ are satisfiable; there is a surjective homomorphism ℎ : → ˆ with ℎ() = ; and if () is satisfiable wrt , then |= ′ if , ˆ |= ′(), for any CQ ′(). An ontology language ℒ admits containment reduction if every ℒ-ontology does. For languages ℒ that admit containment reduction, a unique characterization of ∈ wrt is called a singular+characterisation if + = {ˆ}. It is easy to see that if ℒ admits both (polysize) unique characterisations within and containment reduction, then every ∈ has a (polysize) singular+characterisation. Containment reduction is a rather general condition: FO without equality including DLs such as ℒℋℐ and DL-Liteℋ [ 12 ] (aka DL-Litecℋore [ 13 ]) and also some DLs with limited counting such as DL-Liteℱ [ 12 ] (aka DL-Litecℱore [ 13 ]) admit containment reduction but ℒ does not.

The two main approaches to compute − and obtain singular+characterisations for languages with containment reduction are based on frontiers and splittings (aka dualities) [ 6 ]. A frontier of wrt within is any set ℱ ⊆ such that () |= ′ and ′ ̸|= , for all ′ ∈ ℱ; and () if |= ′′ for ′′ ∈ , then ′′ |= or there is ′ ∈ ℱ with ′ |= ′′. An ontology language ℒ admits (polysize) finite frontiers within if every ∈ has a (polysize) finite frontier wrt to any ℒ-ontology within .

Theorem 1. () DL-Liteℋ and the fragment DL-Lite−ℱ of DL-Liteℱ , in which − is not functional for any ⊑ ∃, admit polysize frontiers within ELIQ [ 14 ]. () DL-Liteℱ does not admit finite frontiers within ELIQ [ 14 ]. () ℰ ℒ does not admit finite frontiers within ELIQ.

The frontier of a query supplies the negative examples for a singular+unique characterisation. Theorem 2. If ℒ admits both (polysize) frontiers within and containment reduction, then ℒ admits (polysize) singular+characterisations within , with − = ℱ, for any ∈ .

The second path to singular+characterisations is via finite splittings, which only exist if a ifnite signature of predicates is fixed. Let be a class of queries and its restriction to , ⊆ finite, and a -ontology. A set () of pointed -data instances (, ) is called a split-partner for wrt within if, for all ′ ∈ , we have , |= ′() for some within if all finite sets of -queries have split partners wrt any -ontology in ℒ. (, ) ∈ () if ′ ̸|= for all ∈ . An ontology language ℒ has general split-partners to the empty ontology, no polysize split-partners exist within -ELIQ [ 10 ].

Theorem 3. () ℒℋℐ has exponential-size general split-partners within -ELIQ, () even wrt

Thus, ℰ ℒ has finite general split-partners but no frontiers within ELIQ, and DL-Lite−ℱ has finite frontiers but no finite general split-partners within ELIQ. This is in contrast to the ontology-free case where frontiers and splittings are more closely linked [ 6 ]. ∈ . then ℒ admits (polysize) singular+characterisations within , with − Theorem 4. If ℒ admits (polysize) general split-partners within and containment reduction, = ({}), for any Temporalisation. A temporal data instance is a sequence 0, . . . , of domain data instances with regarded as a timestamp. To query temporal data, one can equip standard CQs with the operators of linear temporal logic LTL as proposed in [ 15, 16, 17, 18 ]. Within this framework, various query languages that admit (polysize) unique characterisations and learnability have been identified in the case when no background ontology is present [ 10 ]. Here, we assume that the temporal data is mediated by a standard (non-temporal) DL ontology whose axioms are supposed to be true at all times. We consider a few families of temporal queries defined in [ 10 ] that are built from domain queries in a given class (say, ELIQ or conjunctions of concept names, denoted ) using ∧ and the temporal operators ○ (at the next moment), ♢ (some time later), ♢ (now or later), and U (strict until): the family LTL○ ♢ () of path queries of the form = 0 ∧1(1 ∧2(2 ∧· · ·∧ U )), where ∈ {○ , ♢ , ♢ } and ∈ ; the family LTL ( ) LTL○ ♢ () restricts LTL○ ♢ () to the operators ○ and ♢ ; note that ♢ ≡ ○ ♢ . of path queries = 0 ∧ (1 U (1 ∧ (2 U (. . . ( U ) . . . )))), where ∈ , ∈ and its subfamily LTLU( ) of peerless queries in which ̸|= and ̸|= . The subfamily ∪ {⊥};

Temporal queries have a few essential diferences from the domain ones. First, no example set can distinguish ♢ ( ∧ ) from ♢ ( ∧ (♢ ∧ ♢ ( ∧ . . . ))) with suficiently many alternating , . A syntactic criterion (excluding proper conjunctions that do not have a ○ -neighbour) of unique characterisability of queries in LTL○ ♢ (), called safety, was found in [ 10 ]. Second, containment reduction does not work anymore since to characterise, say, ♢ two positive examples are needed. By generalising safety in a natural way, we obtain our first transfer result: uniquely characterisable within LTLU ( ). polynomially characterisable wrt for bounded temporal depth.

Theorem 5. Let ℒ admit (polysize) singular+characterisations within and be a ℒ-ontology that admits containment reduction. Then ∈ LTL○ ♢ () is (polysize) uniquely characterisable wrt within LTL○ ♢ () if is safe wrt ; all ∈ LTL○ ♢ () are (polysize) uniquely characterisable wrt . If admits polysize singular+characterisations within , then LTL○ ♢ () is

As a consequence of the above results, we obtain, e.g., that every safe query in LTL○ ♢ (ELIQ) characterisable wrt any ℒℋℐ-ontology. Our second transfer result is as follows: is polynomially characterisable wrt any DL-Liteℋ or DL-Lite−ℱ ontology and exponentially Theorem 6. Let ℒ have (exponential-size) general split-partners within and let be a ontology in ℒ that admits containment reduction. Then every ∈ LTLU( ) is (exponential-size)

As a consequence, we obtain that every query in LTLU( ), where is the class of -ELIQs, is exponentially uniquely characterisable within LTLU ( ) wrt any ℒℋℐ ontology. Learning. We apply our results on characterisability to learnability of queries in LTL○ ♢ (ELIQ) wrt ontologies in Angluin’s framework of exact learning [ 8 ]. In the nontemporal case, exact learning of queries has recently been studied [ 6, 9, 14, 19 ]. Given some class of queries and an ontology , the learner aims to identify a target query ∈ using membership queries of the form ‘does , |= () hold?’ to the teacher. It is assumed that the target query uses only symbols that occur in the ontology . We call polynomial query (polynomial-time) learnable wrt ℒ-ontologies using membership queries if there is a learning algorithm that receives an ℒ-ontology and an example (, ) with , |= () with satisfiable under , and constructs (up to equivalence wrt ) using polynomially many queries of polynomial size (in time polynomial) in the size of , , .

As we always construct example sets efectively, our unique (exponential) characterisability results imply (exponential-time) learnability with membership queries. Obtaining polynomialtime learnability from polynomial characterisations is more challenging and, in fact, not always possible. We concentrate on ontologies formulated in fragments ℒ of the DL ℰ ℒℋℐℱ which are in normal form [20], but conjecture that our results continue to hold in general. ℒ admits polytime instance checking if , |= (), for a concept name , can be decided in polynomial time. Meet-reducibility is in polytime if it can be checked in polytime whether an ELIQ is equivalent to a proper conjunction of ELIQs wrt to an ℒ-ontology. The following is shown by lifting the techniques for the non-temporal case developed in [ 19, 14 ] to the temporal case: Theorem 7. Let ℒ be an ontology language that contains only ℰ ℒℋℐℱ -ontologies in normal form and that admits polysize frontiers within ELIQ that can be computed. Then: () The class of safe queries in LTL○ ♢ (ELIQ) is polynomial query learnable wrt ℒ-ontologies using membership queries. () The class LTL○ ♢ (ELIQ) is polynomial query learnable wrt ℒ-ontologies using membership queries if the learner knows the temporal depth of the target query in advance. () LTL○ ♢ (ELIQ) is polynomial query learnable wrt ℒ-ontologies using membership queries. If ℒ further admits polynomial-time instance checking and polynomial-time computable frontiers within ELIQ, then in () and (), polynomial query learnability can be replaced by polynomialtime learnability. If, in addition, meet-reducibility wrt ℒ-ontologies is in polynomial time, then also in () polynomial query learnability can be replaced by polynomial-time learnability.

Theorem 7 fully applies to DL-Lite−ℱ as it enjoys all properties mentioned, while DL-Liteℋ enjoys all properties mentioned except that meet-reducibility can be checked in poly-time. Most importantly, DL-Lite−ℱ and DL-Liteℋ admit polynomial time computable frontiers [ 14 ]. Outlook. Many interesting and challenging problems remain to be addressed. For instance, is it possible to overcome some of our negative results for unique characterisability by admitting some form of infinite (but finitely presentable) examples? Some results in this direction without ontologies are obtained in [21]. doi:10.1016/j.websem.2014.11.008. [16] S. Borgwardt, V. Thost, Temporal query answering in the description logic EL, in: Proc. of

IJCAI, AAAI Press, 2015, pp. 2819–2825. URL: http://ijcai.org/Abstract/15/399. [17] A. Artale, R. Kontchakov, A. Kovtunova, V. Ryzhikov, F. Wolter, M. Zakharyaschev, Ontology-mediated query answering over temporal data: A survey, in: Proc. of TIME, Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2017, pp. 1:1–1:37. URL: https://doi.org/ 10.4230/LIPIcs.TIME.2017.1. doi:10.4230/LIPIcs.TIME.2017.1. [18] A. Artale, R. Kontchakov, A. Kovtunova, V. Ryzhikov, F. Wolter, M. Zakharyaschev, First-order rewritability and complexity of two-dimensional temporal ontology-mediated queries, J. Artif. Intell. Res. 75 (2022) 1223–1291. URL: https://doi.org/10.1613/jair.1.13511. doi:10.1613/jair.1.13511. [19] M. Funk, J. C. Jung, C. Lutz, Exact learning of ELI queries in the presence of dl-lite-horn ontologies, in: Proc. of DL, CEUR-WS.org, 2022. [20] F. Baader, I. Horrocks, C. Lutz, U. Sattler, An Introduction to Description Logics, Cambridge

University Press, 2017. [21] P. Sestic, Unique Characterisability of Linear Temporal Logic, Msc, University of Amsterdam, 2023. [22] V. Gutiérrez-Basulto, J. C. Jung, R. Kontchakov, Temporalized EL ontologies for accessing temporal data: Complexity of atomic queries, in: Proc. of IJCAI, IJCAI/AAAI Press, 2016, pp. 1102–1108. URL: http://www.ijcai.org/Abstract/16/160. [23] A. Artale, R. Kontchakov, V. Ryzhikov, M. Zakharyaschev, A cookbook for temporal conceptual data modelling with description logics, ACM Trans. Comput. Log. 15 (2014) 25:1–25:50. URL: https://doi.org/10.1145/2629565. doi:10.1145/2629565. [24] P. A. Wałęga, B. Cuenca Grau, M. Kaminski, E. V. Kostylev, DatalogMTL over the Integer Timeline, in: Proc. of KR, 2020, pp. 768–777. URL: https://doi.org/10.24963/kr.2020/79. doi:10.24963/kr.2020/79. [25] D. Angluin, Learning regular sets from queries and counterexamples, Inf. Comput. 75 (1987) 87–106. URL: https://doi.org/10.1016/0890-5401(87)90052-6. doi:10.1016/ 0890-5401(87)90052-6. [26] M. Shahbaz, R. Groz, Inferring mealy machines, in: Proc. of FM, Springer, 2009, pp.

207–222. [27] F. Aarts, F. Vaandrager, Learning i/o automata, in: Proc. of CONCUR, Springer, 2010, pp.

71–85. [28] S. Cassel, F. Howar, B. Jonsson, B. Stefen, Active learning for extended finite state machines, Formal Aspects Comput. 28 (2016) 233–263. URL: https://doi.org/10.1007/ s00165-016-0355-5. doi:10.1007/s00165-016-0355-5. [29] F. Howar, B. Stefen, Active automata learning in practice - an annotated bibliography of the years 2011 to 2016, in: Machine Learning for Dynamic Software Analysis: Potentials and Limits, International Dagstuhl Seminar 16172, volume 11026 of Lecture Notes in Computer Science, Springer, 2018, pp. 123–148. URL: https://doi.org/10.1007/978-3-319-96562-8_5. doi:10.1007/978-3-319-96562-8\_5. [30] A. Camacho, S. A. McIlraith, Learning interpretable models expressed in linear temporal logic, in: Proc. of ICAPS, AAAI Press, 2019, pp. 621–630. URL: https://aaai.org/ojs/index. php/ICAPS/article/view/3529. [31] C. Lemieux, D. Park, I. Beschastnikh, General ltl specification mining (t), in: Proc. of ASE,

IEEE, 2015, pp. 81–92. [32] D. Neider, I. Gavran, Learning linear temporal properties, in: Proc. of FMCAD, IEEE, 2018, pp. 1–10. URL: https://doi.org/10.23919/FMCAD.2018.8603016. doi:10.23919/FMCAD. 2018.8603016. [33] N. Fijalkow, G. Lagarde, The complexity of learning linear temporal formulas from examples, CoRR abs/2102.00876 (2021). URL: https://arxiv.org/abs/2102.00876. arXiv:2102.00876. [34] M. Fortin, B. Konev, V. Ryzhikov, Y. Savateev, F. Wolter, M. Zakharyaschev, Reverse engineering of temporal queries mediated by LTL ontologies, in: Proceedings of IJCAI, 2023. [35] M. Arenas, G. I. Diaz, The exact complexity of the first-order logic definability problem,

ACM Trans. Database Syst. 41 (2016) 13:1–13:14. [36] P. Barceló, M. Romero, The complexity of reverse engineering problems for conjunctive queries, in: Proc. of ICDT, 2017, pp. 7:1–7:17. [37] J. Lehmann, P. Hitzler, Concept learning in description logics using refinement operators,

Machine Learning 78 (2010) 203–250. [38] V. Gutiérrez-Basulto, J. C. Jung, L. Sabellek, Reverse engineering queries in ontologyenriched systems: The case of expressive Horn description logic ontologies, in: Proc. of IJCAI-ECAI, 2018. [39] M. Funk, J. C. Jung, C. Lutz, H. Pulcini, F. Wolter, Learning description logic concepts: When can positive and negative examples be separated?, in: Proc. of IJCAI, 2019, pp. 1682–1688. [40] P. G. Kolaitis, Schema Mappings and Data Examples: Deriving Syntax from Semantics (Invited Talk), in: Proc. of FSTTCS, volume 13, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2011, pp. 25–25. URL: http://drops.dagstuhl.de/opus/ volltexte/2011/3359. doi:10.4230/LIPIcs.FSTTCS.2011.25. [41] B. Alexe, B. ten Cate, P. G. Kolaitis, W. C. Tan, Characterizing schema mappings via data examples, ACM Trans. Database Syst. 36 (2011) 23. [42] B. ten Cate, R. Koudijs, Characterising modal formulas with examples, CoRR abs/2304.06646 (2023). URL: https://doi.org/10.48550/arXiv.2304.06646. doi:10.48550/ arXiv.2304.06646. arXiv:2304.06646. [43] A. Artale, R. Kontchakov, A. Kovtunova, V. Ryzhikov, F. Wolter, M. Zakharyaschev, Firstorder rewritability of ontology-mediated queries in linear temporal logic, Artif. Intell. 299 (2021) 103536. URL: https://doi.org/10.1016/j.artint.2021.103536. doi:10.1016/j.artint. 2021.103536. [44] M. Bienvenu, B. ten Cate, C. Lutz, F. Wolter, Ontology-based data access: A study through disjunctive datalog, CSP, and MMSNP, ACM Trans. Database Syst. 39 (2014) 33:1–33:44. [45] R. McKenzie, Equational bases and nonmodular lattice varieties, Transactions of the

American Mathematical Society 174 (1972) 1–43. [46] S. Kikot, R. Kontchakov, M. Zakharyaschev, On (in)tractability of OBDA with OWL 2 QL, in: R. Rosati, S. Rudolph, M. Zakharyaschev (Eds.), Proc. of DL, CEUR-WS.org, 2011. URL: https://ceur-ws.org/Vol-745/paper_7.pdf. [47] C. Chang, H. J. Keisler, Model Theory, Elsevier, 1998. [48] S. Tobies, Complexity results and practical algorithms for logics in knowledge representation, Ph.D. thesis, RWTH Aachen University, Germany, 2001. URL: http://sylvester.bth. rwth-aachen.de/dissertationen/2001/082/01_082.pdf . [49] M. Bienvenu, P. Hansen, C. Lutz, F. Wolter, First order-rewritability and containment of conjunctive queries in Horn description logics, in: Proc. of IJCAI, 2016, pp. 965–971.

References

[1] D. M. L. Martins , Reverse engineering database queries from examples: State-of-the-art, challenges , and research opportunities, Inf. Syst . 83 ( 2019 ) 89 - 100 .

[2] S. Staworko , P. Wieczorek , Characterizing XML twig queries with examples , in: Proc. of ICDT , 2015 , pp. 144 - 160 . URL: https://doi.org/10.4230/LIPIcs.ICDT. 2015 . 144 . doi: 10 .4230/ LIPIcs.ICDT. 2015 . 144 .

[3] B. Konev , C. Lutz , A. Ozaki , F. Wolter , Exact learning of lightweight description logic ontologies , J. Mach. Learn. Res . 18 ( 2017 ) 201 : 1 - 201 : 63 . URL: http://jmlr.org/papers/v18/ 16 - 256 .html.

[4] B. ten Cate , V. Dalmau , P. G. Kolaitis , Learning schema mappings , ACM Trans. Database Syst . 38 ( 2013 ) 28 : 1 - 28 : 31 . URL: https://doi.org/10.1145/2539032.2539035. doi: 10 .1145/ 2539032.2539035.

[5] A. Ozaki , Learning description logic ontologies: Five approaches. where do they stand? , Künstliche Intell . 34 ( 2020 ) 317 - 327 . URL: https://doi.org/10.1007/s13218-020-00656-9. doi: 10 .1007/s13218-020-00656-9.

[6] B. ten Cate , V. Dalmau , Conjunctive queries: Unique characterizations and exact learnability , ACM Trans. Database Syst . 47 ( 2022 ) 14 : 1 - 14 : 41 . URL: https://doi.org/10.1145/3559756. doi: 10 .1145/3559756.

[7] J. C. Jung , C. Lutz , H. Pulcini , F. Wolter , Logical separability of labeled data examples under ontologies , Artif. Intell . 313 ( 2022 ) 103785 . URL: https://doi.org/10.1016/j.artint. 2022 . 103785 . doi: 10 .1016/j.artint. 2022 . 103785 .

[8] D. Angluin , Queries and concept learning , Mach. Learn . 2 ( 1987 ) 319 - 342 . URL: https: //doi.org/10.1007/BF00116828. doi: 10 .1007/BF00116828.

[9] M. Funk , J. C. Jung , C. Lutz , Actively learning concepts and conjunctive queries under ELr-ontologies , in: Proc. of IJCAI, ijcai.org , 2021 , pp. 1887 - 1893 . URL: https://doi.org/10. 24963/ijcai. 2021 /260. doi: 10 .24963/ijcai. 2021 /260.

[10] M. Fortin , B. Konev , V. Ryzhikov , Y. Savateev , F. Wolter , M. Zakharyaschev , Unique characterisability and learnability of temporal instance queries , in: Proc. of KR , 2022 . URL: https://proceedings.kr.org/ 2022 /17/.

[11] J. C. Jung , V. Ryzhikov , F. Wolter , M. Zakharyaschev , Temporalising unique characterisability and learnability of ontology-mediated queries , CoRR abs/2306 .07662 ( 2023 ). URL: https://doi.org/10.48550/arXiv.2306.07662. doi: 10 .48550/arXiv.2306. 07662. arXiv: 2306 . 07662 .

[12] D. Calvanese , G. D. Giacomo , D. Lembo , M. Lenzerini , R. Rosati , Tractable reasoning and eficient query answering in description logics: The DL-Lite family , J. Autom. Reasoning 39 ( 2007 ) 385 - 429 .

[13] A. Artale , D. Calvanese , R. Kontchakov , M. Zakharyaschev, The DL-Lite family and relations , J. Artif. Intell. Res . 36 ( 2009 ) 1 - 69 .

[14] M. Funk , J. C. Jung , C. Lutz , Frontiers and exact learning of ELI queries under dl-lite ontologies , in: Proc. of IJCAI , 2022 , pp. 2627 - 2633 . URL: https://doi.org/10.24963/ijcai. 2022 /364. doi: 10 .24963/ijcai. 2022 /364.

[15] F. Baader , S. Borgwardt , M. Lippmann, Temporal query entailment in the description logic SHQ , J. Web Semant . 33 ( 2015 ) 71 - 93 . URL: https://doi.org/10.1016/j.websem. 2014 . 11 .008.