Separability and Its Approximations in Ontology-based Data Management

1.Introduction

The separability problem deals with finding an intensional representation of two datasets, i.e., sets of data items, interpreted as positive and negative examples. In this problem, one is given two sets of data items, one with positive and the other with negative examples, and is asked to provide a query so that the evaluation of such a query over the database contains all the data items in the set of positive examples, and none of the data items in the set of negative examples. We say that a solution to this problem is a query that separates the given datasets. A special case of this problem arises when only one set of positive examples is given as input, and one is interested in finding a query whose evaluation over the database coincides with the data items in such a set. In this paper, we refer to the latter special case with the term characterizability, and we say that a solution to this problem is a query that characterizes the given dataset.

The separability problem has initially been studied for relational databases and is known in the community as the query-by-example problem.11 Over the years, researchers have found several interesting applications of the separability problem, spanning from simplifying query formulation by non-experts, to debugging facilities for data engineers. Indeed, the problem has been studied as a useful tool for data exploration, concept learning, data analysis, usability, data security and more [51,54]. Moreover, as already observed in [37], the problem is studied in two special cases in which the input datasets are constituted by only one single tuple. In separability, this special case is studied for entity comparison in RDF graphs, where the goal is to find a meaningful description that separates one entity from another. Similarly, in characterizability, this special case is studied for generating referring expressions (GRE), where one is interested in describing a single data item by a logical expression that allows to separate it from all other data items. With the rise of Machine Learning (ML), we argue that this topic acquires primary importance for providing meaningful explanations to any typical supervised black-box model used for classification tasks. When applied to classification, the ultimate goal of supervised learning is to construct models that are able to predict the target output (i.e., the class) of the proposed inputs. To achieve this, the learning algorithm is provided with some training examples that demonstrate the intended relation of input and output values. Then, the learned model is supposed to be able to correctly classify instances that have not been shown during training. A crucial problem for wise and safe adoption of ML-based black-box models is that, especially in high-risk domains such as healthcare and finance, it is often very hard to understand the rationale behind a classification made by these models. This may lead to discriminatory biases in the classification that were not intended and, more surprisingly, of which the designers were unaware of.

In this paper, we assume that the classification task is performed in an organization that adopts an Ontology-based Data Management (OBDM)22 approach [46,48]. OBDM is a paradigm for accessing data using a conceptual representation of the domain of interest expressed as an ontology. The OBDM paradigm relies on a three-level architecture, consisting of the data layer, the ontology, and the mapping between the two. Consequently, an OBDM specification is a triple J=⟨O,S,M⟩ which, together with an S-database D, form a so-called OBDM system Σ=⟨J,D⟩. We are going to tackle the separability problem by leveraging the notion of evaluation of a query with respect to an OBDM system, in turn based on the notion of certain answers to a query over an OBDM system. Intuitively, given an OBDM system Σ=⟨J,D⟩ and two D-datasets λ+ and λ−, our goal is to derive a query expression over O that separates λ+ and λ− in Σ (called here proper separation).

An important contribution of our work is to provide approximated results for all the cases in which it is not possible to provide a separating query. We argue that, in these cases, reasonable and useful ontological characterizations can still be provided. We propose to resort to suitable approximations of the proper separating query, by introducing the notions of sound and complete separating queries. The former is a query whose certain answers have empty intersection with the D-dataset λ−, whereas the certain answers of the latter form a superset of the D-dataset λ+. Obviously, we are interested in computing the best approximated separating queries, which we call maximally sound and minimally complete separations, respectively. A maximally sound (resp., minimally complete) separation is a sound (resp., complete) separation such that no other sound (resp., complete) separation exists that better approximates the input datasets. Moreover, we cover the special cases in which the input datasets are constituted by only one single tuple for all our results and refer to them as the single tuple variants of the problems we deal with.

