In Ontology-based Data Management (OBDM), an abstraction of a source query q is a query over the ontology capturing the semantics of q in terms of the concepts and the relations available in the ontology. Since a perfect characterisation of a source query may not exist, the notions of best sound and complete approximations of an abstraction have been introduced and studied in the typical OBDM context, i.e., in the case where the ontology is expressed in DL-Lite, and source queries are expressed as unions of conjunctive queries (UCQs). Interestingly, if we restrict our attention to abstractions expressed as UCQs, even best approximations of abstractions are not guaranteed to exist. Thus, a natural question to ask is whether such limitations afect even larger classes of queries. In this paper, we answer this fundamental question for an essential class of queries, namely the class of monotone queries. We define a monotone query language based on disjunctive Datalog enriched with an epistemic operator, and show that its expressive power sufices for expressing the best approximations of monotone abstractions of UCQs.
In Ontology-based Data Management (OBDM) [
Recent papers [
The first investigations on abstraction appear in [
Thus, with the exception of [7], all the results on abstractions have been obtained under the assumptions that abstractions are expressed as UCQs over the ontology, and many of them originate from the observations that best approximations in the UCQ class are not guaranteed to exist. Thus, a natural issue to investigate is whether such limitations afect even larger classes of queries for expressing abstractions. The main goal of this paper is to address the following question: do approximations of perfect abstraction that are best in a fundamental class of queries, namely the class of monotone queries, always exist? Obviously, a related goal is to derive algorithms for computing approximations of abstractions that are best in the class of monotone queries, if they exist. Note that the class of monotone queries includes queries expressible in First-Order Logic and is therefore extremely important.
In this paper we answer positively to the above-mentioned fundamental question. More specifically, the contributions of the paper can be summarized as follows. We present a general framework for abstraction in OBDM, based on the definition of queries as functions from the logical models of OBDM systems to sets of tuples. The framework includes a new monotone query language, called Datalog∨K, based on disjunctive Datalog enriched with inequalities and an epistemic operator (Section 2). We consider a scenario where the OBDM specification is based on DL-LiteRDFS (i.e., the fragment of RDFS expressible in Description Logic), and show that, in the considered scenario, for any source UCQ , the best (sound or complete) approximations of the -abstraction of in the class of monotone queries always exists and can be expressed in Datalog∨K (Section 3). As a consequence, if the perfect abstraction exists and is in the class of monotone queries, then it can be expressed in Datalog∨K (Section 4).
This paper is an extended abstract of [10]. Hence, while we assume basic knowledge about databases [11] and Description Logics (DL) [12], for specific concepts and notations, we refer to the Preliminaries section of [10].
In what follows, we implicitly refer to an OBDM specification = ⟨, , ℳ⟩, and when we
denote a query by (resp., ) we mean that the query is a query for (resp., a source query),
i.e., is over the signature of the ontology (resp., the schema ). We follow [
We say that is a perfect -abstraction of if , = , for each -database consistent with .
As the condition for an ontology query to be a perfect abstraction of a source query is a strong one, it might be very well the case that a perfect abstraction of a source query does not exist. It is then reasonable to consider weaker notions, such as sound or complete approximations, of perfectness. forWeeacshayt-hdaatt abasise acocmonpsleistete(nretswp.itshoun.d) -abstraction of if ⊆ , (resp. , ⊆ ),
Obviously, we might be interested in complete or sound abstractions that approximate at best, at least in the context of a specific class of queries. If ℒ is a class of queries, we say that a query ∈ ℒ is an ℒ-minimally complete (resp., ℒ-maximally sound) -abstraction of if is a complete (resp., sound) -abstraction of and there is no query ′ ∈ ℒ such that ′ is a complete (resp., sound) -abstraction of and ′ ⊏ (resp., ⊏ ′).
We now introduce a new language, called Datalog∨K, for expressing queries over OBDM specifications. The language is based on disjunctive Datalog, and is used in this paper for expressing abstractions. The basic component of a Datalog∨K query is a rule. Assume two disjoint and countably infinite sets of predicates ℰ and , called extensional and intensional, respectively. A Datalog∨K rule has one of the following forms: • The typical form of disjunctive Datalog, i.e., (¯) → 1(¯1) ∨ . . . ∨ (¯) (1) where (¯) is a conjunction of relational atoms on the predicates of with ⃗ as variables, and for = 1, . . . , , (¯) is a single relational atom whose predicate is in such that ¯ ⊆ ¯, • A new form specified as follows
K(∃¯.(¯, ¯) ∧ (¯)) → 1(¯1) ∨ . . . ∨ (¯) (2) where is a conjunction of relational atoms over ℰ , (¯) is a conjunction of inequality atoms involving only variables from ¯ and for = 1, . . . , , = ∃¯ . (¯ , ¯ ), where is a conjunction of relational atoms on . When ¯ contains only variables ¯ occurring in (¯, ¯) , for = 1, . . . , , we say that the rule is safe.
An -ary Datalog∨K query over an OBDM specification is a finite set of Datalog∨K rules whose extensional predicates coincide with the alphabet of , and whose intensional predicates include a special -ary predicate . We say that is safe if all of its rules are safe. The semantics of is provided relative to an OBDM system. Given an OBDM system ⟨, ⟩, an interpretation for is a pair = ((⟨, ⟩), ), where is a first-order interpretation (with domain Const ) for the predicates in . As usual, we may also see as the set of facts {()¯ | ¯ ∈ }. We now define when satisfies a Datalog∨K rule.
• satisfies a rule of the form (1) if the first-order formula ∀¯. (¯) → 1(¯1) ∨ . . . ∨ (¯) is true in , • satisfies a rule of the form (2) if for all tuples ¯ of constants in Const , the fact that the ifrst-order formula ∃¯.(¯, ¯) ∧ ()¯ is satisfied by every model in mod (⟨, ⟩) implies that satisfies the first-order formula ∃¯ . (¯ , ¯ ), for some = 1, . . . , . Observe that, if the rule is unsafe, ¯ may contain constants of Const that do not occur in ¯.
An interpretation for is called a model of if all the rules of are satisfied by . Finally, we define the notion of answers to an -ary Datalog∨K query w.r.t. an OBDM system ⟨, ⟩, denoted by ,, as follows: {¯ ∈ Dom(, , ) | ¯ ∈ for each model ((⟨, ⟩), ) of }.
Let = ⟨, , ℳ⟩ be an OBDM specification such that = ∅, = {1/2, 2/1, 3/1} and ℳ = {m1, m2, m3, m4}, where: m1 : m2 : m3 : m4 :
E(1, 2) SN() ∃.E(, )
E(, ) ∀1, 2.1(1, 2) ∀.1(, ) ∀.2() ∀.3() → → → → The mapping ℳ of establishes how predicates in the schema relate to the ontology predicates E (which stands for edge) and SN (which stands for special node).
Let us now consider the following safe Datalog∨K query over . returns all the pairs (1, 2) of special nodes that are known to be distinct and such that there is a path from 1 to 2 passing only for nodes known to be special:
K(E(1, 2) ∧ SN(1) ∧ SN(2)) K(SN(1) ∧ SN(2) ∧ 1 ̸= 2) 1(1, ) ∧ 1(, 2) 1(1, 2) ∧ 2(1, 2) → → → → 1(1, 2) 2(1, 2) 1(1, 2)
Ans(1, 2) The following proposition shows that Datalog∨K is a monotone query language.
Every Datalog∨K query over is in M , for every OBDM specification .
The semantics should make it clear that K is the knowledge operator in the S5 epistemic logic: the formula K should be read as “ is known (i.e., logically implied) by the system” [13]. Therefore, when accessing the information modeled by ⟨, ⟩, a Datalog∨K query extracts what is known by the system, and this characteristic is crucial for not falling into undecidability resulting from using Datalog rules jointly with Description Logics (see [14, 15]), as stated in the following proposition. Let Σ be an OBDM system. Answering safe Datalog∨K queries w.r.t. Σ is decidable if and only if answering CQs w.r.t. Σ is decidable1.
Although our framework is general enough to consider any DL for expressing ontologies and any query language for expressing source queries, in the rest of this paper we will carry out our investigation in the following setting: () ontologies are expressed in DL-LiteRDFS, and () source queries are expressed as UCQs.
1With answering we implicitly refer to the associated recognition problem, i.e., check whether a tuple is in the answer to a query.
At this point, one may wonder whether Datalog∨K is the right language to express monotone abstractions in this setting. While a thorough analysis of the language is outside the scope of the present paper, the following proposition provides a positive answer to this question, at least from the computational point of view.
In our setting, () answering safe Datalog∨K queries is in coNP in data complexity, and () there exists an OBDM specification and a CQ such that, given an -database , answering the M-maximally sound -abstraction of is coNP-hard in data complexity.
To ease the presentation, from now on we assume that mappings and source queries do not mention constants. However, all our results can be straightforwardly adapted to the case where constants are allowed.
In this section we investigate the problem of the existence of M-minimally complete and Mmaximally sound abstractions, in the restricted setting specified at the end of the previous section. In particular, we start by showing that M-minimally complete abstractions of UCQ source queries always exist and can be expressed in Datalog∨K. Then, because of the lack of space, we will just mention the corresponding result on M-maximally sound abstractions.
Given a CQ = {¯ | ∃¯.(¯, ¯) }, the subroutine SaturateQ( ) computes a UCQ̸= in the following way: for each possible unifier on the variables in ¯ ∪ ¯ such that () ∈ ¯ for each ∈ ¯, SaturateQ( ) contains a query obtained from ( ) by adding the inequality atom 1 ̸= 2 for each pair of distinct variables 1, 2 occurring in ( ). For a UCQ , we denote by SaturateQ( ) the UCQ̸= obtained by applying SaturateQ() to each disjunct of . We write each CQ̸= generated by SaturateQ( ) as = {¯ | ∃¯.(¯, ¯) ∧ (¯, ¯) }, where (¯, ¯) and (¯, ¯) are the conjunctions of the relational atoms over and of the inequality atoms, respectively, occurring in the body of .
Moreover, for an OBDM specification = ⟨, , ℳ⟩ and a CQ̸= = {¯ | ∃¯.(¯, ¯) ∧ (¯, ¯) } over , we denote by the following Datalog∨K rule of form (2):
= K(∃¯.ℳ() ∧ (¯, ¯)) → Ans(¯) , where (i) ℳ() is computed by simply ignoring the inequality atoms and chasing the set of relational atoms occurring in the body of ; (ii) ¯ ⊆ ¯ is the subset of the existential variables of occurring in ℳ(); (iii) ¯ are the fresh variables introduced when computing ℳ(); and (iv) (¯, ¯) is the conjunction of the inequality atoms obtained from (¯, ¯) by removing all those atoms of the form ̸= and ̸= in which is an existential variable occurring in ¯ but not in ¯ (i.e., not in ℳ()) and is any other possible variable. Observe that the epistemic operator is exploited to bind the existential variables coming from . This is achieved by pushing the subset ¯ of the existential variables ¯ of occurring in ℳ() inside the K operator.
We are now ready to present the algorithm M-MinComplete for computing the M-minimally complete -abstractions. Given an OBDM specification = ⟨, , ℳ⟩ and a UCQ over such that SaturateQ( ) = 1 ∪ . . . ∪ , M-MinComplete(, ) outputs the Datalog∨K query = {1 , . . . , } over .
Consider the OBDM specification illustrated in Example 2 and the CQ = {() | ∃.1(, )} over . One can verify that M-MinComplete(, ) returns the following safe Datalog∨K query over asking for all those nodes such that either is connected to a node ′ known to be diferent from or is a special node with a self-loop:
Ans()
Ans()
K(E(, ) ∧ ̸= )
K(E(, ) ∧ SN())
→
→
Note that is a better complete approximation than the query {() | ∃.E(, )}, which is
the UCQ-minimally complete -abstraction of [
M-MinComplete(, ) terminates and returns the unique (up to -equivalence) M-minimally complete -abstraction of . Furthermore, we observe that the result of M-MinComplete(, ) is independent from the assertions occurring in the ontology of the OBDM specification . Similar results can be obtained for OBDM specifications based on more expressive Horn DL ontologies.
Before concluding this section, we observe that M-MinComplete(, ) may return unsafe Datalog∨K queries. Nevertheless, these queries enjoy nice computational properties in our setting.
Let be a Datalog∨K query with only rules of the form K(∃¯.(¯, ¯) ∧ (¯)) → Ans(¯). In our setting, (i) answering is in PTime in data complexity, and (ii) if is safe, then it is possible to compute a UCQ̸= over such that , = , for each -database .
As for best sound approximations of abstractions, it can be shown (cf. details in [10]) that, similarly to the case of best complete abstractions, an algorithm exists that, given a UCQ , terminates and computes the unique (up to -equivalence) M-maximally sound -abstraction of , expressed as a Datalog∨K query. Thus, we have the following:
Given a UCQ , both the unique (up to -equivalence) M-minimally complete and the M-maximally sound -abstraction of always exist and can be expressed as Datalog∨K queries. Consider the OBDM specification illustrated in Example 2. One can verify that the following set ℛ of safe Datalog∨K rules is the unique (up to -equivalence) M-maximally sound -abstraction of :
K(E(1, 2) ∧ 1 ̸= 2) → K(E(, )) → K(∃.E(, )) → K(SN()) → 1(1, 2) 3() ∨ 1(, ) 2() ∨ ∃.1(, ) ∨ 3() 1(, )
It follows from Theorem 3 that either the perfect abstraction of a source UCQ can be expressed in Datalog∨K, or it cannot be expressed as a monotone query (if it exists at all). We now present an algorithm that, given an OBDM specification and a source UCQ , returns the perfect -abstraction of , if and only if it exists and is in M. To this aim, we make use of Proposition 3, and refer to the defined in that proposition as the rewriting of w.r.t. .
Our algorithm, that we call M-Perfect, goes as follows. Given an OBDM specification = ⟨, , ℳ⟩ and a UCQ over as input: if (i) = M-MinComplete(, ) is safe and (ii) ⊑ ; then return ; otherwise, report “no perfect -abstraction of is in M”.
In Example 3, M-Perfect(, ) returns , which is the perfect -abstraction of .
We conclude this section by establishing termination and correctness of the M-Perfect algorithm.
M-Perfect(, ) terminates and returns the unique (up to -equivalence) perfect -abstraction of if and only if such an abstraction can be expressed in M.
We presented a thorough study of monotone abstractions of UCQs in OBDM systems. We proved that best approximations of such abstractions always exist and introduced a query language, Datalog∨K, that captures them. Directions for future work are many. In the context of monotone abstractions, we would like to investigate the case of more expressive ontology languages, e.g., DL-Liteℛ, as well as more expressive source query languages, e.g., unions of conjunctive queries with inequalities and disjunctive Datalog. Finally, the problem of checking whether given best approximations are expressible in simpler and more user friendly languages remains open.
This work has been partially supported by the ANR AI Chair INTENDED (ANR-19-CHIA-0014), by MIUR under the PRIN 2017 project “HOPE” (prot. 2017MMJJRE), and by the EU under the H2020-EU.2.1.1 project TAILOR, grant id. 952215. [7] G. Cima, M. Lenzerini, A. Poggi, Non-monotonic ontology-based abstractions of data services, in: Proceedings of the Seventeenth International Conference on Principles of Knowledge Representation and Reasoning (KR 2020), 2020, pp. 243–252. [8] G. Cima, M. Console, M. Lenzerini, A. Poggi, Abstraction in Data Integration, in: Proceedings of the Thirty-Sixth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2021), 2021, pp. 1–11. [9] G. Cima, Abstraction in Ontology-based Data Management, Ph.D. thesis, Sapienza University of Rome, 2020. [10] G. Cima, M. Console, M. Lenzerini, A. Poggi, Monotone abstractions in ontology-based data management, in: Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI 2022), 2022. [11] S. Abiteboul, R. Hull, V. Vianu, Foundations of Databases, Addison Wesley Publ. Co., 1995. [12] F. Baader, D. Calvanese, D. McGuinness, D. Nardi, P. F. Patel-Schneider (Eds.), The Description Logic Handbook: Theory, Implementation and Applications, Cambridge University Press, 2003. [13] H. J. Levesque, G. Lakemeyer, The Logic of Knowledge Bases, The MIT Press, 2001. [14] A. Y. Levy, M.-C. Rousset, Combining Horn rules and description logics in CARIN, Artificial
Intelligence 104 (1998) 165–209. [15] D. Calvanese, R. Rosati, Answering recursive queries under keys and foreign keys is undecidable, in: Proceedings of the Tenth International Workshop on Knowledge Representation meets Databases (KRDB 2003), volume 79 of CEUR Electronic Workshop Proceedings, 2003.