Evolution of OWL 2 QL Knowledge Bases: From Inexpressibility to Practical Approaches

Abstract

Knowledge bases (KBs) are not static entities: new information constantly appears and some of the previous knowledge becomes obsolete. In order to reflect this evolution of knowledge, KBs should be expanded with the new knowledge and contracted from the obsolete one. This problem is well-studied for propositional but much less for first-order KBs. In this work we investigate knowledge expansion and contraction for KBs expressed in OWL 2 QL, a tractable fragment of the Web Ontology Language OWL 2. We start with a novel knowledge evolution framework and natural postulates that evolution should respect, and compare our postulates to the well-established AGM postulates. We then review well-known model and formula-based approaches for expansion and contraction for propositional theories and show how they can be adapted to the case of OWL 2 QL. In particular we show inexpressibility challenges for the former and practical algorithms for the latter approaches.

-

Ontology Web Language (OWL) provides excellent mechanisms for representing structured knowledge as knowledge bases (KBs). OWL is the standard ontology language of the Semantic Web. KBs have been successfully used in various applications including Web search [ 19,1,2 ], and search over KGs [ 5,37,40,39,38 ], Medicine [ 3 ], Media [ 31 ], E-commerce [ 8 ], data integration [ 23,25,20,35 ] and industrial modelling [ 22 ] and analytics [ 26,24,34,33 ]. In these and other applications KBs naturally change over time and thus KB management systems should be equipped with services to support KB evolution [ 13 ].

In KB evolution the task is to incorporate new knowledge N into an existing KB K, or to delete some obsolete knowledge N from K, in order to take into account changes that occur in the underlying domain of interest [ 21 ]. The former evolution task is typically referred to as knowledge expansion and the latter as contraction. In general, the new (resp., obsolete) knowledge is represented by a set of formulas denoting those properties that should be true (resp., false) after the ontology has evolved. In the case where the new knowledge interacts in an undesirable way with the knowledge in the ontology, e.g., by causing the ontology or relevant parts of it to become unsatisfiable, the new knowledge cannot simply be added to the ontology. Instead, suitable changes need to be made in the ontology so as to avoid the undesirable interaction, e.g., by deleting parts of the ontology that conflict with the new knowledge. Different choices are possible, corresponding to different semantics for knowledge evolution [ 4,41,21,11,12,36 ].

The main two types of semantics that were proposed for the case of propositional knowledge are model-based [ 41 ] and formula-based [ 11 ]. In model-based semantics the idea is to resolve the undesirable interaction at the level of models of K and N . For example, in model-based expansion the result of evolution are those models of N that are minimally distant from the ones of K, where a suitable notion of distance needs to be chosen, possibly depending on the application. In formula-based semantics the idea is to do evolution at the level of the deductive closure of the formulae from K and N . Since many (possibly counter-intuitive) semantics can be defined within the model or formula-based paradigm, a number of evolution postulates [ 21,11 ] have been proposed and they define natural properties a semantics should respect. It is thus common to verify for each evolution semantics whether it satisfies the postulates.

For the case of propositional knowledge, there is a thorough understanding of semantics as well as of computational properties of both expansion and contraction. The situation is however much less clear when it comes to DL KBs, which are decidable first-order logic theories. Differently from the propositional case, in general they admit infinite sets of models and infinite deductive closures. Moreover, going from propositional letters to first-order predicates and interpretations, on the one hand calls for novel postulates underlying the semantics of evolution, and on the other hand broadens the spectrum of possibilities for defining such semantics. A number of attempts have been made to adapt approaches for the evolution of propositional knowledge to the case of DLs, cf. [ 12,10,36,32 ]. However, there is no thorough understanding of evolution from the foundational point of view even for DLs with the most favorable computational properties, such as the logics of the OWL 2 QL [ 7 ] and E L [ 6 ] families, which are at the basis of two tractable fragments of OWL 2. 2

Contributions

In this work we address this problem and propose an exhaustive study of evolution for OWL 2 QL. In particular, we address the problem considering three dimensions: 1. knowledge evolution tasks: we study how knowledge can be expanded or contracted; 2. type of evolution semantics: we study model-based and formula-based semantics; 3. evolution granularity: we study when evolution affects the TBox (for terminological knowledge), or the ABox (for assertional knowledge), or both of them. We provide the following contributions [ 43 ]: – We propose a knowledge expansion and contraction framework that accounts for

