We consider the usual scenario of ontology mediated querying where queries are posed to a database whose knowledge is enriched by means of an ontology. A tuple (L; Q), where L is an ontology language and Q is a query language, is referred to as an OMQ language. One thoroughly explored fragment of FOL as a basis for ontology speci cation languages is that of tuple generating dependencies (TGDs). A tgd is a rule (logical implication) having as body and head conjunctions of atoms, where some variables occurring in head atoms might be existentially quanti ed (all other variables are universally quanti ed). As such, it potentially allows the derivation of atoms over fresh individuals (individuals not mentioned in the database). Answering (even atomic) queries with respect to sets of tgds is undecidable [7]. However, there has been lots of work on identifying decidable fragments [7, 1, 9]. A prominent such fragment is that of Guarded TGDs (GTGD) [7]: a tgd is guarded if all universally quanti ed variables occur as terms of some body atom, called guard. Many Description Logic languages like E LH or E LHI can be expressed using GTGDs. While query answering with respect to GTGDs is decidable, the combined complexity of the problem is high: exptime-complete for bounded arity schemas, and 2ExpTime-complete in general. At the same time, while the fragment is tractable w.r.t. data complexity [6], the coe cient of the polynomial depends on the size of the ontology, which might be relatively high. By xing the set of tgds, the combined complexity drops to NP for evaluating conjunctive queries (CQs), and to PTime for evaluating atomic queries and CQs of bounded treewdith [8] which is similar to the complexity of query evaluation over databases [15]. A natural question is when can OMQs from (GTGD, UCQ) be evaluated e ciently? The above question has been partially answered in [2]. There, the complexity of evaluating OMQs over bounded arity schemas is studied in a parameterized setting, with the parameter being the size of the OMQ. Under the assumption that FPT 6= W[1], it is shown that a recursively enumerable (r.e.) class of OMQs over bounded arity schemas can is xed parameter tracatable (fpt) i it has bounded semantic treewidth, i.e. there exists a k such that every OMQ from the class is equivalent to another OMQ from (GTGD, UCQ) whose UCQ has syntactic treewidth k [4]. The work generalizes previous results concerning
e ciency of evaluation of OMQs over bounded arity schemas based on the DL
languages E LH and E LHI from [
The characterization from [
The main research question we address in this paper is the following: when is it possible to e ciently evaluate OMQs from (GTGD, UCQ) in the case where there is no restriction concerning schema arity? We consider again a parameterized setting, where the parameter is the size of the OMQ. Given a r.e. class of OMQ Q from (GTGD, UCQ), we denote with p-OMQ(Q) the parameterized problem of evaluating OMQs from Q. As our rst main result shows, in this case another structural measure for OMQs/UCQs plays a central role: submodular width. Similarly to the de nition of semantic treewidth for OMQs, it is possible to de ne a notion of semantic submodular width of an OMQ. We obtain the following:
Main Result 1. Let Q be a r. e. class of OMQs from (GTGD, UCQ). Assuming the Exponential Time Hypothesis, p-OMQ(Q) is xed-parameter tractable i Q has bounded semantic submodular width.
To prove the result, we use the fact that every OMQ from (GTGD, UCQ)
can be rewritten into an OMQ from (GDLog, UCQ) [
Typically, in a database setting, the database induced by a CQ (or its core) can be seen as a canonical database which entails the query and on which to base further constructions. However, in the case of OMQs which pose restrictions on the database schema this is no longer possible: a CQ might contain symbols which are not allowed to occur in a database. In fact, this is a typical usage of ontologies: to enrich the database schema with new terminology. As such, we identify other representative databases for OMQs. Based on these new concepts, for OMQs from (GDLog, UCQ) it is possible to obtain an alternative characterization for fpt evaluation based on syntactic measures:
Main Result 2. For Q a r. e. class of OMQs from (GDLog, UCQ), let Qc and DQ be the classes of covers and characteristic databases for OMQs from Q, respectively. Under the Exponential Time Hypothesis, the following statements are equivalent:
3. DQ has bounded submodular width.
The hardness result for the above characterization exploits the seminal
result of Marx [
The problem of evaluating uniform CSPs can be seen as an alternative
presentation of the problem of evaluating a r.e. class of Boolean CQs over databases.
In fact, Grohe's characterization for fpt evaluation of r. e. classes of CQs in the
bounded arity case has been achieved via a uniform CSP detour [
Main Result 3. For Q an OMQ from (GDLog; UCQ), there exists an fptreduction from p-CSP(DQ; ) to p-OMQ(fQg).
The reduction is important also as a stand-alone result as it can be used as
a black-box tool to port results from the uniform CSP/database realm to the
OMQ one. To further showcase this, we revisit the problem of evaluating r.e.
classes of OMQs over bounded arity schemas, previously addresed in [
So far we have only considered Boolean OMQs, as the corresponding results
for CQ evaluation in the unbounded arity case have also only been established
in the Boolean case. As future work, we plan to extend our work to the
nonBoolean case. Many results from the database world concerning e ciency of
performing tasks like counting [