Views are a mechanisms for precomputing answers to query of particular significance. Views have a definition (the query itself) and an extension obtained by evaluating the query over the data sources. Views are used for controlling the access to data and keep data even when the original sources are not accessible anymore. In this paper we introduce views definitions in DL-LiteR ontologies as an additional form of assertions in the TBox, and we study the basic reasoning tasks involving them, including consistency, containment, disjointness, projection classification, and query answering.
The notion of view is used in data management to create an abstraction of a query (which forms the definition of the view), and to see it as an ordinary database object. When such an object is mentioned in a data service (query or update), the data manager substitutes it with its “content”, and then executes the service resulting from the substitution. In relational databases, views can be seen as new relations derived from the elementary ones (base relations). But views are also available in NoSQL systems (e.g., MongoDB), and they have been studied for graph databases as well. Note that there are two interpretations of the notion of “content” here: for dynamic views, the content is simply the definition of the associated query, whereas for static views (also called materialized views), the content is the so-called “extension” of the view, i.e., the result that was pre-computed and cached for the associated query.
There are many uses of views in data management. For example, they can provide the user with concepts that are derived from the elementary database objects, thus improving abstraction. Or, they can represent a selection of the data contained in a particular portion of the database, so as to limit the degree of exposure of the underlying data to the outer world. Indeed, users of a given class may have permission to query the view, while denied access to the rest of the database. Views can also present aggregations to the users, thus providing calculated results as part of the data temselves. Finally, views can be used in data integration to specify which portion of a data source is mapped to which concepts in the global schema, or in data exchange to characterize the portion of the data to be transferred from the sources to the target system.
Generally speaking, the notion of view can be very well used in knowledge
bases too. Surprisingly, however, there are only few works dealing with views in
such area in general, and in Description Logics in particular. Here, we mention
those works that are the most relevant for the present paper. In [
In this paper we follow an approach similar to the one adopted in [
Example 1. Consider an ontology containing the following axioms: 9hasTaken v Student, 9hasGiven v Professor, 9isTheCourseOf v Course, 9teaches v Professor, 9teaches v Course where the notion of “exam” is represented in terms of a number of binary relations linking the various actors (student, professor) and components (course, grade) of the exam. If we want to provide the user with a different abstraction of the notion of exam, in particular as a specific predicate with 4 arguments, indicating who has taken the exam, what is the corresponding course, who is the professor (who must teach the course) who has given the exam, and which is the assigned grade, then we can define the following view: Exam(x; y; w; z)
teaches(w; y), grade(t; z) The above example shows that with the new predicate symbols corresponding to the views, the ontology is enriched with new abstractions that can be used during both ontology exploration for domain analysis, and query answering. The introduction of such new predicates may help overcoming some limitations of Ontology-based Data Access (OBDA) systems. The first limitation has to do with the nature of the ontology languages used in OBDA, which only allows unary and binary predicates. The use of views provides the possibility of using n-ary predicates in modeling the domain. The second limitation is related to the controlled expressive power in specifying the axioms of the ontology. For example, no lightweight ontology languages allows the free use of joins in concepts and role expressions. Once again, the possibility of defining conjunctive views may help overcoming this limitation.
Obviously, once we have introduced views in our ontology, we should be able to reason about them in all the tasks where the ontology plays a role. We discuss two basic classes of reasoning tasks, namely query answering, and reasoning about views. It is easy to see that, with the limitation (iii), computing the certain answers to (unions of) conjunctive queries whose atoms are ordinary concepts and relations, and view symbols can be still done in AC0 in the case where the ontology is expressed in DL-LiteR. Indeed, a simple unfolding strategy suffices for this purpose. Reasoning on views, on the other hand, is more challenging. Indeed, we aim at designing algorithms and study the complexity of checking view consistency, view containment and view disjointness. This is exactly the topic of this paper.
The paper is organized as follows. In Section 2 we illustrate some preliminary notions of queries in Description Logics. Section 3 describes our approach for extending ontologies with views. Section 4 presents algorithms and complexity analyses for reasoning about views. Finally, Section 5 concludes the paper, by highlighting possible directions for future work. 2
In this section we briefly recap the basic notions of Description Logics [
B ::= A j 9R C ::= B j :B
R ::= P j P E ::= R j :R where A 2 Nc denotes an atomic concept, P 2 Nr denotes an atomic role, B denotes a basic concept, that can either be an atomic concept or an expression of the form 9R, and R denotes a basic role, that can be either an atomic role or the inverse of an atomic role. Finally, C and E denote, respectively, a general concept, that can be either a basic concept or its negation, and a general role, that can be either a basic role or its negation.
A DL-LiteR TBox T over a signature S is formed by a finite set of inclusion assertions of the form:
B v C
R v E where general concept expressions (resp. general role expressions) are allowed to occurs only on the right-hand side of the inclusion assertion. Intuitively, an assertion of the form B v C states that all instances of the basic concept B are also instances of the general concept C, whereas an assertion of the form R v E states that all instances of the basic role R are also instances of the general role E.
A DL-LiteR ABox A over a signature S is formed by a finite set of membership assertions on atomic concepts and roles, of the form:
A(a)
P (a; b) where a; b 2 Ni are constants denoting object (individuals) in the domain, A(a) states that the object denoted by the constant a is an instance of the atomic concept A, and P (a; b) states that the pair of objects identified by constants a and b is an instance of the atomic role P . Given a TBox T and an ABox A defined as above, a DL-LiteR knowledge base (KB) over a signature S is defined as the pair O = hT ; Ai.
The semantics of a DL-LiteR KB O = hT ; Ai is given in terms of firstorder interpretations. An interpretation I over a signature S is defined as a pair I = h I ; I i where I is a nonempty interpretation domain, and I is an interpretation function, that assigns to each concept C a subset CI of I , to each role R a binary relation RI over I , and to each individual a an element aI of I , according to the following rules: aI 2 AI P I
I I I
I (9R)I a j 9b: ha; bi 2 RI
Given a KB O = hT ; Ai over a signature S, and an interpretation I = I ; I over the same signature, then an inclusion assertion B v C (resp. R v E) in T is said to hold in I if and only if BI CI (resp. RI EI ), while a membership assertion A(a) (resp. P (a; b)) is said to hold in I if and only if aI 2 AI (resp. haI ; bI i 2 P I ). An interpretation I is a model for O, denoted as I j= O, if and only if it satisfies every inclusion assertion and every membership assertion in O. The set of all models of a KB is indicated as Mod (O) = fI j I j= Og. We use the same notation I j= T and Mod (T ) also when we refer only the TBox T . Conjunctive Queries over DL-LiteR. A conjunctive query (CQ) over a DL knowledge base is an open first-order logic formula of the form:
9~y:conj(~x; ~y)
where ~x are the free (or distinguished ) variables, and ~y are the existentially
quantified (or non-distinguished ) variables, and conj is a conjunction of atoms
over the signature of the knowledge base, each of the form A(z) or P (z; w), where
A is an atomic concept, P is an atomic role, and z, w are constants appearing in
A or variable names. A CQ that does not involve any free variable is called a
boolean CQ corresponding to a closed formula of first-order logic. Sometimes, it
is convenient to denote CQs using datalog notation [
conj(~x; ~y) where q(~x), called the head of the query, is a symbol that is not part of the signature of the KB, and conj (~x; ~y) is called the body of the query. Using this notation, variables in ~x appearing in the head of the query denote the free variables, while variables in ~y, that do not appear in the head of the query, are the non-distinguished variables, and are assumed to be implicitly existentially quantified. Moreover, conjunction in datalog notation is typically represented by separating atoms with a comma. Using datalog notation, a boolean CQ can be simply written as: q() conj(~y).
The semantics of a CQ are given in terms of answers : Given an interpretation I, the answers to a CQ 9~y:conj(~x; ~y) is given in terms of the assignments : V ars ! I from the free variables in ~x to the constants in I, such that, when substituted, make the formula true in I.
conjI = f (~x) j I; j= 9~y:conj(~x; ~y)g
The crucial characteristic of DL-LiteR ontologies is that they enable the
socalled Ontology-based Data Access [
While in this paper we do not consider directly query answering, we will exploit DL-LiteR nice computational features when reasoning on views. 3
In this section we describe an extension to the notion of DL-LiteR KB that includes views defined as conjunctive queries.
If O = hT ; Ai is a DL-LiteR KB over a signature S, a view V over O is defined as follows: where v is the name associated with the view V , and conj is a CQ over O with free variables ~x. As a notation, in what follows we will indicate with name(V ) the corresponding view symbol v associated with V , with def (V ) the corresponding conjunctive query 9~y:conj(~x; ~y) associated with V , and with arity(V ) the arity of the view V , coinciding with the number of free variables ~x.
Now, if Nv = fv1; : : : ; vng is a finite set of view names, where each vi is a symbol not appearing in S, and V = fV1; V2; : : : ; Vng is a set of views over O, where each Vi 2 V is defined as follows:
Vi = hvi; 9~y:conji(~x; ~y)i then Ov = hT ; A; Vi is called a view-enriched knowledge base over the signature Sv = hNc; Nr; Ni; Nvi.
For convenience, with a little abuse of notation, for view Vi we will sometimes use the abbreviated form vi(~x) conji(~x; ~y).
Example 2. Let’s consider the following ontology, composed by:
T = fStudent v Person;
A = fStudent(john);
LivesIn(john; london);
Then we can introduce a view V = fV1g as follows:
V1 = hPersonCountry; 9y:Person(x1) ^ LivesIn(x1; y) ^ LocatedIn(y; x2)i name(V1) = PersonCountry arity(V1) = 2 def (V1) = 9y:Person(x1) ^ LivesIn(x1; y) ^ LocatedIn(y; x2) The abbreviated form for the view V1 is:
In order to define the semantics for Ov, we need to provide the semantics for the views in V. Thus, starting from the notion of interpretation as described in Section 2, we extend the interpretation function to views as follows: viI = conjiI = f (~x) j I; j= 9~y:conj(~x; ~y)g that is, the interpretation of a view vi is equivalent to the assignments that make the corresponding formula conji true in I. Notice that by adopting this definition, such views act as a conservative extension to the KB language.
Example 3. An interpretation I that satisfies the ontology in the example above is the following:
I = fj; k; l; mg
PersonI = fj; mg
StudentI = fjg ProfessorI = fmg
CityI = flg CountryI = fkg
LivesInI = fhj; lig LocatedInI = fhl; kig johnI = j maryI = m londonI = l ukI = k Consider that the query def (V1) = 9y:Person(x) ^ LivesIn(x; y) ^ LocatedIn(y; z) is evaluated as (def (V1))I = fhj; kig, and this evaluation is assigned to name(V1) = PersonCountry, hence, PersonCountryI = fhj; kig. 4
We now proceed in defining a set of reasoning services in DL-LiteR that are of interest when taking into account views as defined in Section 3. In particular, we are interested in the following reasoning tasks: – View consistency: Given a TBox T and a view V , defined as:
V = hv; 9~y:conj(~x; ~y)i we are interested in checking whether V is consistent w.r.t. T , denoted as V 6=T ;. In other words, we want to know if there exists an interpretation I such that I j= T , and vI 6= ;.
Example 4. Consider the TBox from Example 2, and the view V1:
it is easy to see that this view is consistent with T . Indeed the interpretation I in Example 3 is a model of T for which the interpretation of PersonCountry is non-empty. However, if we consider for example a view V2 defined as: then it is immediate to see that this view must be empty in every possible model of T since the TBox assertion Student v :Professor implies that their intersection is empty in every model of T , and hence Student(x1) ^ Professor(x1) is false for every assignment of x1 in every model of T . – View containment: Given a TBox T and two views V1, V2, where arity(V1) = arity(V2), defined as:
V1 = hv1; 9y~1:conj1(~x; y~1)i
V2 = hv2; 9y~2:conj2(~x; y~2)i we are interested in checking whether v1 is contained in v2, denoted as V1 T V2. In other words, we are interested in checking whether v1I v2I , for every interpretation I that is a model of T .
Example 5. Consider again the TBox T from Example 2, and the views V1 and V2 defined respectively as follows: it follows from the TBox axioms that V2 must be contained in V1 in every possible model of T since the TBox contains the assertion Student v Person. – View disjointness: Given a TBox T and two views V1, V2 where arity(V1) = arity(V2), defined as:
V1 = hv1; 9y~1:conj1(~x; y~1)i
V2 = hv2; 9y~2:conj2(~x; y~2)i we are interested in checking whether v1 is disjoint from v2, denoted as V1\V2 =T ;. In other words, we are interested in checking whether v1I \v2I = ;, for every interpretation I that is a model of T .
Example 6. Consider once more the TBox T from Example 2, and the views V1 and V2 defined respectively as follows:
we have that V1 and V2 must be disjoint in every possible model of T since Student and Professor are disjoint in T . 4.1
Checking View Consistency We show how view consistency can be reduced to knowledge base satisfiability. To do so, we introduce the notion of canonical ABox Aq of a boolean CQ q. Definition 1. Given a boolean conjunctive query q, defined as 9~y:conj(~y), the canonical ABox Aq for q is formed by the set of membership assertions as follows: – For each variable y in q we include a new constant cy in the signature. – One membership assertion A(t^) for each atom of the form A(t) 2 9~y:conj(~y), where t^ = c if t is a constant c, and t^ = cy if t is a variable y. – One membership assertion P (t^1; t^2) for each atom of the form P (t1; t2) 2 9~y:conj(~y), where t^i = c if ti is a constant c, and t^i = cy if ti is a variable y.
Using the canonical ABox of a view V = hv; 9~y:conj(~x; ~y)i, we can check consistency v 6=T ; by applying the boolean procedure ViewConsistency(T ; V ), defined as follows: 1. Freeze the free variables ~x, by replacing them with fresh constants ~a. Notice that when we replace the free variables ~x in 9~y:conj(~x; ~y), we obtain a boolean query v~a of the form 9~y:conj(~a; ~y). 2. Compute the canonical ABox Av~a of 9~y:conj(~a; ~y). 3. Return true iff the KB hT ; Av~a i is consistent.
Theorem 1. Let T be a DL-LiteR TBox, and V be a view, V =6T ; iff ViewConsistency(T ; V ) evaluates to true.
Proof. (() Let V = hv; 9~y:conj(~x; ~y)i. By definition ViewConsistency(T ; V ) returns true iff hT ; Av~a i is satisfiable. This means that there exists an interpretation I such that I j= hT i; Av~a . Then the query 9~y:conj(~a; ~y) evaluates to true in I. Notice that 9~y:conj(~a; ~y) is obtained from 9~y:conj(~x; ~y) by freezing the free variables ~x with fresh constants ~a. Thus, if we consider the assignment such that (~x) = ~aI we have that I; j= 9~y:conj(~x; ~y), hence, vI = f (~x)g and hence V is consistent.
()) If there exists an interpretation I for which vI 6= ;, then there exists an assignment from the free variables ~x such that I; j= 9~y:conj(~x; ~y). Moreover, considering the existentially quantified variables, there exists an assignment 0 such that I; 0 j= conj(~x; ~y). Let us introduce fresh constants ~a for ~x and ~b for ~y and extend the interpretation I to I’ that interprets these fresh constants as ~aI0 = 0(~x) and ~bI0 = 0(~y). Then we immediately get that I0 is such that I0 j= hT ; Av~a i, hence hT ; Av~a i is satisfiable. tu
Considering the complexity of KB consistency in DL-LiteR, it is immediate to assess the complexity of view consistency.
Theorem 2. Let T be a DL-LiteR TBox, and V be a view, checking whether V 6=T ; is in PTime in T , and AC0 in def (V ). 4.2
Checking View Containment We now show how view containment can be reduced to query answering. We will again make use of the canonical ABox of a view, as defined above. Consider two views, V1 = hv1; 9y~1:conj1(~x; y~1)i and V2 = hv2; 9y~2:conj2(~x; y~2)i, we can check containment V1 T V2, by applying the boolean procedure ViewContainment(T ; V1; V2), defined as follows: 1. Freeze the free variables ~x, by replacing them with fresh constants ~a. Notice that we obtain two boolean queries vi;~a of the form 9~y:conji(~a; ~y). 2. Compute the canonical ABox Av1;~a of v1;~a. 3. Return T ; Av1;~a j= v2;~a (note that v2;~a is a boolean query).
Theorem 3. Let T be a DL-LiteR TBox, and V1, V2 be two views of the same arity, then V1 T V2 iff ViewContainment(T ; V1; V2) evaluates to true. Proof. ()) If V1 T V2, then for every interpretation I that is a model of T , we have that v1I v2I . Let’s now consider the boolean queries v1;~a; v2;~a, obtained by freezing the variables ~x. It is easy to see that, by construction, T ; Av1;~a j= v1;~a is always true. Since we know that v1I v2I , we can conclude also that T ; Av1;~a j= v2;~a. (() If T ; Av1;~a j= v2;~a, then by applying the deduction theorem we have that T j= ^A2Av1;~a A =) v2;~a but ^A2Av1;~a A is v1;~a, hence we have T j= v1;~a =) v2;~a. That is, for every model I0 of T extended with the interpretation of the fresh constants ~a, we have that v1I;0~a v2I;0~a. If we now replace the fresh constants with variables we get that for every model I of T and every assignment of the free variables ~x, we have I; j= 9y~1:conj1(~x; y~1) implies I; j= 9y~2:conj2(~x; y~1). Hence the claim. tu
Considering the complexity of query answering in DL-LiteR, it is immediate to assess the complexity of view containment.
Theorem 4. Let T be a DL-LiteR TBox, and V1, V2 be two views of the same arity, checking whether V1 T V2 is in PTime in T , AC0 in def (V1), and NP in def (V2). 4.3
Checking View Disjointness In this section we show how view disjointness can be reduced to KB satisfiability. Consider two views, V1 = hv1; 9y~1:conj1(~x; y~1)i and V2 = hv2; 9y~2:conj2(~x; y~2)i, we can check disjointness V1 \ V2 =T ;, by applying the boolean procedure ViewDisjointness(T ; V1; V2), defined as follows: 1. Freeze the free variables ~x, by replacing them with fresh constants ~a. Notice that we obtain two boolean queries vi;~a of the form 9~y:conji(~a; ~y). 2. Compute the canonical ABoxes Av1;~a of v1;~a and Av2;~a of v2;~a. 3. Return true iff T ; Av1;~a [ Av2;~a is inconsistent.
Theorem 5. Let T be a DL-LiteR TBox, and V1, V2 be two views of the same arity, then V1 \ V2 =T ; iff ViewDisjointness(T ; V1; V2) evaluates to true. Proof. From the definition of view disjointness we have that, for every model I of T , V1\V2 =T ; if and only if v1I \v2I = (9y~1:conj1(~x; y~1))I \(9y~2:conj2(~x; y~2))I = (9y~1; y~2: (conj1(~x; y~1) ^ conj2(~x; y~2)))I = ;, that is, the conjunction of def (V1) and def (V2) is inconsistent w.r.t. T . Moreover, it is easy to see that the canonical ABox of the conjunction of def (V1) and def (V2), after replacing the free variables with fresh constants ~a is equal to Av1;~a [ Av2;~a . Hence, we can apply the same reasoning that we adopted for view consistency, and get the thesis. tu
Considering the complexity of KB consistency in DL-LiteR, it is immediate to assess the complexity of view disjointness.
Theorem 6. Let T be a DL-LiteR TBox, and V1, V2 be two views of the same arity, then V1 ^ V2 =T ; is in PTime in T , and AC0 in def (V1) and def (V2).
Other Reasoning Services on Views Definitions By using the basic reasoning services introduced above, we can define more complex reasoning services on view definitions. Here we discuss a few of them.
We start with view classification, which is one of the key reasoning services
available in ontology-based systems. Classification consists typically in computing
the hierarchical representation of the subsumption (“is-a”) relation between the
concepts in the ontology as logical consequences of the TBox assertions [
Classification can be extended to views. View classification corresponds to systematically checking whether V1 T V2 for all views in V. This is of particular interest to understand if a certain view can be used for approximating another one without actually computing the latter, for example.
It is also of interest to check how unary views are classified w.r.t. concepts by systematically checking whether V T VA and VA T V for all unary views and atomic concepts A, where VA is the trivial unary view VA = hvA; A(x)i. In this way we can understand how unary view relate to the concepts in the ontology. Note that a similar classification can be done with binary views and roles.
Finally, we can also check containment and disjointness w.r.t. to projections over views. One interesting use of this possibility is to actually type each component of a view with the most specific subsumer and subsumee atomic concept to understand which concepts an n-ary view relates to. 5
We have presented a proposal for enriching Description Logic knowledge bases
with views. Our paper can be seen as a first step in a path towards a complete
approach to the management of views in Description Logic and in Ontology-Based
Data Access systems. There are many interesting directions to explore following
the path. Probably, the most relevant is the introduction of views defined using
epistemic operators in the body, in the spirit of [