TBox, ABox, and general KB evolution. – We propose natural evolution postulates and show how they are related to the wellknown AGM postulates [ 21 ]. – We show how one can rigorously extend propositional model-based evolution semantics to the first-order case, defining a 5-dimensional space of possible options, comprising 3 24 model-based evolution semantics for DLs that essentially include all previously proposed model-based approaches for DLs. These dimensions are: (1) ABox vs. TBox vs. general evolution; (2) expansion vs. contraction; (3) global vs. local; (4) symbol vs. atom; (5) set inclusion vs. cardinality. 5 For most of these semantics and the case of OWL 2 QL KBs we prove negative expressibility results: in general evolution of OWL 2 QL KBs cannot be expressed as a OWL 2 QL KB. – We investigate formula-based evolution for OWL 2 QL. In particular, for known formula-based evolution approaches [ 11 ] we show intractability of computing evolution results for OWL 2 QL KBs. Moreover, we propose a non-deterministic approach for general KB evolution, which turns out to become deterministic for ABox evolution; for both cases we develop polynomial-time algorithms.

3 Illustration of Contributions

We now exemplify the inexpressibility of evolution results under model-based semantics and then show how the same examples can be solved with formula based semantics.

3.1 Illustration of Inexpressibility

In order to understand why model-based approaches to evolution are problematic for OWL 2 QL recall the following property of the logic. Let M be a set of interpretations such that there are OWL 2 QL assertions ', such that – J j= ' _ for every J 2 M, and – there are J', J 2 M such that J' 6j= ' and J 6j= .

Then, there is no OWL 2 QL KB K such that M = Mod(K).

We now illustrate this phenomenon on several evolution scenarios. We will do it on the intuitive level and without referring to concrete model-based semantics. Formal details can be found in [ 43 ].

Consider a KB where the structural knowledge is that wives (concept Wife) are exactly those individuals who have husbands (role HasHusband) and that some wives are employed (concept EmpWife). Bachelors (concept Bachelor) cannot be husbands. Priests (concept Priest) are clerics (concept Cleric) and clerics are bachelors. Both clerics and wives are receivers of rent subsidies (concept Renter). We also know that adam and bob are priests, mary is a wife who is employed and her husband is john. Also, carl is a catholic minister (concept Minister).

This knowledge can be expressed in OWL 2 QL by the KB Kex, consisting of the following TBox T and ABox A:

T = f Wife v 9HasHusband; 9HasHusband v Wife;

EmpWife v Wife; Bachelor v :9HasHusband ; Priest v Cleric; Cleric v Bachelor;

Cleric v Renter; Wife v Renter g

A = f Priest(adam); Priest(bob); EmpWife(mary); HasHusband(mary; john) g 5 Note that our proposed model-based semantics can be applied to any description logic. In the TBox expansion scenarios the new information NT can state that wives are not renters anymore or that priests are not renters anymore:

NT = fPriest v :Renterg; or NT = fWife v :Renterg: In both cases the inexpressibility phenomenon holds. Indeed, in the first case since priests are not renters anymore, in each model of the evolution result both axioms ' = (Priest v Cleric), = (Cleric v Renter) cannot hold at the same time, but, due to the minimality of change principle, at least one of them should hold. The second case is analogous but with ' = (EmpWife v Renter) and = (Wife v Renter). These two cases hold for different model-based semantics and nicely illustrate that the inexpressibility property affects evolution at the TBox level even when there is a rather simple interaction between atomic concepts such as A v B v C or A v B and A v C. The same effect can be also shown for TBox contraction: instead of adding Priest v :Renter to the example KB, one can contract the KB with the axiom Priest v Renter and essentially the same argument for inexpressibility will hold.

In the ABox expansion scenario the new information Ne consider the case when John becomes a priest, that is,