In this context, the training set used in the classification task, which is a collection of data items that are labeled as positive and negative examples, is seen as two sets of tuples in the database schema. The query derived by solving the separability problem results into an intensional definition of such training set, and are considered as an explanation of the intensional properties of the training set. The same principle can also be applied to a set of tuples that has not been seen during the training of the model. In this scenario, one can consider the black-box model as an oracle that assigns a class to all given tuples. Then, the query derived by solving the separability problem in this new context, is considered as an explanation of the intrinsic behaviour of the model. Traditionally, there are two different types of explanations: global and local. We refer to the former for explanations of the general behaviour of the model, and to the latter for explanations of the output of the model with respect to a specific object. The present work poses the foundational basis for providing both kind of explanations. Indeed, it deals with global explanations when the separating query is searched with respect to positive and negative examples containing and arbitrary number of tuples. It deals with local explanations when the sets of positive and negative examples for which one searches for a separating query contain only one single tuple.

Our procedure fits into the definition of post-hoc explanations of black-box models, i.e. a set of techniques aimed at approximating the behaviour of a black-box model with a surrogate interpretable model. We are now going to describe how in our context the role of the surrogate model is played by the query resulting from the solution of the separability problem. Suppose an organization that adopts the OBDM paradigm wants to train a model for predicting which candidates in a selection process are the most likely to perform well in a certain job. For training the model, the organization is given the curricula of current employees with a feedback on their performances that makes it possible to divide the training set in two different classes: the good and bad performers. For the sake of simplicity, suppose John, Mary, and Jane, who studied Biology, Medicine, and Math respectively, perform well. Suppose also that Matt, Angeline, and Jess, who studied Music, Linguistics, and Fashion respectively, perform badly. The ML-based black-box model is trained with this dataset and it is optimised to reach the highest possible accuracy. Now suppose some candidates apply for the job and are evaluated by the model. The latter states that Lucy, Mara, and George, who studied Math, Chemistry, and Physics respectively, have high probability to perform well in doing the job. At the same time, the model states that Lucas, and Paul, who studied Art, and Classics are believed to perform badly. The organization now wonders why the black-box model divided the candidates in this way. By instantiating a separability problem with the two sets of positive and negative candidates, the organization finds out that, no matter how sophisticated the internal details of the black-box model are, the resulting classification is so that all positive candidates are answers to the query “return all the candidates with a scientific background”, and none of the negative candidates are. This separating query provides an intuitive explanation of the actual behaviour of the model. Of course, there are in general many valid separating queries for a given instance of a separability problem, as it is possible that in many cases there is no valid separating query at all.

Contributions of the paper The contribution provided by this paper can be summarized as follows:

This paper is an extended version of our CIKM’21 conference paper [22]. We point out that the conference paper focused only on the characterizability reasoning task, whereas here we illustrate a formal framework and study the related computational problems both for separability and characterizability. Furthermore, in this extended version we provide all the full proofs that were only sketched in [22]. Finally, we observe that the CHAR(DL-LiteR,GLAV,UCQ) decision problem is incorrectly claimed to be CONEXPTIME-complete in the conference version of this paper. In this extended version, we fix this error and show that this decision problem is actually Π3p-complete.

To the best of our knowledge, the present work is the first to introduce separability and characterizability in the OBDM context. In particular, while separability and characterizability have been studied in various ontology-enriched query answering settings, this is the first to take into account all the layers stack of the OBDM paradigm, thus including also the mapping layer, and also propose and study natural relaxations of the separability and characterizability notions. Nevertheless, we remark that both in the Computation and in the Existence problems for separability and characterizability we mainly focus only on UCQ as a query language, while other works on the subject also investigate the typically more challenging scenario of CQ as a query language (see, e.g., [7,30,34,64]).

Finally, we mention that, since DL-LiteR is insensitive to the adoption of the unique name assumption (UNA) for UCQ answering [5], all our results hold both with and without the UNA.

Outline of the paper The paper is organized as follows. After the discussion of related works in Section 2, Section 3 introduces the relevant background for our study and Section 4 illustrates a formal framework for separation in OBDM. Then, Sections 5, 6, and 7 present the results on the three computational problems Verification, Computation, and Existence, respectively. We deal first with the Computation problem and then with the Existence problem because the solutions we will provide about the Computation problem will help us to solve some tasks about the Existence problem. Finally, Section 8 concludes the paper with a perspective on future work.

