SQOWL2 is a compiler which allows an RDBMS to support sound reasoning of SROIQ(D) description logics, by implementing ontologies expressed in the OWL 2 DL language as a combination of tables and triggers in the RDBMS. The reasoning process is divided into two phases of classification of the T-Box and type inference of the A-Box. SQOWL2 establishes a relational schema based on classification completed using the Pellet reasoner, and performs type inference by using SQL triggers. SQOWL2 supports type inference over all OWL 2 DL constructs, and supports a more conventional relational schemas, rather than naively mapping OWL classes and properties to relational tables with one and two columns. Moreover, SQOWL2 is a transactional reasoning system (with full ACID properties), since the results of reasoning are available within the same transaction as that in which the base data of the reasoning was inserted.
The most common storage method used in mainstream data processing is to use a relational database management system (RDBMS), which have a number of well known and understood properties. One key property is the ACID property of transactions [6], which in outline, states that a group of operations grouped together into a transaction should occur as an atomic action, and for which once the results are reported, they are durable after a system crash. In the context of reasoning on ontologies, the notion of transactions may be naturally extended to the notion of transactional reasoning [12], where the results of reasoning derived from data changed by the database operations should be available as part of the atomic action of the transaction.
To illustrate the concept of transactional reasoning, consider the description logic rule Father ≡ Man " Parent. If the data about these classes were held in a RDBMS, and John was recorded as a Man, then if a transaction added that John was a Parent, then any query on the result of the transaction should also be able to view that John is a Father. However, most approaches to storing ontology data in an RDBMS will make the process of reasoning be detached from transaction processing of the data. Specifically, in our example, after the transaction that added John was a Parent, the database could be queried and find that he was not a Father until a separate process of reasoning had derived that fact. Hence we would say that these approaches do not support transactional reasoning.
Our work focuses on reasoners that support the OWL language, and in particular the OWL 2 DL version [13]. To achieve transactional reasoning, two approaches were identified in [12]: view based reasoning (VBR), where rules are used to derive the result of reasoning as each query is executed over the database, and trigger based reasoning (TBR) where triggers (active rules) are used to materialise the result of reasoning at data insert time, and queries simply read the materialised views. As discussed in [12], the advantages and disadvantages of using views or materialised views are well known, and each serve different real world requirements. In the context of reasoning, one specific advantage of the TBR approach is that reasoning is incremental, and supports very fast query processing. Examples of VBR approaches include DLDB2 [14] and DBOWL [2], and of TBR include SQOWL [11]. This paper describes a substantial improvement on SQOWL, called SQOWL2.
To illustrate the issues addressed in this paper, we introduce the family ontology1. It uses almost all the new OWL 2 features [7]. The family ontology includes the following OWL 2 DL rules of T-Box (which contain classes that by convention begin with upper case letters, and properties which by convention start with lower case letters):
Father " Mother $ ⊥ (
(18), (19) and (20), respectively. Subsumption, disjointness, self restriction and property chains can be described by rule (21), (22), (23) and (24), respectively.
In addition to the T-Box, data in an OWL 2 DL ontology is called the A-Box, and is stated as grounded predicates over the classes or properties of the T-Box. Examples of such data in the family ontology are:
hasHusband(Mary, John) (27)
hasParent(Lewis, Albert) (28)
hasParent(Albert, Alex) (29)
In the SQOWL approach presented in [11], a very simple process was used where the OWL classes and properties are mapped to unary and binary relations, as shown in Example 1.
Man(id)
The SQOWL approach then allowed the use of any OWL reasoner such as
FacT++ [3] or Pellet [15] to perform classification of the T-Box, which was
then used to build trigger rules over the relational schema. The type inference
over the A-Box then occurs as data is inserted into the RDBMS by the execution
of the triggers. For example, in classification, from rules (
From this classified schema, triggers were generated. For example, taking the rules (30)–(32) above, we can derive four logical triggers (which we will detail the syntax of in Section 3.2) of the form: when +Father(x) then Man(x), when +Parent(x) if Man(x) then Father(x) when +Father(x) then Parent(x), when +Man(x) if Parent(x) then Father(x)
The SQOWL2 approach presented in this paper provides the following significant improvements over the original SQOWL approach in [11]. 1. SQOWL2 supports sound reasoning of the more recent OWL 2 DL standard, as opposed to OWL 1 DL support by SQOWL. In particular SQOWL2 supports keys, property chains, and reflexive properties (Type inference of qualified cardinality restrictions is introduced in [11]). 2. SQOWL2 gathers together all the reasoning rules associated with a particular concept into a single trigger statement, rather than producing a separate trigger statement per rule. Not only is this more efficient, but also in allows SQOWL2 to generate triggers for those DBMS such as Microsoft’s SQL Server that only support one trigger (of a given type) per table. 3. SQOWL2 uses the fact (originally from [1]) that a property is functional to allow the property to be stored in the same table used to stored class that is the domain of the property. This results in SQL schemas that are like those one would produce via a conventional design process into 3NF schema, and will allow SQOWL2 to be adapted so that it can be used to generate triggers on top of existing relational schemas (as opposed to generating new schemas with associated triggers).
The remainder of the paper gives more detail of the operation and performance of SQOWL2. Section 2 gives an overall architecture of SQOWL2, which provides a complete system for building databases with triggers from specifications in OWL 2 DL. Section 3 describes the details of the process used in generating SQL triggers to implement the OWL 2 DL type inference process. Section 4 then evaluates SQOWL2 on how the SQOWL2 tool can be used, and its performance over some benchmark datasets. Finally, Section 5 compares SQOWL2 with several related systems, and is followed by a conclusion section. 2
SQOWL2 Architecture SQOWL2 uses this division of the OWL 2 DL reasoning process (classification of T-Box and type inference of A-Box) to build a reasoning system in several steps, the overall design for which is illustrated in Figure 1.
The T-Box (schema) from the ontology is then read using the OWL API [8]. Any A-Box (data) is also read and held until after the relational schema and triggers have been created. In the current prototype, classification of the T-Box (i.e. reasoning over the schema) is performed using Pellet, though in principle any other reasoner could be used. The revised T-Box is then used to (a) produce a relational schema, and (b) define triggers over that schema, which will perform the reasoning outlined in the previous section.
Once the schema and triggers have been created, the relational database is now capable of performing type inference over the A-Box (i.e. reasoning over the data). If the OWL 2 DL ontology contained an A-Box, then this is inserted into database as the last phase of the SQOWL2 execution. Then the relational database becomes a free standing type inference system, when inserts made using SQL resulting in a type inference being performed, and derived data being inserted into the database. 3
From OWL 2 DL to Triggers We now outline in more detail the reasoning process followed by SQOWL2 in first generating a database schema, then deriving logical triggers over that schema. For reasons of space we do not detail the mapping of the triggers in SQL statements, but this process is very straightforward. 3.1
Building a traditional RDB schema SQOWL2 builds the relational database schema in two stages, which depends on the classification results from Pellet. The first step builds a canonical relational schema (Example 1), where each class maps to a unary relation, and each property to a binary relation (i.e. a class is mapped to a relational table with one column, and a property is mapped to a relational table with two columns). Moreover, subclass relationships should be mapped as foreign keys.
The second stage is to map the canonical schema to a physical relational schema, by taking account of functional properties (cardinality restriction is no more than one) and key properties (properties that together can uniquely identify an object) and in the OWL 2 DL ontology. In general, if a class C(x) has n functional properties (or key properties): P1(x, y1), . . . , Pn(x, yn) that contain C as their domain, then we store the class and properties as a single table C(x, y1, ... . . . , yn).
For example, if hasHusband and hasSpouse are denoted as functional properties in the family ontology, and hence are not stored as separate tables, but instead are stored in the table representing the domain, giving the following modified schema as Example 2.
hasRelative(domain,range) fk
fk
hasGrandParent(domain,range) loves(domain,range)
fk
Mother(id)⇒fkParent(id) 3.2
Type inference by generating SQL triggers Type inference needs to occur every time a data value is inserted into the database schema, which is achieved by having SQL triggers invoke queries and updates after each insert. For example, rule (30) implies all instances in Father should also appear in Man. In this case, if data John is inserted into table Father, a trigger needs to exist to insert John to table Man.
SQL triggers are translated from constructors of OWL 2 DL ontologies according to logical triggers. The logical triggers are of the general form:
OWL 2 DL construct : ! when event if condition then action. where event identifies the insertion of a particular class or property in the database. There are two types of event: if event is prefixed with − then condition and action are executed before the insertion, whilst if event is prefixed with + then condition and action are executed after the insertion.
SQL before triggers (PL/pgSQL)/instead of triggers (Transact SQL) are used to implement − events, and after triggers, used for + events. The condition is a Datalog query over the database, and action is one of insert, ignore and reject.
One basic rule deals with the notion that because of the open world nature of reasoning, we might repeatedly infer the same fact, and thus we have to prevent duplicate updates to a table. This is implemented by the logical trigger: class: C ! when −C(x) if C(x) then ignore This means that when a value is inserted into a table, before the actual insert is done, a check is made to determine if the value is already present in the table, and if so, the insert is ignored.
Another simple logical trigger deals with subclass rules such as (30) and (31): subClassOf: C $ D ! when +C(x) if true then D(x) which ensures that any insert to a subclass is inferred to also be an insert to the superclass. Similarly, the logical trigger for subproperty rule such as (21) is: subPropertyOf: P $ Q ! when +P (x, y) if true then Q(x, y)
A new feature of OWL 2 DL (compared to OWL 1 DL) is the property chain, which allows for a property to be defined from the concatenation of two or more other properties. For example, one can define that a parent of a parent is a grandparent by rule (24). The logical trigger for a property chain (contains two subchain properties) is: propertyChain: P1 ◦ P2 $ P ! when +P1(x, y) if P2(y, z) then P (x, z) ! when +P2(y, z) if P1(x, y) then P (x, z) Hence in the first rule, an insert to the first property in the chain causes a check for matched data in the second property in the chain, and if found causes an insert to the chained property table. We also generalise the above logical trigger to handle the situation that a chain property contains n subchain properties: propertyChain: P1 ◦ . . . ◦ Pi ◦ . . . ◦ P!n $ P ! when +P1(x, y) if P2,n(y, z) then P (x, z)
! ! when +Pn(y, z) if P!1,n−1(x, y) then P (x, z)
! ! when +Pi(p, q) if P1,i−1(x, p), Pi+1,n(q, z) then P (x, z) 1<i<n ! where Pm,n(x, y) =
πPm.domain,Pn.range σPj.range=Pj+1.domain(Pm × . . . × Pn) m≤j<n Therefore, the first and second situations mean that if there is an insertion to the first or last subchain, the trigger will treat the remaining subchains as a join unit and search data matched inside the unit. The third scenario handles the insertion to the middle subchains (i.e. not the first or the last subchain) by creating two join units and then fetching matching data from them.
For example, in family ontology, rule (36) defines one subset of hasBrotherInLaw that:
hasSibling ◦ hasSpouse ◦ hasBrother $ hasBrotherInLaw (36)
John) to table Man, the logic trigger will infer a new insertion (Kate, Lewis) to table hasBrotherInLaw.
Also introduced in OWL 2 DL is the ability to define a reflexive property, an irreflexive property and a self restriction by allowing a special class Self to be used in the range of a property (that corresponds to class in the domain). The domain of a reflexive property is always the whole universe. For example, rule (17) states property hasRelative is reflexive in which anyone is a relative of them-self. The negative side of reflexivity is irreflexivity, which means no individual is related to itself by a irreflexive property, such as hasParent defined in rule (18). The logical triggers for reflexive & irreflexive properties are: reflexiveProperty: & $ ∃P.Self ! when +&(x) if ¬P (x, x) then P (x, x) irreflexiveProperty: & $ ¬∃P.Self ! when −P (x, x) if true then reject In the case of reflexive properties, since their domain is always the whole universe, each insert x in an ontology entails that (x, x) also needs to be inserted to this property table. In contrast, in irreflexive properties, tuples like (x, x) are not allowed to be inserted and should be rejected.
Compared with reflexive properties, self restriction means the domain is not always the whole universe. For example, rule (23) defines a new class Narcissist in which all individuals love (e.g. property loves) themselves (i.e. the reflexivity is limited only to Narcissist). The logical trigger for self restriction is: selfRestriction: C ≡ ∃P.Self ! when +P (x, y) if x = y, ¬C(x) then C(x) ! when +C(x) if ¬P (x, x) then P (x, x) This trigger enables that if a property tuple (x, x) is inserted to the self restricted property, the data x should also be inserted to the related class. Moreover, if there is an data x in the related class, the property tuple (x, x) should be inferred and inserted to the property.
In addition to the above new features, OWL 2 DL also improves its ability
of expressiveness by adding other constructors, such as disjoint union (rules (
disjointUnion: CN ≡ C1 # . . . # Cn, Ci " Cj $ ⊥ 1≤i,j≤n,i#=j ! when −Ci(x) 1≤i≤n if f oreach(1 ≤ j ≤ n, j -= i), ¬Cj (x) then Ci(x) if ¬CN (x) then CN (x).
asymmetricProperty: P " P− $ ⊥ ! when −P (x, y) if P (y, x) then reject The trigger for disjointUnion only allows insertion if the data which will be inserted to a class does not appear in its disjoint classes (the trigger for disjoint properties is in a similar way with properties). Moreover, in disjointUnion trigger, any inserted data which does not exist in the union class will be inserted to the union class. Furthermore, the asymmetricProperty trigger does not allow tuple (x, y) existing with its asymmetric tuple (y, x).
Note that if C(x, y1, . . . , yi, . . . , yn) is used in the physical relational schema to represent functional property P (x, yi) from the canonical relational schema, then all references to P (x, yi) in the rules are replaced by C(x, y1, . . . , yi, . . . , yn). For instance, if as illustrated in the previous subsection, properties hasHusband and hasSpouse are added as additional columns to table Woman and Person, respectively, then references to hasHusband and hasSpouse are changed to Woman and Person. 4
Evaluation of SQOWL2 The SQOWL2 system can be evaluated in three steps. Firstly, in order to show that the system is able to perform type inference over a large A-Box, three benchmark ontologies are loaded into SQOWL2, and the total load and reasoning times are reported. Secondly, in order to evaluate the reasoning completeness, we compare the reasoning performance between SQOWL2 and two Tableaux reasoners. Finally, we evaluate the performance of incremental consistency checking. 4.1
Execution times of SQOWL2 over Large A-Boxes
Three example ontologies have been used to test and benchmark SQOWL2. The
first ontology has been produced by us, called the family ontology, improved
from [7] and formed by amalgamating fragments from the OWL 2 standard,
together with an A-Box generator. The family ontology benchmark used in the
evaluation provides four different ontologies with increasing size of A-Box:
family(
The other two ontologies are the well known Lehigh University
Ontology Benchmark (LUBM) [4] and University Ontology Benchmark
(UOBM) [10]. To be more specific, LUBM(
SQOWL2 was used with Pellet for T-Box reasoning to produce tables and triggers on a Microsoft SQL Server 2005 database, on a machine with 8 cores, 2 Intel Xeon E5345 2.33GHz CPUs, and 8GB of memory. The performance results of type inference on family ontologies are shown in Figure 2. From the graphs, it can be seen that SQOWL2 is able to perform transactional reasoning at an average rate of 100 fact inserts per second for a 150,000 fact ontology, in the process inferring an additional 300,000 facts. Since the ontology is very small, the time taken for creating the database tables and triggers was only 0.6 seconds. (a) Type Inference Time
(b) Data Inference Amount
SQOWL2 were also tested against the LUBM and UOBM benchmarks. These two benchmarks contain only OWL 1 constructors; therefore, the benchmarks are essentially testing less complex reasoning. The performance of reasoning is shown in Table 1, from which is can be seen that SQOWL2 is able to process over 150 inserts per second on average.
Action LUBM UOBM Loading T-Box 1.43s 1.42s Classification 0.41s 0.64s Building DB schema 0.38s 0.77s Type inference 255.68s 1250.08s Data facts in A-Box 100,543 260,580
Facts in DB after reasoning 137,920 279,436 HermiT 1.3.6 and Pellet 2 are two Tableaux reasoners, which support reasoning over OWL 2 DL. We expect Tableaux reasoners to provide more complete results at the expense of execution time. To evaluate the reasoning efficiency and completeness of SQOWL2, we compare the performance results between SQOWL2 and Tableaux reasoners in two ways: time spent on reasoning and the amount of data after reasoning. The Wine ontology 2 is a more complicated OWL 1 DL ontology, but does not come with any data generator (just around 500 A-Box facts). In addition, a family ontology (family(0)) which contains a small A-Box (1491 A-Box facts) is also used to show the performance of SQOWL2. The comparison of reasoning (which includes classification and type inference)between SQOWL2 and Hermit & Pellet is illustrated in Figure 3. As expected, SQOWL2
takes less time, but shows a very high reasoning completeness level. For wine ontology, SQOWL2 only spent 10.2s on reasoning (Hermit uses 21.6s), but generates 2277 A-Box instances which is 100% of the results found by Hermit. For family ontology, the reasoning is more efficient and the completeness level is also 100%. 4.3 Incremental Consistency Checking of Adding Information Incremental consistency checking happens when the A-Box is updated. In this evaluation of incremental reasoning, we only focus on adding new individuals and property tuples rather than the deleting or other update operations. To illustrate, we could have a new A-Box fact hasWife(Lewis,Susan) added to the family ontology. In Pellet, this fact can be added directly by a Pellet API, and the incremental reasoning time of Pellet should be recorded. However, in SQOWL2, ontologies are translated to database schema. Therefore, the new axiom can be translated to a SQL insertion that,
By comparing the incremental consistency checking time of adding this axiom
using Pellet and the time to execute the above SQL statement. SQOWL2 shows
a very faster speed of incremental reasoning of adding information. Execution
times of such an insert on a fully populated version of the family(
Related Work There are different kinds of DL reasoners. Tableaux reasoners which are using tableaux algorithms, such as Pellet, Racer [5] and FacT++, are the most common used, since they are efficient on classification of a T-Box and consistency checking of an A-Box. However, they are not efficient at handling ontologies with a large A-Box.
Compared with Tableaux reasoners, there is an alternative way of performing reasoning by using reasoning rules (rule based reasoning), in order to handle large scale of ontologies. According to the description from the Introduction part, rule based reasoning systems may be divided into VBR, TBR and application based reasoner (ABR) [12] depending on the methods they used to implement the rules. VBR systems, such as DLDB2 and DBOWL use SQL views to achieve type inference, while SQOWL2, a TBR system applies SQL triggers to infer new information based on OWL constructors. ABR systems, such as SOR [9, 16], uses reasoners to implement type inference outside a DB.
SOR (called Minerva previously), as an example of ABR, uses several tableaux based reasoners to classify the T-Box first and then apply SQL statements to apply description logic program rules, in order to implement its type inference engine. It materialises reasoned ontologies inside an RDBMS, which shows a faster querying process. However, current version of SOR only supports OWL 1 DL. Since it only maps a reasoned ontology into a relational schema. It does not allow type inference inside the database; therefore, SOR does not support transactional reasoning and incremental reasoning inside an RDBMS.
Moreover, since in DBOWL, views are non-materialised, it cannot allow queries running in the speed as SQOWL2, which materialised the inferred information. In addition, VBR systems known to us do not support type inference on OWL 2 DL features. For instance, DBOWL and DLDB2 both only cover OWL 1 DL features. Furthermore, SQOWL2 establishes a more traditional relational schema which is a 3NF schema, by translating functional properties and key properties as additional attributes to the properties’ domain tables. 6
Conclusions SQOWL2 is the first transactional reasoning system that supports sound reasoning of OWL 2 DL, and which supports processing of reasoning over standard relational schemas, where functional properties of a class are all held together in a single relation. The evaluation shows that SQOWL2 is substantially faster than Pellet and HermiT, yet provides result sets which are as complete for the benchmark ontologies. It is also shown to be much faster at incremental consistency checking, and since it materialises the reasoned data, is fast as query processing. Of course, the approach is unsuited to applications were the inferred data is very large, and queries are relatively infrequent compared to updates.
Whilst other reasoners exist that are optimised for performance over large A-Boxes, none of these support transactional reasoning, nor are effective at incremental reasoning. Naturally, the advantages of SQOWL2 have to be balanced with its disadvantages. Firstly, since the results of reasoning are being materialised as data is inserted, certain applications might generate very large materialised views from relatively small original datasets. Secondly, our work has not yet addressed the key issue of handling deletes from the database effectively, which is the subject of our current work.