NA = fPriest(john)g: The example TBox entails that in this case Mary cannot be the wife of John anymore: John becomes a bachelor who cannot be a husband. In this case one can show that in each model of the evolution result the disjunction of the two ABox axioms ' = Priest(bob) and = Priest(adam) holds but there are models where one of the two holds but not the other, that is, when either Bob or Adam becomes the new husband of Mary. This again leads to the inexpressibility of the evolution result.

3.2 Illustration of Bold Semantics

Given a KB and new knowledge that should be added to the KB, Bold Semantics essentially takes a maximal subset of axioms (entailed) from the KB that together with the new knowledge is satisfiable. There clearly may be more than one such maximal subset and thus Bold Semantics is non-deterministic for OWL 2 QL. On the positive side, computation of evolution results under Bold Semantics can be done in time polynomial in the size of the KB. Moreover, one can show that if the evolution of OWL 2 QL KBs affects only the ABox level, then the evolution result is always is unique.

Following our example, evolution with any of the NT should delete either ' or from the original KB, thus there is non-determinism. While, for NA evolution is unique and it requires to drop from the original KB the fact that Mary is a wife of john but add that she is a wife of someone 9HasHusband(mary). 3.3

Postulates

Postulates are basic principles that describe the rational behind knowledge evolution. They are typically defined independently from the actual approaches or algorithms to compute evolution results. Moreover, in order to make sure that a defined approach (algorithm) makes sense one typically verifies whether it confirms some postulates. The classical AGM postulates for knowledge evolution have originally be defined for the case of propositional knowledge. At the same time, the ’granularity’ of knowledge changes when moving from propositional to Description Logics: the atomic statements of a DL, namely the ABox and TBox axioms, are more complex than the atoms of propositional logic. On the other hand, a set of propositional formulas makes sense, intuitively, if it is satisfiable, while a KB can be satisfiable, but incoherent, that is, one or more concepts are necessarily empty. Therefore, we proposed new postulates for expansion and contraction, to be adopted in the context of evolution on the Semantic Web. Moreover, we showed how our postulates are related to the AGM ones and showed that our evolution operators satisfy the proposed postulates. Due to lack of space we now present only postulates for knowledge expansion.

Let K be the KB and Ke0 the result of its expansion with new knowledge Ne. E1: Expansion should preserve the coherence of the KB, that is, if K is coherent, then so is Ke0.

E2: Expansion should entail all new knowledge, that is, Ke0 j= Ne.

E3: Expansion with old information should not affect the KB, that is, if K j= Ne, then

Ke0 K.

