Connecting Databases and Ontologies: A Data Quality Perspective

Abstract

Taking a database-theoretic perspective on the problem of mapping relational databases to ontologies, we come up with a new mapping language that is inspired by the semijoin algebra. We illustrate the user friendliness of the mapping language by examples, and prove the decidability of some important reasoning problems by embedding our mapping language into the guarded fragment of rst-order logic. We argue that these reasoning problems are relevant in data quality explorations.

Keywords

• data quality
• OBDA
• semijoin algebra

Motivation

guarded fragment ontology-based data access The literature contains many proposals for mapping relational databases to ontologies. The major motivation for these proposals is probably ontology-based data access (OBDA) [ 20 ], i.e., the capability of interrogating databases by using an ontological vocabulary. The current study, however, started with a di erent purpose, which can be coined as ontology-based database repairing or ontologybased database cleaning. Database repairing and cleaning are approaches for dealing with dirty data, where dirtiness refers to the violation of integrity constraints or, more abstractly, the non-conformity to rules that the data should obey. Ideally, all such data rules should be declared at database design time and subsequently enforced by the database management system. In practice, however, we seldom dispose of an exhaustive declaration of all data rules: some rules were overlooked when the database schema was conceived, while others were hidden in procedural programming code. Moreover, in the course of time, new rules may emerge because of new legislation (e.g., GDPR), while existing rules may be invalidated. Now let us assume that we have access to an ontology that talks about objects and relations that also exist in some presumably dirty database. Our hypothesis is that data quality problems may become more visible when we succeed in connecting or mapping the database to the ontology, enabling us to confront the stored data with the ontological \ground truth." It should be mentioned here that an ontologically based approach to data quality is not a new idea: it already appeared in [ 19 ], was formalized in [ 10 ], and is mentioned in [ 20 ] as an important direction for future research.

In the problem of mapping relational databases to ontologies, we are given a relational database schema (i.e., a set of relation names), a description logic vocabulary (i.e., a set of unary and binary predicate names, called concept names and role names), and a TBox in some description logic. Moreover, we are given a database-to-ontology mapping, which de nes a computable function from the set of database instances (over the xed database schema) to the set of ABoxes in the description logic. If M denotes such a mapping and db denotes a database instance that serves as input to M, then we write M(db) for the resulting ABox. In a data cleaning context, we may be interested to know, for example, whether the knowledge base (T ; M(db)) is consistent, and if not, what data in db causes inconsistency.

In this paper, we introduce and study a language for specifying such mappings M, seeking a good balance between expressiveness and complexity. Four design considerations are as follows.

First, we work in a perspective where columns in relations are not only numbered, as in mathematical logic, but also named with attributes. We will not assume that real-world entities have unique identi ers. Instead, we will use tuples with attributes to identify entities. This allows us, for example, to distinguish between the actress fLastname : Hilton, Firstname : Parisg and the entity fHotel : Hilton, City : Parisg, which is a hotel in Paris.

Second, the language for mapping databases to ontologies will be a subset of relational algebra. This leads to a succinct syntax without rst-order variables. A major convenience for end-users is that any syntactically correct combination of the algebra operators is allowed in our mapping language. This would not be achievable in predicate logic, where end-users would be troubled with syntactic restrictions like safeness and guardedness.

Third, like with description logics, a major consideration in the design of our mapping language is the balance between expressiveness and complexity. For expressiveness considerations, we allow negation in our mapping language, which is often considered useful [ 4 ]. On the other hand, the full expressive power of predicate logic would result in the undecidability of some basic reasoning problems.

Fourth, relational database schemas are often obtained from a conceptual schema expressed in the Entity-Relationship model [ 9 ] or some variant of it. In such database schemas, most database tables are in 3NF and correspond to either an entity type or a relationship type in the conceptual schema. Intuitively, concept names and role names in description logics also correspond, respectively, to entity types and relationship types. Therefore, a plausible assumption is that in a well-designed database, the same real-world entity will generally not be spread out over multiple database tables, thus reducing the need for arbitrary joins in the mapping rules of M. On the other hand, negation may be commonly needed (for example, to compute foreign students as all students except Belgian citizens).

