TY - JOUR T1 - Logic-based query optimization for object databases JF - IEEE Transactions on Knowledge and Data Engineering Y1 - 2000 A1 - Grant,J. A1 - Gryz,J. A1 - Minker, Jack A1 - Raschid, Louiqa KW - access scope KW - application domain KW - class hierarchy information KW - Constraint optimization KW - data integrity KW - Data models KW - Datalog KW - Datalog representation KW - deductive databases KW - equivalent logic query KW - integrity constraints KW - Lifting equipment KW - Logic KW - logic based query optimization KW - logic programming KW - logic queries KW - logic query KW - logical representation KW - object data model KW - object databases KW - object queries KW - object schema KW - object-oriented databases KW - ODL KW - ODMG database schemas KW - optimization technique KW - optimized OQL queries KW - OQL object query KW - query languages KW - Query optimization KW - query optimization techniques KW - Query processing KW - Relational databases KW - residue technique KW - semantic knowledge KW - semantic query optimization AB - We present a technique for transferring query optimization techniques, developed for relational databases, into object databases. We demonstrate this technique for ODMG database schemas defined in ODL and object queries expressed in OQL. The object schema is represented using a logical representation (Datalog). Semantic knowledge about the object data model, e.g., class hierarchy information, relationship between objects, etc., as well as semantic knowledge about a particular schema and application domain are expressed as integrity constraints. An OQL object query is represented as a logic query and query optimization is performed in the Datalog representation. We obtain equivalent (optimized) logic queries, and subsequently obtain equivalent (optimized) OQL queries for each equivalent logic query. We present one optimization technique for semantic query optimization (SQO) based on the residue technique of U. Charavarthy et al. (1990; 1986; 1988). We show that our technique generalizes previous research on SQO for object databases. We handle a large class of OQL queries, including queries with constructors and methods. We demonstrate how SQO can be used to eliminate queries which contain contradictions 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 describing the method, can be used in optimizing a query with a method VL - 12 SN - 1041-4347 CP - 4 M3 - 10.1109/69.868906 ER -