E4: The union of N2e with the expansion of K with N1e implies the expansion of K with N1e [ N2e.

E5: Expansion should not depend on the syntactical representation of knowledge, that is, if K1 K2 and N1e N2e, then K10e K20e. 4

Discussion of Contributions

The first important conclusion from our work is that model-based approaches are intrinsically problematic for KB evolution, even in the case of such a lightweight DL as OWL 2 QL. Indeed, recall that OWL 2 QL is not closed under evolution for any of the model-based semantics and thus these semantics are impractical. As a consequence, one has either to search for conceptually different semantics that rely on other principles of ‘composing’ the output set of models constituting the evolution result, or one has to develop natural restrictions on how model-based approaches can ‘compose’ this set. An alternative approach would be to develop approximation techniques that allow one to efficiently capture evolution results.

A second important conclusion is that classical formula-based approaches are too heavyweight from the computational point of view and thus their practicality is questionable. On the other hand, the most conceptually simple model-based semantics such as bold semantics can potentially lead to practical evolution algorithms. However, their practicality requires further empirical evaluation. Finally, we have discussed that the classical evolution postulates that were originally developed for propositional theories are not directly applicable to the case of first-order knowledge since they are blind to some fundamental properties of such knowledge, such as coherency. We have shown how to adapt such postulates to the richer setting considered here, and have analyzed whether the various model-based and formula-based semantics satisfy the revised postulates.

We believe that our work opens new avenues for research in the area of knowledge evolution, which is an important part of knowledge engineering, since it shows how to lift approaches to knowledge evolution from the propositional to the first-order case. Moreover, we have presented techniques that allow one to prove inexpressibility of model-based evolution, and coNP-hardness of formula-based evolution. We believe that these techniques can be relevant to knowledge management tasks beyond evolution. 5

Future Work

We see several important directions for future work. First, the problem of expressibility in OWL 2 QL is still open for various model-based evolution semantics (see Table 1). These settings are all for ABox expansion and contraction under global model-based semantics. An important research direction is to apply in practice the ideas we developed and, in particular, to implement an ontology evolution system. The system can be based on formula-based approaches and implement Algorithms 1–4 that we proposed. Such system could also be based on approximations of model-based semantics, which are out of the scope of this paper, see, e.g., [ 30,28,27,29,28,10,17,18 ]. Then, it would be interesting to conduct an empirical evaluation for various semantics, in order to establish which semantics give more intuitive results from the users’ point of view, and which ABox evolution approaches are more scalable. A further direction to investigate is to identify the minimum extensions of OWL 2 QL that would allow it to capture the results of model-based evolution for OWL 2 QL KBs. For this, one can draw inspiration from the work in [ 32 ]. Also, it is still unknown what are minimal DLs that are closed under local model-based evolution, and in general that are well tailored towards model-based approaches. Then, knowledge evolution has important implications to privacy: one should make sure that changes in knowledge do not make violations in access control policies. This is a non-trivial task since, e.g., new knowledge can interact with the old one in such a way that a person without access rights to a particular knowledge can derive such knowledge from this combination [ 16,14,15 ]. Finally, we believe that it is important to develop knowledge evolution techniques where the user has a much better control over the evolution process. For this, one can draw inspiration from previous work, e.g., from [ 9 ], where the authors proposed techniques to control what syntactic structures of a given KB cannot be changed by the evolution process, or from [ 42 ], where the authors proposed to combine knowledge evolution with models of trust, i.e., the new knowledge in their approach is only partially trusted (note that this scenario inherits the inexpressibility issues of MBAs).

Acknowledgements This work was partially funded by the SIRIUS Centre, Norwegian Research Council project number 237898; by the UNIBZ projects PARCIS and TaDaQua, and by the “European Region Tyrol-South Tyrol-Trentino” (EGTC) under the first call for basic research projects within the Euregio Interregional Project Network IPN12 “Knowledge-Aware Operational Support” (KAOS).

References

1. Freebase : an open, shared database of the world's knowledge . http://www.freebase.com/

2. Google KG . www.google.co.uk/insidesearch/features/search/knowledge.html

3. SNOMED CT . http://www.ihtsdo.org/snomed-ct

4. Abiteboul , S. , Grahne , G.: Update semantics for incomplete databases . pp. 1 - 12 ( 1985 )

5. Arenas , M. , Grau , B.C. , Kharlamov , E. , Marciuska , S. , Zheleznyakov , D. : Faceted search over rdf-based knowledge graphs . J. Web Semant . 37 - 38 , 55 - 74 ( 2016 )

6. Baader , F. , Brandt , S. , Lutz , C. : Pushing the E L envelope . In: IJCAI. pp. 364 - 369 ( 2005 )

7. Calvanese , D. , De Giacomo , G. , Lembo , D. , Lenzerini , M. , Rosati , R. : Tractable reasoning and efficient query answering in description logics: The DL-Lite family . J. of Automated Reasoning 39 ( 3 ), 385 - 429 ( 2007 )

8. Charron , B. , Hirate , Y. , Purcell , D. , Rezk , M. : Extracting semantic information for ecommerce . In: ISWC . pp. 273 - 290 ( 2016 )

9. Cuenca Grau , B. , Jiménez-Ruiz , E. , Kharlamov , E. , Zheleznyakov , D. : Ontology Evolution Under Semantic Constraints . In: KR. pp. 137 - 147 . AAAI Press ( 2012 )

10. De Giacomo , G. , Lenzerini , M. , Poggi , A. , Rosati , R.: On instance-level update and erasure in description logic ontologies . J. of Logic and Computation 19 ( 5 ), 745 - 770 ( 2009 )

11. Eiter , T. , Gottlob , G.: On the complexity of propositional knowledge base revision, updates and counterfactuals . Artificial Intelligence 57 , 227 - 270 ( 1992 )

12. Flouris , G.: On belief change in ontology evolution . AI Communications-The Eur. J. on Artificial Intelligence 19 ( 4 ) ( 2006 )

13. Flouris , G. , Manakanatas , D. , Kondylakis , H. , Plexousakis , D. , Antoniou , G.: Ontology change: Classification and survey . Knowledge Engineering Review 23 ( 2 ), 117 - 152 ( 2008 )

14. Grau , B.C. , Kharlamov , E. , Kostylev , E. , Zheleznyakov , D. : Controlled Query Evaluation over OWL 2 RL Ontologies . In: ISWC ( 2013 )

15. Grau , B.C. , Kharlamov , E. , Kostylev , E. , Zheleznyakov , D. : Controlled Query Evaluation over Lightweight Ontologies . In: DL ( 2014 )

16. Grau , B.C. , Kharlamov , E. , Kostylev , E. , Zheleznyakov , D. : Controlled Query Evaluation for Datalog and OWL 2 Profile Ontologies . In: IJCAI ( 2015 )

17. Grau , B.C. , Kharlamov , E. , Zheleznyakov , D. : How to contract ontologies . In: OWLED ( 2012 )

18. Grau , B.C. , Kharlamov , E. , Zheleznyakov , D. : Ontology Contraction: Beyond the Propositional Paradise . In: AMW ( 2012 )

19. Guha , R.V. , Brickley , D. , Macbeth , S. : Schema. org: evolution of structured data on the web . Commun. ACM 59 ( 2 ), 44 - 51 ( 2016 )

20. Horrocks , I. , Giese , M. , Kharlamov , E. , Waaler , A. : Using semantic technology to tame the data variety challenge . IEEE Internet Computing 20 ( 6 ), 62 - 66 ( 2016 )

21. Katsuno , H. , Mendelzon , A. : On the difference between updating a knowledge base and revising it . In: KR. pp. 387 - 394 ( 1991 )

22. Kharlamov , E. , Grau , B.C. , Jiménez-Ruiz , E. , Lamparter , S. , Mehdi , G. , Ringsquandl , M. , Nenov , Y. , Grimm , S. , Roshchin , M. , Horrocks , I. : Capturing industrial information models with ontologies and constraints . In: ISWC. pp. 325 - 343 ( 2016 )

23. Kharlamov , E. , Hovland , D. , Skjaeveland , M.G. , Bilidas , D. , Jiménez-Ruiz , E. , Xiao , G. , Soylu , A. , Lanti , D. , Rezk , M. , Zheleznyakov , D. , Giese , M. , Lie , H. , Ioannidis , Y.E. , Kotidis , Y. , Koubarakis , M. , Waaler , A. : Ontology Based Data Access in Statoil . J. Web Sem . 44 , 3 - 36 ( 2017 )

24. Kharlamov , E. , Kotidis , Y. , Mailis , T. , Neuenstadt , C. , Nikolaou , C. , Özçep , Ö.L. , Svingos , C. , Zheleznyakov , D. , Ioannidis , Y.E. , Lamparter , S. , Möller , R. , Waaler , A. : An ontologymediated analytics-aware approach to support monitoring and diagnostics of static and streaming data . J. Web Semant . 56 , 30 - 55 ( 2019 )

25. Kharlamov , E. , Mailis , T. , Mehdi , G. , Neuenstadt , C. , Özçep , Ö.L. , Roshchin , M. , Solomakhina , N. , Soylu , A. , Svingos , C. , Brandt , S. , Giese , M. , Ioannidis , Y.E. , Lamparter , S. , Möller , R. , Kotidis , Y. , Waaler , A. : Semantic access to streaming and static data at Siemens . J. Web Sem . 44 , 54 - 74 ( 2017 )

26. Kharlamov , E. , Mehdi , G. , Savkovic , O. , Xiao , G. , Kalayci , E.G. , Roshchin , M. : Semantically-enhanced rule-based diagnostics for industrial internet of things: The SDRL language and case study for siemens trains and turbines . J. Web Semant . 56 , 11 - 29 ( 2019 )

27. Kharlamov , E. , Zheleznyakov , D. : Capturing instance level ontology evolution for DL-Lite . In: ISWC ( 2011 )

28. Kharlamov , E. , Zheleznyakov , D. : On prototypes for Winslett's semantics of DL-Lite ABox evolution . In: DL ( 2011 )

29. Kharlamov , E. , Zheleznyakov , D. : Understanding Inexpressibility of Model-Based ABox Evolution in DL-Lite . In: AMW ( 2011 )

30. Kharlamov , E. , Zheleznyakov , D. , Calvanese , D. : Capturing model-based ontology evolution at the instance level: The case of DL-Lite . J. of Computer and System Sciences 79 ( 6 ), 835 - 872 ( 2013 ). https://doi.org/10.1016/j.jcss. 2013 . 01 .0065

31. Kobilarov , G. , Scott , T. , Raimond , Y. , Oliver , S. , Sizemore , C. , Smethurst , M. , Bizer , C. , Lee , R. : Media meets semantic web - how the BBC uses dbpedia and linked data to make connections . In: ESWC ( 2009 )

32. Liu , H. , Lutz , C. , Milicic , M. , Wolter , F. : Foundations of instance level updates in expressive description logics . Artificial Intelligence 175 ( 18 ), 2170 - 2197 ( 2011 )

33. Mehdi , G. , Kharlamov , E. , Savkovic , O. , Xiao , G. , Kalayci , E.G. , Brandt , S. , Horrocks , I. , Roshchin , M. , Runkler , T.A. : Semantic rule-based equipment diagnostics . In: ISWC . pp. 314 - 333 ( 2017 )

34. Mehdi , G. , Kharlamov , E. , Savkovic , O. , Xiao , G. , Kalayci , E.G. , Brandt , S. , Horrocks , I. , Roshchin , M. , Runkler , T.A. : Semdia: Semantic rule-based equipment diagnostics tool . In: CIKM. pp. 2507 - 2510 ( 2017 )

35. Pinkel , C. , Binnig , C. , Jiménez-Ruiz , E. , Kharlamov , E., May , W. , Nikolov , A. , Bastinos , A.S. , Skjaeveland , M.G. , Solimando , A. , Taheriyan , M. , Heupel , C. , Horrocks , I. : RODI: benchmarking relational-to-ontology mapping generation quality . Semantic Web 9 ( 1 ), 25 - 52 ( 2018 )

36. Qi , G. , Du , J.: Model-based revision operators for terminologies in description logics . In: IJCAI . pp. 891 - 897 ( 2009 )

37. Sherkhonov , E. , Grau , B.C. , Kharlamov , E. , Kostylev , E.V. : Semantic faceted search with aggregation and recursion . In: ISWC . pp. 594 - 610 ( 2017 )

38. Soylu , A. , Giese , M. , Jiménez-Ruiz , E. , Kharlamov , E. , Zheleznyakov , D. , Horrocks , I. : Ontology-based end-user visual query formulation: Why, what , who, how, and which? Universal Access in the Information Society 16 ( 2 ), 435 - 467 ( 2017 )

39. Soylu , A. , Giese , M. , Schlatte , R. , Jiménez-Ruiz , E. , Kharlamov , E. , Özçep , Ö.L. , Neuenstadt , C. , Brandt , S. : Querying industrial stream-temporal data: An ontology-based visual approach . JAISE 9 ( 1 ), 77 - 95 ( 2017 )

40. Soylu , A. , Kharlamov , E. , Zheleznyakov , D. , Jiménez-Ruiz , E. , Giese , M. , Skjaeveland , M.G. , Hovland , D. , Schlatte , R. , Brandt , S. , Lie , H. , Horrocks , I. : Optiquevqs: A visual query system over ontologies for industry . Semantic Web 9 ( 5 ), 627 - 660 ( 2018 )

41. Winslett , M. : Updating Logical Databases. Cambridge University Press ( 1990 )

42. Zheleznyakov , D. , Kharlamov , E. , Horrocks , I. : Trust-sensitive evolution of DL-Lite knowledge bases . In: AAAI . pp. 1266 - 1273 ( 2017 )

43. Zheleznyakov , D. , Kharlamov , E. , Nutt , W. , Calvanese , D. : On expansion and contraction of dl-lite knowledge bases . J. Web Semant . 57 ( 2019 )