The above considerations have brought us to the semijoin algebra [ 11 ], a fragment of the relational algebra which can be translated in GF , the guarded fragment of rst-order logic. In terms of expressiveness, our mapping language is incomparable with the commonly used language of GLAV mappings.

This paper is organized as follows. The next section discusses related work. Section 3 illustrates the concepts of this paper by means of a simple example. Section 4 introduces some preliminary de nitions. Section 5 introduces Entityexpressions and Relationship-expressions, which are the building blocks for our mapping rules that are introduced in Section 6. The decidability of some important reasoning problems is established in Section 7. Section 8 concludes the paper. 2

Related Work

Starting with the seminal work by Poggi et al. [ 13 ], recent years have seen active research on disclosing relational databases to ontologies or the semantic Web [7, 14{16, 20]. The most commonly used rules used for mapping relational databases to ontologies have the form 8x ('(x) ! 9y (x; y)) ; (1) where the left-hand side ' is a conjunction of atoms over the database schema, and the right-hand side is a conjunction of atoms over the vocabulary (concept names and role names) of the ontology. A closed formula of the form (1) is called a GLAV mapping or, in the database literature, a tuple-generating dependency (tgd). A tgd is full if no existential quanti er occurs in it. A GAV tgd is a full tgd whose right-hand side is a single atom. A LAV tgd is a tgd whose left-hand side is a single atom. Bienvenue [ 4 ] uses GAV:;6= tgds, which extend GAV tgds by allowing negated atoms and inequalities in the left-hand side. In [ 13 ], the left-hand side is allowed to be an arbitrary SQL query. Most studies in OBDA have adopted the relational database model; a recent notable exception is [ 5 ] which also considers NoSQL databases.

As explained in the introduction, our incentive for studying OBDA is that it can provide an ontologically based approach to data quality. This involves identifying inconsistency and redundancy in OBDA mappings, as well as testing for other (un)desirable properties [ 10, 12, 13 ]. A recent survey on OBDA [ 20 ] mentions data quality as an important research direction.

When mapping relational databases to ontologies, a di culty is that the relational database model uses value-based primary keys to identify tuples, while description logics use abstract individual names to refer to objects, possibly in combination with the Unique Name Assumption. This di culty is nicely discussed in [13, p. 149], where a solution is proposed that uses Herbrand terms of the form f (a) as individual names, where f is a function symbol and a is a sequence of database values whose length is the arity of f . By allowing multiple function symbols, this solution can distinguish between fperson (Hilton; Paris) and fhotel (Hilton; Paris). Our approach resembles the latter solution, with one signi cant di erence: instead of using function symbols, we use attribute names to distinguish between two sequences that contain the same data values. Such attribute-based representation has recently appeared in the description logic DLR+ [ 2 ]. We do not address the problem that the same entity may be identied by di erent identi ers [ 8, 21 ]. 3

Introductory Example

Before starting the technical development, we introduce our mapping language by means of a simple example. A fact ENROLLED (c; f; `; p; y) in our example database means that student (f; `) is currently enrolled in course c and took the prerequisite course p in the year y. A fact TAUGHT -BY (c; f; `; h; s) means that the course c is taught by (f; `) and takes place at every hour h during semester s. The same course can be taught more than once in a week.

ENROLLED TAUGHT -BY

Course CS402 CS402

First Tom Tom

Last Jones Jones

Prerequisite

CS311 CS401

Year 2008 2009 Course CS402 CS402

First David David

Family Maier Maier

Hour Mon. 10am Tue. 10am

Semester Spring Spring We will identify all persons by their rst and last names, using the attributes First and Last . The operator First;Last takes the projection on First and Last . Since the table TAUGHT -BY uses the attribute Family for last names, we rename that attribute by means of the renaming operator Family!Last . Let S :=

First;Last ENROLLED and T :=

First;Last ( Family!Last TAUGHT -BY ):

Thus, S is the set of persons that are students, and T is the set of persons that are teachers. We will identify all courses by the attribute Course, which necessitates the use of the renaming operator Prerequisite!Course . Let C :=

Course ENROLLED [ [

Course ( Prerequisite!Course ENROLLED )

Course TAUGHT -BY Thus, C is the set of all courses. We are now ready to give three mapping rules for populating concept names Student, Teacher, and Course:

S : Student;

T : Teacher;

C : Course:

Our mapping language captures negation by means of the di erence operator . For example, one could declare

S

T : PersonWhoDoesNotTeach:

Finally, we show a mapping rule for roles. Assume we are in the spring semester, and are interested in who attends which course in the current semester. We show a mapping rule for the role name attends:

S; C n

Semester=SpringTAUGHT -BY ; ENROLLED : attends (2) S gets all students. Next, C n Semester=Spring(TAUGHT -BY ) gets all courses that take place in the spring semester. Technically, n is the semijoin operator, whose e ect is to return those courses in C that join with some tuple in the selection Semester=SpringTAUGHT -BY . Then, the third argument ENROLLED speci es that a student in the rst argument has to be related to a course in the second argument if they occur together in a same tuple of ENROLLED . The last argument, attends, speci es the role name for student-course pairs so obtained. 4

Preliminaries

Preliminaries from database theory. We assume a denumerable set att of attributes, a denumerable set dom of constants, and a denumerable set relname of relation names. We assume a total order att on att. We assume a total function sort with domain relname that maps every relation name to a nite set of attributes.

Let U be a nite set of attributes. A tuple over U is a total mapping from U to dom. A relation over U is a nite set of tuples over U . An attribute renaming for U is a total injective function from U to att. We write A1; A2; : : : ; An ! B1; B2; : : : ; Bn for the attribute renaming f such that f (Ai) = Bi for i 2 f1; : : : ; ng and f is the identity on other attributes. If t is a tuple over U and f is an attribute renaming, then f (t) denotes the tuple s over ff (A) j A 2 U g such that for every A 2 U , s(f (A)) = t(A). For example, if t = fA : a, B : b, C : cg and f = AB ! BD, then f (t) = fB : a, D : b, C : cg.

A database schema is a nite set of relation names. The following de nitions are relative to a xed database schema. A database instance db associates, to each relation name R, a nite relation over sort (R), denoted Rdb. A database instance is also called a database.

Relational algebra. The operations of the relational algebra [ 1 ] are selection , projection , (natural) join on, semijoin n, renaming , union [, and di erence . Conditions in selections can be equalities between attribute values and constants, that is, A=B and A=c. A projection X E takes the projection of E on the set X of attributes. A renaming f E, where f is an attribute renaming, applies f to all tuples in E. A join E on F returns all tuples that can be constructed by taking the union of two tuples, one from E and one from F , that agree on their common attributes. A semijoin E n F returns every tuple of E that agrees with some tuple of F on their common attributes. In the full relational algebra, n is not a primitive operator, because it can be expressed as a projection of a join: En F sort(E)(E on F ). However, semijoin is a primitive operator in the semijoin algebra, which allows semijoins but disallows joins. The formal semantics of all operators can be found in [ 1 ]; they de ne eval (E; db), the relation to which an algebra expression E on a database db evaluates.

The guarded fragment of rst-order logic. We de ne GF as the following restriction of predicate calculus, with equality: { every quanti er-free formula belongs to GF ; { if '(x; y) belongs to GF and R(x; y) is a relation atom in which all free variables of ' actually occur, then the formulas 9y (R(x; y) ^ '(x; y)) and 8y (R(x; y) ! '(x; y)) belong to GF ; and { GF is closed under ^, _, :, !, $.

A rst-order formula is called guarded if it belongs to GF .

When we use formulas in predicate logic as database queries, we will make sure that these formulas are domain-independent [1, De nition 5.3.7], and we assume that constant symbols occurring in these formulas are interpreted as themselves, which incorporates the Unique Name Assumption. 5

Entity-Expressions and Relationship-Expressions

In this section, we introduce Entity-expressions and Relationship-expressions, which will be used in Section 6 to construct mapping rules. The following de nitions are relative to a xed database schema and description logic vocabulary (i.e., a nite set of concept names and role names).

De nition 1 (Entity-Expression). Entity-expressions (EEs) are recursively de ned as follows: 1. Every relation name is an EE. 2. If E is an EE and X sort (E), then X E is an EE with sort ( X E) = X. 3. If E is an EE and f is an attribute renaming for sort (E), then f E is an

EE with sort ( f E) = ff (A) j A 2 sort (E)g. 4. If E is an EE, A; B 2 sort (E), and c 2 dom, then A=cE and A=BE are

EEs with sort ( A=cE) = sort ( A=BE) = sort (E). 5. If E1 and E2 are EEs such that sort (E1) = sort (E2), then E1 [ E2 and

E1 E2 are EEs with sort (E1 [ E2) = sort (E1 E2) = sort (E1). 6. If E1 and E2 are EEs, then E1 nE2 is an EE with sort (E1 n E2) = sort (E1).

Note that Entity-expressions cannot use the join operator on. The fragment of relational algebra that replaces the join operator on with the semijoin operator n is known as the semijoin algebra. An important result by Leinders et al. [ 11 ] states that the semijoin algebra is contained in GF . Our setting slightly di ers from this earlier work because we have attribute renamings f and selections of the form A=c, both of which are not present in [ 11 ]. The proof of the following Theorem 1 translates Entity-expressions in domain-independent formulas in the guarded fragment. It di ers from [ 11 ] in that it uses constants and does not use the formulas Gk(x1; : : : ; xk) introduced by Leinders et al. for de ning the guarded k-tuples of a structure.

Theorem 1. For every Entity-expression E with sort (E) = fA1; : : : ; Ang, it is possible to construct a domain-independent formula '(x1; : : : ; xn) in GF such that for every database db, for all a1; : : : ; an 2 dom, fA1 : a1; : : : ; An : ang 2 eval (E; db) if and only if db j= '(a1; : : : ; an). Furthermore, ' can be constructed as a disjunction of formulas in GF , all of the form 9y (R(x; y) ^ (x; y)).

The join operator on can be used in Relationship-expressions, which captures a common intuition that relationships are places where entities \join." De nition 2 (Relationship-Expression). Relationship-expressions (REs) are recursively de ned as follows: { Every Entity-expression is an RE. { If E1 and E2 are REs, then E1 on E2 is an RE. { The set of REs is closed under the operators A=c, A=B, f , [, and .

Note that the set of Relationship-expressions is not closed under projection or semijoin; for example, T n (R on S) and AB(R on S) are not Relationshipexpressions. In this way, Theorem 1 remains valid if we replace \Entity-expression" with \Relationship-expression" in its statement. 6

The Mapping Language

We will now introduce the notion of Database-to-ABox Dependency (DAD). From here on, all de nitions are relative to a database schema S, a description logic vocabulary C [ R (i.e., a set of concept names and role names), and a description logic DL. A DAD can be of two sorts: a Concept DAD (CDAD) takes as input a database and returns a set of concept assertions; a Role DAD (RDAD) takes as input a database and returns a set of role assertions. CDAD The following de nition introduces the syntax and semantics for a Concept DAD. The semantics of CDAD relies on a function from the set of all tuples to I, the set of individual names.

De nition 3 (Concept DAD). A Concept DAD (CDAD) is an expression E : C where E is an Entity-expression (over the database schema S) and C is a concept name in C.

We assume a denumerable set I of individual names. We assume an injective function from the set of all tuples (taken over all nite subsets of att) to the set of individual names. Let db be a database. The set of concept assertions generated by E : C from db is the following:

f (t) : C j t 2 eval (E; db) g:

Note that if t1 = fLastname : Hilton, Firstname : Parisg and t2 = fHotel : Hilton, City : Parisg, then (t1) 6= (t2), because is injective and t1 6= t2. RDAD The syntax for a Role DAD is slightly more complex: it is a sequence of two Entity-expressions, one Relationship-expression, and a role name r in R. Informally, given a database, such a Role DAD generates a role assertion (a; b) : r whenever a and b belong, respectively, to the result of the rst and the second Entity-expression, and together t the Relationship-expression. We give an example, and then provide a formal de nition. Example 1. Consider the following data from the Mathematics Genealogy Project at http://www.genealogy.ams.org.

PHD

First Last

Jan Chomicki Tomasz Imielinski Witold Lipski

Assume that no two distinct persons in this database agree on their rst and last names. Let f be a renaming such that f (First ) = AdvisorFirst and f (Last ) = AdvisorLast . Thus, the inverse of f , denoted f 1, maps AdvisorFirst and AdvisorLast to, respectively, First and Last . The following Entity-expression P gets rst and last names of all persons in the database:

P := fFirst;LastgPHD [ f 1 fAdvisorFirst;AdvisorLastgPHD : It is signi cant to note that Wiktor Marek will be added with attributes First and Last , even though he does not appear with these attributes in the PHD table. The following RDAD populates the role name SupervisedBy : [P; P=f ; PHD ] : SupervisedBy : (3) Given a database db, this rule will add a role assertion ( (s); (t)) : SupervisedBy to the ABox whenever s; t 2 eval (P; db) such that some tuple of eval (PHD ; db) includes both s and f (t). For example, if s0 = fFirst : Witold, Last : Lipskig and t0 = fFirst : Wiktor, Last : Marekg, then ( (s0); (t0)) : SupervisedBy is added to the ABox because s0 [ f (t0) = fFirst : Witold, Last : Lipski, AdvisorFirst : Wiktor, AdvisorLast : Marekg is included in the last tuple of the PHD table.

De nition 4 (Role DAD). A Role DAD (RDAD) is an expression of the form [E1=f1; E2=f2; E] : r where E1 and E2 are Entity-expressions, f1 and f2 are attribute renamings, E is a Relationship-expression such that sort ( f1 E1) [ sort ( f2 E2) sort (E), and r is a role name in R.

If f1 or f2 is the identity, it can be omitted. Such an RDAD is called join-free if on does not occur in it (but n can occur). For example, the RDADs (2) and (3) are both join-free. As for the semantics, the set of role assertions generated by [E1=f1; E2=f2; E] : r from a database db is the following: f ( (t1); (t2)) : r j t1 2 eval (E1; db), t2 2 eval (E2; db),

and f1(t1) [ f2(t2) t for some t 2 eval (E; db) g. 7

Reasoning Problems

We now move from a single CDAD or a single RDAD to sets of CDADs and RDADs, and introduce some reasoning problems. De nition 5. Let db be a database. Let M be a set of CDADs and RDADs. We write M(db) for the smallest ABox that contains all concept and role assertions generated from db by the CDADs and RDADs in M.

A CDAD is said to be active on db if it generates at least one concept assertion from db; an RDAD is active on db if it generates at least one role assertion from db.

In the following de nition, one may think of as a set of database constraints. However, when studying problems like Satisfiability (see below), we may add to some desirable properties, like 9xR(x) if we are asking for a satisfying database in which R is nonempty.

De nition 6. A DB2KB (or OBDA speci cation) is a triple ( ; M; T ) where { is a set of closed rst-order formulas over the database schema; { M is a set of CDADs and RDADs; and { T is a DL TBox.

Console and Lenzerini [ 10 ] introduced the notions of faithfulness and protection for characterizing data quality in OBDA. These notions are recalled next, together with the well-known notion of satis ability. For aesthetic reasons, we state all questions in the form \Is there a database such that. . . ?". Therefore, we are asking for the complement of faitfulness and protection as de ned in [ 10 ]. Finally, the notion of global-consistency appeared in [ 12 ].

INPUT: A DB2KB ( ; M; T ).

QUESTIONS: { Satisfiability: Is there a database db such that db j= and the knowledge base (T ; M(db)) is consistent? { Non-Faithfulness: Is there a database db such that the knowledge base (T ; M(db)) is consistent but db 6j= ? { Non-Protection: Is there a database db such that db j= but the knowledge base (T ; M(db)) is inconsistent? { Global-Consistency: Is there a database db such that db j= , all CDADs and RDADs of M are active on db, and the knowledge base (T ; M(db)) is consistent?

Informally, a \yes"-answer to Non-Protection tells us that the ontology has some constraints not implied by . Recall from Section 1 that the discovery of such constraints may be signi cant in data quality assessments. As mentioned just in front of De nition 6, may contain desirable properties in addition to database constraints. For example, for Satisfiability, we can use to express that the database db must be nonempty.

The above problems can be shown to be undecidable in general [10, Theorem 1]. The following theorem shows their decidability under some restrictions on the input, which will be discussed after the theorem. A technical crux in the proof of Theorem 2 concerns the switch from database tuples to DL individual names. Theorem 2. Satisfiability, Non-Faithfulness, Non-Protection, and Global-Consistency are decidable problems if their inputs are restricted to DB2KBs ( ; M; T ) with the following properties: { T can be e ectively expressed in GF ; { every formula in is in GF ; and { all RDADs in M are join-free.

Proof (Sketch). The proof shows that the four mentioned problems can be e ectively reduced to satis ability in GF . We rst explain how the reduction deals with the function in De nition 3 and with M. Let U := fA1; : : : ; Amg be the set of attributes, totally ordered, such that U includes sort (E) for every E : C in M, and U includes sort (E1) [ sort (E2) for every [E1=f1; E2=f2; E] : r in M. Let " be a fresh constant. For each S U , we encode each tuple t over S as (a1; a2; : : : ; am) where for 1 i m, ai := t(Ai) if Ai 2 S, and ai := " otherwise. For example, if U = fLastname, Firstname, Hotel , City g, then ("; "; Hilton; Paris) and (Hilton; Paris; "; ") encode, respectively, a hotel in Paris and an actress. The reduction rst uses the construction of Theorem 1 to translate Entity- and Relationship-expressions into GF . Next, the syntactic form in Theorem 1 allows us to translate CDADs and RDADs in GF . For example, for a CDAD E : C, every disjunct 9y (R(x; y) ^ (x; y)) in E's translation further translates into the guarded formula 8x8y (R(x; y) ! ( (x; y) ! C(t1; : : : ; tm))). Here, C is a predicate symbol of arity m := jU j that uses the encoding explained and illustrated before: for 1 i m, ti := xi if Ai 2 sort (E), and ti := " otherwise. We next show how the reduction deals with T . By the hypothesis of the theorem, T can be expressed by a formula 'T in GF . Of course, in this formula, concept names are unary, and role names are binary. In our reduction, predicates for concept names and role names become, respectively, m-ary and 2m-ary. To this extent, the reduction replaces in 'T every occurrence of every variable x by x1; : : : ; xm. For example, the guarded formula 8x (C(x) ! D(x)) translates into 8x1 8xm (C(x1; : : : ; xm) ! D(x1; : : : ; xm)), a formula that is also guarded. tu

The satis ability problem for GF with constants is EXPTIME-complete when the arities of all relation names are xed [ 17 ]. The EXPTIME-hard lower bound obviously carries over to the problems in Theorem 2. The EXPTIME-upper bound does not, insofar as Theorems 1 and 2 use exponential translations of CDADs and RDADs in GF . However, it is a plausible conjecture that membership in EXPTIME can be obtained along the lines of the proof of [11, Theorem 9].

We brie y discuss the restrictions in the statement of Theorem 2. The restriction that the input TBoxes T must be expressible in GF may be automatically ful lled by the description logic DL under consideration. Indeed, many expressive description logics can be expressed in GF [ 18 ], an example being ALC [3, p. 46]. The requirement that is in GF still allows expressing many interesting properties and database constraints, like non-emptiness of relations and inclusion dependencies, as well as all Boolean combinations of these (because GF is closed under Boolean combinations). On the other hand, GF does not include common database constraints like primary keys or functional dependencies. Theorem 2 imposes no restrictions on CDADs, but RDADs are restricted to be join-free. This restriction is unfortunate, because it means that all Relationshipexpression that occur in RDADs must actually be Entity-expressions. Informally, join-freeness demands that whenever an RDAD puts two entities together in a role, then these entities should already occur together in some database relation. This restriction is plausibly satis ed for database schemas that are obtained from Entity-Relationship diagrams that already capture such roles by relationships (as is actually the case for our example RDADs (2) and (3)). The restriction can be prohibitive though if one wants to combine in a role two entities that are unrelated in the Entity-Relationship diagram. Anyway, our proof of Theorem 2 fails if we relax one of its hypotheses, because such relaxation would take us outside GF .

Finally, we show a result telling us that database constraints can be obtained from an ontology, given a mapping M. As we argued in Section 1, this may be of interest in data cleaning applications to infer missing database constraints. Theorem 3. Let ( ; M; T ) be a DB2KB such that = ; and T is a DL-Litecore TBox. It is possible to construct a nite set 0 of closed rst-order formulas such that for every database db, db j= 0 if and only if (T ; M(db)) is a consistent knowledge base. Moreover, if every RDAD in M is join-free, then 0 is in GF . Proof (Sketch). From [ 6 ], it follows that unsatis ability in DL-Litecore can only arise due to some negative inclusion C v :D implied by the TBox that is violated in the ABox. The negative inclusion C v :D can be of four di erent forms, where A; B denote concept names, and r; s role names: A v :B, A v :9r, 9r v :A, or 9r v :9s. We show here how to deal with A v :B (the other cases are similar): for all CDADs E : A and F : B in M such that sort (E) = sort (F ), 0 contains a formula stating emptiness of fg(E n F ). The latter algebra expression is an Entity-expression, and thus, by Theorem 1, can be expressed in GF . tu 8

Conclusion

The language of CDADs and RDADs allows expressing database-to-ontology mappings in a user-friendly way. The language is based on the semijoin algebra, which is embedded in the guarded fragment of rst-order logic. This results in decidability of some important reasoning problems. Since CDADs and RDADs allow full negation, they can express mappings that are not GLAV mappings. On the other hand, the GLAV mapping 8x8y8z (R(x; y) ^ R(y; z) ^ R(z; x) ! C(x)) is not guarded and cannot be expressed as a CDAD. In future research, we plan to explore in more depth the practice of using ontological knowledge in database repairing, database cleaning, and consistent query answering. We also plan to investigate how our framework can be reconciled with DLR+ [ 2 ], a description logic tailored towards relational databases.

References

1. S. Abiteboul , R. Hull , and V. Vianu . Foundations of Databases. Addison-Wesley , 1995 .

2. A. Artale , E. Franconi, R. Pen~aloza, and F. Sportelli . A decidable very expressive description logic for databases . In International Semantic Web Conference 2017 , pages 37 { 52 , 2017 .

3. F. Baader , I. Horrocks, C. Lutz , and U. Sattler . An Introduction to Description Logic. Cambridge University Press, 2017 .

4. M. Bienvenu . Inconsistency-tolerant ontology-based data access revisited: Taking mappings into account . In IJCAI 2018 , pages 1721 { 1729 , 2018 .

5. E. Botoeva , D. Calvanese , B. Cogrel , J. Corman , and G. Xiao . A generalized framework for ontology-based data access . In AI*IA 2018 , pages 166 { 180 , 2018 .

6. D. Calvanese , G. De Giacomo, D. Lembo , M. Lenzerini , and R. Rosati . Tractable reasoning and e cient query answering in description logics: The DL-Lite family . J. Autom. Reasoning , 39 ( 3 ): 385 { 429 , 2007 .

7. D. Calvanese and E. Franconi . First-order ontology mediated database querying via query reformulation . In S. Flesca, S. Greco , E. Masciari, and D. Sacca, editors, A Comprehensive Guide Through the Italian Database Research Over the Last 25 Years. , volume 31 of Studies in Big Data , pages 169 { 185 . Springer International Publishing, 2018 .

8. D. Calvanese , M. Giese , D. Hovland , and M. Rezk . Ontology-based integration of cross-linked datasets . In International Semantic Web Conference 2015 , pages 199 { 216 , 2015 .

9. P. P. Chen. The Entity-Relationship Model { Toward a uni ed view of data . ACM Trans. Database Syst ., 1 ( 1 ):9{ 36 , 1976 .

10. M. Console and M. Lenzerini . Data quality in ontology-based data access: The case of consistency . In AAAI 2014 , 2014 .

11. D. Leinders , M. Marx , J. Tyszkiewicz , and J. V. den Bussche. The semijoin algebra and the guarded fragment . Journal of Logic, Language and Information , 14 ( 3 ): 331 { 343 , 2005 .

12. D. Lembo , J. Mora , R. Rosati , D. F. Savo , and E. Thorstensen . Mapping analysis in ontology-based data access: Algorithms and complexity . In International Semantic Web Conference 2015 , pages 217 { 234 , 2015 .

13. A. Poggi , D. Lembo , D. Calvanese , G. De Giacomo, M. Lenzerini , and R. Rosati . Linking data to ontologies . J. Data Semantics , 10 : 133 { 173 , 2008 .

14. J. F. Sequeda . Integrating relational databases with the semantic web: A re ection . In Reasoning Web 2017 , pages 68 { 120 , 2017 .

15. J. F. Sequeda , S. H. Tirmizi , O. Corcho , and D. P. Miranker . Survey of directly mapping SQL databases to the semantic web . Knowledge Eng. Review , 26 ( 4 ): 445 { 486 , 2011 .

16. D. Spanos , P. Stavrou , and N. Mitrou . Bringing relational databases into the semantic web: A survey . Semantic Web , 3 ( 2 ): 169 { 209 , 2012 .

17. B. ten Cate and M. Franceschet . Guarded fragments with constants . Journal of Logic, Language and Information , 14 ( 3 ): 281 { 288 , 2005 .

18. C. Thorne , R. Bernardi , and D. Calvanese . Designing e cient controlled languages for ontologies . In Computing Meaning: Volume 4 , pages 149 { 173 . Springer Netherlands, Dordrecht, 2014 .

19. Y. Wand and R. Y. Wang . Anchoring data quality dimensions in ontological foundations . Commun. ACM , 39 ( 11 ): 86 { 95 , 1996 .

20. G. Xiao, D. Calvanese , R. Kontchakov , D. Lembo , A. Poggi , R. Rosati , and M. Zakharyaschev . Ontology-based data access: A survey . In IJCAI 2018 , pages 5511 { 5519 , 2018 .

21. G. Xiao, D. Hovland , D. Bilidas , M. Rezk , M. Giese , and D. Calvanese . E cient ontology-based data integration with canonical IRIs . In ESWC 2018 , pages 697 { 713 , 2018 .