logi is be oming popular in areas su h as the Semanti Web, it is very In this paper we present the DLog des ription logi reasoner spe i ally We present the ar hite ture of DLog and des ribe its interfa es. These ally during the normal Prolog exe ution of the generated program. This ate with the ProtØgØ ontology editor, as a server appli ation. We also dire tly on top of existing information sour es.
Keywords: large data sets, des ription logi , reasoning, logi programresults in better s alability and helps using des ription logi ontologies make it possible to use ABoxes stored in databases and to ommuniany knowledge of the parti ular individuals: they are a essed dynamiming, databases designed for su h s enarios.
In this paper we fo us on the des ription of the DLog appli ation itself. trieval are ine ien t for large amounts of underlying data. As des ription evaluate the performan e of the DLog database extension. important to have systems that an reason e ien tly over large data sets.
Abstra t. Traditional algorithms for des ription logi (DL) instan e reThe DLog approa h transforms des ription logi axioms using the SHIQ allows us to store the individuals in a database instead of memory, whi h DL language into a Prolog program. This transformation is done without is mostly based on the des ription logi , and it is intended to be the SHIQ DLs are intended to provide the mathemati al ba kground needed for more intelDes ription Logi s (DLs) allow us to represent knowledge bases onsisting of using semanti s for various reasons. As an example, in the Semanti Web idea, ontologies, des ribed in the Web Ontology Language (OWL) [1℄. This language standard knowledge representation format of the Web. alls for reasoners that are able to e iently handle su h abundan e of data. terminologi al axioms (the TBox ) and assertional knowledge (the ABox ).
Des ription Logi s are be oming widespread as more and more systems start ligent query answering. Here the knowledge is aptured in the form of expressive However, we have tremendous amounts of information on the Web whi h side of DLog an be found in [3℄ and in [4℄. whi h allows des ription logi reasoning on top of existing information sour es. and the summary of our results. performan e of the database extension of DLog w.r.t. the version whi h stores interfa es are des ribed in Se tions 4 and 5, respe tively. Se tion 6 evaluates the feren e algorithm from the data storage.
Se tion 3 we give a general introdu tion to the DLog approa h and present the this, we started to investigate te hniques whi h allow the separation of the instored in a database. two phases. First we reate a query-plan in Prolog from the a tual DL knowls alability problems and undermines the point of using databases. Be ause of for querying des ription logi on epts in an environment where the ABox is on epts need to examine the whole ABox to answer a query. This results in In this paper we fo us on the ar hite ture of the DLog system, as well as We have developed a solution, where the inferen e algorithm is divided into on its external interfa es. We dis uss the interfa e used for a essing databases, edge base, without a essing the underlying data set. Subsequently, this queryis not a simple te hni al problem: most existing algorithms for querying DL plan an be run on real data, to obtain the required results. The implementaWe also des ribe the ProtØgØ [2℄ interfa e that makes it possible to use DLog as This paper is stru tured as follows. Se tion 2 summarises related work. In the ABox as Prolog fa ts. Finally, in Se tion 7, we on lude with the future work Moreover, as these data annot be stored dire tly in memory, we need solutions http://dlog-reasoner.sour eforge.net. the ba k-end reasoner of this popular ontology editor. Details on the theoreti al tion of these ideas is in orporated in the DLog reasoning system, available at ar hite ture and implementation details of the system. The database and ProtØgØ this task, as these are not apable of handling ABoxes stored externally. This We found that most existing des ription logi reasoners are not suitable for is proved to be an instan e of The main drawba k of this approa h is that i C. to build a model showing that a given on ept is satisable. To infer that an Extreme ases involve serious restri tions on the knowledge base to ensure of-the-art DL reasoners, su h as Ra erPro [6℄ or Pellet [7℄. individual is an instan e of a on ept an indire t assumption is added i C, ¬C(i) it annot be dire tly used for high volume instan e retrieval, be ause it would Several te hniques have emerged for dealing with ABox-reasoning. Tradite hniques have been developed in re ent years [5℄. These are used by the statee ien t exe ution with large amounts of instan es. For example, [8℄ suggests a tional ABox-reasoning is based on the tableau inferen e algorithm, whi h tries to the ABox, and the tableau-algorithm is applied. If this reports in onsisten y, To make tableau-based reasoning more e ien t on large data sets, several require he king all instan es in the ABox, one by one. KAON2 (1) we use a pure two-phase reasoning approa h (i.e. the ABox is a be modied and optimised for reasoning over des ription logi knowledge bases. by transforming the knowledge base into a disjun tive datalog program. SHIQ this method and provides reasoning servi es over the des ription logi language ever, this approa h still requires the input of the whole ontent of the ABox uses a dire t transformation of des ription logi on epts into denite Horn- ALC lauses, and poses some restri tions on the form of the knowledge base, whi h only axioms of form i.e. we annot make role assertions. C(a), This work, however, mostly fo uses on TBox reasoning.
Paper [9℄ dis usses how a rst order theorem prover su h as Vampire an disallow axioms requiring disjun tive reasoning. As an extension, [13℄ introdu es well-established, e ien t and robust implementations.
This work, however, still poses restri tions on the use of disjun tions. essed only during query answering) and (2) we translate into Prolog whi h has solution alled the instan e store, where the ABox is stored externally, and is a essed in a very e ien t way. The drawba k is that the ABox may ontain In [10℄, a resolution-based inferen e algorithm is des ribed, whi h is not as a fragment of the language that an be transformed into Horn- lauses. SHIQ Arti le [12℄ introdu es the term Des ription Logi Programming. This idea before attempting to answer any queries. The KAON2 system [11℄ implements Although the motivation and goals of KAON2 are similar to ours, unlike sensitive to the in rease of the ABox size as the tableau-based methods. Howtransforms the des ription logi formulae to a set of DL lauses [15℄, whi h are Next, the TBox is pro essed in two steps. First the DL translator module ode. This generated ode is equivalent, with respe t to instan e retrieval, to the ompletely) in external databases. The ABox is pro essed rst, produ ing the be generated dire tly into memory or may be saved to disk for later (standalone) for translating the TBox. The generation of ABox ode in ludes optimisations ABox ode (whi h is a Prolog module), and the ABox signature, whi h is required input DL knowledge base. The TBox translator module uses various optimisamore e ien t Prolog programs. The ABox and TBox ode an PSfratgiornespl[a3℄etmoeonbttsain use. su h as indexing on se ond argument for roles stored in memory. passed on to the TBox translator module that generates the exe utable TBox depends on the signature of the data set, and be ause of the top-down inferen e are a essed via the ODBC driver of SWI-Prolog; as a onsequen e DLog an A predi ate is a query predi ate [3℄, if it is non-re ursive, it does not invoke ABox assertions are des ription logi onstru ts that are readily available in DL The meta data provided is used to onne t to the database, and, for ea h table to use for given on epts and roles, et . Be ause of the aforementioned reby individuals. An arbitrary name an be used for su h an individual. during exe ution. The name query predi ate ree ts that fa t that su h predidatabase a ess using existing tools and interfa es su h as ProtØgØ and the As the rst phase of reasoning (i.e. the generation of a query plan) only new roles (obje t properties), attributes (datatype properties) and individuals spe ify database usage. To a ess a database, several pie es of information are dened in the namespa e http://www. s.bme.hu/dlogDB.
DIG interfa e it utilises even if those do not, at the moment, provide a way to ates an be transformed to omplex database queries (provided that all on epts This allows on epts and roles to be stored partially in databases and partially the existing databases of other appli ations. Thirdly, querying some on epts forman e as the database engine an optimise the query using statisti al and it makes integrating DLog with existing systems easier, as the reasoner an use its negation, and is not invoked from within its negation. Here, a predi ate is P0 interfa e with most modern database systems. We wanted a way to spe ify and roles required are stored in a single database). This an in rease the perThe ODBC interfa e pres ribes that database onne tions are to be idenof Prolog, DLog an e ien tly use databases to store the ABox. systems and interfa es, su h as OWL and DIG.
Query predi ates require neither loop elimination, nor an estor resolution (namely those orresponding to so- alled query predi ates) may be performed There may be several advantages in using databases to store the ABox. tied by a Data Sour e Name (DSN). In DLog we introdu e an individual to In order to spe ify the database a ess for on epts and roles we introdu e deliver a marked in rease in performan e. said to invoke a predi ate if there are intermediate predi ates Pn, n ≥ 1, n − 1 body the head of whi h is for Pi−1, i = 1, . . . , n.
Firstly, this allows reasoning on data sets that annot t into memory. Se ondly, using omplex database queries, rather than DL reasoning, whi h is expe ted to su h that is dire tly invoked by i.e. it o urs in a lause P1 . . . Pn−1, Pi Pi−1, propriate database query, lists appropriate individuals (or pairs of individuals). represent a given database onne tion. Roles and on epts are also represented needed: the name of the database, a user name, a password, a des ription of whi h in memory. This may be very useful when developing ontologies.
We designed the database interfa e to be as simple as possible. The databases on ept and role, an additional lause is generated, whi h, by exe uting an apstru tural knowledge of the database in question. quirements we de ided to use ABox assertions to arry this meta-information. as attributes of the same individual.
The latter is a large setba k as most of the queries are instan e he ks, assuming the individuals of Obviously, both hasQuery and hasNegQuery an appear ¬C. the individual name. a view and the name of the olumn(s) of this table. This approa h, alled the respe tively.
If the omplex interfa e is used, the name of the table or view to use is The SQL query in the simple interfa e is dened using the string attribute olumns, and for those used for on epts it must return one olumn that ontains on ept, we provide some additional attributes: hasNegQuery, hasNegTable and hasQuery. The individual represents the role or on ept and the attribute value Therefore the se ond, preferred, way is to provide the name of a table or of hasNegQuery for a name representing the on ept we spe ify a query listing C the the proje tion optimisation of [3℄ is used. provides mu h greater exibilit y and better performan e. omplex interfa e may require the reation of new views in the database, but the attributes hasLHS and hasRHS are used for the left and the right hand side, Be ause, in ProtØgØ, individuals annot be spe ied as instan es of a negated individuals of a on ept is given using the string attribute hasColumn. For roles, epts, in a way similar to their respe tive positive pairs. By providing an attribute hasNegColumn. These are used to spe ify the database a ess of negated onis the query string. For individuals representing roles the query must return two spe ied by the string attribute hasTable. The name of the olumn listing the ing a patri ide hild, who, in turn, has a non-patri ide hild. The ABox axioms, The examples ontain ABox assertions, whi h are displayed as RDF triples Polyneikes), (Oedipus, Polyneikes) and (Polyneikes, Thersandros)). The quotes. The namespa e http://www. s.bme.hu/dlogDB# is represented by the example. This lassi al example involves the on ept des ribing a person havBoth the role hasChild and the on ept Patri ide are taken from this whi h are now to be stored in a database, des ribe the hasChild relation between We hose this name as a mnemoni for a r ole from the namespa e io, alled DSN is spe ied as "io aste" (line 1). This onne tion is a essed without Figure 4 shows the use of the simplied interfa e for the ABox of the Io aste ABox also spe ies whi h individuals are patri ide and whi h are non-patri ide database. The role hasChild is represented by the instan e dlog:riohasChild. simple, and one for the omplex interfa e. than dlog:hasDSN. in this ontology. The database onne tion is named iodb, and the orresponding the role is of no interest, so we hose to have the same individual as on the left pairs of individuals (traditionally ontaining (Io aste, Oedipus), (Io aste, dlog: prex. in {subje t, predi ate, obje t} format. String values are shown between We have hosen the namespa e represented by the io: prex for the names this individual represents the role io:hasChild. Here, the right hand side of (traditionally Oedipus is known to belong to the former, while Thersandros to the latter). hand side. Line 6 tells that the individual dlog: ioPatri ide is an instan e of We now present two examples for interfa ing with databases, one for the hasChild, but any other name ould have been used. Line 2 tells the system that spe ifying a user name or a password. A ordingly, iodb has no attributes other o urring in the ABox if it ontains an instan e whi h is in the namespa e ea h role, and use it to onstru t a database a ess for the given role. has to make on ept an instan e of The DLog system will he k ea h on ept C. that the user in ludes the triple {role, indiv} in the ABox. Here indiv is R, The database interfa e is urrently in the alpha test phase. We believe that http://www. s.bme.hu/dlogDB. If su h an instan e is found, it is interpreted (parts of) the ABox in databases. However, we hope that our work ontributes as a handle to a database whi h is to produ e (additional) instan es for the to implementing this ultimate goal. given on ept.
To spe ify that the individual on ept represents the on ept one simply C, http://www. s.bme.hu/dlogDB within the domain (i.e. the left hand side) of Similarly, to spe ify that an individual role represents the role we require R, mately the standard interfa es, su h as DIG, should be extended to allow storing our approa h for this task, dis ussed above, is an intermediate solution. Ultian arbitrary individual. Again DLog will look for an instan e in the namespa e friend. Now, if we assume that Ja k is al oholi , then the axiom in line 1 implies al oholi . In spite of this, in the presen e of ertain role instan e patterns, one al oholi parent are non-al oholi (as they see a good example). In the lassi that Joe has to be non-al oholi . Other patterns, where Joe an be inferred to lations only, and no on ept assertions about anyone being al oholi or nonLine 1 des ribes that those who have a friend who is al oholi are non-al oholi to the RDF namespa e: http://www.w3.org/1999/02/22-rdf-syntax-ns#.
For example, onsider the following pattern: Ja k is Joe’s parent and also his an an estor; and Joe’s two an estors are in the hasFriend relationship. that Joe is not al oholi . On the other hand, if Ja k is not al oholi , it follows (as they see a bad example), while line 2 states that those who have a nonbe non-al oholi , are the following: Joe is a friend of himself; Joe is a friend of form the ABox ontains role assertions for the hasParent and hasFriend rean infer some people to be non-al oholi , using ase analysis. 1 Note that the prex rdf, used in the predi ate position of the triple in line 6, refers from line 2 that Joe is not al oholi , either. Thus these two role assertions imply and one for its negation (line 10). he k queries run with a poor performan e. possible query predi ates in the TBox to dire t database queries, and instan e whi h has a WHERE lause. This way the existing table people an be used without The simplied interfa e allows omplex queries, su h as the one for Patri ide the on ept io:Patri This individual, whi h thus represents the on ept ide1.
We now present a se ond example. The TBox of this example, taken from modi ation. However, this approa h makes it very di ult to transform any io:Patri ide, has two queries asso iated with it: one for io:Patri ide (line 8) [4℄, is shown below.
ProtØgØ [2℄ is an open sour e ontology editor that supports the Web Ontology interfa e [16℄. The DLog server implements the DIG interfa e and an be used to exe ute instan e retrieval queries issued from the graphi al interfa e of ProtØgØ. and its negation through appropriate database views. In Figure 5, lines 1013 spe ify the database a ess for the role hasFriend, while lines 1419 allo w for a essing individuals belonging to the on ept al oholi Fig. 5. An example of the omplex database interfa e. 10 5 Integrating DLog with ProtØgØ From this information DLog an reate a query for instan e retrieval ("SELECT the omplex query for the role hasParent, f. lines 46. The olumns of this ases when at least one of the individuals is known (e.g. "SELECT hild FROM using the omplex interfa e. Here, the database al oholi is a essed with the hild, parent FROM hasParentView"), and three other query patterns for the of omplex database queries for the query predi ates. hasParentView WHERE parent = ?"). This approa h allows for the generation In Figure 5 we present a database a ess spe i ation for the above example, view, hild and parent (lines 78), ontain the data for the role hasParent. that a new view, alled "hasParentView", was dened in the database to hide user name "drunkard" and the password "palinka" (lines 13). We assume 18 {dlog: al Al oholi , dlog:hasNegTable, "nonal oholi View"} 3 {dlog:al db, dlog:hasPassword, "palinka"} 11 {dlog:ral hasFriend, dlog:hasTable, "friends"} 7 {dlog:ral hasParent, dlog:hasLHS, " hild"} 6 {dlog:ral hasParent, dlog:hasTable, "hasParentView"} 17 {dlog: al Al oholi , dlog:hasColumn, "name"} 12 {dlog:ral hasFriend, dlog:hasLHS, "friend1"} 13 {dlog:ral hasFriend, dlog:hasRHS, "friend2"} 8 {dlog:ral hasParent, dlog:hasRHS, "parent"} 9 {dlog:ral hasFriend, al :hasFriend, dlog:ral hasFriend} 10 {dlog:ral hasFriend, dlog:hasConne tion, dlog:al db} 2 {dlog:al db, dlog:hasUserName, "drunkard"} 19 {dlog: al Al oholi , dlog:hasNegColumn, "name"} 14 {dlog: al Al oholi , rdf:type, al :Al oholi } 16 {dlog: al Al oholi , dlog:hasTable, "al oholi View"} 4 {dlog:ral hasParent, al :hasParent, dlog:ral hasParent} 15 {dlog: al Al oholi , dlog:hasConne tion, dlog:al db} 5 {dlog:ral hasParent, dlog:hasConne tion, dlog:al db} 1 {dlog:al db, dlog:hasDSN, "al oholi "} a dire t XML parser, it has some di ulties when used in XML mode. For With Xer es we plan to use SAX parsing, instead of DOM, with the hope of lower memory usage and faster parsing. hope of better performan e, we are planning to swit h to Apa he Xer es-C++. operated in an XML ompatibility mode, allowing namespa es. As this is not For parsing XML we use the SGML module of SWI-Prolog, whi h an be a epts input les that are not even well-formed XML. Be ause of this, and in example even with the stri test settings and treating all warnings as errors, it biguities of the DIG spe i ations, despite there being an (exa t) XML s hema ports multiple on urrent knowledge bases. We strove for an implementation as database, this ommand was dened, but ProtØgØ uses the new version that supgeneri and omplying to the interfa e denition as possible while, also being format. For the implementation we used the HTTP server provided with SWIeven dened in version 1.1 of DIG. In DIG 1.0, whi h supported only a single Prolog. In implementing the interfa e we fa ed di ulties aused by some amdenition. Another di ult y was that ProtØgØ does not stri tly follow the defThe DIG interfa e spe ies ommuni ation via HTTP, and uses XML data inition of the interfa e. For example it uses a learKB ommand that is not ompatible with ProtØgØ. the DLog server. Figure 6 shows the results of a query issued from ProtØgØ, as answered by 11 Fig. 6. S reenshot of query results in ProtØgØ answered by DLog.
(DCG).
the indexing optimisation turned o. When this optimisation is turned on, the However, we believe that in the ase of large data sets and omplex queries whi h ts into memory, is bene ial only be ause of the redu ed ompile-time. number of generated ABox lauses is doubled, and translation time in reases queried on ept in 0.36 se onds. This, ompared to the original 0.02 se onds is a ordingly. mu h slower. However, the time we spent at ompile-time was altogether 0.07 of total query exe ution time, more than a three-fold de rease was a hieved, Detailed evaluation of the DLog System an be found in [3℄. using the database interfa e. se onds, resulting in a total exe ution time of 0.43 se onds. To sum up, in terms The database variant of the example enumerates all the instan es of the When the ABox is stored in memory, the translation takes 1.41 se onds, and the exe ution takes only 0.02 se onds. Note that these gures were obtained with time an also be better than that of the in-memory variant. (espe ially if these ontain on epts giving rise to query predi ates) exe ution these individuals from the list of query results. in ProtØgØ (i.e. individuals present only in databases) ProtØgØ silently drops The integration of ProtØgØ and the database interfa e is in progress. A serious di ult y is that if the results of a query ontain individuals that are not dened database 0.05 0.02 0.36 0.43 (se onds) load translate exe ute total in-memory 0.88 0.53 0.02 1.43
time it takes to load the le whi h ontains the axioms, in luding the XML This se tion ontains a preliminary performan e test of the database interparsing. The translation time is the time it takes to generate the TBox and We tried the database interfa e on a large version of the Io aste problem whi h ontains 5058 pairs in the hasChild relation, 855 instan es that are known The exe ution results are summarised in Table 1. The load time means the to be patri ide, and 314 that are known to be non-patri ide. fa e. of the in-memory version. Future improvements in lude the optimisation of query predi ates, by transforming them to database queries, and better integration of ProtØgØ and the ule to handle omposite queries, and the support for additional interfa e formats, of DLog with the ProtØgØ ontology editor. time and, with advan ed optimisations, it may provide e ien y similar to that In this paper we have shown the ar hite ture of the DLog system, dis ussed a database interfa e. Our plans also in lude the implementation of a query modor if it is shared with other systems. Using databases an greatly redu e ompile The database interfa e is espe ially useful if the data set annot t in memory su h as OWL, or the KRSS notation used by e.g. the Ra erPro engine. database interfa e for representing large ABoxes, and reported on the integration
A knowledgements Referen es 13 Canada. (2004) uary 2008) Conditionally a epted for publi ation in Theory and Pra ti e of Logi of Protege-2000: Combining interoperability and exibilit y. Programming. ilities for Ra er and an Appli ation to Software-Engineering Problems. In: Pro1. Be hhofer, S.: OWL web ontology language referen e. W3C re ommendation OWL-DL reasoner. Web Semant. 5(2) (2007) 5153 in OWL/RDF do uments: First results. In: Ninth International Conferen e on the (February 2004) 6. Haarslev, V., Mller, R., van der Straeten, R., Wessel, M.: Extended Query Fawith large numbers of individuals. In: Pro eedings of DL2004, British Columbia, 8. Horro ks, I., Li, L., Turi, D., Be hhofer, S.: The Instan e Store: DL reasoning Canada, June 2-5. (2004) 163173 7. Sirin, E., Parsia, B., Grau, B.C., Kalyanpur, A., Katz, Y.: Pellet: A pra ti al http:// iteseer.nj.ne . om/noy01knowledge.html (2000) 3. LukÆ sy, G., Szeredi, P.: E ien t des ription logi reasoning in Prolog: the DLog 2. Noy, N., Fergerson, R., Musen, M.: The knowledge model Prin iples of Knowledge Representation and Reasoning, KR 2004, Whistler, BC, (De ember 2008) To appear in ICLP 2008. eedings of the 2004 International Workshop on Des ription Logi s (DL-2004), 5. Haarslev, V., Mller, R.: Optimization te hniques for retrieving resour es des ribed system. Te hni al report, Budapest University of Te hnology and E onomi s (Jan4. LukÆ sy, G., Szeredi, P., KÆdÆr, B.: Prolog based des ription logi reasoning. Whistler, BC, Canada, June 6-8. (2004) 148157 the earlier version of the paper, and espe ially for re ommending the Billion Triples Challenge for evaluation. The authors are grateful to the anonymous reviewers for their omments on