2.Related work

Query definability and query-by-example have long been studied for classical databases, starting from [70] up to many recent studies [3,7,41,52,64,65,68]. We have laid the foundations for analysing the complexity of our decision problems from the results in [3,7]. We found the work in [65] inspirational since they dealt with the problem of deriving a metric for establishing how close is a non proper separating query to the optimal solution. We found the survey in [52] important for the whole research problem as they present a well described motivating example and they outline the main open problems of this topic.

Our work has also been inspired by the notion of Abstraction [19,20,23]. Although the goal is still to derive a query expression over the ontology, in that work the input is a query over the data layer of the OBDM architecture, whereas in query definability (resp. in query-by-example) the input is a set of tuples (or two sets of tuples). It follows that the two tasks are completely different and require different technical solutions. We postpone a detailed comparison between Abstraction and the separability notion investigated in this paper in Section 4.1 (when we will have all the technical tools in hand to provide an in-depth comparison).

The works that are closer to ours are the ones in [4,34,55]. In [4] the authors study the existence, and verification problems both for query definability and for query-by-example, and computation problem for the query definability case. In their work, the ontology is expressed as an RDF graph and they consider several fragments of SPARQL as the query language to be used for the separation of the examples. Differently from the present work, they do not aim at finding the best approximated separation. We share with [55] the expressive power of the language used for the ontology (DL-Lite), and for the separation query the input examples (UCQs). However, the work in [55] does not deal with the cases in which proper separations for the input examples do not exist, and it is based on a slightly different framework from ours, i.e. since in that work they study the problems in the context of ontology-mediated queries, they do not have the mapping layer that instead is part of our more general OBDM paradigm.

The work in [34], studies the query-by-example problem for expressive horn description logic ontologies, namely Horn-ALCI. Apart from the clear difference in the expressive power of the ontologies, their work does not consider the case of approximated separations of the input examples, and it does not consider the mapping layer.

This work has also been inspired by [11,31,38,44]. All these papers’ goal is to learn a concept expression that best captures a given set of examples (or two set of positive and negative examples for query-by-example). We differ from these works because our goal is to derive a full-blown query that separates the input examples.

The problem of checking whether there exists a formula separating positive and negative examples in the presence of an ontology has recently been studied in [37,40]. Other than verifying that the ontology entails the searched formula for all positive examples, the authors conducted an in-depth analysis of the so-called separability problem accounting for both weak separability, i.e. the one we study in this paper, and strong separability, i.e. checking whether the negation of the separating formula is entailed by the KB. They also consider the case of enriching the separating formula by adding helper symbols that are not originally present in the ontology, and study the complexity of the decision problems for a wide range of languages both for expressing the ontology and the separating formula. In this paper, we are interested in studying the weak separability problem in the context of the OBDM by also considering the cases in which the separating formula does not exist and one wants to search for sound and complete approximations of it.

Another important line of research related to the present work is the one regarding post-hoc explanations of opaque machine learning models. As also highlighted by other works [25,26,49,60], the query-by-example problem can easily be adapted for explaining the output of a black-box machine learning classification model. For example, consider the case of a binary classifier labelling a set of examples in two classes 1 and 0. In this scenario, the solution of the query-by-example problem is considered as a surrogate of the machine learning model, so that the examples labelled by class 1 are the answers of the reverse engineered query, while none of the examples labelled by class 0 are. Therefore the query acts as an explanation because it provides a more human understandable way, especially in our framework in which the query is based on the knowledge of the ontology, for classifying the given examples in the two different classes. Although relevant for our work, we differ from all the above cited papers. In [60], they map the inputs of the machine learning classifier to the ontology and then uses a concept learning tool to find a class expression over the ontology that best describes the positive example. In [25], for explaining the behaviour of a black-box classifier, they build another black-box classifier (a neural network) and then project the output of this latter model onto a so-called rule space, where each coordinate represents the activation of a rule that is described in First Order Logic. In [26] they present the TREPAN algorithm, i.e. a way for building a decision tree in which the nodes are linked to an ontology, that is used as a means for explaining the input positive and negative examples. We consider the work in [49] to be relevant for our work, even though is rather preliminary and does not specify many important details such as the expressive power of the language of the ontology, and the language of the query they search for. The biggest differences with the present work are the fact that they do not consider the mapping layer between the ontology and the data, and that they do not focus on the concepts of maximally-sound and minimally-complete solutions, in cases where a perfect solution does not exist. On the contrary, they define a best approximated query as the one minimising the jaccard distance between the answers of the query and the set of positive examples in the input.

