|
|
|
@inproceedings{DBLP:conf/cikm/Borgida94,
author = {Alexander Borgida},
title = {On The Relationship Between Description Logic and Predicate Logic},
booktitle = {Proceedings of the Third International Conference on Information
and Knowledge Management (CIKM'94), Gaithersburg, Maryland, November
29 - December 2, 1994},
publisher = {ACM},
year = {1994},
pages = {219-225},
ee = {db/conf/cikm/Borgida94.html, http://doi.acm.org/10.1145/191246.191283},
crossref = {DBLP:conf/cikm/94},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
Description languages 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 define 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 (FOPC) with at most three variable symbols, though we have to allow numeric quantifiers and infinitary disjunction in order to handle some special constructors. Conversely, we show that all first-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 conclude by exhibiting queries that cannot be expressed as DL concepts, and reflecting briefly on consequences.
Copyright © 1994 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.
Data released under the ODC-BY 1.0 license — See also our legal information page