A Unified Framework for Class Based Representation Formalisms

Diego Calvanese, Maurizio Lenzerini, and Daniele Nardi

Proc. of the 4th Int. Conf. on the Principles of Knowledge Representation and Reasoning (KR'94)

The notion of class is ubiquitous in Computer Science and is central in many knowledge representation languages. In this paper we propose a representation formalism in the style of concept languages, with the aim of providing a unified framework for class-based formalisms. The language we consider is quite expressive and features a novel combination of constructs including number restrictions, inverse roles and inclusion assertions with no restrictions on cycles. We are able to show that such language is powerful enough to model frame systems, object-oriented database languages and semantic data models. As a consequence of the established correspondences, several significant extensions of each of the above formalisms become available. The high expressivity of the language and the need for capturing the reasoning in different contexts forces us to distinguish between unrestricted and finite model reasoning. A notable feature of our proposal is that reasoning in both cases is decidable. For the unrestricted case we exploit a correspondence with propositional dynamic logic and extend it to the treatment of number restrictions. For the finite model case we develop a new method based on the use of linear programming techniques. We argue that, by virtue of the high expressive power and of the associated reasoning techniques on both unrestricted and finite models, our language provides a unified framework for class-based representation formalisms.


@inproceedings{KR-94,
  title =        "A Unified Framework for Class Based Representation
Formalisms",
  year =          "1994",
  author =       "Diego Calvanese and Maurizio Lenzerini and Daniele Nardi",
  editor =       "J. Doyle and E. Sandewall and P. Torasso",
  booktitle =     "Proc. of the 4th Int. Conf. on the Principles of Knowledge
Representation and Reasoning (KR'94)",
  pages =        "109-120",
  publisher =     "Morgan Kaufmann, Los Altos",
}
postscript (gzipped)