First Order Rewritability for Ontology Mediated Querying in Horn-DLF D

Abstract

We study rst order (FO) rewritability for query answering in the setting of ontology mediated queries (OMQ) in which ontologies are formulated in the Horn fragments of the feature description logic DLF D. In general, OMQ approaches for logics such as DLF D rely on non-FO completion of the data (ABoxes) that can commonly be expressed as Datalog programs. In this paper, we study the problem of the existence of FO rewritings for a given Horn-DLF D theory (TBox) in terms of Beth de nability, and show how Craig interpolation can then be used to e ectively construct the rewritings (when they exist) from the Clark's completion of Datalog programs for computing ABox completions. In addition, since data that populates OMQ is commonly residing in relational database systems, we show how constraints enforced by such systems can be used to expand the scope of rewritable queries.

Introduction

In earlier work [ 25,27 ], we presented a combined-combined approach to ontology mediated querying (OMQ) of backend relational data sources when ontologies are formulated as TBoxes in the Horn fragments of the description logic (DL) DLF D and where ABoxes are induced by data residing in the data sources. The logic DLF D is the most expressive member of the FunDL family of feature-based DLs [ 26 ], which are particularly well suited for capturing relational schemata by virtue of being feature-based and also by virtue of including the path functional dependency (PFD) concept constructor. PFDs makes it possible to capture a variety of equality generating dependencies commonly occurring in relational schemata, such as primary keys, uniqueness constraints and functional dependencies. To illustrate, we show in the next section how the relational schema in Figure 1 can be captured as a Horn-DLF D TBox, the FunDL dialect that will be the focus of the remainder of this paper. This example also serves to illustrate how the parts of a TBox that re ect a relational schema could in principle be automatically generated, and thereby make it unnecessary to author so-called mapping rules in ontology based data access (OBDA) (again see [ 25,27 ]).

The combined-combined approach is so named because any of the Horn fragments of DLF D in the FunDL family will require using ontological knowledge, a Horn-DLF D TBox in our case, for two steps in OMQ. The rst step, as with the combined approach to OMQ [ 19,20,22,23 ], is to complete the ABox via a Datalog program that adds tuples to tables in the backend relational database. Note that this rst step depends only on the TBox. The second step, as with the perfect rewriting approach to OMQ and OBDA [ 9 ], is to rewrite a query to account for such artifacts as inheritance and attribute typing in the TBox.

In this paper, we show how Beth de nability can be used to resolve the problem of recognizing when a rst order (FO) rewriting of the Datalog program needed in the rst step exists, and then how Craig interpolation can be used to e ectively construct such a rewriting. A key insight is to employ the Clark's completion of the Datalog program in both the diagnosis and synthesis of FO expressibility of ABox completion.

The existence of such a rewriting enables an OMQ frontend to a relational data source to operate entirely by a more re ned query reformulation that, for a given user query, ultimately yields an SQL query over the data source, that is, with no requirement to update tables in the data source beforehand. An additional advantage of our approach is that it also becomes straightforward to incorporate the bene ts of integrity constraints such as foreign key constraints that are enforced by a relational database management system to simplify query reformulation. Indeed, such integrity constraints can enable FO rewriting of data completion that would otherwise not be possible.

In summary, our contributions are as follows. 1. We show how to decide FO rewritability of OMQ in Horn-DLF D via Clark's completion of Datalog programs and Beth de nability; 2. We show how an equivalent non-recursive Datalog program can be derived via Craig's theorem and interpolation in cases where ABox completion for a given TBox is indeed FO expressible; 3. We illustrate how integrity constraints in backend relational schema can enable FO rewritability of OMQ that would otherwise not be possible; and 4. We show how our framework extends to query speci c OMQ in a straightforward manner.

The remainder of the paper is organized as follows. Section 2 immediately following provides the necessary background and de nitions. Here, we review HornDLF D and the combined combined approach to OMQ. Our main results follow in Section 3 in which we show how the above-mentioned artifacts, Clark's completion of Datalog programs for example, can be employed to both decide FO rewritability and to synthesize FO rewritings of ABox completion in the combined combined approach to OMQ. In Section 4 shows how a Datalog program computing an ABox completion can usefully incorporate database constraints enforced by backend relational database systems. Section 5 then considers query speci c OMQ, that is, when the combination of a Datalog ABox completion procedure and a speci c query are FO expressible. Summary comments and our conclusions are in Section 6.

