Subsumption between Queries to Object-Oriented Databases

M. Buchheit, M. Jeusfeld, W. Nutt, M. Staudt

	   Most work on query optimization in relational and
	   object-oriented databases has concentrated on tuning
	   algebraic expressions and the physical access to the database
	   contents. The attention to semantic query optimization,
	   however, has been restricted due to its inherent complexity.
	   We take a second look at the problem for queries in
	   object-oriented databases and find that reasoning techniques
	   for concept languages developed in Artificial Intelligence
	   apply for the following reasons:  concept languages have been
	   tailored for efficiency and their semantics is compatible with
	   class and query definitions in object-oriented databases. We
	   propose a query optimizer which decides subset relationships
	   between a query and a view (a simpler query whose answer is
	   stored) in polynomial time.