Inductive Logic Programming (ILP) [43] has long been considered related to the query definability and query-by-example tasks. We also considered it inspiring for our work, but we soon acknowledged that the expressive power of the languages used for representing the knowledge base are incomparable, and that in ILP they are interested in searching for explanations of a set of logical facts rather than a set of tuples.

The Active Learning task initially introduced by [2] has been studied as a possible framework for learning queries from examples in relational databases [64] and in the presence of DL-Lite ontologies [30]. Moreover, instances of the framework in [2] can be found in [42] and in [57]. In particular, the goal of [42] is to learn an ontology that is equivalent to a target ontology, while the goal of [57] is to learn an ontology that is query inseparable with respect to a target ontology T and a query language Q, i.e. given a set of ground atoms (ABox) A, the learned ontology H must be such that ⟨H,A⟩⊧q if and only if ⟨T,A⟩⊧q, for every q∈Q.

Finally, query inseparability has been studied even outside the learning task. For example, [9] studies query inseparability for (fragments of) Horn-ALC as ontology language and CQ as a query language, whereas [10] studies query inseparability for both the ontology languages ALC and EL and for (fragments of) UCQ as a query language.

3.Preliminaries

We recall some notions about relational databases [1], Description Logics (DLs) [6], and Ontology-based Data Management (OBDM) [47]. We define ΓS, ΓO, Const, and V to be the pairwise disjoint, countably infinite sets of symbols for database predicates, ontology predicates, constants, and variables, respectively. We further assume that ΓO is partitioned into the disjoint sets ΓA and ΓP for atomic concepts and atomic roles, respectively.

Databases, datasets, and queries A relational database schema (or simply schema) S is a finite subset of ΓS. Given a schema S, an S-database D is a finite set of facts (a.k.a. ground atoms) of the form s(c→), where s is an n-ary predicate in S, and c→=(c1,…,cn) is an n-tuple of constants from Const. We denote by dom(D) the finite subset of Const of those constants occurring in D. Given a schema S and an S-database D, a D-dataset λ of arity n is simply a finite set of n-tuples c→ of constants occurring in D, i.e., λ⊆dom(D)n.

A query qS over a schema S is an expression in a certain query language Q using the predicate symbols of S and arguments of predicates are variables from V, i.e., we disallow constants to occur in queries. Each query has an associated arity. The evaluation of a query qS of arity n over an S-database D is a set of answers qSD, each answer being an n-tuple of constants occurring in dom(D), i.e., qSD⊆dom(D)n. A query qS of arity 0 over a schema S is called a boolean query, and we denote by qSD={⟨⟩} (resp., qSD=∅) the fact that D⊧qS (resp., D⊭qS).

Following the terminology of [7,63], we say that a query qS over a schema S explains two D-datasets λ+ and λ− (resp., defines a D-dataset λ+) inside an S-database D if λ+⊆qSD and qSD∩λ−=∅ (resp., qSD=λ+). We also say that λ+ and λ− are Q-explainable (resp., λ+ is Q-definable) inside D, for a query language Q, if there exists a query qS∈Q that explains λ+ and λ− (resp., defines λ+) inside D.

