The field of Virtual Knowledge Graphs (VKGs) continues to grow in both academic and applied contexts. Yet, the issue of updates in VKG systems has not yet received adequate attention, although it is crucial to manage data modifications at the data source level through the lens of an ontology. In this paper, we focus on VKGs whose ontology is specified in the lightweight ontology language DL-Lite, and we propose diverse settings and research directions we intend to explore to address the challenge of translating ontology-based updates into updates at the level of data sources. We also pay attention to the important problem of automated analysis of mappings, which plays a major role when it comes to reformulating ontology-based update requests into update requests over the data sources.
the ontology layer can be translated into an equivalent first-order query that can be executed
over the data source layer [
The focus of research in VKGs has been on query answering, i.e., on using the ontology layer
and the corresponding knowledge graph to extract data specified through a query from the
underlying data sources. However, ontology-based updates in VKGs remains a challenging
task, which refers to modifying its extensional content with new knowledge that may or may
not be consistent w.r.t. the original one. This task comes with some important challenges.
The first is due to the complex logic-based inferences in ontologies that lead to the need for a
non-deterministic approach to updating knowledge bases [
The main focus of this PhD work is to address the fact that little attention has been paid so far to the problem of updating VKGs through operations that are performed at the ontology level, where changes applied over the ontology are translated into minimally suitable updates over the underlying database through the mappings. A solution to this problem would be of great practical relevance since it would allow the management of the key operations that are of interest in an information system (i.e., queries and updates) through the lens of ontology.
This article initially presents our motivation behind exploring the concept of ontology-based updates within the context of VKGs. To this end, we recall the notion of knowledge base updates as it is investigated in the literature, which provides us key definitions that will be useful for further investigation in our specific research context. Subsequently, we introduce the concept of updates in VKGs, where the goal is to manipulate data source instances by means of operations performed over the ontology layer. We outline the current research challenges for the study of VKG updates, which include defining an inconsistency-tolerant semantics for updates in VKGs, investigating computational properties of update and query operations under such semantics, and finding conditions under which VKG updates can bypass ontology axioms (via query rewriting). Furthermore, we want to study how to enrich a given VKG system with additional information to ensure a unique translation of updates at the ontological level to updates of the data sources.
Here we briefly introduce standard DL Knowledge Bases (KBs). Subsequently, we provide the definition of DL-Lite, the specific DL variant that forms the focus of this research study. Our exposition concludes with an explanation of the concept of VKGs and its principal components. In the following, we assume to have three distinct, countably infinite alphabets: for ontology predicates, for source predicates, and for constants. These alphabets are pairwise disjoint.
Description Logics (DLs) [
DLs allow for modeling a domain of interest by employing concepts and roles within a knowledge base (KB). Specifically, a KB = ⟨ , ⟩ in a DL consists of two components: the TBox and the ABox . A TBox is the intensional level of the KB, capturing the terminological knowledge (or schema) of the domain. An ABox comprises information at the instance level, providing concrete instances of the concepts and roles defined in the TBox.
In this paper, we center our attention on a specific family of DLs known as DL-Lite [
The semantics of a DL KB is given in terms of First-Order interpretations, referring to the
interpretation structures of First-Order Logic [
We recall here the main elements of the VKG framework, which is also known as Ontology-based
Data Access (OBDA) [
A VKG instance is a pair = ⟨, ⟩ where = ⟨ , ℳ, ⟩ is a VKG specification , and is a relational database instance compliant with . Its semantics is defined in terms of FO interpretations over . An interpretation ℐ is a model of ⟨, ⟩ if (i) ℐ |= and (ii) ℐ satisfies the set ℳ() of facts retrieved through ℳ from , where ℳ() is formally defined as follows: ℳ() = { (⃗) | ⃗ ∈ eval ( (⃗), ) and (⃗) ⇝ (⃗) ∈ ℳ}, where eval ( (⃗), ) is the evaluation of (⃗) over . In other words, an interpretation ℐ is a model of ⟨, ⟩ if it is a model of ⟨ , ℳ()⟩. It is worth noting that the retrieved ABox ℳ() is kept virtual, which means that for tasks such as query answering, we do not need to compute it.
Let us consider a VKG instance = ⟨, ⟩ with the specification = ⟨ , ℳ, ⟩. We are interested in ABox updates that consist of basic operations of two types, namely insertions and deletions of ABox facts. Formally, an ABox update is a pair = ⟨ , − ⟩, where + denotes + a finite set of ABox insertions and − denotes a finite set of ABox deletions, where each insertion and deletion is represented as an ABox assertion. We would like to understand how these ABox updates should be reflected in updates at the level of the data sources (DSs). Similarly to ABox updates, we also represent a data source update as a pair = ⟨ , − ⟩, where + denotes a + ifnite set of data source insertions and − denotes a finite set of data source deletions, each of them represented by a data source fact.
Let us consider for now the setting of a plain KB = ⟨ , ⟩, for instance, a university’s KB, which contains comprehensive information about students and their ongoing programs. Suppose that several students have changed their academic majors, and the update , is a list of these students with their new majors. This new data may conflict with some assertions in the ABox . For example, if in no student can be registered in two diferent majors at the same time, and asserts that John is a Computer Science (CS) major, but should be registered in Physics due to , then John can no longer be a CS major. To reconcile the conflict between the existing information in the KB and the new data in , we can update to reflect that John actually has switched majors, which involves removing the outdated major in CS assignment. In most scenarios, to resolve inconsistencies that originate from changes at the instance level, it seems to be more intuitive to update the instance level rather than the intensional level. This means we would want the updated KB ′ to be of the form ′ = ⟨ , ′⟩, where computing an ABox update results in a new ABox ′, that along with the original TBox , represents the outcome of the update process.
However, in a VKG setting, a vital additional component is present – the underlying data source, , which is mapped to the ABox through a set ℳ of declarative mappings. When ABox updates are triggered by real-world changes (like John changing his major), it is not only critical to maintain consistency in the ABox, but it is also crucial to ensure that these updates propagate to , preserving a harmonized state across the VKG system. In an ideal VKG framework featuring update propagation, when an update is performed at the ABox level, the changes should be automatically reflected in the underlying data source via the mappings. This notion implies a change to the structure of the VKG system from = ⟨, ⟩ to ′ = ⟨, ′⟩, highlighting the necessity of an update mechanism capable of propagating changes from ABox updates to the actual database. This kind of mechanism would considerably improve data consistency, reliability, and the practical utility of VKG systems in dynamic environments.
In this respect, we discuss in the next section three main goals to be achieved: First, we intend to formalize the framework of updates in the context of VKGs. Second, we delve into the task of computing updates at the ABox level of a VKG by propagating them to the underlying data source. And last, we propose an analysis of how schema mappings and ontology axioms afect updates in VKGs.
4.1. Updates in DL-Lite KBs
The problem of instance-level updates in DL KBs has been studied extensively in the past
[
Hence, the work on KB update is closely related to the work on inconsistency management
under incomplete information. Three main strategies have been identified as ways to deal with
inconsistency in such a context: (i) the first one consists of adjusting the constraints in the
TBox so that the updated ABox remains consistent; (ii) the second one, called consistent query
answering [23], is concerned with answering queries while keeping the inconsistency in the KB;
1Note that, under the open world assumption typically holding in DL KBs, deletion operations instead do per se not
generate inconsistencies.
(iii) the third one, which is more appropriate in our context (and in which we are interested),
consists of removing facts from the original ABox to restore consistency [16, 17]. As shown
in the literature [
In order to properly formalize the notion of KB updates, we need to define what it means for
an update to be coherent w.r.t. to a TBox . These notions are inspired by [
The above definition exhibits the conditions required to be satisfied in order to validate the coherence of an update w.r.t the ontology. The first condition states that all the facts to be added should be consistent with the TBox and the second condition is added to ensure that there is no insertion and deletion of the same fact. This definition leads us to the characterization of accomplishment of updates over a KB which is based on the notion of the minimal change principle + Definition 2 (Accomplishing an update). Let = ⟨ , ⟩ be a KB, = ⟨ , − ⟩ an update coherent with , and ′ an ABox. Then ′ accomplishes the update of with if (i) ′ is -consistent, (ii) ⟨ , ′⟩ ̸|= , for each ∈ − , and (iii) ′ = ′′ ∪ + for some ′′ ⊆ .
As we want to ensure that the resulting KB remains as close as possible to the original one, a semantic for the closeness measure has to be taken into account when comparing diferent resulting ′ accomplishing [25, 19, 26]. That’s why the term close does not have a general definition that will fit with all circumstances when it comes to KB evolution. However, the notion of maximal accomplishment of an update has to be formalized, regardless of the chosen closeness measure. + Definition 3 (Maximally accomplishing an update). Let = ⟨ , ⟩ be a KB, = ⟨ , − ⟩ an update that is coherent with the TBox , and ′ an ABox that accomplishes the update of with . Then ′ maximally accomplishes the update of with if there is no ′1 ⊋ ′ that accomplishes the update of with .
In the case of DL-Lite, it was shown in [26] that for any KB update there is a unique ABox ′ that maximally accomplishes it. For what follows, we denote by ∙ the KB ⟨ , ′⟩, where ′ is the ABox that maximally accomplishes the update of with .
The definitions introduced so far in this section are useful to formally define a KB update
within the context of VKG systems = ⟨, ⟩, where = ⟨ , ℳ, ⟩, as an update over
⟨ , ℳ()⟩. Computing such update essentially consists in computing the set of insertions
and deletions of facts over ℳ(). In [
In order to maintain consistency between the knowledge graph and the data source, whenever a change is applied over the knowledge base we need to accurately propagate it down to the data source. This ensures that the source mirrors the requested change through the mappings. In this context, we have to extend the notion of KB updates to the VKG setting: we consider that the ABox facts in are provided through the mapping ℳ from a data source .
Since the knowledge graph is kept virtual, the only way to realize a KB update is to ifnd an appropriate database state ′ from which it is possible to reach the updated ABox ′. The translation of KB updates into suitable database (DB) updates is one of the key problems we are interested in this research, and to formalize it we first need to introduce the notion of realizability for KB updates.
Definition 4 (Realizability). Let = ⟨⟨ , ℳ, ⟩, ⟩ be a VKG instance forming a KB = ⟨ , ⟩ with = ℳ(), and let be a KB update coherent with . Then, is realizable over through ℳ if there exists a DB instance ′ such that ℳ(′) = ∙ .
In the context of VKGs, since mappings are seen as view functions over the underlying data
source, the existence of a DB instance as specified in the above definition, is related to the
notion of translatability of view updates described in [
However, due to the ambiguities provided by the presence mappings, there might exist multiple DB instances that realize a given KB update. Such ambiguity, which reflects the non-injectivity of the mappings, is defined in the following: Definition 5 (Ambiguous Mapping). A mapping ℳ is said to be ambiguous if there exist two DB instances 1 and 2 s.t. (i) 1 ̸= 2 and (ii) ℳ(1) = ℳ(2).
The above definition shows how the injectivity of the mapping is tightly connected to updates in VKG instances. Specifically, this tells us that there might exist multiple DB instances that accomplish a given KB update when the mapping component is not injective. However, whenever a mapping ℳ is injective, every KB updates are uniquely translatable and is illustrated in the following proposition: Definition 6 (Unique realizability). Let = ⟨⟨ , ℳ, ⟩, ⟩ be a VKG instance forming a KB = ⟨ , ⟩ with = ℳ(), and let be a KB update coherent with . Then, is uniquely realizable over through ℳ if there exists a unique DB instance ′ such that ℳ(′) = ∙ . Proposition 1. Let ℳ be a non-ambiguous mapping of VKG instance = ⟨⟨ , ℳ, ⟩, ⟩, and let be an update coherent with . If is realizable, then is also uniquely realizable. Proof. It is clear that if two DB instances 1 and 2 realize a KB update , then we get ℳ(1) = ℳ(2), which, by non-ambiguity of ℳ, entails 1 = 2.
As stated in [27], the converse does not hold, i.e., even if ℳ is ambiguous, a KB update that is realizable might still be uniquely realizable. Therefore, in order to deal with the ambiguity provided by the presence of mappings in practical VKG systems (which represents a major concern in our research), we pose in the following sections the main research challenges we are facing, and any answer to them would benefit us in continuing our research. In a typical VKG instance, where the mapping component ℳ is ambiguous, some KB updates will result in diferent DB instance candidates realizing them. As an example, if a mapping maps both the Student and Professor relations from the DB schema to the Person atom in the VKG, a KB update that adds a new person will result in two possible DB instances, one with an update to the Student relation and the other with an update to the Professor relation. To achieve automated propagation of updates to the data sources, one approach is to develop methods to automatically select the most suitable DB instance that realizes the desired VKG update based on some preferences initially provided by the users. We should note that all DB instances that realize a KB update are equivalent w.r.t. the mapping and the TBox, i.e., they create ABoxes that are equivalent with respect to the TBox. This notion of equivalence is defined as follows: Definition 7 (ℳ-equivalence of DB instances). Given a VKG specification = ⟨ , ℳ, ⟩ and two DB instances 1, 2 for , we say that 1 and 2 are ℳ-equivalent w.r.t. if ℳ(1) ≡ ℳ(2).
In order to reduce the space of possible DB instances that realize a given KB update, we take advantage of the notion of repair by complying with the minimal change principle w.r.t. the original instance. Moreover, we want to base our selection of repair on a set of preferences provided by the user, as explained in [28]. This brings us to the following research questions: Q1: How can we formalize a preference-based selection of DB instances that realize updates over VKGs? Q2: Given a VKG instance = ⟨⟨ , ℳ, ⟩, ⟩, how can we formalize a suitable notion of interference of predicates over that may occur when propagating any given KB update, and how can we actually compute such interferences? For instance, in our previous example, the relations Student and Professor are interfering since they map to the same atom in the KB.
The above research question is helpful to check whether a priority operator based on preferences given by the user is total, in the sense that it resolves all interferences. This is because a preference that cannot be further extended should specify how to resolve every interference [28]. This leads to a further research question: Q3: What language is suitable to express user preferences in the context of updates in VKGs?
Finally, we also want to consider the case where KB updates are not realizable, i.e., given a KB updated with , there is no DB instance such that ℳ() = ∙ . The absence of realizability entails the presence of DB instances that are not ℳ-equivalent and that create diferent approximations of ∙ . This adds a further challenge, which consists of choosing the DB instance ′ such that the KB ′ = ⟨ , ℳ(′)⟩ is minimally distant from ∙ , for a suitably defined notion of distance. Therefore, we need to provide a relaxed version of realizability, which consists of finding a DB instance that realizes at best a given KB update . This brings us to the following research question: Q4: Given a non-realizable KB update over a KB , how can we select the DB instance that through ℳ approximates at best ∙ ?
In this section, we are interested in statically analyzing updates in the context of VKGs, i.e.,
given a VKG specification = ⟨ , ℳ, ⟩ and a KB update , we want to compute a suitable
DB update that is its translation and that updates any data source in such a way that via the
mapping it generates the updated KB. Following [
Definition 8 (Translation). Given a VKG specification = ⟨ , ℳ, ⟩ and a KB update , a DB update is a translation of if for every DB instance satisfying from which we have = ⟨ , ℳ()⟩, we have that: (1) ∙ = ⟨ , ℳ( ∙ )⟩ and (2) ∙ = whenever ∙ = .
Based on the above definition, we want to be able to statically compute the translation (or set of translations) of a given KB update, which is composed of a set of insertions and deletions of relations over the data source.
Unlike the method proposed in [
In this setting, we want to formalize the notion of static realizability, which is defined as follows: Definition 9 (Static realizability). Let = ⟨ , ℳ, ⟩ be a VKG specification and a KB update. Then, we say that is statically realizable if there exists a DB update over the signature such that ⟨ , ℳ( ∙ )⟩ = ⟨ , ℳ()⟩ ∙ , for every DB instance compliant with .
Given this notion of static realizability, we can now formulate a further research question: Q5: How can KB updates be statically and efectively realized in state-of-the-art VKGs that support query rewriting?
Finally, we want to study mapping analysis in the scope of VKGs, especially its inherent properties that are intrinsically connected to VKG updates. The task of mapping specification within the context of VKGs can be complex, necessitating a deep understanding of both the ontology and the associated data source. This nuanced "cognitive distance" between the data sources and the ontology often prompts the formulation of a complex mapping, expressed via assertions that correlate queries over the ontology with those over the data sources. A particular interest to us is the concept of injectivity of schema mapping—a facet that bears significant implications for the translation of KB updates into DB updates within the framework of VKG.
The injectivity property of the mapping is particularly crucial for updates, as it ensures that each change in the ontology corresponds to a unique change in the DB. If a mapping is not injective, a single update at the ontology level could potentially correspond to multiple updates at the DB level, creating ambiguity in the translation process. This ambiguity could lead to inconsistent states between the ontology and the DB, undermining the overall integrity of the system. However, the absence of injectivity in the schema mapping does not entirely prevent the translation of updates. There may be situations where updates can be uniquely translated even if the schema mapping is not injective. Still, such scenarios are more challenging to manage and typically require additional mechanisms or constraints to ensure the correct translation of updates.
As a first step towards analyzing mapping in VKG, we want to determine whether a given mapping specification is injective (or ambiguous) and in order to achieve it we are planning to use an automated model prover.
Q6: Given a VKG specification = ⟨ , ℳ, ⟩, how can we check whether the mapping component ℳ is injective?
To address this research question, our planned approach is to harness the capabilities of automated tools, such as the Z3 model prover-a highly proficient theorem prover developed under the auspices of Microsoft Research [29]. The ultimate aim is to integrate this tool into the Ontop system infrastructure for mapping analysis.
Also, we express interest in non-injective mappings, particularly in deriving the necessary information from the system to facilitate a deterministic translation of KB updates. This is tightly connected to work on unique solutions in data exchange, as studied in [30] where we want to ensure that for any subjective mapping, there is always a unique data source state from which it’s possible to compute a given KB. This is formulated in the following research question: Q7: Given a VKG specification = ⟨ , ℳ, ⟩ where ℳ is not injective, what additional information is necessary in order to maintain consistency between the knowledge base and the DB via the mapping?
This paper aims to address foundational and applied issues in the realm of Virtual Knowledge Graphs (VKGs), focusing on the introduction and exploration of Ontology-based updates and evolution within the context. We explored the multifaceted issue of translating knowledge base updates into database updates in the setting of VKGs. The crux of our research challenges stems from the dual nature of the problem: maintaining consistency in an incomplete information context and the inherent ambiguity introduced by mappings between ontology and data sources.
Regarding the research questions mentioned in this paper, we have already obtained some preliminary results. However, these methods require extensive discussion and need to be further analyzed to ascertain their validity and the potential for being extended.
This work was partially supported by the Wallenberg AI, Autonomous Systems, and Software Program (WASP), funded by the Knut and Alice Wallenberg Foundation, and by the Province of Bolzano and DFG through project D2G2 (DFG grant no. 500249124). Šimkus was partially supported by the Austrian Science Fund (FWF) project P30873. 46–56. [16] G. De Giacomo, M. Lenzerini, A. Poggi, R. Rosati, On instance-level update and erasure in description logic ontologies, J. of Logic and Computation 19 (2009) 745–770. [17] M. Winslett, A model-based approach to updating databases with incomplete information,
ACM Trans. on Database Systems 13 (1988) 167–196. [18] M. Lenzerini, D. F. Savo, Updating inconsistent description logic knowledge bases, in:
Proc. of the 20th Eur. Conf. on Artificial Intelligence (ECAI), 2012, pp. 516–521. [19] M. L. Ginsberg, D. E. Smith, Reasoning about action I: A possible worlds approach, Artificial
Intelligence 35 (1988) 165–195. [20] R. Fagin, J. D. Ullman, M. Y. Vardi, On the semantics of updates in databases, in: Proc. of the 2nd ACM Symp. on Principles of Database Systems (PODS), 1983, pp. 352–365. [21] M. Lenzerini, Data integration: A theoretical perspective., in: Proc. of the 21st ACM Symp. on Principles of Database Systems (PODS), 2002, pp. 233–246. doi:10.1145/543613. 543644. [22] D. Zheleznyakov, E. Kharlamov, W. Nutt, D. Calvanese, On expansion and contraction of DL-Lite knowledge bases, J. of Web Semantics 57 (2019) 1–19. doi:10.1016/j.websem. 2018.12.002. [23] L. Bertossi, Database Repairs and Consistent Query Answering, Morgan & Claypool
Publishers, 2011. [24] G. Flouris, D. Plexousakis, Handling Ontology Change: Survey and Proposal for a Future Research Direction, Technical Report TR-362 FORTH-ICS, Institute of Computer Science, Forth, Greece, 2005. [25] M. L. Ginsberg, Counterfactuals, Artificial Intelligence 30 (1986) 35–79. [26] D. Calvanese, E. Kharlamov, W. Nutt, D. Zheleznyakov, Evolution of DL-Lite knowledge bases, in: Proc. of the 9th Int. Semantic Web Conf. (ISWC), volume 6496 of Lecture Notes in Computer Science, Springer, 2010, pp. 112–128. doi:10.1007/978-3-642-17746-0_8. [27] E. Franconi, P. Guagliardo, On the translatability of view updates, in: Proc. of the 6th Alberto Mendelzon Int. Workshop on Foundations of Data Management (AMW), volume 866 of CEUR Workshop Proceedings, CEUR-WS.org, 2012, pp. 154–167. [28] S. Staworko, J. Chomicki, J. Marcinkowski, Prioritized repairing and consistent query answering in relational databases, Ann. of Mathematics and Artificial Intelligence 64 (2012) 209–246. doi:10.1007/s10472-012-9288-8. [29] L. De Moura, N. Bjørner, Z3: An eficient SMT solver, in: Proc. of the Int. Conf. on Tools and Algorithms for the Construction and Analysis of Systems, Springer, 2008, pp. 337–340. [30] N. Ngo, E. Franconi, Unique solutions in data exchange, in: Proc. of the 25th Int. Conf. on Database and Expert Systems Applications (DEXA), volume 8645 of Lecture Notes in Computer Science, Springer, 2014, pp. 281–294.