Query-by-Example for Expressive Horn Description Logics?

Abstract

We initiate the study of query-by-example (QBE) in the framework of ontologybased data access. Query-by-example is a reverse engineering problem that asks for the existence of a query complying with a set of speci ed examples. Formally, we study the following problem QBE(L; Q) for some ontology language L and a query language Q: { Input: L-knowledge base (T ; A), sets S+; S , and a signature { Question: is there a query q(x) 2 Q using only symbols in (T ; A) j= q(a) for all a 2 S+, and (T ; A) 6j= q(b) for all b 2 S ? As a simple example, consider the knowledge base consisting of T = fHuman v Vertebrate; Vertebrate v 9hasPart:Spineg; A = fHuman(ax); hasPart(an; sp); Spine(sp); Bug(bug)g: If the positive examples are S+ = fax; ang and the negative example is S = fbugg, then q(x) = 9y hasPart(x; y) ^ Spine(y) is a witness query. However, there is no witnessing query in the case S+ = fan; bugg and S = faxg. Motivation. Query-by-example is a classical querying paradigm [2] which has, due to `big data', lately gained new interest since even expert users might nd it useful to explore the data in this way. The practical motivation for our paper is to improve the usability of ontology-based systems. In such systems, users access the knowledge base through queries usually formulated in powerful query languages such as (unions of) conjunctive queries (U)CQs. Unfortunately, it has been observed that casual non-expert users are often not able to specify queries in these formalisms, e.g., Statoil geologists [3], clearly hampering the usability of ontology-based systems. Query-by-example suggests an alternative approach to querying: instead of writing the query itself, the user provides examples that she does (not) expect as answers and the system supports the user by providing a conforming query. This is possibly repeated until the user is satis ed. From the theoretical perspective, our motivation is to continue bridging the gap between DL and machine learning research. Indeed, QBE over description logic knowledge bases can be viewed as an instantiation of the inductive logic ? Accepted at IJCAI-ECAI 2018 [1]. Authors were funded by EU's Horizon 2020 programme under the Marie Sklodowska-Curie grant 663830, the Research Foundation Flanders project G.0428.15, and ERC consolidator grant 647289 CODA, respectively

-

programming (ILP) framework [ 4 ], where typically the knowledge base P is given in Prolog or a di erent rule language, and the goal is to learn a set of rules P0 such that P [ P0 conforms with the examples. The cases of our query languages correspond to single rule programs P0 for CQs and sets of rules with the same head for UCQs, respectively.

It is worth mentioning that the query-by-example framework has been studied and implemented for ALC-knowledge bases and ALC concept queries as query language [ 5 ].

Contribution. Our main contributions are characterizations, algorithms, and complexity bounds for QBE(L; Q) for L an expressive Horn DL L 2 fHorn-ALCI; Horn-ALCg and Q 2 fCQ; UCQg. We start with providing natural modeltheoretic characterizations for QBE(Horn-ALCI; Q) for Q 2 fCQ; UCQg by lifting characterizations known from the relational database setting [ 6 ] by replacing the database with the universal model of the knowledge base. Unfortunately, our characterizations do not give immediate rise to a decision procedure because the universal model is typically in nite. To overcome this, we exploit the regularity of universal models and provide decision procedures running in 2-ExpTime and coNExpTime for Horn-ALCI and Horn-ALC, respectively. Having these, we prove matching lower bounds, the most challenging one being a 2-ExpTime-lower bound for QBE(Horn-ALCI; Q), Q 2 fCQ; UCQg. Interestingly, some results depend on restricting the signature, so we consider also the variant QBEf of QBE with unrestricted signature. Some of our techniques are inspired from approaches to query conservative extensions [ 7, 8 ], but we are not aware of direct reductions. The following table summarizes our results.

L ! QBE(L; CQ) QBE(L; UCQ) QBEf (L; CQ) QBEf (L; UCQ)

Horn-ALCI

2-ExpTime 2-ExpTime 2-ExpTime ExpTime

Horn-ALC

coNExpTime

ExpTime coNExpTime

ExpTime Most notably, { in the cases of QBE (Horn-ALC; CQ), the availability of TBoxes does not increase the complexity compared to the relational database setting [ 9, 6 ], { inverse roles lead to a jump in the complexity, and { 2-ExpTime-hardness already holds for ELI TBoxes and concept queries.

We obtain the same results for the variant QDEF of QBE, the problem to decide whether some q 2 Q returns precisely the positive examples. We also investigate the size of witness queries which is vital for practical purposes since eventually the user is interested in obtaining a query to further explore the data. We particularly show that they can be double exponentially large, which is in contrast to the relational database setting. We further show that { if a witness query exists { there is always one of at most double exponential size (Horn-ALC), respectively fourfold exponential size (Horn-ALCI). Such sizes are clearly impractical which motivates the study of approximations in the future.

References

1. Gutierrez-Basulto , V. , Jung , J.C. , Sabellek , L. : Reverse engineering queries in ontology-enriched systems: The case of expressive horn description logic ontologies . In: Proc. of IJCAI-ECAI-18 , AAAI Press ( 2018 )

2. Zloof , M.M. : Query-by-example: the invocation and de nition of tables and forms . In: Proc. of VLDB-75 . ( 1975 ) 1 { 24

3. Hovland , D. , Kontchakov , R. , Skj veland, M.G., Waaler , A. , Zakharyaschev , M. : Ontology-based data access to Slegge . In: Proc. of ISWC-17 . ( 2017 ) 120 { 129

4. Nienhuys-Cheng, S., de Wolf, R., eds.: Foundations of Inductive Logic Programming. Volume 1228 of Lecture Notes in Computer Science . Springer ( 1997 )

5. Lehmann , J. , Hitzler , P. : Concept learning in description logics using re nement operators . Machine Learning 78 ( 1 ) ( Sep 2009 ) 203

6. ten Cate, B. , Dalmau , V. : The product homomorphism problem and applications . In: Proc. of ICDT-15 . ( 2015 ) 161 { 176

7. Botoeva , E. , Konev , B. , Lutz , C. , Ryzhikov , V. , Wolter , F. , Zakharyaschev , M. : Inseparability and conservative extensions of description logic ontologies: A survey . In: Proc. of RW-16 . ( 2016 )

8. Jung , J. , Lutz , C. , Martel , M. , Schneider , T. : Query conservative extensions in horn description logics with inverse roles . In: Proc. of IJCAI-17 . ( 2017 )

9. Barcelo , P. , Romero , M.: The complexity of reverse engineering problems for conjunctive queries . In: Proc. of ICDT-17 . ( 2017 )