We are particularly interested in conjunctive queries and unions thereof. A conjunctive query (CQ) over a schema S is an expression of the form qS={x→∣∃y→.ϕ(x→,y→)} such that (i) x→=(x1,…,xn), called the target list of qS, is an n-tuple of distinguished variables from V, where n is the arity of qS (ii) y→=(y1,…,ym) is an m-tuple of existential variables from V; and (iii) ϕ(x→,y→), called the body of qS, is a finite conjunction of atoms of the form s(v1,…,vp), where s is an p-ary predicate in S and vi is either a distinguished or an existential variable, i.e., vi∈x→∪y→ for each i∈[1,p]. A union of conjunctive queries (UCQ) qS over a schema S is a finite set {x1→∣∃y1→.ϕ1(x1→,y1→)}∪⋯∪{xm→∣∃ym→.ϕm(xm→,ym→)} of CQs over S with same arity, called its disjuncts.

For a conjunction of atoms ϕ(x→,y→), we denote by set(ϕ) the set of all the atoms occurring in ϕ. For a set of atoms C and a tuple c→=(c1,…,cn) of constants, we denote by query(C,c→) the CQ {x→∣∃y→.ϕ(x→,y→)}, where (i) ϕ(x→,y→) is the conjunction of all the atoms occurring in the set of atoms C′, where C′ is obtained from C by replacing everywhere each constant ci occurring in c→ with a fresh variable xci and each constant c not occurring in c→ with a fresh variable yc, (ii) x→=(xc1,…,xcn), and (iii) y→ is the tuple of all variables occurring in C′ that do not occur in x→.

Given a set of atoms C, we denote by dom(C) the set of all constants and variables occurring in C. Observe that dom(C)⊆Const∪V. Let C1 and C2 be two sets of atoms. We say that a function h:dom(C1)→dom(C2) is a homomorphism from C1 to C2 if h(C1)⊆C2, where h(C1) is the image of C1 under h, i.e., h(C1)={h(α)∣α∈C1} with h(s(t1,…,tn))=s(h(t1),…,h(tn)) for each atom α=s(t1,…,tn). For two sets of atoms C1 and C2 and two tuples of terms t1→ and t2→, we write (C1,t1→)→(C2,t2→) if there is a function h from dom(C1)∪t1→ to dom(C2)∪t2→ such that (i) h is a homomorphism from C1 to C2, and (ii) h(t1→)=t2→ (where, for a tuple of terms t→=(t1,…,tn), h(t→)=(h(t1),…,h(tn))), (C1,t1→)↛(C2,t2→) otherwise.

We define the semantics of (U)CQs in terms of homomorphisms. For an S-database D and a CQ qS={x→∣∃y→.ϕ(x→,y→)} over S of arity n, we let qSD to be the set of n-tuples c→ of constants occurring in D for which (set(ϕ),x→)→(D,c→). Furthermore, for an S-database D and a UCQ qS=q1∪⋯∪qm over S, we let qSD=q1D∪⋯∪qmD.

Syntax and semantics of DL-LiteR In this paper, a DL ontology (or simply ontology) O is a TBox (“Terminological Box”) expressed in a specific DL, that is, a finite set of assertions stating general properties of atomic concepts and roles built according to the syntax of the specific DL, which represents the intensional knowledge of a modeled domain. The alphabet of an ontology O is the finite subset of ΓO of atomic concepts and atomic roles mentioned in the assertions of O, and we assume that every ontology O comprises the special bottom concept ⊥ in its alphabet. In this paper, whenever we speak of a query qO over an ontology O, we implicitly mean a query in a certain query language Q that uses the atomic concepts and the atomic roles in the alphabet of O as predicate symbols.

The semantics of DL ontologies is specified through the notion of first-order interpretations: an interpretation I is a pair I=⟨ΔI,·I⟩, where the interpretation domain ΔI is a non-empty, possibly infinite set of objects, and the interpretation function ·I assigns to each constant c∈Const an object cI∈ΔI, to each atomic concept A∈ΓA a subset AI of ΔI (with the requirement ⊥I=∅), and to each atomic role P∈ΓP a subset PI of ΔI×ΔI. We say that an interpretation I satisfies an ontology O, denoted by I⊧O, if I satisfies every assertion in O. When convenient, with a slight abuse of notation, we treat an interpretation I as the (potentially infinite) set of facts of the form A(o) and P(o1,o2) that are true in I, i.e., that are such that o∈AI and (o1,o2)∈PI.

