Identifying Objects Over Time with Description Logics∗

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, ser-vice codes, mobile addresses and so on. In this paper, we con-sider how a Boolean complete description logic with a con-cept constructor for expressing “always ” can also be em-bellished with a concept constructor for dynamic or tempo-ral 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 hypotheti-cal 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 sim-ple kinds of eventualities leads to a significant increase in the complexity of the membership problem.