In the context of Ontology Based Data Access (OBDA), consistency of data ensures that the data sources are coherent with the rules of the domain of interest represented by the ontology. However, even when consistency holds, the data underlying an OBDA system can still be in a state that users perceive of poor quality, according to some intuitive requirements. In many of these cases, the mechanism currently used to specify an OBDA system seems to lack of the ability to express such requirements. In this work, we argue that those requirements are often not about the world that the ontology represents, but about the knowledge that the system possesses on the world. Thus, with the aim of formalizing data quality specifications in the OBDA context, we propose the usage of a language of modal constraints, and show how they can be used in practice to capture cases of poor data quality. For this novel class of assertions, and for OBDA systems where the ontology is expressed in DL-Lite, we present algorithms and complexity results for the problem of checking the accuracy of the knowledge that the system posses, i.e., whether the system respects the modal constraints in the specification.
The problem of assessing the quality of data is a well-known topic, that has always
received a lot of attention from different branches of the scientific community, in
particular in statistics and data management (see [
Assessing the quality of data is a manifold process, that consists of many different tasks. To ease its overall complexity, a largely accepted practice is the adoption of dimensions. A data quality dimension is a single aspect onto which the analysis is focused. Unfortunately, such dimensions often lack of a formal definition
A notable attempt to tackle this problem has been proposed by Y. Wand, and R. Y.
Wang in [28]. In that work, the authors propose to build data quality dimensions starting
from a formal framework, inspired to the notion of ontology, i.e. a formal description
of a portion of the real world, made in terms of its states and laws. Despite being a very
promising intuition, one of the first attempts to use it in practice has been proposed only
recently in [
In this work, we go along the same line, and use the ontology-based data access paradigm (OBDA for short) to assess the accuracy dimension, i.e. the extent to which the information stored inside a database is accurate.
OBDA is a novel paradigm, aiming at accessing and managing the data contained
in a database by means of a formal specification, made of an ontology and a mapping
([
The advantages of using an OBDA system to assess the quality of a database are manifold. The high level of abstraction achieved by the OBDA paradigm, in fact, is very useful when considering the overall quality of the data scattered through the tables of real data sources. Furthermore, OBDA systems can be used to get rid of all the superfluous information, such as index attributes and reference tables, and focus on the real data quality issues.
However, differently from the dimension of consistency studied in [
Example 1 (Consistent but inaccurate data). The following is the database schema S of the system used by a company to store data about orders and customers.
CEN SU SpSSN; Address; N ame; Surname; DateOf Birthq; P RODU CT SpP roductCode; T ypeq;
ORDERSpOrderCode; P ersonCode; P roductCode; hasBeenP aidqu
Consider the following instance D of the schema.
D t P ERSON SpP 1; SSN 1; trueq; P ERSON SpP 2; SSN 2; trueq
CEN SU SpSSN 1; A1; N ame1; Surname1; DOB1q;
ORDERSpO01; P 1; P r1; trueq; ORDERSpO03; P 3; P r3; f alsequ
The company recognizes the status of golden customer only to those individuals who have already paid an order. No constraints in the database schema, however, enforce this requirement. The OBDA specification B, defined as follows, formally describes this scenario.
Order DhasOrdered ; DhasOrdered Order; Customer DhasOrdered; DhasOrdered Customer; Customer DhasAddress; hasP aid hasOrderedu M t P ERSON Spx; z1; ‘true’q GoldenCustomerpxq; P ERSON Spx; z1; z2q ^ CEN SU Spz1; y; z3; z4; z5q ORDERSpx; y; z1; z2q hasOrderedpy; xq; ORDERSpx; y; z1; ‘true’q hasP aidpy; xq; ORDERSpz1; x; z2; z3q Customerpxqu Customer; hasAddresspx; yq;
is consistent, in the sense that no rule of the ontology is violated. However, the data stored in D are inaccurately considering the customer associated with P 2 as a golden customer, in spite of the fact that no paid order is connected to that customer code.
In order to represent such constraint, and in fact many others, we can resort to what the OBDA system xB; Dy is sure about, or, in other terms, what the OBDA system knows.
Example 2. (Enforcing knowledge) Consider again the scenario described in Example 1, and suppose to impose to the system an additional constraint k, whose intuitive meaning is the following: each known golden customer has a known paid order associated to her.
Now consider the following. The golden customers known by the system are, intuitively, P 1 and P 2. However, no known paid order is associated to P 2. Thus, we can conclude that the constraint k is not satisfied by the OBDA system xB; Dy.
In the rest of this paper, we expand on the topic of using constraints of the kind
presented in Example 2, with the aim of expressing requirements about the accuracy
of data. To this aim, we shall present the class of epistemic dependencies, i.e. a modal
derivative of the well known class of embedded dependencies (see e.g. [
In fact, the languages currently used to specify OBDA systems are, in general,
unable to express requirements about knowledge, as shown in the previous example.
Furthermore, the language presented in [
In order to give to our framework formal semantic, we shall study the problem of constraint satisfaction using the well known modal logic of knowledge and belief OL, due to Levesque ([19]).
Notice that we don’t claim any novelty on the notion of epistemic state of an
ontology, see e.g. [
The paper is organized as follows. In Section 2 we present preliminary notions that we use throughout this work. In Section 3 we detail the notion of what is known to an OBDA system, which we use in Section 4 to present our class of constraints. The complexity of handling such constraints is presented in Section 6. The notion of data accuracy in the OBDA scenario is investigated in Section 5. In Section 7 we conclude. 2
In this section we present technical notions that we use in the remainder of this work.
Formulas and interpretations. For our logical formulas, we consider predicate
logic, and sometimes allow the presence of modal operators. For the syntax of formulas,
we assume the standard inductive definition (see e.g. [
A query is an open formula, i.e. a formula in which some variables don’t appear in the scope of any quantifier. Two notable classes of queries are the class of conjunctive queries, and union thereof. A conjunctive query (CQs) is a conjunction of existentially quantified atoms, possible containing free variables. For union of conjunctive queries (UCQs), we further require that the free variables in each disjunct are the same. To better point out the set of free variables of a query q, we sometimes use the set theoretic notation, i.e. tx | qpxqu, where x is a vector of variables.
Objective formulas shall be interpreted over first order interpretations, with their
usual semantics (see e.g. [
For queries, we are interested in computing their certain answers, i.e. the set of substitutions for their free variables that make the formula true in every model of a given logical theory. We denote the set of certain answers for a given query q, under the logical theory L, as anspq; Lq. We assume anspK; Lq H , whenever L has at least one model.
Databases. In this work, we consider relational databases, and refer the reader to
[
symbols, while CS is a set of formulas in the alphabet S . A set of ground facts, built using the alphabet S of a schema S , is called S -database. Whenever an S -database
or simply legal. In this work, we don’t impose any particular restriction on the class of constraints that can appear in a database schema.
Description Logic ontologies. An ontology is the conceptualization of a domain of interest, expressed in terms of a formal language. In this work, we consider ontologies expressed using Description Logic, and focus our attention on the language
the sake of brevity, we provide only a short account of DL-LiteA here.
The syntax of concept, role and attribute expressions in DL-LiteA over an
alphabet T is specified by means of the following grammar (where A; P; U are atomic
concepts, roles, and attributes, respectively, and T1; : : : ; Tn are unbounded pairwise
disjoint predefined value-domains):
Tn
1 Not to be confused with the set of DLs studied in [
In DL-LiteA TBoxes we further impose that roles and attributes occurring in functionality assertions cannot be specialized, i.e., they cannot occur in the right-hand side of positive inclusions (see [23] for a detailed account on DL-LiteA).
Note that checking DL-LiteA-KB for satisfiability, i.e., checking whether
empty, can be done in AC0 with respect to A and in PTIME with respect to T .
Ontology Based Data Access. An OBDA system is constituted by an intentional component, that we call OBDA specification, and an extensional component, represented by a database.
An OBDA specification is in turn constituted by three main components , i.e. the ontology, the mapping, and the database schema.
Definition 1 (OBDA specification). An OBDA specification B is a triple xT ; M; Sy, where – T is a DL-LiteA TBox, called the ontology of B, with alphabet T ; – S x S ; CS y is a database schema, called the source schema of B; – M is a finite set of mapping assertions between S and T , called the mapping of B, where each mapping assertion is of the form @x pxq D y px; yq, where pxq is a conjunctive query over S with free variables x, and px; yq is a conjunctive query over the alphabet T with free variables x Y y.
In what follows, we will refer to a specific form of mappings, called GAV,
extensively studied in the database literature [
S -database D, we obtain an OBDA system. We define the semantics of an OBDA system by specifying which are the models of B relative to D, denoted by M odDpBq.
wise, they are all those interpretations I for T that satisfy T , and such that the pair xD; Iy satisfy all mapping assertions in M, written xD; Iy |ø M.
Definition 2 (OBDA system semantics). Let B x T ; M; Sy be an OBDA specification, and let D be a S -database. Then M odDpBq t I | I |ø T ; pD; Iq |ø M; and D |ø S u:
to checking whether M odDpBq H . If the system is managed by suitable software components, including a database management system ensuring that D |ø CS , then the satisfiability checking reduces to verifying whether there exists an interpretation I for
Query answering and rewriting. OBDA systems defined above enjoy several desirable properties, that we cannot discuss here for lack of space. We only briefly discuss how we can compute certain answers for queries in a satisfiable OBDA system. Let B x T ; M; Sy be a OBDA system, and D a S -database. The results presented in [23] show that, in order to answer a union of conjunctive query q (expressed in the alphabet T ) posed to B x T ; M; Sy and D, we can compute the perfect rewriting of q with respect to T and M, written RT ;Mpqq, which is a union of conjunctive query over the alphabet S , and then evaluate RT ;M over D. We will make use of this result in the following. Answering queries under an OBDA system is in P T ime w.r.t. the size of the ontology, and in AC0 w.r.t. the size of the database. 3
In our study of data accuracy, a central part is played by the knowledge that an OBDA system possesses on the real world. In this section, we discuss how we can formally represent this knowledge.
To this aim, we resort to the predicate version of the well known modal logic OL
of knowledge and belief, due to Levesque ([19]). Through the years, OL has been
extensively used in many different flavors ([
epistemic state E is simply a set of first order interpretations, called worlds. For worlds
inside the same epistemic state E , we require that they share a single (countably infinite)
domain of discourse, E , called the set of standard names for E . Notice how this
assumption implies the Barcan axiom ([
Definition 3. Let be a generic OL formula, E an epistemic state, and w a world in E . Then is true in E ; w, or E ; w ( , if the following conditions hold. – – – – – – is an atomic formula, and w |ø .
1, and E ; w * 1 1 ^ 2, and both E ; w ( 1 and E ; w ( 2 hold.
D x: 1pxq, and for some tuple c of parameters, we have that E ; w (
Kp 1q, and w1 P W øae E ; w1 ( 1.
Op 1q, and w1 P W ae E ; w1 ( 1. 1pcq.
Abbreviations _, , and @ shall be considered with the usual meaning.
Intuitively, if an OBDA system knows that some formula is true, then it is true in all the possible worlds represented by the ontological specification. On the other hand, if a formula is what an OBDA system only-knows about the real world, all and only the wolds in which that formula is true are models of the system.
In light of this, the knowledge possessed by an OBDA system is closely related to the data stored inside its database. In fact, from the notion of semantics given in Definition 2, something can be true in all the models of an OBDA system only if it is grounded into its extensional part.
Notice however, that the standard definition of semantics for OBDA systems cannot be directly used in the OL context. In order to gather all the knowledge that a system possesses on the real world, we make use of the O operator, and interact with the gathered knowledge by means of K.
ize the notion of what an agent knows about its own knowledge, i.e. its auto-epistemic state. Whenever O is not present, this notion needs to be formalized by means of some meta-logical operator, such as the stable expansion (see e.g. [21]), or the | operator ([25]).
We use the notion of knowledge state, presented below, to formalize this concept in the OBDA scenario.
Definition 4. Let O be an ontology based data access system, then the epistemic state E is said to be a knowledge state of O if and only if E ( OpOq.
Our notion of knowledge state of an OBDA system is similar to the notion of
epistemic model of an ontology given in [
From Definition 4 comes the following.
Proposition 1. Let E , E 1 be two knowledge states for the OBDA system O. Then E and E 1 are equivalent, up to isomoprhisms on the set of standard names.
theory. In fact, once fixed the set of standard names, the knowledge state of an OBDA system must contain all and only the first order interpretations that are models of the system.
In the OBDA systems defined in Section 2, knowledge state is the product of the general truth about the real world, expressed in the ontology, and the data stored in the database. In light of this, OBDA specifications currently lack of the ability to directly express requirements on knowledge. The language of constraints presented in Section 4 can be used to express requirements over epistemic states, and hence enforce, or assess, the knowledge possessed by an OBDA system. 4
To describe our language of constraints for knowledge states, we start from the considerations about integrity constraints presented by Reiter in [24].
In that work, the author defines the class of pure KFOPCE sentences being, essentially, the class of all K-modal sentences in which predicates appear only in the scope of the modal operator K. This class of formulas is then used to express a more meaningful form of integrity constraints for databases, through the notion of the entailment operator | .
Later, in [25], the author establishes an equivalence between such operator and the validity of formulas of the form: OpT q Kp q, where T is a first order non modal theory, and is a pure KFOPCE formula.
A similar notion is used in [
using a syntactically restricted form of the epistemic operator K.
To refer to this concept, and avoid any discrepancy in the notation, we shall call these formulas simply subjective.
– –
is either: 1. a formula
For our language of constraints, we make use of this same intuition but, unlike our
predecessors, we restrict ourselves to the well known class of embedded dependencies
([
Definition 5. A formula is a subjective disjunctive dependency if and only if it has the form such that the following conditions hold.
px; yq is a formula of the form Cipxi; yi; biq, where each Cipxi; yi; biq is a i relational atom in the variables xi Y yi Y bi, x i xi, y i yi, and b i bi s spx; zq, where each spx; zq has the form:
Dz:KpDb1 ' j
Cj pxj ; zj ; bj qq and each Cj pxj ; zj ; bj q is a relational atom in the variable xj Y zj Y bj , and x xj , z zj , b1 bj , or
j j j 2. a conjunction of equality atoms in the form
are variables from x, or 3. the symbol K. e te t1e, where each te and t1e
For the sake of brevity, from now on we shall refer to the class of purely subjective embedded dependencies simply as epistemic dependencies (EDs for short), and consider this as our class of constraints. Notice how the explicit usage of the operator K makes EDs different from the constraints presented in [27].
As already pointed out in Section 3, the notion of semantics given in Definition 2 is not well suited for the interaction with EDs. The next definition presents a novel notion of satisfaction, suitable for EDs in the OBDA scenario.
Definition 6. Let O be an OBDA system, and k an epistemic dependency. Then we say that O satisfies k if and only if OpOq Kpkq.
EDs can be used to enhance OBDA specifications, adding further constraints about knowledge. We now present a new definition for OBDA specifications, augmented by a set of EDs.
Definition 7. Let K be a set of epistemic dependencies, and B an OBDA specification. Then the constrained OBDA specification BK is the pair xB; Ky.
A constrained OBDA specification can be paired with a database to form a constrained OBDA system, in the usual way. The following is the definition of semantics for constrained OBDA systems.
Definition 8. Let BK x B; Ky be a constrained OBDA specification, and let D be a database. Then a first order interpretation I is a model for the constrained OBDA system OK x BK; Dy if and only if: 1. I is a model for the OBDA system O x B; Dy 2. O satisfies k, for each k P K
Intuitively, condition 2 requires that a given set of constraints is satisfied by the current epistemic state of the system. In this sense, the condition is on the whole system, and the single model doesn’t play any part in it.
As usual, a constrained OBDA system with no model, is said to be unsatisfiable, satisfiable otherwise. In the same way, we call a database D consistent with respect to a constrained OBDA specification BK, whenever the system xBK; Dy is satisfiable; inconsistent otherwise.
The complexity of checking whether an OBDA system satisfies a given ED (Definition 6), and hence the complexity of checking whether a constrained OBDA system is satisfiable (Definition 8), is analyzed in Section 6. 5
With the aim of drawing a parallel between data accuracy and OBDA, we start this
section by reminding the reader of the standard definition of accuracy. A database D is
said to be accurate whenever it accurately describes the reality of interest, with respect
to the tasks at hand (see e.g. [
When the database is paired to an OBDA specification, we can use the language of the ontology to express accuracy requirements, by means of a set of EDs. In fact, as already mentioned, something is known to an OBDA system only if it is grounded into the data stored into its database. Next definition formalizes this intuition. Definition 9. Let BK x B; Ky be a constrained OBDA specification, and let D be a database. Then D is said to be of poor quality with respect to accuracy, according to BK, if and only if D is consistent with B but it is not consistent with BK.
One may ask whether EDs posses the expressiveness required to specify meaningful constraints. In the remainder of this section, we argue that this is the case, by showing some practical example of what EDs may express, using the scenario presented in Example 1.
Example 3 (Information accuracy). Consider again the constraint described in Example 2. It’s very straightforward to see how the following ED fully captures the intended meaning. y:KphasP aidpx; yqq As expected, the constraint k1 is violeted for x{P 2.
Example 4 (Completeness of the known information). The problem of assessing data completeness is a complex topic, behind the scope of this work, and probably outside the expressiveness of our constraints.
In spite of this, EDs can still be used to impose completeness on the known information. The following constraint checks whether the address of each customer that has paid an order is known to the system.
k2 : @x:KpDy:Customerpxq ^ hasP aidpx; yqq D z:KphasAddresspx; zqq Notice how k2 doesn’t require any known order. The constraint is violated for x{P 2. Example 5 (Disjunctions). We believe that one of the most interesting features of EDs is the possibility of using disjunctions. For example, we can impose that only golden customers can delay the payment of known orders, i.e. each known order has been either paid, or placed by a golden customer.
KpDy:hasP aidpy; xqq_
KpDz:hasOrderedpz; xq ^ GoldenCustomerpzqq Constraint k3 is violated for x{O03. 6
In this section we present an algorithm to check whether an OBDA system satisfies a given ED, and show its complexity. In what follows, we shall often transform subjective formulas into first order queries of a specific form. The following definition details this transformation.
Definition 10. Let : KpDy
Cipxi; yiqq be a formula where x is either free or quani tified outside the scope of K. Then q pxq is the following conjunctive query: ' tx | Dy
Cipxi; yiqu i
We now present the complexity results for the problem of checking satisfaction of EDs. To this aim, we start by formalizing the decision problem associated to the notion of satisfaction.
Definition 11. Let O be an OBDA system, and let k be an epistemic dependency. Then K-Satisfaction is the following decision problem: check whether O satisfies k.
answering. To this aim, we start by stating the following lemma.
Lemma 1. Let KpDy:Cpx; yqq, where C is a conjunction of propositional atoms, and let O x B; Dy be a satisfiable OBDA system. Then OpOq KpDy: pc; yqq, being c a tuple of standard names, if and only if c P anspq pxq; Oq.
OBDA system. Intuitively, we can compute the answer of the conjunctive query representing each part of an ED, and then compare the results.
Theorem 1. Let B be an OBDA specification, D a database, and O x B; Dy a satisfiable OBDA system. Furthermore, let k : s be an epistemic dependency in the form of Definition 5.
Then O satisfies k if and only if, for each vector of standard names c, such that anspq pc; yq; Oq is non-empty, we have that also anspq s pc; zq; Oq is non-empty for some s.
Theorem 1 directly suggests the algorithm presented in Figure 1. Intuitively, the algorithm goes as follows: it computes the perfect rewriting of the queries representing each part of an ED, and issues a suitable first order query to the underlying database system to check whether a violating tuple exists. s Algorithm check-dependency.
Let k : be an ED in the form of Definition 5, and O x T ; M; Sy. check-dependency(k, O, D) do: qbpx; yq : RT ;Mpq px; yqq; if ( ipx; zq) then qhpx; zq : i
RT ;Mp ipx; zqq; i else qh : ;
k : D x; y; z:qbpx; yq ^ return ansp k; Dq;
qhpx; zq;
Theorem 2. Let B x T ; M; Sy be an OBDA specification, k an epistemic dependency, and D a database. Then, K-Satisfaction problem for k under B is in AC0 in the size of D, in P T ime in the size of T and M.
Complexities shown in Theorem 2 are a direct consequence of the complexity of
query answering under an OBDA systems (see e.g. [
In this work we tackled the problem of assessing the accuracy of the data stored inside a database system, using the OBDA paradigm. Our techniques exploit the great level of abstraction of OBDA systems to thoroughly examine the information stored in the database, and makes use of modal formulas to interact with the real data.
We plan to extend this work by studying techniques to assess the accuracy at the schema level, i.e. to check whether a given database schema enforces sufficient accuracy requirements.
Acknowledgments I would like to thank Maurizio Lenzerini for the many invaluable discussions on the topics of this paper. Work partially supported by the EU under FP7, project Optique (Scalable End-user Access to Big Data), grant n. FP7-318338. 19. Levesque, H.J.: All I know: A study in autoepistemic logic. Artif. Intell. 42(2-3), 263–309 (1990) 20. Levesque, H.J., Lakemeyer, G.: The logic of knowledge bases. MIT Press (2000) 21. Moore, R.C.: Semantical considerations on nonmonotonic logic. Artif. Intell. 25(1), 75–94 (1985) 22. Motik, B., Horrocks, I., Sattler, U.: Bridging the gap between OWL and relational databases.
J. Web Sem. 7(2), 74–89 (2009), http://dx.doi.org/10.1016/j.websem.2009.02.001 23. Poggi, A., Lembo, D., Calvanese, D., De Giacomo, G., Lenzerini, M., Rosati, R.: Linking data to ontologies. J. Data Semantics 10, 133–173 (2008) 24. Reiter, R.: On integrity constraints. In: Proceedings of the 2nd Conference on Theoretical
Aspects of Reasoning about Knowledge, Pacific Grove, CA, March 1988. pp. 97–111 (1988) 25. Reiter, R.: What should a database know? J. Log. Program. 14(1&2), 127–153 (1992) 26. Rodriguez-Muro, M., Calvanese, D.: High performance query answering over dl-lite ontologies. In: Principles of Knowledge Representation and Reasoning: Proceedings of the Thirteenth International Conference, KR 2012, Rome, Italy, June 10-14, 2012 (2012) 27. Tao, J., Sirin, E., Bao, J., McGuinness, D.L.: Integrity constraints in OWL.
In: Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2010, Atlanta, Georgia, USA, July 11-15, 2010 (2010), http://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/view/1931 28. Wand, Y., Wang, R.Y.: Anchoring data quality dimensions in ontological foundations. Commun. ACM 39(11), 86–95 (1996)