create table EMP ( name STRING not null, dept STRING, man STRING, primary key ( name ), constraint deptRef foreign key ( dept ) references DEPT, constraint manRef foreign key( man ) references EMP ); create table DEPT ( name STRING not null, head STRING, primary key ( name ), candidate key ( head ), constraint headRef foreign key( head ) references EMP ); All member dialects of the FunDL family of DLs [ 26 ] are fragments of FOL with underlying signatures based on disjoint sets of unary predicate symbols PC, called primitive concepts, constant symbols IN, called individuals, and unary function symbols F, called features. The latter replace roles in other DLs and are interpreted as either total functions or partial functions, depending on the particular FunDL dialect.

The most expressive member of the FunDL family is the dialect DLF D. In this paper, we consider Horn-DLF D, the most expressive Horn fragment of DLF D, assuming in particular that an ontology is given as a Horn-DLF D TBox.1 To simplify our presentation, we also assume features are interpreted as total functions.

De nition 1 (Horn-DLF D) A path function Pf is a word in F , with the

empty word denoted by id , and concatenation by \:". Concept descriptions of two kinds, C and D, are de ned by the grammar rules on the left-hand-side of Figure 2, where A 2 PC, f 2 F and Pf (possibly subscripted) refers to a path function. An instance of the nal production is called a path functional dependency (PFD).

Semantics is de ned in the standard way with respect to an interpretation

I = (4; ( )I ) that xes the meaning of symbols in PC, IN and F. Here, features are interpreted as total functions. We also assume the unique name assumption (UNA) whereby, for any distinct individuals a and b, aI 6= bI .

The interpretation function I is extended to path expressions by interpreting

id (the empty word) as the identity function x:x, concatenation as function composition, and to complex concept descriptions C or D as given on the righthand-side of Figure 2. An interpretation I satis es a subsumption C v D if 1 Here, we do not consider the problem of recognizing when TBoxes in very expressive DLs have unique minimal models. C ::= A D ::= C j 8 Pf :C j C1 u C2

CI DI , a concept assertion A(a) if aI 2 AI , and a feature assertion f (a) = b if f I (aI ) = bI , where a; b 2 IN.

A knowledge base (KB) K = (T ; A) consists of a TBox T of subsumptions, and an ABox A of assertions. I satis es K if it satis es each subsumption and assertion in K.

Although incorporating features deviates from the normal practice of using binary predicate symbols called roles, features make it easier to incorporate concept constructors suited to the capture of relational data sources that include various dependencies by a straightforward rei cation of n-ary predicates. Thus, e.g., a role R can be rei ed as a primitive concept RC and two features domR and ranR in Horn-DLF D, and a subsumption A v 8R:B can then be captured as a subsumption 8domR:A v 8ranR:B.

As usual, to ensure decidability in the presence of ABoxes [ 28 ] and reasonable computational properties of the logic, one looks for additional restrictions on the PFD concept constructors. One restriction, which has been investigated (e.g., [ 17,27 ]), is to limit the PFD constructor to one of the following two forms: 1: C : Pf1; : : : ; Pf : Pfi; : : : ; Pfk ! Pf or 2: C : f1; : : : ; fk ! g We can allow a more complex variant of (2) if the ABox completion admits/requires creating additional constant symbols; for details|beyond the scope of this paper|see [ 27 ]. Also, in this paper we will not explore the parameter tractable fragments of Horn-DLF D nor the issues connected with interpreting features as partial functions. Both these issues were studied in [ 25 ] which shows, among other things, how partiality can be easily simulated in Horn-DLF D. Example 2 Figure 3 lists the subsumptions for a Horn-DLF D TBox that provides an ontological view of the relational schema illustrated in Figure 1. Part (a) are subsumptions that capture column de nitions and data dependencies manifest in the schema itself. This part of an ontology can be automatically generated (disjoint classes) EMP u DEPT v ?