We are particularly interested in DL ontologies expressed in DL-LiteR, the member of the DL-Lite family [15] that underpins OWL 2 QL, i.e., the OWL 2 profile especially designed for efficient query answering [53]. A DL-LiteR ontology O is a finite set of assertions of the form:

For the constructs of DL-LiteR, the interpretation function ·I of an interpretation I=⟨ΔI,·I⟩ extends to basic concepts and basic roles as follows: (∃P)I={o∣∃o′.(o,o′)∈PI} and (P−)I={(o,o′)∣(o′,o)∈PI}. Finally, an interpretation I satisfies a concept inclusion assertion B1⊑B2 (respectively, role inclusion assertion R1⊑R2) if B1I⊆B2I (respectively, R1I⊆R2I), and it satisfies a concept disjointness assertion B1⊑¬B2 (respectively, role disjointness assertion R1⊑¬R2) if B1I∩B2I=∅ (respectively, R1I∩R2I=∅).

Syntax and semantics of ontology-based data management According to [47,58], an Ontology-based Data Management (OBDM) specification is a triple J=⟨O,S,M⟩, where O is a DL ontology, S is a relational database schema, also called source schema, and M is a mapping, i.e., a finite set of assertions relating the source schema S to the ontology O. An OBDM system is a pair Σ=⟨J,D⟩, where J=⟨O,S,M⟩ is an OBDM specification and D is an S-database. For readability purposes, with a slight abuse of notation, we sometimes denote an OBDM system as a quadruple Σ=⟨O,S,M,D⟩, where ⟨O,S,M⟩ is an OBDM specification and D is an S-database.

In this paper, each assertion in the mapping component of an OBDM system is a Global-And-Local-As-View (GLAV) assertion [27], that is, an assertion of the form qS→qO, where qS and qO are CQs over S and over O, respectively, with the same target list x→=(x1,…,xn). Special cases of GLAV assertions highly considered in the data integration literature are Global-As-View (GAV) and Local-As-View (LAV) assertions [45]: in a GAV (resp., LAV) assertion, qO (resp., qS) is simply an atom without existential variables. Finally, a GLAV (resp., GAV, LAV, GAV∩LAV) mapping M consists in a finite set of GLAV (resp., GAV, LAV, both GAV and LAV) assertions.

Given a GLAV mapping M relating a source schema S to an ontology O, an interpretation I, and an S-database D, we denote by ⟨I,D⟩⊧M the fact that (c1,…,cn)∈qSD implies (c1I,…,cnI)∈qOI for each possible mapping assertion qS→qO in M and for each possible tuple (c1,…,cn) of constants occurring in D. Here, qOI denotes the evaluation of qO over the interpretation I seen as a (potentially infinite) set of facts.

As customary in OBDM, we define the semantics of OBDM systems Σ=⟨O,S,M,D⟩ by specifying which are the first-order models of the OBDM specification ⟨O,S,M⟩ relative to the S-database D. Specifically, we say that an interpretation I is a model of an OBDM system Σ=⟨O,S,M,D⟩ if (i) I⊧O, and (ii) ⟨I,D⟩⊧M. Finally, we say that an OBDM system Σ is consistent if it has at least one model, inconsistent otherwise.

For an OBDM system Σ=⟨J,D⟩, with J=⟨O,S,M⟩, and a query qO over O, we denote by certqO,JD the set of certain answers of qO w.r.t. Σ, i.e., the set of tuples of constants (c1,…,cn) occurring in D such that (c1I,…,cnI)∈qOI for each model I of Σ. If Σ is inconsistent, then the set of certain answers of any query qO over O w.r.t. Σ is simply the set of all possible tuples of constants occurring in D whose arity is the one of the query. Finally, we say that two queries q1 and q2 are equivalent w.r.t. an OBDM system Σ=⟨J,D⟩ if certq1,JD=certq2,JD.

