SUBSUMPTION BETWEEN QUERIES TO OBJECT-ORIENTED DATABASES

Most work on query optimization in relational and object-oriented data bases has concentrated on tuning algebraic expressions and the physica l access to the database contents. The attention to semantic query opt imization, however, has been restricted due to its inherent complexity . We take a second look at semantic query optimization in object-orien ted databases and find that reasoning techniques for concept languages developed in Artificial Intelligence apply to this problem because co ncept languages have been tailored for efficiency and their semantics is compatible with class and query definitions in object-oriented data bases. We propose a query optimizer that recognizes subset relationshi ps between a query and a view (a simpler query whose answer is stored) in polynomial time. The selected schema and query language is maximal in the sense that any added feature ruins tractability.