In the database literature it has been proposed to resort to active integrity constraints in order to restore database integrity. Such active integrity constraints consist of a classical integrity constraint together with a set of preferred update actions that can be triggered when the constraint is violated. In this overview paper we start by reviewing the main repairing routes that have been proposed in the literature. We do so from the perspective of Dynamic Logic, viewing active integrity constraints as programs that test whether a constraint is violated and if so perform appropriate update actions. We then discuss how these ideas can be adapted to Description Logics. We assume extensions of TBox axioms by update actions that denote the preferred ways an ABox should be repaired in case of inconsistency with the axioms of the TBox. The extension of the TBox axioms with these update actions constitute new, active TBoxes.
One of the most important and notoriously di cult issues in the database and AI literature is the problem of updating a database under a set of integrity constraints. In the course of database maintenance several changes are applied to the databases and checking whether these constraints are still entailed is of fundamental importance.
The TBoxes of Description Logic knowledge bases bear resemblances with integrity constraints. However, due to the open world assumption the TBox axioms do not have to be entailed by the ABox; instead, their role is to infer more than what is literally written in the ABox. TBoxes therefore only have to be consistent with the ABox. Hence the counterpart of checking whether the Copyright c 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). updated database still entails the integrity constraints is the problem of checking whether the updated ABox is still consistent with the TBox.1
When a database fails to satisfy the integrity constraints then there are basically two di erent options: one may either live with the inconsistency or repair the database in order to restore integrity. If one chooses the latter option then one has to explicitly construct the repaired database. The former option requires the de nition of non-standard inconsistency-tolerant semantics that are a priori in the spirit of paraconsistent logics; one may in particular rely on hypothetical repairs. The two options therefore lead to solutions that are technically quite similar.
Procedures restoring the consistency of a database with respect to a set of
integrity constraints were extensively studied in the last decades [
The situation is similar for description logic knowledge bases when an ABox is updated in a way such that it becomes inconsistent with a given TBox. For DL knowledge bases, the most widespread methods to repair inconsistencies are based on the so-called justi cations, which are minimal subsets of the KB containing the terminological and assertional axioms from which an undesirable consequence is inferred. Axiom pinpointing through justi cations became an important topic of research within the DL community and several results were quickly established [25, 18, 27]. Both black-box [26, 2] and glass-box [21, 19] methods emerged for computing justi cations. The former have a more universal approach and are used independently of the reasoner at hand, while the latter have a more delicate construction that is tied to speci c reasoners and usually require less calls. After computing all justi cations of an undesirable consequence, the next step is to obtain a minimal hitting set [24] made up of one axiom per justi cation and remove it from the knowledge base. More recent approaches have focused on providing methods for weakening the axioms instead of removing them, since the latter can prove to be too big of a change [29]. Another research avenue investigates repair-based semantics for query answering [4, 5].
It seems fair to say that for the time being there is no consensus on the `right' way of repairing inconsistent knowledge bases. Given these long-standing di culties to de ne appropriate repairs, it seems reasonable to resort to more modest approaches where more information is fed into the repair process. In the present paper we take inspiration from a research avenue in the database literature where integrity constraints are equipped with additional information about the preferred way to maintain consistency: in [16] Active Integrity Constraints 1 We note that there are approaches combining integrity constraints with TBoxes.
The most prominent ones are based on the extension of KBs with constraint axioms. These axioms are however used for validation purposes only and do not share the same semantics as regular TBox axioms [20, 28]. (AICs) were proposed as an enhancement of classical integrity constraints with update actions. This research avenue was further pursued in a series of publications [7, 8, 11]. AICs extend classical integrity constraints with preferred update actions. This introduces a dynamic view of the concept of integrity constraint. From now on we therefore call classical integrity constraints static constraints and will talk about the static part of an AIC.
For instance, consider the classical integrity constraint:
8(E; S1; S2)[Employee(E; S1) ^ Employee(E; S2) ! S1 = S2] which says that every employee should only have one salary. It can be extended into the active constraint: 8(E; S1; S2)[Employee(E; S1)^Employee(E; S2)^S1 > S2 ! Employee(E; S1)] which states that if there is an employee with two salaries then the preference is to remove the highest salary (instead of removing one randomly).
Another example is the static integrity constraint:
(8X)[Bachelor(X) ^ Married(X) ! ?] which says that no one should have the property of being a bachelor and married at the same time. It can be turned into the active constraint:
(8X)[Bachelor(X) ^ Married(X) ! ?; f Bachelor(X)g] whose meaning is that when there is a person in the database who has both the status of being a bachelor and the status of being married then the preferred repair is to remove from the database the bachelor status (as opposed to removing the married status) since married status can be achieved from being bachelor but not the other way. In this way, the possible repairs better match designer preferences when maintaining the database. Moreover, it can be expected that their number is narrowed down.
In the propositional case, an active integrity constraint can be represented as a couple:
r = hC(r); R(r)i where C(r) is a boolean formula (called the static part of r and denoting a static constraint) and R(r) is a set of update actions, each of which is of the form +p or p for some atomic formula p. The idea is that (1) when the static constraint C(r) is false then the constraint r is violated, and (2) a violation of r can be repaired by performing one or more of the update actions in R(r). 2
It remains to give a semantics to a given set of active integrity constraints in terms of the repairs it induces. The two most important ones that were proposed in the literature are the founded and the justi ed repairs. While both semantics greatly reduce the number of possible repairs, di erent choices between update actions in R(r) can still lead to di erent repairing routes, or even no repairs at all. This is for example trivially the case when R(r) is the empty set.
In the rst paper about AICs the authors introduce founded repairs [16]. The idea is that any update action applied to the database should be supported by the `active part' of an AIC, i.e., by a preferred update action of a violated constraint. They also obtain complexity results for the problem of existence of founded repairs, both in the general case ( P2 -complete) as well as in the case that AICs comprise `single heads', i.e., only one preferred update action is allowed in each constraint (NP-complete). Recognizing that the existence of founded repairs is not always guaranteed though, they go on to de ne preferred repairs as an intermediate repairing route between founded and standard repairs that always exist. The complexity for the problem of existence of preferred repairs is shown to be P2 -complete. Further research on AICs also ensued [6, 7] that reviewed and expanded upon the aforementioned results.
The rst new de nitions on repairing procedures that are based on preferences between update routes came in [8], an attempt to relate the seemingly different approaches to AICs and revision programming. There, the authors distinguish between the various repairs that they propose (standard repairs, founded repairs, justi ed repairs) and their weaker versions (weak repairs, founded weak repairs, justi ed weak repairs), with only the former complying to the minimality of change principle that the previous approaches took by default. The de nitions of justi ed weak repairs and justi ed repairs were introduced as a response to the so-called circularity of support defect that founded repairs cannot evade and which the authors argue against. Furthermore, they leave the rst-order setting of the previous papers and use a propositional one. The propositional setting of [8] provides a valuable stepping stone to present and discuss our own approach. Another distinguishing feature in their work is that they investigate properties of normalization, i.e., `breaking' all active integrity constraints into many copies such that each one has at most one preferred update action. They denote the di erences that exist in these two di erent classes of AICs, both in practice (resulting in more or fewer repairs) as well as in the complexity of deciding the existence of repairs under normal AICs. The consensus on complexity results is very interesting, with all of the di erent kinds of repairs, being either weak or minimal, and being applied on either normal AICs or standard AICs, to fall either on the NP-complete or P2 -complete territory.
Last but not least, further approaches to re ne or extend active integrity constraints have been investigated in [12, 11] with analyses of algorithms on trees, extensions to knowledge bases outside databases, as well as independence/precedence relations among active integrity constraints.
In the paper [15] we have recast these di erent semantics in Dynamic Logic. More precisely, we have shown that active integrity constraints can be viewed as particular programs in Dynamic Logic of Propositional Assignments DL-PA: they consist in a test of the negation of the static part of the AIC that is followed by a nondeterministic composition of the possible update actions. The latter are identi ed with sets of assignments of propositional variables to truth values. Given an AIC r = hC(r); R(r)i, the associated DL-PA program is therefore: :C(r) ? ; [ R(r) [ :C(r) ? ; [ R(r) r These are the building blocks of programs capturing all the above semantics, as shown in [15]. Furthermore, a new kind of repair program is de ned there as: and is compared to the existing semantics. 3
From Active Integrity Constraints to Active TBoxes It seems natural to us to transfer the active integrity constraint idea to the Description Logic setting. If we identify ABoxes with databases and TBoxes with integrity constraints then the axioms of the latter should be extended with preferred update actions. These update actions should prescribe the changes the ABox should undergo in order to reestablish consistency whenever it is inconsistent with the TBox. We call these extended TBoxes active TBoxes. They enable ontology engineers to easily express preferred update actions, thereby avoiding that unwanted repairing routes are followed. The idea is to repair inconsistent KBs by updating ABox assertions in order to comply with (preferred update actions indicated by) the axioms of the active TBox. Somewhat surprisingly, this research avenue had not been tried in the DL literature.
For example, consider the following static TBox:
T = fFather v Male u Parent; OnlyChild v 8hasSibling:?g An ontology engineer may wish to enhance it to two possible active TBoxes, viz. aT1 = f 1; 2g and aT2 = f 3; 4g where:
We can witness how, through these enhanced concept inclusions, one can be more speci c in the update actions that s/he prefers when repairing an ABox that is inconsistent with T : the active axioms of aT1 dictate that an individual who is a father should remain a father in case of inconsistency, whereas an individual who has siblings should change its status and not be an only child anymore. Similarly for aT2, where ` hasSibling:>' removes all relations between individuals that violate the axiom and individuals satisfying > (i.e., all individuals), thus stating that an only child who has siblings should drop its `sibling' relationship with everyone and stay an only child. Now consider the following ABox: A = fJohn : Male u Father u :Parent; Mary : OnlyChild; hasSibling(Mary; John)g A repaired ABox then according to aT1 should be the following: A1 = fJohn : Male u Father u Parent; Mary : :OnlyChild; hasSibling(Mary; John)g whereas a repaired ABox according to aT2 should be the following:
A2 = fJohn : Male u :Father u :Parent; Mary : OnlyChildg 4
We have attempted to materialize the above intuitions in a number of di erent formats and examine how the various de nitions of repairs from the database literature translate and behave in the DL setting. This has resulted in several publications as well as the PhD thesis [22].
Our main goal was to apply the idea behind active integrity constraints in the Description Logic setting and, in particular, to provide extensions of TBox axioms so that they are able to suggest preferred repairing routes in case of inconsistencies. We started by overviewing active integrity constraints in the propositional setting through the DL-PA lens. Embeddings of weak, founded and justi ed repairs into DL-PA were proposed and studied in [13, 15]. The DL-PA framework moreover naturally leads to a a new, dynamic way of integrity maintenance, dynamic repairs. We have analysed the properties of all these repairs and provides complexity results for the problem of existence of dynamic repairs. We also took advantage of the dynamic framework|i.e., the logic DL-PA|in order to explore an extension on databases with history and adjust the behavior of the various repairs so that they work in this setting. Finally, we provided DL-PA counterparts of all the reasoning and decision problems arising in the repair setting, such as the existence of a repair or the existence of a unique repair.
In the paper [23] we have started to lift the idea behind AICs to Description Logics. There, the rst de nition of `active' TBoxes was introduced. After a brief discussion on the di erences and di culties of leaving the propositional setting, we examine preliminary steps into repairing ABoxes syntactically so that they conform to the preferences denoted by the active axioms. These syntactic repairs are inspired by (and correspond to) the weak and founded repairs of the database literature. Proving to be quite impractical though, we suggest that a semantic approach seems more viable.
In the paper [14] we went on to pursue this semantic approach and investigated how the dynamic logic-based framework can be transferred to the DL level. We use a more local approach, where preferred update actions in the active axioms behave similarly to the update actions introduced before, i.e., they have the form A for an atomic concept A denoting either the addition or the removal of an individual from the set of individuals that have property A. This approach, although more expressive and well-behaved than the syntactic one of [23], still leaves a lot of repairing scenarios unattainable, mainly because of its boolean nature and close similarity to the repairs of the database literature.
In Rantsoudis's Phd thesis a more elaborate logic and techniques are introduced and discussed which apply changes globally, in the sense that preferred update actions of the form C can be applied to all individuals violating an axiom and C is not necessarily atomic [22, Chapter 5]. As before, a dynamic logic framework that is in uenced by the logic DL-PA is used. Furthermore, although the resulting logics are extensions of ALCO and ALCIO respectively with dynamic operators, they are shown to be as expressive as their static counterparts (with the addition of the universal role).
The Phd thesis [22, Chapter 6] concludes with a proposal to connect the approaches of the syntactic approach in [23] and the semantic approach in [14], thus completing the picture on active TBox-based ABox repairs. It also brie y discusses future work, with possible applications of the proposed repairing methods on nonmonotonic scenarios.