Query rewriting Given a UCQ qO over a DL-LiteR ontology O, we denote by PerfectRef(O,qO) the UCQ computed by executing the algorithm PerfectRef [15] on O and qO (slightly extended to deal also with the bottom concept ⊥). In a nutshell, the PerfectRef algorithm uses the concept/role inclusions of the input DL-LiteR ontology O as rewriting rules applied to the input UCQ qO. In this way, it compiles into the query qO all the knowledge provided by O that is relevant to answering the query. PerfectRef applies repeatedly the following two steps until a fixpoint is reached: step (i) uses concept/role inclusions as rewriting rules to rewrite query atoms one by one, each time producing a new CQ to be added to the final output; step (ii) unifies the query atoms to enable further executions of step (i). For additional details, we refer the reader to [15].

Let J=⟨O,S,M⟩ be an OBDM specification where O=∅, i.e., O has no assertions, and M is a GLAV mapping. From results of [17,29], it is well-known that, given a UCQ qO over O, by splitting the GLAV mapping M into a GAV mapping followed by a LAV mapping over an intermediate alphabet, it is always possible to compute a UCQ over S, denoted by MapRef(M,qO), such that MapRef(M,qO)D=certqO,JD for each S-database D.

Now, let J=⟨O,S,M⟩ be an OBDM specification where O is a DL-LiteR ontology and M is a GLAV mapping. Given a UCQ qO over O, in what follows, we denote by rewqO,J the following UCQ over S: rewqO,J:=MapRef(M,PerfectRef(O,qO)). By combining the above observation regarding MapRef with the correctness of the PerfectRef algorithm [15] and the fact that DL-LiteR is insensitive to the adoption of the UNA for UCQ answering [5], we derive that certqO,JD=rewqO,JD holds for each UCQ qO over O and for each S-database D such that ⟨J,D⟩ is consistent. Furthermore, by combining the above observation regarding MapRef with results of [58], we derive that, given an S-database D, the OBDM system ⟨J,D⟩ is inconsistent if and only if rewVO,JD={⟨⟩}. Here, VO is the O-violation query, i.e., the boolean UCQ over O constituted by the disjunct {()∣∃y.⊥(y)} and a disjunct of the form {()∣∃y.A1(y)∧A2(y)} (respectively, {()∣∃y1,y2.A1(y1)∧R(y1,y2)}, {()∣∃y1,y2,y3.R1(y1,y2)∧R2(y1,y3)}, and {()∣∃y1,y2.R1(y1,y2)∧R2(y1,y2)}) for each disjointness assertion A1⊑¬A2 (respectively, A1⊑¬∃R or ∃R⊑¬A1, ∃R1⊑¬∃R2, and R1⊑¬R2) occurring in O, where an atom of the form R(y,y′) stands for either P(y,y′) if R denotes an atomic role P, or P(y′,y) if R denotes the inverse of an atomic role, i.e., R=P−.

Canonical structure Given an S-database D and a GLAV mapping M relating a source schema S to an ontology O, the chase [13] of D with respect to M, denoted by M(D), is the set of atoms computed as follows: (i) M(D) is initially set to the empty set of atoms; then (ii) for every GLAV assertion {x→∣∃y→.ϕS(x→,y→)}→{x→∣∃z→.φO(x→,z→)} in M and for every tuple c→ of constants occurring in D such that (set(ϕS),x→)→(D,c→), we add to M(D) the image of the set of atoms set(φO) under h′, that is, we set M(D):=M(D)∪h′(φO(x→,z→)), where h′ extends h by assigning to each variable z occurring in z→ a different fresh variable of V still not present in dom(M(D)). Observe that M(D) is guaranteed to be finite and can be always computed in exponential time.

