Evolution of Ontologies using ASP
Contents
1. e U kb p 45 changeDel q Vj dom type V V for all 1 lt j lt head In this way we extend our change by deterministic consequences to possibly reduce the number of incremental steps For our example in Fig 1 this results in the additionally required changeDel c_IsA b a Evolution of Ontologies using ASP 15 n times level timeouts n times level timeouts 1 123 3 2 37 0 1 2 2 10 70 0 2 2437 4 72 0 2 3 3 16 28 20 3 454 6 8 50 0 3 3 4 16 15 30 4 619 0 11 94 0 4 7 0 16 96 51 5 711 1 13 44 2 5 3 5 16 19 66 6 756 1 14 27 6 6 7 3 18 00 76 Table 7 a Go Benchmark b CIDOC Benchmark 6 Experiments For our experiments we considered two real world ontologies of different size and struc ture in order to study the effects of both the size and of the morphology of the ontol ogy on the performance of our approach The first considered ontology is Gene Ontology GO Consortium 2000 a large ontology from the bio informatics consisting of roughly 458 000 entries 28 000 classes 370 000 relations and 60 000 instances The second on tology is CIDOC CIDOC 2010 a medium sized ontology from the cultural domain con sisting of roughly 1500 entries with about 250 properties 80 classes and 700 relations As we can see GO s emphasis is on classes while CIDOC contains many properties To generate the changes we too2. l j body l j 1 h head 8 Ostrowski et al kb ci a kb cs a kb cs b kb cs c kb c_IsA b c kb c_IsA b a kb c_IsA c a kb c Inst a b kb c Inst x c kb c Inst x a changeAdd c_IsA a b Table 4 Instance from example in Fig 1 Our goal is to find a C minimal set of potential side effects V which means that there exists no set of potential side effects V such that V C V We do this using the grounder gringo which ground instantiates a logic program with variables We create a logic pro gram where the single solution is the subset minimal set of potential side effects V To build a logic program we first have to define the inputs to the problem called in stance An instance Z K C of a KB K and a change C is defined as a set of facts L K C kb p p z Kj U changeAdd p x p z C U changeDel p p x C7 In the above instance predicate kb contains the facts in the KB whereas predicates changeAdd changeDel contain the facts that the change dictates to add delete respec tively Note that this representation forms a twist from the standard representation since a ground fact p Z K is represented as kb p X same for the change The representation of the KB X in Fig 1 and its demanded change C can be found in Table 4 Furthermore we have to collect all resources available in the KB 1 or newly introduced by the ch
3. a seemingly strange behaviour it has lots of timeouts but very fast execution on average when no timeout occurs This indicates that the deviation of execution times even for KBs changes of the same size is very large for CIDOC i e the performance is largely affected by the spe cific form of the KB or change Given that this behaviour is much less apparent in GO we conclude that it is due to the existence of many properties in CIDOC in fact it turns out that property related constraints increase the number of potential side effects thereby increasing the computational effort required but only if such rules are violated As a result for the updates that included many property related changes the execution time increases often causing timeouts whereas for updates that include few property related changes the 16 Ostrowski et al execution time is rather small Given that GO contains no properties the execution times are much more smooth few timeouts but worse average performance If we concentrate on the average level where a solution was found we see a strong correlation between the level and the average time reported Also we note that as the size of the change increases so does the level and the average required time 7 Summary and Outlook In this paper we studied how we can solve the problem of ontology evolution in the pres ence of ontological constraints using ASP rules Based on the setting and solution pro posed i
4. and implementing the stable model semantics Artificial Intelligence 138 1 2 181 234 STOJANOVIC L MAEDCHE A MOTIK B AND STOJANOVIC N 2002 User driven ontology evolution management In Proceedings of the 13 European Conference on Knowledge Engi neering and Knowledge Management EKAW 02 SYRJ NEN T Lparse 1 0 user s manual http www tcs hut fi Software smodels lparse ps gz TAO J SIRIN E BAO J AND MCGUINNESS D 2010 Extending owl with integrity constraints In Proceedings of the 23 International Workshop on Description Logics DL 10 CEUR WS 573 UMBRICH J HAUSENBLAS M HOGAN A POLLERES A AND DECKER S 2010 Towards dataset dynamics Change frequency of linked open data sources In Proceedings of the WWW2010 Workshop on Linked Data on the Web LDOW2010
5. decomposing changes into smaller independent sets that can be applied in a sequence rather than in a bulk manner without jeopardizing the correctness and optimality of the result References ALCHOURRON C E GARDENFORS P AND MAKINSON D 1985 On the logic of theory change Partial meet contraction and revision functions Journal of Symbolic Logic 50 510 530 BARAL C 2003 Knowledge Representation Reasoning and Declarative Problem Solving Cam bridge University Press BERNERS LEE T HENDLER J A AND LASSILA O 2001 The semantic web Scientific Amer ican 284 5 34 43 BRICKLEY D AND GUHA R 2004 Rdf vocabulary description language 1 0 Rdf schema www w3 org TR 2004 REC rdf schema 20040210 CALI A GOTTLOB G AND LUKASIEWICZ T 2009 Datalog A unified approach to ontologies and integrity constraints In Proceedings of the International Conference on Database Theory ICDT 09 Evolution of Ontologies using ASP 17 CIDOC 2010 The CIDOC Conceptual Reference Model cidoc ics forth gr official release cidoc html CONSORTIUM T G O 2000 Gene ontology tool for the unification of biology In Nature genetics Vol 25 25 29 DEUTSCH A 2009 Fol modeling of integrity constraints dependencies Encyclopedia of Database Systems 1155 1161 FLOURIS G MANAKANATAS D KONDYLAKIS H PLEXOUSAKIS D AND ANTONIOU G 2008 Ontology change Classification and survey The Knowledge Engineering Re
6. left hand side such that correspond e 99 ing instances of literals on the right hand side hold Syrj nen Gebser et al While allows for specifying integer intervals allows for pooling alternative terms to be used as arguments within an atom For instance p 1 3 as well as p 1 2 3 stand for the three facts p 1 p 2 and p 3 Given this q X p X results in q 1 q 2 q 3 See Gebser et al for detailed descriptions of the input language of the grounder gringo 4 Evolution using ASP 4 1 Potential Side Effects In order to determine the result of updating a KB we need to determine the side effects that would resolve any possible validity problems caused by the change The general idea is simple since the original KB is valid a change causes a violation if it adds removes a fact that renders some constraint invalid To explain this in more detail let us denote by V the set of potential side effects of a change C In general given a set of facts C we will write Ct C to denote the positive negative facts of C respectively First of all we note that V will contain all facts in C except those already implied by K i e if p z CT and p z K then p z V and if p z C and p Z K then p z V Condition I The facts in the set V U K are called available This initial set of effects may cause a constraint violation Note that a constraint r is violated during a change iff the r
7. operation by e In our example we get Ko eC K44 Note that Ko e C results from applying the change C and its most preferable side effects upon Ko 3 Answer Set Programming ASP In what follows we rely on the input language of the ASP grounder gringo Gebser et al extending the language of parse Syrj nen and introduce only informally the basics of ASP A comprehensive formal introduction to ASP can be found in Baral 2003 We consider extended logic programs as introduced in Simons et al 2002 A rule r is of the following form he by 0m bm41 On By head r hand body r b1 0m bm 4i bn we denote the head and the body of r respectively where stands for default negation The head H is an atom a belonging to some alphabet A the falsum L or a cardinality constraint L 2 U In the latter 2 a or 2 a is a literal for a A and 1 lt i lt k L and U are integers providing a lower and an upper bound Such a constraint is true if the number of its satisfied literals is between L and M Either or both of L and U can be omitted in which case they are identified with the trivial bounds 0 and oo respectively A rule r such that head r L is an integrity constraint one with a cardinality constraint as head is called a choice rule Each body component B is either an atom or a cardinality constraint for 1 lt i lt n If body r 0 r is called a fact and we skip wh
8. set of potential side effects according to Condition II pAdd qn Vn e U avail si p U pAdd pi U kb qn U Vn dom type V Va for all 1 lt l body and 1 h lt head Similarly to capture Condition II we need two sets of rules 9 and 10 since we do not want to do this only for negative side effects n vail on the lhs of the rule but also for facts that are not in the KB K 8 gt gt gt gt pDelete p tu e U avail s si p U pAdd pi U kb p U ry zs 9 nAvail qn U Vn dom type Vn Vn m pDelete p c e U avail s si p pAdd pi kb p kb qn Vn dom type Vn Va for all 1 lt 1 7 body l 4 j 1 lt h lt head The last Condition IV can be expressed by the following rule set 11 10 gt gt gt gt pDelete pi U e U avail si p U kb p U pDelete qn U Va dom type Vn Vn for all 1 l body and 1 h lt head 11 Proposition 1 Given a KB K and a change C and let A be the unique answer set of the stratified logic program ground Z K C U 1 then V p z pAdd p x Ayu wp x pDelete p Z A is a subset minimal set of potential side effects of the KB K and the change C For our example in Fig 1 this results in the set of potential side effects in Table 5 Note that the potential side effects contain all possible side effects including side effects that
9. 3 l newAvail k si p T oldStep level delete pi for all 1 body 1 h lt head We define the operator 7 K C k as T K C 0 ground Z K C and 7 K C k where k gt O is the set of facts of the unique answer set of the logic program ground T K C k 1 0 Q 43 7 KC C n produces a subset of the potential side effects only using repairs up to level n Given our example in Fig 1 7 K C 7 gives us the set shown in Table 6 and 7 K C 15 gives us the same set of side effects as already show in Table 5 5 2 Exploiting Deterministic Side Effects A second way to improve performance is to consider deterministic side effects of the origi nal changes As an example of a deterministic side effect suppose that the original change includes the deletion of a class a corresponding to the side effect cs a Then per rule R5 cf Table 2 all class subsumptions that involve a must be deleted as well cor responding to the side effect c s4 Therefore the latter side effect s are a necessary deterministic consequence of the former so they can be added to the set of side effects right from the beginning at level 1 Formally for all DED constraints of the form V noaa iai Vi lt e p U POE where p U is a single atom we generate the following rules changeAdd q U V e U changeAdd p U E Ei urn 44 kb qj U Vj dom type V Vj changeDel p
10. FORTH Technical Report TR 415 May 2011 1 Evolution of Ontologies using ASP Max Ostrowski and Giorgos Flouris and Torsten Schaub and Grigoris Antoniou 1 Universitit Potsdam 2 FORTH ICS 3 University of Crete Abstract RDF S ontologies are often used in e science to express domain knowledge regarding the respective field of investigation e g cultural informatics bioinformatics etc Such ontologies need to change often to reflect the latest scientific understanding on the domain at hand and are usually associated with constraints expressed using various declarative formalisms to express domain specific require ments such as cardinality or acyclicity constraints Addressing the evolution of ontologies in the presence of ontological constraints imposes extra difficulties because it forces us to respect the as sociated constraints during evolution While these issues were addressed in previous work this is the first work to examine how ASP techniques can be applied to model and implement the evolution pro cess ASP was chosen for its advantages in terms of a principled rather than ad hoc implementation its modularity and flexibility and for being a state of the art technique to tackle hard combinatorial problems In particular our approach consists in providing a general translation of the problem into ASP thereby reducing it to an instance of an ASP program that can be solved by an ASP solver Our experiments are promising even
11. The predicates pAdd and pDelete represent the potential side effects already found in all levels before k Therefore the new additions from the last processed level are added to the pAdd and pDelete predicate 25 to 26 respectively pAdd T X newPadd k 1 T X Q5 pDelete T X newPdel k 1 T X Q6 The redundant predicates nNewAvail and newAvail contain everything that is newly avail able or not available at level k 27 and 28 nNewAvail k T X newPdel k T X 27 newAvail k T X newPadd k T X 28 Finally nAvail and avail accumulate the available not available facts 29 to 31 nAvail T x nNewAvail k T a 29 avail T x kb T x 30 avail T x newAvail k T x 31 For our conditions II III and IV we can distinguish three different cases depending on the level of the corresponding ASP rules The ASP rules for constraints r with e level r k are grounded for all potential side effects new and old ones and entities in the KB e level r k are only grounded if either of the potential side effects on the rhs of the rule r is newly added on the level k e level r k are grounded if at least one of the potentially available not available entries has been added at step k These three steps are now described in detail for each condition For Condition II the rule sets 32 33 and 34 correspond to the set 8 Section 4 The rule set 32 produces the cor
12. ange 2 So the predicate dom associates a resource to its type dom type Xi X kb T X 1 dom type X X changeAdd T X Q for all X X The following two rules 3 and 4 correspond to Condition I above stating that the effects of C should be in V unless already in X The predicates pAdd and pDelete are used to represent potential side effects additions and deletions respectively i e facts in the sets V V7 pDelete T X changeDel T X kb T X Q pAdd T X changeAdd T X kb T X 4 To find those facts that are added due to subsequent violations we define for the set Vt U K the predicate avail in 5 and 6 For negative potential side effects V we use a redundant predicate nAvail 7 avail T X kb T X 5 avail T X pAdd T X 6 nAvail T X pDelete T X 7 At a next step we need to include the ontological constraints R into our ASP program by creating the corresponding ASP rules Unlike ontological constraints which determine whether there is an invalidity we use the ASP rules to determine how to handle this inva lidity So now consider a constraint r 7 as defined in Section 2 3 For r we define a set Evolution of Ontologies using ASP 9 c IsA a b c_IsA c c c_IsA c b c IsA b b c IsA a a c IsA a c ac_IsA b a c IsA b c c IsA c q Table 5 Potential Side effects of example in Fig 1 of rules 8 that produce the
13. at during a change the modifications applied upon the original KB must be minimal In other words given many different evolution results that satisfy the principles of success and validity one should return the one that is closer to the original KB where closeness is an application specific notion The above non trivial problem was studied in Konstantinidis et al 2008 resulting in a general purpose changing algorithm that satisfies the above requirements Unfortunately the problem was proven to be exponential in nature so the presented general purpose al gorithmic solution to the problem which involved a recursive process was inefficient ASP is a flexible and declarative approach to solve NP hard problems The solution that was presented in Konstantinidis et al 2008 regarding the problem of ontology evolution in the presence of integrity constraints can easily be translated into a logic program with first order variables this is the standard formalism that is used by ASP which is then grounded into a variable free representation by a so called grounder that is then solved by a highly efficient Boolean solver As it is closely related to the SAT paradigm knowledge about different techniques for solving SAT problems are incorporated into the algorithms Using first order logic programs is a smart way to represent the problem while remaining highly flexible especially in the set of constraints related to the ontology The
14. e is an error prone and te dious process The objective of this work is to assist knowledge engineers in applying their changes in an automated manner while making sure that no invalidities are introduced in the KB during the evolution In addition to the Validity Principle two other principles are usually considered The first is the Principle of Success Alchourron et al 1985 stating that the required changes take priority over existing information i e the change must be applied in its entirety The second is the Principle of Minimal Change Alchourron et al 1985 stating that during a change Fig 1 A knowl the modifications applied upon the original KB must be minimal In other edge base with words given many different evolution results that satisfy the principles of change change NE appearing as bold Success and validity one should return the one that is closer to the orig arrow inal KB where closeness is an application specific notion In this work we determine the notion of closeness that is used in the Principle of Minimal Change using a relation the function and use of this relation is described in detail later 2 3 Formal Setting To address the problem of ontology evolution we use the general approach presented in Konstantinidis et al 2008 In that work an RDF S KB K is modeled as a set of ground facts of the form p 2 where p is a predicate name and 7 is a vector of con stants Constan
15. e top of the hierarchy Even though this distance can be computed using a grounder like gringo for simplicity we rely on a precomputed predicate lowestDist type X X N which gives the distance N for each entry X The corresponding minimization statement is minimize kb cs X N L lowestDist cs X N kb cs X 20 Here N denotes the weight of the literal in the statement By using negative weights we do maximization instead of minimizing We clearly want to maximize the distance to the top of the hierarchy As these entities are less general and a change is therefore less severe Again L L 1 denotes the level of the minimize constraint so minimizing the number of additions is more important than maximizing the distance As gringo allows hierarchical optimization statements we can easily express the whole ordering x in a set of optimize statements O Evolution of Ontologies using ASP 11 Proposition 3 Given a KB K a change C and a set of potential side effects V we define a set of facts V pAdd p X p V U pDelete p ap V Let A be the answer set of the logic program ground Z K C U V U 12 18 which is minimal wrt the optimize statements O then A K K p Z add p z A U p x delete p x A is the unique valid minimal change of KB X 5 Refinements In this section we refine the above direct translation in order to increase the efficienc
16. en writing facts below In addition to rules a logic program can contain minimize statements of the form minimize wiQL4 lk wy OL Besides literals and integer weights w for 1 j lt k a minimize statement includes integers L providing priority levels A minimize statement distinguishes optimal an swer sets of a program as the ones yielding the smallest weighted sum for the true literals among sharing the same highest level of priority L while for L gt L the sum equals that of other answer sets For a formal introduction we refer the interested reader to Simons et al 2002 where the definition of answer sets for logic programs contain ing extended constructs cardinality constraints and minimize statements under choice semantics is defined Likewise first order representations commonly used to encode problems in ASP are only informally introduced In fact gringo requires programs to be safe that is each vari Evolution of Ontologies using ASP 7 able must occur in a positive body literal Formally we only rely on the function ground to denote the set of all ground instances ground II of a program II containing first order variables Further language constructs of interest include conditional literals like a b the range and pooling operator and as well as standard arithmetic operations The 66 99 connective expands to the list of all instances of its
17. enote that we only want to consider the last current incremental step k in rules 35 and 36 newPdel k pj pDelete p U avail s si p U p kb p e U nAvail qn U V m type Vi Va 35 step level delete p step lev Dus pj 1 newPdel k pj pDelete p U avail s si p U pAdd pi kb p e U kb qn Wa dom type Vn Va 36 step level delete p step level delete p 1 for all 1 lt l j body l Z j 1 h lt head For constraints r with level r lt k the following rule set 37 and 38 capture Condition III and check whether one of the potential side effects on the rhs of the rule is newly added on level k newPdel k pj U lt pDelete p avail s si p 0 NS pi kb pj e U nAvail qn U Vn dom type Vn Vn 37 step level delete p newPdel k pj pDelete p avail s s p U newPadd k pi U kb p e U kb an U Vn dom type Vn Va 38 step level delete p forall 1 lt l j body l Z j 1 lt h lt head The rule sets 39 and 40 check if at least one of the potentially available not available entries has been added at step k newPdel k p pDelete pj avail s s p U pAdd pi 0 kb p U e U nAvail qn Vn dom type Vs Va 1 newAvail k s si p U 39 U nNewAvail k qn U Vn dom type Vn Vn oldStep leve
18. ered in terms of severity using a special ordering denoted by lt prea for example the addition of a class predicate cs is more important than the addition of a subsumption predicate c s4 i e c IsA lt prea cs Then a delta A is preferable than A i e Ay x A2 iff the most important predicate per lt prea appears less times in Aj In case of a tie the next most important predicate is considered and so on If the two deltas contain an equal number of ground facts per predicate as in the case of our example with A Ko K4 1 A Ko K43 the ordering considers the constants involved a constant is considered more important if it 6 Ostrowski et al occupies a higher position in its corresponding subsumption hierarchy in the original KB In this respect A Ko K4 1 causes less important changes upon Ko than A Ko K4 2 because the former affects b c c IsA c b c IsA b c whereas the latter affects c a c IsA a c c IsA c a this means that 41 is a preferred result over K4 2 per the principle of minimal change The ordering between ground facts that allows this kind of comparison is denoted by c Formally A Ko K41 x A Ko K4 2 note that the subscript Ko in the ordering is important because the position of constants in the hierarchy of the original KB Xo is considered For a more formal and detailed presentation of the ordering we refer the reader to Konstantinidis et al 2008 We denote the evolution
19. f level 1 to repair our KB If with this subset of possible side effects no solution to the problem can be found we increase k by one and continue the computation reusing the already computed part of the potential side effects For grounding this means we only want to have the possibility to find potential side effects p z of a level p lt k To exploit this idea we associate each constraint r with a level denoted by level r The level of r is the maximum of the levels of the predicates qn p that appear in the Ihs of the corresponding ASP rules of r namely 8 and 9 10 11 respectively see Section 4 To express the corresponding ASP rules we need some general rules First 21 stip ulates the fact step for the current level as we move to subsequent levels step is up dated to indicate the level we processed or are just processing Rule 22 stipulates the fact oldStep 1 for all already processed levels 1 step k 21 oldStep k 1 k gt 1 22 To denote potential side effects of a given level k we use the predicates newPadd k p x and newPdel k p x unlike pAdd pDelete which contain potential side effects of all 12 Ostrowski et al levels The ASP rules representing Condition I originally expressed using 3 and 4 for pAdd pDelete are expressed for the new predicates as follows newPdel k T X changeDel T X k 1 kb T X 23 newPadd k T X changeAdd T X k 1 kb T X 24
20. for large ontologies and also show that the scalability of the approach depends on the morphology of the input 1 Introduction The Semantic Web s vision originally proposed in Berners Lee et al 2001 is an exten sion of the current web that provides a common framework including tools languages and methodologies to allow information on the web to be both understandable by humans and processable by machines this enables people and machines to work in cooperation and process meaning and information on the web Ontologies describe our understanding of the physical world in a machine processable format and form the backbone of the Seman tic Web They are usually represented using the RDF S McBride et al 2004 Brickley and Guha 2004 language in a nutshell RDF S permits the representation of different types of resources like individuals classes of individuals and properties between them as well as basic taxonomic facts such as subsumption and instantiation relationships Several recent works Serfiotis et al 2005 Motik et al 2007 Lausen et al 2008 Cali et al 2009 Tao et al 2010 have acknowledged the need for introducing constraints in ontologies Given that RDF S does not impose any constraints on data any application specific constraints e g functional properties or semantics e g acyclicity in subsump tions can only be captured using declarative formalisms for representing constraints on top of RDF S data In this pa
21. id change w r t Ko iff Ko C is valid In our example C is not a valid change because XC violates rule R13 thus it cannot be returned as an evolution result The only possible solution to this problem is to remove c sA b a from K4 removing c_IsA a b is not an option because its addition is dictated by the change This is an extra modification that is not part of the original change but is in a sense enforced by it and the related principles such extra modifications are called side effects After applying this side effect we would get K2 Ko U c_IsA a b N c IsA b a We note that Ko is no good either because R12 is violated To resolve this we need to apply more side effects In that case we have two options either removing c_IsA b c or c_IsA c a This leads to two alternative solutions namely K3 4 Ko U c_IsA a b N c IsA b a c_ IsA b c and K3 2 Ko U c_IsA a b c_IsA b a c_IsA c a Again adding c_IsA b a is not an option because its addition was dictated in a previous step Once again K3 4 32 are not valid so one more step is required for K3 R12 is violated because c_IsA c a c_IsA a b K3 but c_IsA c b K3 1 so we add c_IsA c b the other options are overruled from previous steps resulting to K4 1 for K3 2 R12 is violated again because c_IsA a b c_IsA b c Ka but c_IsA a c Ka so we add c_IsA a c the other options are overruled from previous steps resul
22. ight hand side rhs of r becomes true and the left hand side Ihs is made false Thus if a potential addition V makes the rhs of r true and Ihs is false then we have to add some fact from the Ihs of the implication to the potential positive side effects to make lhs true Condition II or remove some fact from rhs to make it false Condition IIT If a removal in V makes the Ihs of r false and all other facts in rhs are available so rhs is true we have to remove some fact from rhs to make it false Condition IV To do that we first define a select function s X X X on a set X of atoms to remove exactly one element of a set So we can then refer to the element X and the rest of the set s X separately Abusing notation we write pred p U for pred p U pred pn U for any predicate name pred where p is the set of atoms pi U ve Poody Formally a set V is a set of potential side effects for a KB K and a change C if the following conditions are all true IreVifreC andr Korze C and x K II VV q U Vn V if s p U C Vt UK and p U V and q U V E K III p U V if s si p U C Vt UK and p U V and p U K and for all V either q U Vn V or qn U Vn K IV p V if si p Vt UK and p U K and VV q Vp V for each constraint r defined in Section 2 3 and for all variable substitutions for wrt gt E U and for all 1
23. k the original knowledge base K GO or CIDOC ran domly selected 6 entries J C K and deleted I from K resulting in a valid KB X We then created our pool of changes Ic which contains 6 randomly selected entries from K as deletions and the 6 entries in J as additions The change C for our benchmark was created by randomly selecting n entries from Je 1 lt n lt 6 Our experiment measured the time required to apply C upon K The above process was repeated 100 times for each n 1 n lt 6 giving a total of 600 runs The benchmark was run on a machine with 4 x 4 CPU s 3 4Ghz each and was restricted to 4 GB of RAM Our implementation uses a single threaded version of gringo3 0 4 and clasp2 0 0RC1 A timeout of 3600 seconds was imposed on the experiments so that any run that reached this timeout was stopped Table 7 contains the results of our experiments in GO and CIDOC respectively Each row in the table contains the experiments for one value of n size of C and shows the average CPU time in seconds of all runs that did not reach the timeout column times the average level of incremental grounding where the solution was found level and the number of timeouts timeouts The results of our experiments are encouraging GO despite its large size and the in herently intractable nature of the evolution problem can evolve in a decent amount of time and has very few timeouts On the other hand CIDOC exhibits
24. l delete p newPdel k pj lt pDelete p avail s si p 0 pAdd pi 0 kb pj eG kb an U V dom type Vn Va 40 1 newAvail k s s p U oldStep level delete p for all 1 1 7 body l j 1 lt h head Condition IV is captured using the rules 41 to 43 that correspond to the rules 11 in Section 4 For the current incremental step k we use newPdel k pi pDelete pi e U avail si p U kb pi U pDelete qn U Vn dom type Vn Vn 41 step level delete pi step level delete pi 1 for all 1 lt l body 1 h lt head For constraints r with level r lt k the rule 42 14 Ostrowski et al c lsA a b c IsA c c c IsA c b c IsA b b c IsA a a c IsA a c Table 6 Potential Side effects of example in Fig 1 to level 7 checks whether one of the potential side effects on the rhs of r is newly added on level k newPdel k pi pDelete pi e U avail si p kb pi 0 newPdel k qn Vn dom type Vn Vn s 42 step level delete pi for all 1 lt l lt body 1 h lt head To capture Condition IV for all constraints r with level r k the rule 34 checks if at least one of the potentially available not available entries has been added at step k gt gt gt gt newPdel k p U 4 pDelete m U e U avail si p U kb pi U pDelete qn U Vn dom type Vn Vn 4
25. n Konstantinidis et al 2008 we recast the problem and the corresponding algo rithm in terms of ASP rules thereby reducing the problem to an ASP program that can be solved by an efficient and optimized ASP reasoner This resulted to a flexible approach for changing ontologies Given that the problem is inherently exponential in nature Konstantinidis et al 2008 the reported times Table 7 for the evolution of two real world ontologies are decent To the best of our knowledge there is no comparable approach because the approach presented in Konstantinidis et al 2008 did not report any experiments and other similar approaches either do not consider the full set of options therefore returning a suboptimal evolution result or require user feedback to perform the change which is not the case in our implementation An interesting side product of our approach is that the validity of an ontology can be checked and or imposed by simply applying the empty change upon it so we plan to explore this option in the future for repairing ontologies In addition we will consider further optimizations that will improve the efficiency of the proposed modeling such as using incremental ASP solvers such as iclingo Gebser et al 2008 Finally given that the application of many small changes is usually faster than the application of a single large one because it leads to much smaller sets of potential side effects we plan to consider methodologies for
26. objective of the present work is to recast the problem of ontology evolution in terms of ASP rules and use an efficient grounder and ASP solver to provide a modular and flexible solution In our work we use gringo for the grounding and clasp for the solving process as they are both state of the art tools to tackle ASP problems Gebser et al Our work is based on the approach presented in Konstantinidis et al 2008 and uses similar ideas and notions The main contribution of this work is the demonstration that ASP can be used to solve the inherently difficult problem of ontology evolution in a decent amount of time even for large real world ontologies ASP was chosen for its advantages in terms of a principled rather than ad hoc implementation its modularity and flexibility and for being a state of the art technique to tackle hard combinatorial problems In the next section we describe the problem of ontology evolution and briefly present the solution proposed in Konstantinidis et al 2008 In Section 3 we present ASP Section 4 is the main section of this paper where our formulation of the problem in terms of an ASP program is presented and explained This approach is refined and optimized in Section 5 We present our experiments in Section 6 and conclude in Section 7 Evolution of Ontologies using ASP 3 2 Problem Statement 2 1 RDF S The RDF S McBride et al 2004 Brickley and Guha 2004 language uses triples of the form subject p
27. ollowing transformation for each r R kb p U 1 kb qi U Vi dom type V V e U 18 for all 1 lt i head Rule 18 ensures that if the rhs of a constraint is true wrt to the new KB and the Ihs if false then the selected set of side effects 1s no valid solution Proposition 2 Given a KB K a change C and a set of potential side effects V we define a set of facts V pAdd p x p x V U pDelete p p x V Let A be the answer set of the logic program ground Z K C U V U 12 18 then A K K p x add p Z A U p x delete p Z A is a valid change of KB K 4 3 Finding the Optimal Solution The solutions contained in add delete are all valid solutions per the above proposition but only one of them is optimal and should be returned per the Principle of Minimal Change So the solutions must be checked wrt to the ordering lt x For the most important criteria lt preq we generate minimize statements see Section 3 that minimize the number of occurrences of the applied side effects For adding classes the corresponding minimize statement looks as follows minimize kb cs X L kb cs X 19 Here L denotes the level of the minimize constraint So several minimize constraints can be combined and the order of the minimize statements is respected For the ordering c we need to compare the distance of the entries using their subsumption relation to th
28. per we will consider DED constraints Deutsch 2009 which form a subset of first order logic and have been shown to allow the representation of many use ful types of constraints on ontologies we will consider populated ontologies represented using RDF S and use the term RDF S knowledge base KB to denote possibly interlinked 2 Ostrowski et al and populated RDF S ontologies with associated DED constraints RDF S KBs being representations of the real world are often subject to change for various reasons including changes in the modeled world new information on the domain newly gained access to in formation previously unknown or classified and other eventualities Umbrich et al 2010 Stojanovic et al 2002 Flouris et al 2008 Therefore an important task towards the real ization of the Semantic Web is the introduction of techniques that allow the efficient and intuitive changing of ontologies in the presence of constraints Given the constraints one should make sure that the evolution result is valid i e it does not violate any constraints This is often called the Principle of Validity Alchourron et al 1985 In addition the Prin ciple of Success Alchourron et al 1985 should be satisfied which states that the change requirements take priority over existing information i e the change must be applied in its entirety The final important requirement is the Principle of Minimal Change Alchourron et al 1985 which states th
29. redicate object to express knowledge RDF S permits the specification of various entities called resources which may be classes representing collections of re sources properties which are binary relations between resources and individuals which are resources We use the symbol type u to denote the type of a resource u stating whether it is a class a property etc RDF S also allows for the description of various pre defined relations between resources like the domain and range of properties subsumption relationships between classes and between properties and instantiation relationships be tween individuals and classes or between pairs of individuals and properties RDF S KBs are commonly represented as labeled graphs whose nodes are resources and edges are re lations see Fig 1 for an example In that figure a b and c are classes whereas x is an individual Solid arrows represent subsumption relationships between classes e g b is a subclass of c and dashed arrows represent instantiation relationships e g x is an instance of b The bold arrow represents the change we want to make namely to make a a subclass of b 2 2 Ontology Evolution Principles As explained above in the presence of constraints in the ontology one should make sure that the evolution result is valid i e it does not violate any constraints This is often called the Principle of Validity Alchourron et al 1985 Manually enforcing this principl
30. responding set of potential side effects for the current incremental step k newPadd k qn U Va pAdd qn Vn avail si p U pAdd pi e U kb qn U V dom type Vn Va 32 step level add qn step level add qn 1 for all 1 1 body 1 h lt head For constraints r with level r lt k the following rule 33 captures Condition II and checks whether one of the potential side effects on the ths of the rule is newly added on the level k by using newPadd in the body of the rule We only add step level r to the rule to consider all levels newPadd k dh U Vn Si pAdd qn U V avail si p U newPadd k pi e U kb an U Va 33 dom type Vn Vn step level add qn for all 1 body 1 h lt head To capture Condition II for all constraints r with level r E pu k the rule 34 checks if at least one of the potentially available not available Evolution of Ontologies using ASP 13 entries has been added at step k We add oldStep level r to the rules to consider only levels k newPadd k qn Vn pAdd qn Vn avail si p pAdd pi e U kb an U Va dom type Vn 9n G4 1 newAvail k si p U oldStep level add qn for all 1 lt body 1 h lt head For Condition III rules 35 to 40 correspond to the rules expressed in 9 and 10 We use step level r step level r 1 in the rule body to d
31. s correspond to deletions Ontological constraints are modeled using DED rules Deutsch 2009 which allow for formulating various useful constraints such as primary and foreign key constraints used e g in Lausen et al 2008 acyclicity and transitivity constraints for properties as in Serfiotis et al 2005 and cardinality constraints used in Motik et al 2007 Here we use the following simplified form of DEDs which still includes the above constraint types vU V we 3V qi U V ce U pi U AA Pooay U gt where e U is a conjunction of in equality atoms We denote by p the facts pi U D Poody U and by q the facts aU Vi ie Qheaa U Vnead Table 2 shows some of the constraints used in this work for a full list refer to Konstantinidis et al 2008 We say that a KB X satisfies a constraint r or a set of constraints R iff K F r KF R Given a set of constraints R K is valid iff K F R Now consider the KB Ko and the change of Fig 1 which can be formally expressed using the ground facts of Table 3 To satisfy the principle of success we should add ci x K cs a cs b cs c 9 eJsA bc cIsA b a c IsA c a c Inst r b c Inst r c c Inst r a C c IsA a b Table 3 Facts from example in Fig 1 Evolution of Ontologies using ASP 5 c IsA a b to Ko getting K Ko U c IsA a b The result X1 is called the raw application of C upon Ko and denoted by K Ko C C is called a val
32. ting to Ka Now K4 K4 2 are both possible results for the evolution as they satisfy the principles of success and validity It remains to determine which of the two is preferable in the sense of the principle of minimal change i e which of the two is closer to Ko As explained above to determine this we need to develop an ordering that would rank K44 K4 2 in terms of closeness to Ko Note that X4 differs from Ko in having added c_IsA a b c_IsA c b and deleted c_IsA b a c_IsA b c whereas K4 2 differs from Ko in having added c_IsA a b c IsA a c and deleted c IsA b a c IsA c a We express this by using difference sets called deltas contain ing the ground facts that need to be added and the negated ground facts that need to be deleted to get from one KB to another denoted by A K K In our example A Ko K41 c_IsA a b c_IsA c 0 c IsA b a c IsA b c A Ko K42 c_IsA a b c IsA a c c IsA b a c IsA c a Thus the ranking of closeness is essentially reduced to ranking A Ko K4 1 A Ko K4 2 note that both deltas have the same size and this occurs in many change scenarios so ranking should be based on more subtle differences like the severity of changes in each delta not just their cardinality In Konstantinidis et al 2008 a specific intuitive ordering is described denoted by lt x where K the original KB In a nutshell the available predicates are ord
33. ts represent resources in RDF S parlance and for each type of relation 4 Ostrowski et al RDH S triple Intuitive meaning Predicate c rdf type rdfs Class cis a class cs c x rdf type rdfs Resource is an individual ci x c rdfs sub ClassOf ca IsA between classes c IsA c1 c2 x rdf type c class instantiation c Inst z c Table 1 Representation of RDF S Triples Using Predicates ID Constraint Intuitive Meaning R5 VU V c IsA U V cs U cs V Class subsumption R12 VU V W Class IsA transitivity c IsA U V A c IsA V W c IsA U W R13 VU V c IsA U V c IsA V U L Class IsA irreflexivity Table 2 Ontological Constraints ship that can appear in an RDF S KB a different predicate is defined For example the triple a rdfs subClassOf b which denotes that a is a subclass of b is represented by the ground fact c_IsA a b For the rest of the paper predicates and constants will start with a lower case letter while variables will start with an upper case letter Table 1 shows some of the predicates we use and their intuitive meaning see Konstantinidis et al 2008 for a complete list We assume closed world i e we infer that K p Z whenever p x d K A change C is a request to add remove some facts to from the KB For practical purposes a change is modeled as a set of possibly negated ground facts where positive ground facts correspond to additions and negated one
34. view 23 2 117 152 GEBSER M KAMINSKI R KAUFMANN B OSTROWSKI M SCHAUB T AND THIELE S A users guide to gringo clasp clingo and iclingo Available at http potassco sourceforge net GEBSER M KAMINSKI R KAUFMANN B OSTROWSKI M SCHAUB T AND THIELE S 2008 Engineering an incremental ASP solver In Proceedings of the Twenty fourth International Conference on Logic Programming ICLP 08 M Garcia de la Banda and E Pontelli Eds Lecture Notes in Computer Science vol 5366 Springer Verlag 190 205 KONSTANTINIDIS G FLOURIS G ANTONIOU G AND CHRISTOPHIDES V 2008 A formal approach for rdf s ontology evolution In Proceedings of the 18 European Conference on Artifi cial Intelligence ECAI 08 405 409 LAUSEN G MEIER M AND SCHMIDT M 2008 Spargling constraints for rdf In Proceedings of 11 International Conference on Extending Database Technology EDBT 08 499 509 MCBRIDE B MANOLA F AND MILLER E 2004 Rdf primer www w3 org TR rdf primer MoTIK B HORROCKS I AND SATTLER U 2007 Bridging the gap between owl and relational databases In Proceedings of 17 International World Wide Web Conference WWW 07 807 816 SERFIOTIS G KOFFINA I CHRISTOPHIDES V AND TANNEN V 2005 Containment and mini mization of rdf s query patterns In Proceedings of the 4 International Semantic Web Conference ISWC 05 SIMONS P NIEMELA I AND SOININEN T 2002 Extending
35. will eventually not appear in any valid change 4 2 Solving the Problem Note that the set of potential side effects computed above contains all options for evolving the KB However some of the potential changes in pAdd pDelete are unnecessary in our running example the preferred solution was c IsA a b c IsA b a c IsA b c see Section 2 whereas Table 5 contains many more facts To compute the actual side effects which is a subset of the side effects in pAdd pDelete we use a generate and test approach In particular we use the predicate add p X and delete p i to denote the set of side effects p z A K K respec tively 2p z A K K and use choice rules to guess side effects from pAdd pDelete to add delete respectively see 12 13 below add T X pAdd T X 12 delete T X pDelete T X 13 10 Ostrowski et al Our changed KB is expressed using predicate kb and is created in 14 and 15 consisting of every entry from the original KB that was not deleted and every entry that was added kb T X kb T X delete T X 14 kb T X add T X 15 Moreover we have to ensure that required positive negative changes C are not in the new KB respectively Principle of Success 16 and 17 changeAdd T X kb T X 16 changeDel T X kb T X 7 To ensure the Principle of Validity we construct all constraints from the DEDs R using the f
36. y of our logic program Our first optimization attempts to reduce the size of the potential side effects V whereas the second takes advantage of deterministic consequences of certain side effects to speed up the process 5 1 Incrementally Computing Side Effects As the set of potential side effects directly corresponds to the search space for the problem see 12 13 in Section 4 we could improve performance if a partial set of potential side effects that contains the minimal solution was found instead of the full set According to the ordering of the solutions lt prea we use the symbol level p for each fact p Z to denote the severeness of its application per lt p eq We start with the least severe impact level 1 incrementally assigning higher numbers for more severe changes For example adding a class subsumption c sA is on level 7 level c_IsA 7 removing such a subsumption has level c IsA 15 and adding a class cs has level cs 31 For a complete list of such levels see Konstantinidis et al 2008 Per definition of the ordering a set of side effects that does not contain any fact p z with level p gt k is better than a solution that uses at least one side effect p 2 such that level p gt k Thus we split the computation of the possible side effects into different parts one for each level of lt q optimization We start the computation of possible side effects with k 1 only adding facts o
Download Pdf Manuals
Related Search