On the Relationship between Description Logic and Predicate Logic Queries.

Description Languages (DLs) are descendants of the kl-one [15] knowledge representation system, and form the basis of several object-centered knowledge base management systems developed in recent years, including ones in industrial use. Originally used for conceptual modeling (to de ne views), DLs are seeing increased use as query languages for retrieving information. This paper, aimed at a general audience that includes database researchers, considers the relationship between the expressive power of DLs and that of query languages based on Predicate Calculus. We show that all descriptions built using constructors currently considered in the literature can be expressed as formulae of the First Order Predicate Calculus with at most three variable symbols, though we have to allow numeric quanti ers and in nitary disjunction in order to handle a couple of special constructors. Conversely, we show that all rst-order queries (formulae with one free variable) built up from unary and binary predicates using at most three variables can be expressed as descriptions. We establish similar results for the subset of FOPC involving two variable symbols. We also show that certain subsets of constructors can be used to express only formulae in such well-studied subsets of FOPC as conjunctive queries and existential queries. For these languages, we gain ideas for subsumption algorithms from the work in the database literature on the containment problem of existential queries. The paper also suggests how one can transfer to DLs results from the theoretical database literature about languages based on predicate calculus with recursion.Technical report DCS-TR-295