In this paper we propose a solution that combines the advantages of an ontology speci cation language, having powerful rule-based reasoning capabilities, with the possibility to e ciently exploit large (and, often already existent) enterprise databases. In particular, we allow to \upgrade" existing databases to an ontology for building a uni ed view of the enterprise information. Databases are kept and the existing applications can still work on them, but the user can bene t of the new ontological view of the data, and exploit powerful reasoning and information integration services, including: problem-solving, consistency checking, and consistent query answering. Importantly, powerful rule-based reasoning can be carried out in mass-memory allowing to deal also with data-intensive applications.
experts. Moreover, (ii) the obtained speci cation must incorporate the knowledge
(mainly regarding concept instances) already present in the enterprise information
systems. This knowledge is often stored in large (relational) database systems, and
loading it again in the ontologies may be unpractical or even unfeasible. This
happens because of the large amount of data to deal with, but also since databases
have to keep their autonomy (considering that many applications work on them).
In addition, when data residing in several autonomous sources are combined in a
uni ed view, inconsistency problems may arise [
In this paper we describe a solution that combines the advantages of an ontology representation language (i.e., high expressive power and clean representation of data) having powerful rule-based reasoning features, with the capability to efciently exploit large (and, often already existent) enterprise databases. Basically, if we are given some existing databases, we can analyze their schema and try to recognize both entities and relationships they store. This information is exploited for \upgrading" the database to an ontology. Here, ontology instances are \virtually" speci ed (i.e. they are linked, not imported) by means of special logic rules which de ne a mapping from the data in the database to the ontology. The result is a uni ed ontological speci cation of the enterprise information that can be employed, for browsing, editing and advanced reasoning. Moreover, possible inconsistent information obtained by merging several databases is dealt with by adopting data-integration techniques.
We developed these solutions in OntoDLV [3{5], a system that implements a
powerful logic-based ontology representation language, called OntoDLP, which is
an extension of (disjunctive) Answer Set Programming [6{8] (ASP) with all the
main ontology constructs including classes, inheritance, relations, and axioms.1
OntoDLP combines in a natural way the modeling power of ontologies with a
powerful \rule-based" language allowing for disjunction in rule heads and nonmonotonic
negation in rule bodies. In general, disjunctive ASP, and thus OntoDLP, can
represent every problem in the complexity class 2P and 2P (under brave and cautious
reasoning, respectively) [
Summarizing, the main contributions of this paper are: { an extension of OntoDLP by suitable constructs, called virtual class and virtual relation, which allows one to specify the extensions of ontology concepts/relations by using data from existing relational databases; { the design of a rewriting technique for implementing Consistent Query Answering (CQA) [2, 10{13] in OntoDLV. CQA allows for obtaining as much consistent information as possible from queries, in case of global inconsistent information.
Moreover, we e ciently implemented the proposed extensions in the OntoDLV
system by allowing for the evaluation of queries in mass memory. In this way,
OntoDLV can seamlessly provide to the users both an integrated ontological view
of the enterprise knowledge and e cient query processing on existing data sources.
1 The term \Answer Set Programming" was introduced by Vladimir Lifschitz in his
invited talk at ICLP'99 to denote the declarative programming paradigm originally
described in [
In this section we brie y overview OntoDLP, an ontology representation and
reasoning language which provides the most important ontological constructs and
combines them with the reasoning capabilities of ASP. For space limitations we
cannot include a detailed description of the language. The reader is referred to [
More in detail, the OntoDLP language includes, the most common ontology
constructs, such as: classes, relations, (multiple) inheritance; and the concept
of modular programming by means of reasoning modules. A class can be thought
of as a collection of individuals. An individual, or object, is any identi able entity
in the universe of discourse. Objects, also called class instances, are unambiguously
identi ed by their object-identi er (oid) and belong to a class. A class is de ned by
a name (which is unique) and an ordered list of typed attributes, identifying the
properties of its instances. Classes can be organized in a specialization hierarchy
(or data-type taxonomy) using the built-in is-a relation (multiple inheritance). The
following are examples of both class and instance declarations:
class person(name : string; father : person; mother : person; birthplace : place):
class employee isa fpersong(salary : integer ; boss : person):
john : person(name : \John"; father : jack ; mother : ann; birthplace : rome):
Relationships among objects are represented by means of relations, which, like
classes, are de ned by a (unique) name and an ordered list of attributes. As in
ASP, logic programs are sets of logic rules and constraints. However, OntoDLP
extends the de nition of logic atom by introducing class and relation predicates,
and complex terms (allowing for a direct access to object properties). Logic rules
can be exploited for de ning classes and relations when their instances can be
\derived" (or inferred) from the information already stated in an ontology. This kind
of intensional constructs are called Collection classes and Intensional Relations.
Basically, collection classes collect instances de ned by another class and perform
a re-classi cation based on some information which is already present in the
ontology; whereas, intentional relations are similar to (but more powerful of) database
views. Importantly, the programs (set of rules) de ning collection classes (and
intensional relations) must be normal and strati ed (see e.g., [
E : richEmployee(name : N ) : E : employee(name : N; salary : S); S > 1000000:g Moreover, OntoDLP allows for special logic expressions called axioms modeling sentences that are always true. Axioms provide a powerful mean for de ning/checking consistency of the speci cation (i.e., discard ontologies which are, somehow, contradictory or not compliant with the domain's intended perception). For example, we may enforce that a person cannot be father of himself by writing: : X : person(father : X ):
In addition to the ontology speci cation, OntoDLP provides powerful reasoning and querying capabilities by means of the language components reasoning modules and queries. In practice, a reasoning module is a disjunctive ASP program conceived to reason about the data described in an ontology. Reasoning modules are identi ed by a name and are de ned by a set of (possibly disjunctive) logic rules and integrity constraints; clearly, the rules of a module can access the information present in the ontology.
An important feature of the language is the possibility of asking conjunctive queries, that, in general, can involve both ontology entities and reasoning modules predicates. As an example, we ask for persons whose father is born in Rome as follows: X : person(father : person(birthplace : place(name : \Rome")))? 3
In this section we show how an existing database can be \upgraded" to an OntoDLP ontology. In particular, the new features of the language, called virtual classes and virtual relations, are described by exploiting the following example.
Suppose that a Banking Enterprise asks for building an ontology of its domain of interest. This request has the goal of obtaining a uniform view of the knowledge stored in the enterprise information system that is shared among all the enterprise branches.
The schema of the existing database of the enterprise is reported in Table 1.
The rst step that must be done is to reconstruct the semantics of the data stored
in this database. It is worth noting that, in general, a database schema is the
product of a previously-done modeling step on the domain of interest. Usually,
the result of this conceptual-design phase is a semantic data model that describes
the structure of the entities stored in the database. Likely, the database engineers
exploited the Entity-Relationship Model (ER-model) [
Suppose now that, we obtained the ER-model corresponding to the database
of Table 1. In particular, the corresponding ER diagram is shown in Figure 1.
From this diagram it is easy to recognize that the enterprise is organized into
branches, which are located into a given place and also have an asset and a unique
name. A bank customer is identi ed by its social-security number and, in
addition, the bank stores information about customer's name, street and living place.
Moreover, customers may have accounts and can take out loans. The bank o ers
two types of accounts: saving-accounts with an interest-rate, and checking-accounts
with a overdraft-amount. To each account is assigned a unique account-number,
and maintains last access date. Moreover, accounts can be held by more than one
2 Note that, the reverse-engineering task is not trivial, and even automatic methods may
fail to reconstruct the original semantics [
customer-city customer-name customer-street social-security
loan-branch loan-number
amount customer borrower
loan depositor Interest-rate account-number
balance account
isa savings-account checking-account payment-number payment-date overdraft-amount branch
assets branch-city loan-payments payment payment-amount customer, and obviously one customer can have various accounts (depositors). Note that, in the case of accounts, the ER-model exploits specialization/generalization construct. A loan is identi ed by a unique loan-number and, as well as accounts, can be held by several customers (borrowers). In addition, the bank keeps track of the loan amount and payments and also of the branch at the loan originates. For each payment the bank records the date and the amount; for a speci c loan a payment-number univocally identi es a particular payment.
All this information represents a good starting point for de ning an ontology that describes the banking enterprise domain.3 As a matter of fact, we can easily exploit it both for identifying ontology concepts and for detecting the database tables which store data about ontology instances. In practice, we can \upgrade" the banking database to a banking ontology by creating an OntoDLP (base) class, with name c, for each concept c in the domain; and by exploiting logic rules that specify a mapping between class c and its instances \stored" in the database. A class c de ned by means of mapping rules is called virtual, because its instances come from an external source; but, as far as reasoning and querying are concerned they are like any other class directly speci ed in OntoDLP. More in detail, a virtual class is de ned by using the keywords virtual class followed by the class name, and by the speci cation of class attributes; then, instances are de ned by means of rules containing special atoms that allows for accessing the source database.
First of all, external data sources are speci ed directly in OntoDLP, as instances of the built-in class dbSource as follows: db1 : dbSource(connectionURI : \http : ==db:banking:com"; user : \myUser "; password : \myPsw "): Here, the object identi er db1 is used to identify the enterprise database. Note that such a mechanism allows to build an ontology starting from one or more databases, just specifying more dbSources; moreover, this source identi cation strategy is sufciently general to be (in the future) extended also to access other kind of sources 3 Note also that, our goal is not to provide a tool for reasoning on ER schemata; instead, we allow the ontology engineer to design and \populate" an ontology that exploits data about the instances that is stored in relational databases. beside databases. Now, given the source identi er for the enterprise database, we model the branch entity as follows: virtual class branch(name : string; city : string; assets : integer )f f (BN ) : branch(name : BN ; city : BC ; assets : A) :
branch@db1(branch-name : BN ; branch-city : BC ; assets : A):g
The rule acts as mapping between the data contained in table branch and the instances of class branch by exploiting a new type of atom, called sourced atom. A sourced atoms consist of a name (branch), that identi es a table "at" (@ ) a speci c database source (db1 ), and a list of attributes (that match the table schema). Attributes can be lled in by constants or variables.
Note that, whereas databases store values, ontologies manage instances (which are not values) that are uniquely identi ed by oids.4 We provided a speci c solution for facing with this problem, in which values appearing in the databases are kept, someway, distinct from object identi ers appearing in the ontology. In particular, functional object identi ers, suitably built from database values, are exploited for identifying ontology instaces. In our example, the head of the mapping rule contains the functional term f (BN ), that builds, for each instance of branch, a functional object identi er composed of the functor f containing the value of the name attribute stored in the table branch. In practice, if the branch table stores a tuple ("Spagna","Rome", 1000000), then the associated instance in the ontology will be: f ("Spagna") : branch(name : "Spagna"; city : "Rome"; assets : 1000000 ). In this way, the functional object identi er f ("Spagna") is built from the data value "Spagna", keeping the data alphabet distinct from the one of object identi ers.
Note that name is a key for table branch. Because object identi ers in
OntoDLP uniquely identify instances, it is preferable to exploit only keys for de ning
functional object identi ers. This simple policy ensures that we will obtain an
admissible ontology whenever the source database is unique and consistent; whereas,
if more than one source database is exploited for de ning ontology entities, some
admissibility constraint for the ontology schema (like e.g. referential integrity
constraints, unicity of object identi ers, etc. see [
We say that a virtual class declared by means of sourced atoms is in logical notation. We provided also an alternative notation for accessing database tables, called SQL notation. In particular, the virtual class branch can be equivalently de ned as follows: virtual class branch(name : string; city : string; assets : integer )f f (BN ) : branch(name : BN ; city : BC ; assets : A) : [db1; "SELECT branch-name AS BN ; branch-city AS BC ; assets AS A
F ROM branch "]g
Here, a special atom which contains an SQL query is used in the place of a sourced one. Formally, a SQL atom consists of a pair [db object identi er, sql query] enclosed in square brackets. The db object identi er picks out the database on which the sql query will be performed.
Consider now the customer entity. Also here, we de ne a virtual class as follows:
4 This is the well-known impedance mismatch problem [
virtual class customer (ssn : string; name : string; street : string; city : string)f c(SSN ) : customer (ssn : SSN ; name : N ; street : S ; city : C ) : customer@db1(social -security : SSN ; customer -name : N ; customer -street : S ; customer -city : C ):g The functional term c(SSN ) is used here in order to assign to each instance a suitable functional object identi er built on the social -security attribute value. Note that, a fresh functor is used for each virtual class. In this way, functional object identi ers belonging to di erent classes are kept distinct. In our example, the customer and the branch class instances are made disjoint by using functor f and c, respectively.
Following the same methodology, we de ne a virtual class for the loan entity: virtual class loan(number : integer ; loaner : branch; amount : integer )f l(N ) : loan(number : N ; loaner : f (L); amount : A) :
loan@db1(loan-number : N ; branch-name : L; amount : A):g
Note that, the loan class has an attribute (loaner ) of type branch. In this case, functional terms are carefully employed in order to maintain referential integrity. As shown above, the mapping uses the functional term f (L) to build values for the loaner attribute. Basically, since the branch class use the functor f to build its object identi ers, then we also use the same functor where an object identi er of branch is expected.
In the following, we exploit the same idea to model the payment entity: virtual class payment(ref -loan : loan; number : integer ; payDate : date;
amount : integer )f p(l(L); N ) : payment(ref -loan : l (L); number : N ; payDate : D; amount : A) : payment@db1(loan-number : L; payment-number : N ; payment-date : D; payment-amount : A):g
Also in this case we deal with referential integrity constraints by using a proper functional term l(L) where a loan object identi er is expected (ref -loan attribute); moreover, since payments are identi ed by a pair (payment-number, relative loan) each instance of payment will be identi ed by a functional object identi er with two arguments: one of these is a functional object identi er of type loan; and, the other is the loan number.
As far as accounts are concerned, we know from the ER-model that they are specialized in two types: saving-accounts and checking-accounts. This situation can be easily dealt with by exploiting inheritance (see Section 2). Thus, we rst de ne a virtual class named account as follows:
virtual class account(number : integer ; balance : integer ): and, then, we provide two virtual classes, savingAccount and checkingAccount, namely, which are declared to be both subclasses of account : virtual class savingAccount isa faccountg(interestRate : integer )f acc(N ) : savingAccount (number : N ; balance : B ; interestRate : I ) :
saving-account @db1(account-number : N ; balance : L; interest-rate : I ):g virtual class checkingAccount isa faccountg(overdraft : integer )f acc(N ) : checkingAccount (number : N ; balance : B ; overdraft : I ) :
checking-account @db1(account-number : N ; balance : L; overdraft-amount : I ):g In order to conclude our \upgrading" process, we have to model the relationships holding among the concepts in the banking domain. To deal with this problem, OntoDLP allows for de ning also virtual relations. For instance, the ER diagram of Figure 1 shows that customers and loans are in relationship through borrower and depositor. Hence, we de ne two virtual relations as follows: virtual relation borrower (cust : customer ; loan : loan)f borrower (cust : c(C ); loan : l (L)) :
borrower@db1(customer -social -sec : C ; loan-number : L):g virtual relation depositor (cust : customer ; account : account; ; lastAccess : date)f depositor (cust : c(C ); account : acc(A); lastAccess : D) :
depositor@db1(customer -social -sec : C ; account-number : A; access-date : d ):g It is worth noting that a virtual relation di ers from a virtual class mainly because tuples are not equipped with object identi ers. 4
In previous sections we showed how a existing database can be upgraded to an
OntoDLP ontology. Basically, the instances of ontology entities are virtually
populated by means of special logic rules, which act as a mapping from the information
stored in database tables to ontology instances. In general, the ontology engineer
can obtain the data from several source databases, which are combined in a uni ed
ontological view. This is a typical data integration scenario [
In the eld of data-integration several notions of CQA have been proposed (see [
More formally, given an OntoDLP ontology schema and a set A of axioms or
integrity constraints, let O and Or be two ontology instances7, we say that Or is a
repair [
Note that, as shown in [
In the next Section, we describe how the new features were implemented and in particular we show how to build an ASP program that implements CQA for the above mentioned kind of axioms in the OntoDLV system. 5
In this section, we rst brie y describe the OntoDLV system [
OntoDLV. OntoDLV is a complete framework that allows one to develop
ontology-based applications. Thanks to a user-friendly visual environment,
ontology engineers can create, modify, navigate, query ontologies, as well as perform
advanced reasoning on them. An advanced persistency manager allows one to store
ontologies transparently both in text les and internal relational databases; while
powerful type-cheking routines are able to analyze ontology speci cations and
single out consistency problems. All the system features are made available to software
6 It is worth noting that, in relevant cases like denial constraints, query results coincide
for both correct and complete information assumptions.
7 Here ontology instance refers to the unique set of ground instances modeled by an
ontology speci cation [
In the rst, the relevant information is extracted from the sources by exploiting SQL queries and, is stored into the internal data structures (basically, instances are \imported" and stored by exploiting the persistency manager). In the latter, queries are performed directly at the sources.
The o -line mode is preferable when one wants to migrate the database into an ontology, or when parts of a proprietary database are one-time granted to third parties. In fact, once the import is done, the source database can be disconnected, since instances are stored into the OntoDLV persistency manager. Obviously, depending on database size, the o -line modality could be time-consuming or even unpractical. In addition, one may want to keep the information in the original database (which is accessed by legacy applications), in order to deal with \fresh" information. In those cases, the on-line mode is preferable.
In both on-line and o -line modes, queries on the ontology are performed
directly on mass-memory by exploiting DLVDB [
Importantly, in order to avoid the materialization of the entire ontology for
evaluating an input query, an \unfolding" technique [
As an example, if we ask for the instances of virtual class branch of Section 3 the following mapping directive for DLVDB is generated by the rewriter procedure: USEDB \http : ==db:banking :com":myUser:myPsw.
USE branch (branch-name, branch-city , assets) MAPTO branchPredicate (varchar,varchar,integer ).
The above directive speci es the database (USEDB) on which the SQL query will be performed (may be the source database). Moreover, the listed attributes of the table branch (USE) are mapped (MAPTO) on the logic predicate branchPredicate. In this case, branchPredicate is the predicate name used internally to rewrite in standard ASP the class branch.
Implementation of CQA. In order to implement consistent query answering we developed a new procedure in the OntoDLV system. Given an ontology O, this procedure takes as input a conjunctive query Q, and a set of integrity constraints A and builds both an ASP program cqa and a query Qcqa, such that: Q is consistently true in O w.r.t. A i Qcqa is true in every answer set of cqa, in symbols: cqa j=c Qcqa (in other words Qcqa is cautious consequence of cqa).
Note that, this can be done in our settings since CQA belongs to the 2P
complexity class [
It is worth noting that, the algorithm that builds cqa is evaluated in OntoDLV
together with the ASP program produced by the OntoDLV rewriter. Since the
rewriting process suitably replaces OntoDLP atoms by standard ASP atoms [
a (t) : a(t); not a(t): 3- for all constraints of the form (ii) in A, insert the following rules in a1(t) : a1(t1); not a2(t): 4- for each a(t) occurring in some axiom of A insert into ar(t) : a (t); not a(t); not a(t): cqa a rule:
cqa: cqa: cqa the following rules: 8 Axioms of type (ii) can model inclusion dependencies under the assumption of complete sources, where facts that are not in the ontology are considered to be false. 9 Informally, a set of inclusion dependencies is acyclic if no attribute of a relation R transitively depends (w.r.t. inclusion dependencies) on an attribute of the same R. Finally, Qcqa is built from Q by replacing atoms a(t) by ar(t), whenever a(t) occurs in both Q and some constraint in A. The disjunctive rules (step 1) guess atoms to be cancelled (step 2) for satisfying denial constraints, and rules generated by step 3, remove atoms violating also referential integrity constraints; eventually, step 4 builds repaired relations. Note that the minimality of answer sets guarantees that deletions are minimized.
As an example consider two relations m(code), and e(code,name). Suppose that the axioms are : e(X; Y ); e(X; Z); Y <> Z:, : e(X; Y ); e(Z; Y ); X <> Z: and : m(X); not code(X), where code(X) : e(X; Y ): requiring that both code and name are keys for e and m[code] e[code]. Suppose now that, the following facts are true e(1; a); e(2; b); e(2; a); m(1); m(2); it can be easily veri ed that all the axioms are violated and m(2) is consistently true. The program obtained by rewriting the constraints is: e(X; Y ) _ e(X; Z) : e(X; Y ); e(X; Z); Y <> Z: e(X; Y ) _ e(Z; Y ) : e(X; Y ); e(Z; Y ); X <> Z: e (X; Y ) : e(X; Y ); not e(X; Y ): m (X) : code (X) : code(X); not code(X): m(M ) : mr(X) : m (X); not m(X); not m(X): er(X; Y ) : e (X; Y ); not e(X; Y ); not e(X; Y ): m(X); not m(X): m (M ); not code (M ): and the two answer sets of this program both contain mr(2), thus, m(2)? is derived to be consistently true. 6
As a matter of fact, the problem of linking ontology to databases is not new [
Another related system is MASTRO [
Finally, since OntoDLP can be seen as an extension of disjunctive datalog with
object-oriented constructs, our work is related also to the techniques proposed in
the eld of object-oriented databases for mapping relational data to object-views
(see e.g. [
In this paper we proposed a solution that allows one to \upgrade" one or more existing enterprise relational databases to an ontology. The result is the natural combination of the advantages of an ontology language (clean high-level view of the information and powerful reasoning capabilities) with the e cient exploitation of large already-existent databases.
This was obtained by extending the OntoDLV language and system. In
particular, we implemented virtual classes and virtual relations, two new modeling
constructs that allow the knowledge engineer to de ne the instances of an ontology
by means of special logic rules, which act as a mapping from the information stored
in database tables to concept instances. Moreover, in order to deal with consistency
problems that may arise when data residing in di erent sources are combined in
a uni ed ontological view [
Ongoing work concerns the analysis of performances of our system on real-life and large scale databases.