EMP u STRING v ?

DEPT u STRING v ? (attribute typing) EMP v 8name:STRING

EMP v 8deptRef:DEPT EMP v 8manRef:EMP DEPT v 8headRef:MAN DEPT v 8name:STRING

DEPT v DEPT : name ! id (primary keys) EMP v EMP : name ! id (candidate keys) DEPT v DEPT : head ! name (a) derived from the relational schema (disjoint columns) EMP v DEPT : name ! id (b) additional data dependencies (inheritance) MAN v EMP (local typing) EMP v 8manRef:MAN

DEPT v 8headRef:EMP (inverses) MAN v 9headRef 1 (c) ontology enhancement (for an outline of a procedure to do this, see [ 25 ]). Observe in particular how the name attached to a foreign key constraint, such as headRef, is mapped to a feature with the same name. Part (b) illustrates how additional data dependencies not expressible without appeal to general assertions in SQL can also be captured in Horn-DLF D. Here, the (presumed) fact that name values of employees are disjoint from name values of departments is captured by appeal to an asymmetric use of PFDs. Finally, Part (c) illustrates how an ontology can be enhanced by adding further subsumptions, in this case relating to the virtual concept of a manager.

Conjunctive queries are, as usual, formed from atomic queries (or atoms) of the form \A(x)" and \x:f = y", where x and y are variables, using conjunction and existential quanti cation. To simplify notation, we con ate conjunctive queries with the set of its constituent atoms and a set of answer variables: De nition 3 (Conjunctive Queries and Certain Answers) Let A(xi) and xi1 :fi = xi2 be ( rst-order) atoms, where A is a primitive concept , fi is a feature, and x and y tuples of variables. A conjunctive query (CQ) ' is an expression of the form 9y: V with free variables x, that is constructed from the above atoms using conjunctions and existential quanti cation.

Let K be a Horn-DLF D knowledge base and ' a CQ. A certain answer to ' over K is a substitution of constant symbols a, [x 7! a], such that K j= '[x 7! a].

As usual, UCQ stands for a union of CQs. To study the rst-order rewritability of conjunctive queries over Horn-DLF D TBoxes, we use the following version of the combined combined approach to OMQ in our setting.

Proposition 4 (Combined Combined Approach to OMQ [ 25,27,30 ]) Let K = (T ; A) be a Horn-DLF D knowledge base and ' a conjunctive query.

Then there is a UCQ query 'T and a Datalog program

be e ectively constructed from T , such that

T , both of which can

K j= '[x 7! a] () T (A) j= 'T [x 7! a] for a tuple of constant symbols a and where when evaluated over A.

T (A) is the minimal model of

T The proposition uses a Datalog program T to de ne an ABox completion over which the query 'T , the rewriting of the original user query, is evaluated to compute the certain answers. The Proposition also shows that the data complexity of OMQ in Horn-DLF D is complete for PTIME. 3

Classi cation of Horn-DLF D TBoxes To simplify the presentation, we assume that Horn-DLF D TBoxes are in a normal form given as follows: De nition 5 (Normal Form of Horn-DLF D TBoxes) Let T be a Horn-DLF D TBox. We say that T is in normal form if all subsumptions adhere to one of the following six forms: 1. A v ?, 2. A1 u A2 v B, 3. A v 8f:B, 4. 8f:A v B, 5. A v 9f 1, and 6. A v B : Pf1; : : : ; Pfk ! Pf.

It is an easy exercise to convert an arbitrary Horn-DLF D TBox to its conservative extension in this normal form by introducing additional primitive concepts.

De nition 6 (Datalog Program T ) The Datalog program T used in Pro

position 4 consists of completion rules obtained by translating subsumptions that are logical consequences of T . The form of these subsumptions and their translation are given as follows: (consequences of T ) (completion rule in

T ) A v ? A1 u A2 v B A v 8f:B 8f:A v B

C?(x) CB(x) CB(x) CB(x)

CA(x) CA1 (x); CA2 (x) CA(y); Rf (y; x) CA(y); Rf (x; y)

