A description logic knowledge base (KB) consists of a terminological box and an assertion box. The terminological box defines the terms used in the KB, and the assertion box defines relations between the terms.
This paper investigates the relationships between pairs of knowledge bases. In particular, one can be interested in versioning, where one wants to be able to compute the differences between two knowledge bases; modularization, where one seeks to find a small subset of a given KB that can be used for a specific application; knowledge exchange, where one wishes to transform a KB by a declarative mapping between the associated terminal boxes; and forgetting, where some terms are ignored but the results that do not use these terms are unchanged. One way to set up a pair of KBs is by using a relational signature in a KB, which is a finite collection of concepts and role names, which then specifies a sub-KB of interest. In particular, the paper explores the notion of query entailment between knowledge bases for queries with a given signature.
Entailment can be viewed as determining whether there exists a homomorphism between materializations of the knowledge bases. The authors consider the tractability of this problem for various logic fragments. The problem is explored by recasting it in terms of a game between two players, one of whom seeks to describe the required homomorphism and the opponent who seeks to show that there is no such homomorphism.
The paper gives detailed examples of the concepts and illustrates the game structure with helpful diagrams. Full details of proofs are given in an appendix to the paper.