Artale, Cesarini, and Soda (1996) study reasoning in object-oriented data models by presenting a translation to DLs in the style of the one discussed in Section 5. However, the proposed translation is applicable only in the case where the shema contains no recursive class declarations. This limitation is not present in the work by Bergamaschi and Nebel
(1994), where a formalism derived from DLs is used to model complex objects and an algorithm for computing subsumption between classes is provided.

A recent survey on the application of DLs to the problem of data management has been presented by Borgida (1995). The application to the task of data modeling of reasoning techniques derived from the correspondences presented in Sections 4 and 5 is discussed in more detail by Calvanese, Lenzerini, and Nardi (1998).

Recently, there have also been proposals to integrate the object-oriented and the logic programming paradigms (Kifer & Wu, 1993; Kifer, Lausen, & Wu, 1995). These proposals are however not directly related to the present work, since they aim at providing mechanisms for computing with structured objects, rather than means for reasoning over a conceptual (object-oriented) representation of the domain of interest.

## 6.2 Reasoning In Aluni And In Class-Based Representation Formalisms

ALUNI is equipped with techniques to reason both with respect to unrestricted and with respect to finite models. We briefly sketch the main ideas underlying reasoning in both contexts. A detailed account of the reasoning techniques has been carried out by Calvanese (1996c).

## 6.2.1 Unrestricted Model Reasoning

We remind that reasoning on a knowledge base with respect to unrestricted models amounts to check either concept consistency, i.e., determine whether the knowledge base admits a
(possibly infinite) model in which a given concept has a nonempty extension, or concept subsumption, i.e., determine whether the extension of one concept is contained in the extension of another concept in every model (including the infinite ones) of the knowledge base.

The method to reason in ALUNI with respect to unrestricted models exploits a well known correspondence between DLs and Propositional Dynamic Logics (PDLs) (Kozen & Tiuryn, 1990), which are a class of logics specifically designed to reason about programs.

The correspondence, which has first been pointed out by Schild (1991), relies on a substantial similarity of the interpretative structures of both formalisms, and allows one to exploit the reasoning techniques developed for PDLs to reason in the corresponding DLs. In particular, since ALUNI, the description language of ALUNI, includes the construct for inverse roles, for the correspondence one has to resort to converse-PDL, a variant of PDL that includes converse programs (Kozen & Tiuryn, 1990). However, because of the presence of number restrictions in ALUNI which have no direct correspondence in PDLs, we cannot rely on traditional techniques for reasoning in PDLs. Recently, encoding techniques have been developed, which allow one to eliminate number restrictions from a knowledge base while preserving concept consistency and concept subsumption (De Giacomo & Lenzerini, 1994a). The encoding is applicable to knowledge bases formulated in expressive variants of DLs, and in particular it can be used to reduce unrestricted model reasoning on ALUNI knowledge