are types of the formalism. Since query languages for In order to develop a theory of semantic query optivery rich type (class) system able to directly represent a tional databases was introduced in the early 80’s by constraints with an antecedent and a consequent which abstract from dieren t syntactical representation of seMore generally, rules allow the expression of integrity sion in canonical form (i.e. a form which permits to tion criteria proposed in the database literature and is cess is based on the generation of the semantic expanThe main point is that OODBs provide a Nebel,1993]. (i.e. primitive concepts); further knowledge is expressed as a type in our formalism, and a dirty part that goes mantic expansion of a type, say exp(S) permits to incororiginal query on all databases satisfying the IC rules. mization will be performed only over the clean part of a pile, once at all, the given schema (classes + IC rules), (all the new ) isa relationships which are logically imOODBs and is a virtual class (i.e. a dened concept). tual database schemata are given in terms of base classes junctive queries or single operand queries in [Kim,1989] tion of a query into a clean part, that can be represented glu,1989; Siegel et al.,1992; Chakravarthy et al.,1990]. generalize it to deductive databases and Ozsoyo- [Shenoy based on inclusion statements between concepts, recently mization, we propose a theoretical framework (in term of et al.,1994; Beneventano et al.,1993; Bergamaschi and of the class and the consequent is the class description. (TKRS)). Informally, semantic equivalence means that as IC rules. In particular, structural class descriptions are expressed as rules where the antecedent is a name perfectly ts the usual database viewpoin t. In fact, aclowing et ideally introduce a separa- [Buchheit al.,1994], proposed in et This new perspective [Donini al.,1993]. giving rise to an enriched schema obtained by adding subsumption) which includes the main query transformathe transformed query has the same answer as the mantically equivalent types) of the schema types. Foleorts ha ve been made to improve this technique and to beyond the type system expressiveness. Semantic optiKing Hammer and Zdonik [King,1981a; 1981b]; [Hamsubclass of integrity constraints in the database schema.
OODBs are more expressive than our formalism we, folitance relations between types (classes), it is possible to perform semantic query optimization. referenced as query, corresponds to the so{called conmer and independently developed very sim- Zdonik,1980] lowing the approach of and Ozsoyoglu,1989; [Shenoy semantic query optimization in OODBs [Chan,1992; The notion of semantic query optimization for relaJeusfeld and Staudt,1993; Pang et al.,1991; Buchheit given query. The clean part of a query, in the following By exploiting schema information as, for instance, inherplied by the original schema. The compilation proing. Prior to the evaluation of any query, we comilar optimization methods. During the last decade, many Siegel et for semantic query expansion, the se- al.,1992] More recently, some eorts have been made to perform
formed by detecting the eliminable factors of a query. query, that is, the factors logically implied by the
Werner Nutt. Subsumption algorithms for concept and Nutt, Bernhard Hollunder and [Hollunder 1990] telligenz GmbH, Kaiserslautern, Germany, April 1990. 4, Deutsche Forschungszentrum fuer Kuenstliche Inlanguages. Technical report, Research Report RR-90