Identifying Objects Over Time with Description Logics

Principles of Knowledge Representation and Reasoning: Proceedings of the Eleventh International Conference (KR2008)

Volume

Principles of Knowledge Representation and Reasoning: Proceedings of the Eleventh International Conference (KR2008)

Contents

A fundamental requirement for cooperating agents is to agree on a selection of component values of objects that can be used for reliably communicating references to the objects, that is, to function as their keys. In distributed environments such as the web, it is more likely that a choice of such values may have time limits on the duration of their ability to serve as keys, e.g., values denoting permissions, authorizations, service codes, mobile addresses and so on. In this paper, we consider how a Boolean complete description logic with a concept constructor for expressing "always" can also be embellished with a concept constructor for dynamic or temporal forms of equality generating constraints we call temporal path functional dependencies. In particular, we introduce the temporal description logic DLFDtemp, demonstrate how it can be used, among other things, to capture and reason about temporal keys and functional dependencies for a hypothetical distributed hospital database, and prove that the general membership problem for DLFDtemp is ExpTime-complete. The latter is accomplished by exhibiting a reduction of the general membership problem for DLFDtemp to the simpler dialect DLF. We also show that the addition of very simple kinds of eventualities leads to a significant increase in the complexity of the membership problem.