For every primitive concept B, we introduce an unary EDB predicate PB(x)

together with an additional clause CB(x) PB(x) that captures explicit data in an ABox of the form A(a), and an IDB predicate CB(x) corresponding to the completion of the ABox w.r.t. T . For features, we use Rf (x; y) as a synonym for ABox assertion f (x) = y to conform with standard Datalog syntax. We also de ne an auxiliary symbol C?(x) that will be used to test for ABox consistency. Note that the subsumptions for unquali ed inverse features (5) and PFDs (6) do not contribute to the de nition of an ABox completion since they do not generate additional ABox assertions for primitive concepts. Also note that, unlike in the classical combined approach [ 19,23 ], our combined combined approach does not introduce any new constants in the ABox [ 27 ].

To test for rst-order de nability of the completion (i.e., all predicates that stand for the completed ABox instance), we use the following construction: De nition 7 (Clark's Completion

T is given by a set of formulas

CB(x) $ PB(x) _ (9y: 1) _ : : : _ (9y: n) corresponding to all clauses CB(x)

Note that Clark's result works in the much more general setting of logic programs with function symbols and possibly in nite resolution proofs and under the Negation As Failure semantics. Since Clark's completion makes all IDB predicates closed, we can now use standard tools for testing for explicit de nability. Note that had we used T instead, none of the de nability results could possibly hold. Note that in absence of role/feature subsumptions (such as role hierarchies) we do not need to apply the completion to the Rf atoms.

Proposition 9 (Projective Beth De nability [ 3 ]) Let be an FO theory over symbols in L and L0 L. Then the following are equivalent: 1. For M1 and M2 models of such that M1jL0 = M2jL0 , it holds that M1 j= '[a] i M2 j= '[a] for all M1, M2, and a tuples of constants, and

2. ' is equivalent under to a formula in L0.

This gives us a complete characterization of rst-order rewritability of the ABox closure of individual primitive concepts with respect to Horn-DLF D TBoxes as follows: fPA1 ; : : : ; PAk ; Rf1 ; : : : ; Rfn g.

Theorem 10 Let T be a Horn-DLF D TBox over the primitive concepts and

features fA1; : : : ; Ak; f1; : : : ; fng, and let T 0 be a conservative extension of T in normal form. Then the completion of the primitive concept A w.r.t. T is rst-order de nable if and only if CAi (x) is Beth de nable over T 0 and L0 = Proof. Follows immediately from the properties of Beth de nability (Proposition 9) and the de nition and properties of the Clark's completion (Proposition 8).

Observe that one can restrict the alphabet of the ABox (L0) to target only ABoxes over restricted signature(s).

Given T , one can now reformulate (1) in Proposition 9 as a logical implication problem by making a copy of all formulas of T in which all non-logical symbols not in fPA1 ; : : : ; PAk ; Rf1 ; : : : ; Rfn g are starred. Hence, the de nability question for CA(x) can be expressed as a logical implication question of the form: T [

T j= 8x:CA(x) ! CA(x) (1) Note that, on closer inspection, all formulas in subsumptions.2 Hence: T can be written as ALCI

Theorem 11 Let T be a Horn-DLF D TBox. Then the existence of

1. the rst order rewritability of the A completion with respect to T ,

2. the consistency of T , and

3. the uniform query rewritability over T

are all decidable and in EXPTIME.

Proof. The rst claims follow immediately from Theorem 10 applied to all atoms of the form CB and the decidability and complexity of reasoning in ALCI. The second claim relies on de nability of C?(x) and, in the presence of key PFDs of the form A v B : Pf1; : : : ; Pfk ! Pf, on the de nability of CA(x) and CB(x) since the remaining consistency check for PFD satisfaction can then be expressed as a rst-order query with respect to these explicit de nitions. The last claim follows by observing that (i) de nability of atomic queries implies de nability of arbitrary (U)CQs using the combined-combined approach [ 25 ], and that (ii) non-de nability of a single atomic query exhibits the need for a non rst-order ABox completion for queries containing/consisting of this atom. Note that in the third case one can restrict the de nability conditions to atoms that can appear in the query 'T . A matching lower bound can be obtained for expressive fragments of Horn-DLF D (for which the reasoning complexity is EXPTIME-complete). However, the exact complexity is open for PTIME fragments, such as CF Dnc and CF DI8kc . Note, however, that since the size (and the construction) of rewritings will dominate this cost (even for the simplest ontology languages [ 18 ]), exact complexity bounds are mostly of academic interest. Example 12 Returning to our introductory example, we nd out that neither CEMP(x) nor CDEPT(x) nor the TBox-derived CMAN(x) atom are rst-order de nable. We con rmed this using a tableau-based depth-limited interpolant generator [ 16,31 ]. One of the reasons is that an ABox can contain a chain of alternating deptRef/empRef features without having the objects along this chain alternately belonging to the EMP and DEPT concepts, save the individual at the beginning of this chain. The Datalog completion rules are needed to propagate these concept assertions along such a chain. 2 Disregarding functionality of the original features does not matter at this juncture. To obtain an algorithm that constructs rewritings from our characterization of FO rewritability, we utilize Craig Interpolation: Proposition 13 (Craig Interpolation [ 12 ]) Let ' and be rst order formulas such that j= ' ! . Then there is a rst order formula , called Craig interpolant, containing only symbols common to ' and such that j= ' ! and j= ! .

Moreover, the interpolant can be extracted, typically in linear time, from a proof of j= ' ! , as long as a reasonably structural proof system, such as resolution, (cut-free) sequent calculus, and/or analytic tableau is used.

The formulation (1), after a minor manipulation of the formulas, can thus be used to construct a Craig interpolant for CA(x) from a (analytic) tableau proof of the above logical implication statement (if one exists): one can construct, with the help of blocking [ 1,13 ], a nite analytic tableau for (1). The size of the rewriting, however, will depend crucially on the proof system used and on the presentation of the rewriting. However, by using an optimal tableau for ALC [ 13 ] (modi ed for ALCI), one can construct an exponential representation of the rewriting by sharing common subexpressions in the same way the tableau algorithm caches already unsatis able sets. However, plain rst-order representation of the formula will su er from additional exponential blowup, as one would expect.

Combining the above construction with the already existing rewriting 'T from [ 25 ] we get: Theorem 14 Let K = (T ; A) be a Horn-DLF D knowledge base. Then the data complexity of conjunctive query answering is in AC0 whenever the A completion with respect to T is rst-order de nable with respect to T .

Proof. Let A(x) be a rst order de nition of CA w.r.t. T . Then K j= '(a) i A j= 'T [ A[y=x]=A(y) j A 2 PC](a). The claim follows since 'T [ A[y=x]=A(y) j A 2 PC] is a rst order formula, in particular a UCQ in the case of Horn-DLF D. 4

Integration of Database Constraints

For ABoxes constructed from relational instances (see the discussion in our Introduction and Background Sections), relational systems commonly enforce integrity constraints such as primary and foreign keys. The e ect of these database constraints is that parts of the corresponding ABox are not only consistent with such constraints but are a model. This observation is in particular helpful in the case of foreign keys since they stipulate that parts of the ABox completion are no longer necessary: for a foreign key to hold in an instance of a relational database, either its target exists in the appropriate table or the source is NULL, which can then be interpreted as value unknown and is taken care of by query rewriting 'T .

De nition 15 (Adding Foreign Keys) Let A v B and A v 8f:B be subsumptions corresponding to foreign keys that capture ISA and attribute typing, respectively. For each such constraint, add PB(x) CA(x) and PB(x)

CA(y); Rf (x; y), respectively, to A.

This de nition allows us to sidestep parts of the ABox completion that are mandated by the database constraints and thus already exist in the original instance of the ABox. As a consequence, we have the following extension of Theorem 14: Theorem 16 Let K = (T ; A) be a Horn-DLF D knowledge base. Then the data complexity of conjunctive query answering is in AC0 whenever the A completion with respect to T is rst-order de nable with respect to the theory T [ A. Example 17 Continuing with our example, adding the constraints PEMP(x) PEMP(x) PDEPT(x)

CEMP(y); RmanRef(x; y) CDEPT(y); RdeptRef(x; y)

CEMP(y); RheadRef(x; y) to A, both CEMP(x) and CDEPT(x) become de nable with the expected interpolants CEMP(x) and CDEPT(x) found by the above-mentioned interpolant generator [ 16,31 ]. Moreover, CMAN(x) also becomes de nable by 9y:PEMP(x)^RmanRef(y; x) (again, using the interpolant found by the interpolant generator). 5

Query-speci c Rewritability

Our approach also provides decidability for the non-uniform (query-speci c) problems:

Theorem 18 Let T be a Horn-DLF D TBox and ' a (U)QC. Then the follow

ing are equivalent: 1. T [ T j= 8x:'T ! 'T (x), and

2. ' is rst-order rewritable with respect to T .

The exact complexity again depends on the complexity of (1) above. In the general case, an EXPTIME bound follows from [ 15 ], but again, a more re ned analysis is in order for fragments of Horn-DLF D. 6

Summary and Conclusions

We have shown how the combined combined approach to OMQ can be used to determine when query answering mediated by a Horn-DLF D TBox can be reduced to a rst order query over a plain ABox (or, in turn, over the underlying data source), and when a non- rst order (Datalog-based) completion of the data is needed. Interestingly enough, and unlike other approaches that aim on determining rst-order rewritability, our approach links the problem to well studied issues of explicit de nability [ 3 ], interpolation [ 12 ], and to Clark's completion of logic programs [ 11 ]. In addition, our approach naturally and seamlessly incorporates database constraints that hold in the data source to improve our chances of nding a rst order rewriting.

Further extensions of this work along the following lines is needed: { Performing a ne-grained analysis of computational complexity for tractable members of Horn-DLF D, such as CF Dnc. (We conjecture that the rewritability problem will remain intractable.) { Determining if a dichotomy holds, in particular, if non-rewritability implies NL hardness of OMQ in data complexity. (We conjecture that this is the case since blocked branches of a tableau proof signal non-rewritability and can be used to simulate, e.g., s-t connectivity similarly to the approach in [ 21 ].) { Extensions to situations in which ABox closure requires a nite number of additional auxiliary constants. (The approach itself can immediately use Skolem functions to deal with such constants while retaining completeness. However, decidability and complexity issues stemming from the use of Skolem functions remain to be determined.) { Extensions to DLs outside of the FunDL family, such as the various members of the E L family and to more expressive logics such as Horn-SHIQ. { And integration with an interpolation-based relational query optimizer [ 16,31 ] via depth-limited tableau construction, which, for a su ciently large depth, leads to completeness as in [ 10 ].

An additional issue arises from the assumption of UNA. Indeed, this assumption is implicit in [ 21 ], where explicit equality among constant symbols is simply not considered, and also in most of the other approaches to OMQ via query rewriting, including the original approach introduced in [ 9 ]. In the case of Horn-DLF D, UNA is needed explicitly to accommodate keys and PFDs. We conjecture that some form of UNA is necessary, but whether restricted variants could su ce is unknown. 6.1

Related Work First order rewritability for Horn logics in the ALC=SHIQ family has been studied by others, e.g., see [ 4,6 ]. This earlier work has also developed algorithms for generating such rewritings e ciently for logics in the E L family [ 14 ]. Our approach seems to provide an alternative path to detecting rewritability and to generating rewritings. A feature of our approach is its link to interpolation-based query optimization [ 16,29 ]. The link to query optimization reveals that minimal sized rewritings are often not optimal for query execution. However, establishing limits on the size of rewriting [ 5 ] does provide a guide to what rewritings are reasonable to consider during query optimization.

The use of database constraints, or constraints implied by data mapping rules and database constraints, has been explored in several systems that implement variants of perfect rewriting [ 9 ], such as Ontop and MASTRO [ 2,8 ] and others. Our approach, however, seamlessly accommodates such constraints into the rewriting via interpolation and, again, could serve as an unifying approach between perfect rewriting-based approaches and the combined approach, even for DL-Lite based approaches to OMQ/OBDA.

Our approach cannot deal with rewritings to Datalog/and or Linear Datalog and with dichotomies on the NL-PTIME [ 21 ] and PTIME-coNP boundaries [ 24 ]: extensions of de nability/interpolation beyond rst order theories do not seem to exist at present and it is unclear whether similar approaches can be developed due to the close ties between interpolation and compactness of rst order theories.

Finally, note that Beth de nability and Craig Interpolation have been used

for other purposes, such as query reformulation under rst-order constraints [ 7,16,29,31 ]. That use, however, is orthogonal to the topic of this paper.

References

1. Franz Baader , Diego Calvanese, Deborah L. McGuinness , Daniele Nardi , and Peter F. Patel-Schneider . The Description Logic Handbook: Theory, Implementation, and Applications . Cambridge University Press, 2003 .

2. Timea Bagosi , Diego Calvanese, Josef Hardi, Sarah Komla-Ebri, Davide Lanti, Martin Rezk, Mariano Rodriguez-Muro, Mindaugas Slusnys , and Guohui Xiao . The ontop framework for ontology based data access . In The Semantic Web and Web Science - 8th Chinese Conference, CSWS 2014, Revised Selected Papers , pages 67 { 77 , 2014 .

3. Evert Willem Beth . On Padoa's method in the theory of de nition . Indagationes Mathematicae , 15 : 330 { 339 , 1953 .

4. Meghyn Bienvenu , Peter Hansen , Carsten Lutz, and Frank Wolter . First orderrewritability and containment of conjunctive queries in horn description logics . In Proceedings of the 29th International Workshop on Description Logics , Cape Town, South Africa, 2016 .

5. Meghyn Bienvenu , Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii , Vladislav Ryzhikov, and Michael Zakharyaschev . The complexity of ontologybased data access with OWL 2 QL and bounded treewidth queries . In Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017 , pages 201 { 216 , 2017 .

6. Meghyn Bienvenu , Balder ten Cate, Carsten Lutz, and Frank Wolter . Ontologybased data access: A study through disjunctive datalog, csp, and MMSNP . ACM Trans. Database Syst ., 39 ( 4 ): 33 :1{ 33 : 44 , 2014 .

7. Alexander Borgida , Jos de Bruijn, Enrico Franconi, Inanc Seylan, Umberto Straccia, David Toman, and Grant E. Weddell . On nding query rewritings under expressive constraints . In SEBD , pages 426 { 437 , 2010 .

8. Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, Antonella Poggi, Mariano Rodriguez-Muro, Riccardo Rosati, Marco Ruzzi, and Domenico Fabio Savo. The MASTRO system for ontology-based data access . Semantic Web , 2 ( 1 ): 43 { 53 , 2011 .

9. Diego Calvanese, Giuseppe de Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati . Tractable Reasoning and E cient Query Answering in Description Logics: The DL-Lite Family . J. of Automated Reasoning , 39 ( 3 ): 385 { 429 , 2007 .

10. Jan Chomicki . Depth-bounded bottom-up evaluation of logic program . J. Log. Program. , 25 ( 1 ):1{ 31 , 1995 .

11. Keith L. Clark . Negation as failure . In Logic and Data Bases, Symposium on Logic and Data Bases , Centre d'etudes et de recherches de Toulouse, France, 1977 , pages 293 { 322 , 1977 .

12. William Craig . Three uses of the Herbrand-Genzen theorem in relating model theory and proof theory . Journal of Symbolic Logic , 22 : 269 { 285 , 1957 .

13. Francesco M. Donini and Fabio Massacci . EXPTIME tableaux for ALC . Artif. Intell., 124 ( 1 ): 87 { 138 , 2000 .

14. Peter Hansen , Carsten Lutz, Inanc Seylan, and Frank Wolter . E cient query rewriting in the description logic EL and beyond . In Proceedings of the TwentyFourth International Joint Conference on Arti cial Intelligence , IJCAI 2015 , pages 3034 { 3040 , 2015 .

15. Ian Horrocks , Ulrike Sattler, Sergio Tessaris, and Stephan Tobies . How to decide query containment under constraints using a description logic . In Logic for Programming and Automated Reasoning , 7th International Conference, LPAR 2000, Reunion Island , France, November 11-12 , 2000 , Proceedings, pages 326 { 343 , 2000 .

16. Alexander K. Hudek , David Toman, and Grant E. Weddell . On enumerating query plans using analytic tableau . In Automated Reasoning with Analytic Tableaux and Related Methods - 24th International Conference, TABLEAUX 2015 , Wroclaw, Poland, September 21-24 , 2015 . Proceedings, pages 339 { 354 , 2015 .

17. Vitaliy L. Khizder , David Toman, and Grant Weddell . Reasoning about Duplicate Elimination with Description Logic . In DOOD , pages 1017 { 1032 , 2000 .

18. Stanislav Kikot , Roman Kontchakov, Vladimir V. Podolskii, and Michael Zakharyaschev. Long rewritings, short rewritings . In Proceedings of the 2012 International Workshop on Description Logics, DL-2012 , Rome, Italy, June 7-10, 2012 , 2012 .

19. Roman Kontchakov , Carsten Lutz, David Toman, Frank Wolter , and Michael Zakharyaschev . The combined approach to query answering in DL-Lite . In Proc. KR , pages 247 { 257 , 2010 .

20. Roman Kontchakov , Carsten Lutz, David Toman, Frank Wolter , and Michael Zakharyaschev . The combined approach to ontology-based data access . In Proc. Int. Joint Conf. on Arti cial Intelligence (IJCAI) , pages 2656 { 2661 , 2011 .

21. Carsten Lutz and Leif Sabellek . Ontology-mediated querying with the description logic EL: trichotomy and linear datalog rewritability . In Proceedings of the TwentySixth International Joint Conference on Arti cial Intelligence , IJCAI 2017 , pages 1181 { 1187 , 2017 .

22. Carsten Lutz , Inanc Seylan, David Toman, and Frank Wolter . The combined approach to OBDA: Taming role hierarchies using lters . In ISWC (1) , pages 314 { 330 , 2013 .

23. Carsten Lutz , David Toman, and Frank Wolter . Conjunctive query answering in the description logic EL using a relational database system . In Proc. Int. Joint Conf. on Arti cial Intelligence (IJCAI) , pages 2070 { 2075 , 2009 .

24. Carsten Lutz and Frank Wolter . Non-uniform data complexity of query answering in description logics . In Principles of Knowledge Representation and Reasoning: Proceedings of the Thirteenth International Conference, KR 2012 , 2012 .

25. Stephanie McIntyre , Alexander Borgida , David Toman, and Grant E. Weddell . On limited conjunctions and partial features in parameter-tractable feature logics . In The Thirty-Third AAAI Conference on Arti cial Intelligence , AAAI 2019 , pages 2995 { 3002 , 2019 .

26. Stephanie McIntyre , David Toman , and Grant E. Weddell. FunDL - A family of feature-based description logics, with applications in querying structured data sources . In Description Logic, Theory Combination , and All That - Essays Dedicated to Franz Baader on the Occasion of His 60th Birthday , pages 404 { 430 , 2019 .

27. Jason St. Jacques , David Toman, and Grant E. Weddell . Object-relational queries over CF DInc knowledge bases: OBDA for the SQL-Literate . In Proc. IJCAI , pages 1258 { 1264 , 2016 .

28. David Toman and Grant E. Weddell . On keys and functional dependencies as rst-class citizens in description logics . J. Aut. Reasoning , 40 ( 2-3 ): 117 { 132 , 2008 .

29. David Toman and Grant E. Weddell. Fundamentals of Physical Design and Query Compilation . Synthesis Lectures on Data Management . Morgan & Claypool Publishers, 2011 .

30. David Toman and Grant E. Weddell . Conjunctive Query Answering in CF Dnc: A PTIME Description Logic with Functional Constraints and Disjointness . In Australasian Conference on Arti cial Intelligence , pages 350 { 361 , 2013 .

31. David Toman and Grant E. Weddell. An interpolation-based compiler and optimizer for relational queries (system design report) . In IWIL@LPAR 2017 Workshop and LPAR-21 Short Presentations , Maun, Botswana, May 7- 12 , 2017 , 2017 .