We describe the implementation of the instance store, a DL system using a combination of TBox reasoning and database queries to perform efficient and scalable role-free ABox reasoning.
Description Logic (DL [
To tackle this problem we have developed a Java component, called instance Store
(iS) [
We have discussed the basic ideas behind iS , its performance, and related and
future work in [
The architecture of iS is shown in Figure 1 while its functionality is encapsulated in three basic methods as shown in Figure 2.
The recent W3C recommendation for web ontology languages is OWL [
OWL Wrapper
In the OWL wrapper the ontology is in OWL and, at initialisation time, it is parsed
into a Java OWLOntology object using the OWL API. The iS accepts OWL
descriptions either as Java OWLDescription objects of the OWL API, or as
description strings in OWL Abstract Syntax [
The iS also has a simple XSLT stylesheet which can convert DIG descriptions to descriptions in OWL abstract syntax. The first operation (initialise) connects to the database (creating the tables if needed) and the reasoner and loads the ontology into the reasoner.
The second operation (addAssertion) stores in the database the fact that individual (as a URI) is an instance of (DIG) description, together with additional information gathered through calls to the reasoner, such as the atomic concepts in the ontology the individual is instance of, and the position of the description in the taxonomy.
The third operation (retrieve) again uses the database and the reasoner (with respect to the ontology) to retrieve all individuals (again as URIs) which are instances of the description query. 3
The iS tries to minimise the amount of reasoning required at retrieval time by storing as much information as possible about the descriptions used both during assertion and retrieval. For this we use a relational database whose schema is depicted in Figure 4.
Each description (either asserted or retrieved) is assigned a unique numerical identifier and stored in a dedicated Descriptions table; the identifier acts as primary key and the descriptions are indexed. The assertions are stored in the corresponding table1 containing contains individuals and the identifiers of their associated descriptions; the latter are foreign keys referencing ids in the descriptions table; the individual/descriptionId pair forms a primary key. Next, we use a Types table containing description ids and all the primitive concepts in the ontology which subsume them; again the description ids are foreign keys, the concept/descriptionId pair is a primary key, and the concepts are indexed. Finally, we use three more tables of the same type as Types to store the primitive concepts which are, respectively, equivalent to, parent of and child of a given description.
We have implemented the above schema using three different DBMS: MySQL, Oracle, and Hypersonic. The latter is mostly for testing and demo purposes; it is entirely in Java and requires no installation other than including the corresponding jar in the classpath; each database consists of simply two files, one with properties and one with a script incrementally updated with the issued SQL statements.
MySQL offers the best performance, but it lacks set operations so in our algorithms below we mostly refer to the Oracle implementation. 4
Apart from the initialisation phase, the main functionality of iS consists of asserting that an individual is an instance of a class and retrieving all instances of a description. In both cases, iS first checks if the description is already in store. If this is not the case, then iS uses the TBox reasoner to classify it and then stores the result as shown in Algorithm 1.
Algorithm 1 storeClassification(Description D) : int 1: id ← database.addDescription(D) 2: classification ← reasoner .classify (D) 3: database.addToTypes(id, classification.getAncestors()) 4: if classification.getEquivalents() 6= ∅ then 5: database.addToTypes(id, classification.getEquivalents()) 6: database.addToEquivalents(id, classification.getEquivalents()) 7: else 8: database.addToParents(id, classification.getParents()) 9: database.addToChildren(id, classification.getChildren()) 10: end if 11: return id
1Here we refer to this table as Assertions, but in the actual implementation it is, misleadingly, called primitive.
In order to satisfy the constraint that there is a single description for each individual in the assertions table, before adding an assertion we first check whether the individual is already in store. If this is the case, then the corresponding description is conjuncted with the new description (unless subsumed). See Algorithm 2 for details.
As for retrieval, the first step is to check whether the description whose instances are required is consistent. Next, iS checks whether the description is in store and, if not, the description and its classification are stored in the database. After this preprocessing phase, the actual algorithm begins.
Firstly, iS checks whether the description is equivalent to any primitive concept in the ontology. Since, at this stage, the classification of the description is already in the database, it is sufficient to query the table of equivalents. This is done in Query 1. Note that the query is a join which effectively returns all the ids of descriptions subsumed by primitive concepts equivalent to the query description. If the set returned Query 1 idsFromEquivalents (int id) SELECT DISTINCT Types.descriptionId FROM Types, Equivalents WHERE id = Equivalents.descriptionId
AND Equivalents.concept = Types.concept by such query is not empty then iS can just return the individuals corresponding to such description ids in the table of assertions.
In general, however, there might be no primitive concept equivalent to the query description. In that case we have to return the instances of children of the query description and also check all the instances of its parents. There is a particular case though when this task can be accomplished in a relatively straightforward way, namely when the conjunction of the parents of the query description is equivalent to the query description: we then know that the desired set of instances consists of the intersection of the instances of each parent, union the instances of the children of description. (See Query 2.)
SELECT DISTINCT individual FROM Assertions
WHERE descriptionId IN (
SELECT descriptionId FROM Types WHERE concept = p1 INTERSECT ...
INTERSECT SELECT descriptionId FROM Types WHERE concept = pn UNION SELECT Types.descriptionId FROM Types, Children
WHERE Children.concept = Types.concept
AND Children.descriptionId = id)
When the above does not hold, the iS has then to perform the following, more complex process. First, collect all the description ids corresponding to instances of parents which are not also instances of children. This is performed by Query 3.
SELECT DISTINCT description FROM Descriptions
WHERE Descriptions.id IN (
SELECT descriptionId FROM Types WHERE concept = p1 INTERSECT ...
INTERSECT SELECT descriptionId FROM Types WHERE concept = pn MINUS SELECT Types.descriptionId FROM Types, Children
WHERE Children.concept = Types.concept
AND Children.descriptionId = id)
Next, ask the TBox reasoner to compute the subset of the above candidate descriptions which are subsumed by the query description. This requires a single DIG ask, but as many internal checks as there are candidates. Here the performance of the reasoner really matters. The instances of this set together with the instances of the children of the query description forms then the final result. (See Algorithm 3 for full details.)
Enterprise iS
In many applications, many different clients might want to access iS concurrently and
securely. This can be easily accomplished thanks to our architectural choices. Indeed,
we have developed an Enterprise Java Beans version of iS which is deployed using
the JBoss [
Hibernate allows to persist the plain Java objects corresponding to iS descriptions,
individual, and primitive concepts. Object-relational mappings define the way the
relevant properties in the objects are mapped to entries in a relational database. We
used XDoclet [
As for the reasoner, the use of managed beans means that several instances of the same TBox reasoner can be dynamically spawned when required by the clients (at least if the TBox reasoner is available as a DLL, ie dynamically linked library). The architectural choices made in the implementation of iS ensure that we use appropriate technologies for appropriate tasks. It is clear that at some point the reasoner must be used in order to retrieve individuals, but in our approach it is only used when necessary. Databases are well suited to handling large amounts of data and are optimised for the performance of operations such as joins and intersections – for example the queries described in the query in Figure 2.
As discussed in Section 5, the architecture also allow us to make use of functionality supported by existing component architectures such as Enterprise Java Beans. Then issues like concurrency and security can be passed off to the application servers running the beans.
The use of a database back end also allows us to support persistency. A-boxes may well include large amounts of data, and we can make use of the fact that this is precisely a task that databases are designed to support. There is still, of course, the question of persistent storage of the ontology within the reasoner, but again the separation of the reasoning component from the instance storage means that alternative reasoner implementations can simply be “swapped in” as necessary. Acknowledgements. Phillip Lord participated in the early stages of the implementation of the iS and Nick Taylor and David Roberts from Stilo International PLC participated in the development of the enterprise iS .