We conclude this section with the following observation used for the technical development of the next sections. Let Σ=⟨O,S,M,D⟩ be an OBDM system where O is a DL-LiteR ontology and M is a GLAV mapping. The canonical structure of O with respect to M and D, denoted by COM(D), is the (potentially infinite) set of atoms obtained by first computing M(D) as described before, and then by chasing M(D) with respect to the inclusion assertions of O as described in [15, Definition 5] but using the alphabet V of variables whenever a new element is needed in the chase. Observe that this latter is a fair deterministic strategy, i.e., it is such that if at some point an assertion is applicable, then it will be eventually applied. By combining [28, Proposition 4.2] with [15, Theorem 29], it is well-known that, for a UCQ qO={x1→∣∃y1→.ϕO1(x1→,y1→)}∪⋯∪{xp→∣∃yp→.ϕOp(xp→,yp→)} over O and a tuple c→ of constants occurring in D, if Σ=⟨J,D⟩ is consistent, then the following holds: c→∈certqO,JD if and only if (set(ϕOi),xi→)→(COM(D),c→) for some i∈[1,p].

4.Formal framework

In what follows, we implicitly use Σ=⟨J,D⟩ to denote an OBDM system, where J=⟨O,S,M⟩ is an OBDM specification and D is an S-database. Intuitively, given two sets λ+ and λ− of tuples of constants occurring in D (i.e., λ+ and λ− are D-datasets) of positive and negative examples, respectively, we aim at finding a query qO over the ontology O in a certain target query language Q that logically separates λ+ and λ− w.r.t. Σ. Since the evaluation of queries in OBDM systems is based on certain answers, we are naturally led to the following definition.

The next example illustrates the above definition.

Clearly, the more expressive the target query language Q, the more likely it is possible to distinguish (w.r.t. the OBDM system) the properties between the tuples in λ+ and λ− by means of the operators in Q, and therefore the more likely the proper separation in Q exists. Unfortunately, the next example shows that, even in trivial cases and without any restriction on the target query language Q, proper separations are not guaranteed to exist.

Notice the importance of the role played by the mapping M in order to reach this conclusion. Indeed, if we replace m2 with {(x)∣s2(x)}→{(x)∣B(x)}, then a proper Σ-separation of λ+ and λ− in UCQ would simply be the CQ {(x)∣A(x)} over the ontology O.

Borrowing similar ideas from [23], to remedy situations where proper separations do not exist, we now introduce approximations of proper separations in terms of completeness and soundness. More specifically, a complete separation is a query that captures all the positive examples in its set of certain answers w.r.t. the OBDM system (i.e., satisfies condition (i) of Definition 1), whereas a sound separation is a query that contains none of the negative examples in its set certain answers w.r.t. the OBDM system (i.e., satisfies condition (ii) of Definition 1).

We observe that the condition for being a complete (resp., sound) separation does not involve λ− (resp., λ+).

As the above example manifests, there may be several complete and sound separations. In those cases, the interest is unquestionably in those queries that approximate at best the proper one, at least relative to a target query language Q. Informally, a Q-minimally complete separation is a complete separation in Q containing a minimal (w.r.t. set containment) possible set of negative examples in its set of certain answers, whereas a Q-maximally sound separation is a sound separation in Q capturing a maximal (w.r.t. set containment) possible set of positive examples in its set of certain answers.

By definition, it is immediate to verify that a Σ-proper separation of λ+ and λ− in a query language Q is both a Q-minimally complete Σ-separation of λ+ and λ− and a Q-maximally sound Σ-separation of λ+ and λ−.

We point out that all the above definitions are a generalization of the definitions illustrated in [22] which deal only with datasets of positive examples, rather than datasets of both positive and negative examples as done here. More specifically, in [22], as well as in all the works addressing the separability task, when only a D-dataset λ+ of positive examples is provided, to λ− it is implicitly associated the D-dataset λ−=dom(D)n∖λ+, where n is the arity of the tuples in λ+. With this remark in mind, we can now specialize the above definitions for the only dataset of positive examples case and report the definitions given in [22].

In other words, given an OBDM system Σ=⟨J,D⟩ with J=⟨O,S,M⟩, a D-dataset λ+ of arity n, and a query qO∈Q, we have that qO is a proper in Q (resp., complete in Q, sound in Q, Q-minimally complete, Q-maximally sound) Σ-characterization of λ+ if and only if qO is a proper in Q (resp., complete in Q, sound in Q, Q-minimally complete, Q-maximally sound) Σ-separation of λ+ and λ−, where λ−=dom(D)n∖λ+.