Optimizing object queries using an effective calculus

ACM Transactions on Database Systems - Tập 25 Số 4 - Trang 457-516 - 2000
Leonidas Fegaras1, David Maier2
1The University of Texas at Arlington
2Oregon Graduate Institute of Science and Technology

Tóm tắt

Object-oriented databases (OODBs) provide powerful data abstractions and modeling facilities, but they generally lack a suitable framework for query processing and optimization. The development of an effective query optimizer is one of the key factors for OODB systems to successfully compete with relational systems, as well as to meet the performance requirements of many nontraditional applications. We propose an effective framework with a solid theoretical basis for optimizing OODB query languages. Our calculus, called the monoid comprehension calculus, captures most features of ODMG OQL, and is a good basis for expressing various optimization algorithms concisely. This article concentrates on query unnesting (also known as query decorrelation), an optimization that, even though it improves performance considerably, is not treated properly (if at all) by most OODB systems. Our framework generalizes many unnesting techniques proposed recently in the literature, and is capable of removing any form of query nesting using a very simple and efficient algorithm. The simplicity of our method is due to the use of the monoid comprehension calculus as an intermediate form for OODB queries. The monoid comprehension calculus treats operations over multiple collection types, aggregates, and quantifiers in a similar way, resulting in a uniform method of unnesting queries, regardless of their type of nesting.

Từ khóa


Tài liệu tham khảo

BEECH D., 1993, Proceedings of the Nineteenth International Conference on Very Large Data Bases (VLDB '93, 244

BEERI C., 1990, Proceedings of the Third International Conference on Database Theory (ICDT '90, 72

BELLANTONI S., 1992, Proceedings of the 24th Annual ACM Symposium on Theory of Computing (STOC '92, 283

BREAZU-TANNEN V., 1992, Proceedings of the Third International Workshop on Database Programming Languages: Bulk Types & Persistent Data (DBPL3, 9

BREAZU-TANNEN V., 1992, Proceedings of the 4th International Conference on Database Theory (LNCS 646

BREAZU-TANNEN V., 1991, Proceedings of the 18th International Colloquium on Automata, Languages and Programming (Madrid, July 8-12), 60

10.1145/181550.181564

10.1016/0304-3975(95)00024-Q

CAREY M., 1996, Proceedings of the 22nd International Conference on Very Large Data Bases (VLDB '96, 3

10.1145/191843.191915

CATTELL R., The Object Data Standard: ODMG 3.0. Morgan Kaufmann

CHAN D., 1994, Proceedings of the 12th British Conference on Databases, 55

10.1145/276305.276311

CHERNIACK M., 1998, Proceedings of the 24th International Conference on Very Large Data Bases. 239-250

CLAUSSEN J., 1997, Proceedings of the 23rd International Conference on Very Large Data Bases (VLDB '97

10.1145/141484.130341

CLUET S., 1995, Proceedings of the Fifth International Workshop on Database Programming Languages

10.1145/66926.66952

10.1109/69.124896

DANIELS S., 1991, Query optimization in revelation, an overview, Data Eng., 14, 2

10.1109/69.50908

EISENBERG A., 1999, SQL1999, 131

FEGARAS L., 1993, Proceedings of the International Workshop on Database Programming Languages, 200

FEGARAS L., 1998, Proceedings of the Ninth International Conference on DEXA, 726

10.1145/276305.276310

10.1023/A:1008757010516

FEGARAS L., 1999, Proceedings of the First ECOOP Workshop on Object-Oriented Databases

FEGARAS L., 1995, Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data (SIGMOD '95, 47, 10.1145/223784.223789

FEGARAS L., 1993, Proceedings of the Conference on Deductive and Object-Oriented Databases, 146, 10.1007/3-540-57530-8_9

FEGARAS L., 2009, Proceedings of the ACM SIGMOD Conference on Management of Data (SIGMOD '2000

10.1145/38714.38723

KEMPER A., 1990, Proceedings of the 16th International Conference on Very Large Data Bases (VLDB, 290

10.1145/319732.319745

LEIVANT D., 1993, Proceedings of the 20th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '93, 325, 10.1145/158511.158659

LEUNG T., 1993, Proceedings of the International Workshop on Database Programming Languages, 157

LEVY A.Y., 1994, Proceedings of the 20th International Conference on Very Large Data Bases (VLDB'94, 96

10.1145/235968.233335

LIN J., 1996, Proceedings of the Fifth International Conference on Information and Knowledge Management (CIKM '96, 134

MAIER D., 1993, Proceedings of the Twelfth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS, 1

MEIJER E., 1991, Proceedings of the Fifth ACM Conference on Functional Programming Languages and Computer Architecture, 124, 10.1007/3540543961_7

10.1145/93605.98734

MURALIKRISHNA M., 1992, Proceedings of the 18th International Conference on Very Large Data Bases, 91

OZSOYOGLU Z., 1992, Proceedings of the Eighth International Conference on Data Engineering

PEYTON JONES S. L., The Implementation of Functional Programming Languages

PIERCE B. C., Basic Category Theory for Computer Scientists. Foundations of Computing

10.1016/0306-4379(86)90012-8

SELINGER P.G., 1979, Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD '79, 23

STEENHAGEN H.J., 1994, Proceedings of the Fourth International Conference on Extending Database Technology: Advances in Database Technology (EDBT '94, 337

THOMPSON S., 1998, Haskell: The Craft of Functional Programming

TRINDER P., 1992, Proceedings of the Third International Workshop on Database Programming Languages: Bulk Types & Persistent Data (DBPL3, 55

TRINDER P., 1989, Proceedings of on TENCON'89 (Bombay, Nov.). 186-192

WADLER P., 1990, Proceedings of the 1990 ACM Symposium on LISP and Functional Programming, 61

WONG L., 1993, Proceedings of the Twelfth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS, 26, 10.1145/153850.153853

Thông tin
Thông tin xuất bản

ACM Transactions on Database Systems

Tập 25 Số 4

457-516

Thông tin tác giả