Logic-based query optimization for object databases

We present a technique for transferring query optimization techniques, deve loped for relational databases, into object databases. We demonstrate this technique for ODMG database schemas defined in ODL and object queries expre ssed in OQL. The object scheme is represented using a logical representatio n (Datalog). Semantic knowledge about the object data model, e.g., class hi erarchy information, relationship between objects, etc., as well as semanti c knowledge about a particular schema and application domain are expressed as integrity constraints. An OQL object query is represented as a logic que ry and query optimization is performed in the Datalog representation. We ob tain equivalent (optimized) logic queries and, subsequently, obtain equival ent (optimized) OQL queries for each equivalent logic query. In this paper, we present one optimization technique for semantic query optimization (SQO ) based on the residue technique of [6], [7], [8]. We show that our techniq ue generalizes previous research on SQO for object databases. We handle a l arge class of OQL queries, including queries with constructors and methods. We demonstrate how SQO can be used to eliminate queries which contain cont radictions and simplify queries, e.g., by eliminating joins, or by reducing the access scope for evaluating a query to some specific subclass(es). We also demonstrate how the definition of a method, or integrity constraints d escribing the method, can be used in optimizing a query with a method.