OFL: a functional execution model for object query languages

ABSTRACT

We present a functional paradigm for querying efficiently abstract collections of complex objects. Abstract collections are used to model class extents, multivalued attributes as well as indexes or hashing tables. Our paradigm includes a functional language called OFL (Object Functional Language) and a supporting execution model based on graph traversals. OFL is able to support any complex object algebra with recursion as macros. It is an appropriate target language for OQL-like query compilers. The execution model provides various strategies including set-oriented and pipelined traversals. OFL has been implemented on top of an object manager. Measures of a typical query extracted from a geographical benchmark show the value of hybrid strategies integrating pipelined and set-oriented evaluations. They also show the potential of function result memorization, a typical optimization approach known as "Memoization" ² in functional languages.

REFERENCES

• Aho88: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• Amman85: Amman A., Hanrahan M., and Knshnamurthy R, "Design of a Memory Resident DBMS", IEEE COMPCON, San Francisco, California, February 1985.
• Amman92: Bernd Amann , Michel Scholl, Gram: a graph data model and query languages, Proceedings of the ACM conference on Hypertext, p.201-211, November 30-December 04, 1992, Milan, Italy [doi>10.1145/168466.168527]
• Bakus81: Bakus J., "Function Level Program as Mathematical Objects," ACM Transactions on Database Systems, 6(1), October 1981.
• Bancilhon86: Francois Bancilhon , Raghu Ramakrishnan, An amateur's introduction to recursive query processing strategies, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.16-52, May 28-30, 1986, Washington, D.C., United States
• Bancilhon87: François Bancilhon , Ted Briggs , Setrag Khoshafian , Patrick Valduriez, FAD, a Powerful and Simple Database Language, Proceedings of the 13th International Conference on Very Large Data Bases, p.97-105, September 01-04, 1987
• Batory88: D. S. Batory , T. Y. Leung , T. E. Wise, Implementation concepts for an extensible data model and data language, ACM Transactions on Database Systems (TODS), v.13 n.3, p.231-262, Sept. 1988 [doi>10.1145/44498.45062]
• Beeri90: Catriel Beeri , Yoram Kornatzky, Algebraic optimization of object-oriented query languages, Proceedings of the third international conference on database theory on Database theory, p.72-88, November 1990, Paris, France
• Bitton86: Dina Bitton , Carolyn Turbyfill, Performance Evaluation of Main Memory Database Systems, Cornell University, Ithaca, NY, 1986
• Blakeley93: José A. Blakeley , William J. McKenna , Goetz Graefe, Experiences building the open OODB query optimizer, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.287-296, May 25-28, 1993, Washington, D.C., United States
• Buneman79: Peter Buneman , Robert E. Frankel, FQL: a functional query language, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582104]
• Carey88: Michael J. Carey , David J. DeWitt, A data model and query language for EXODUS, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.413-423, June 01-03, 1988, Chicago, Illinois, United States
• Cattell93: Roderick G. Cattell , Tom Atwood, Object Database Standard: ODMG-93, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• Cluet92: Sophie Cluet , Claude Delobel, A general framework for the optimization of object-oriented queries, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.383-392, June 02-05, 1992, San Diego, California, United States
• Cruz88: Cruz, I.F., "Domains of Application for the G+ Query Language", Office and Database Systems Research, ed. F.H. Lochovsky, CSRI, Univ. of Toronto, 1988.
• Dar91: Shaul Dar , Rakesh Agrawal , H. V. Jagadish, Optimization of Generalized Transitive Closure Queries, Proceedings of the Seventh International Conference on Data Engineering, p.345-354, April 08-12, 1991
• Delobel91: Delobel, C., Lecluse C., Richard P., "Bases de Donn6es : des Systtmes Relationels aux Systtmes h Objects," Book, InterEditions, Paris.
• Field88: Field, A., Harrison P., "Functional Programming," chapter 11 and 12, Book, Addison Wesley 1988.
• Finance94: Béatrice Finance , Georges Gardarin, A rule-based query optimizer with multiple search strategies, Data & Knowledge Engineering, v.13 n.1, p.1-29, Aug. 1994 [doi>10.1016/0169-023X(94)90045-0]
• Frohn94: Jürgen Frohn , Georg Lausen , Heinz Uphoff, Access to Objects by Path Expressions and Rules, Proceedings of the 20th International Conference on Very Large Data Bases, p.273-284, September 12-15, 1994
• Gardarin92a: Georges Gardarin , Patrick Valduriez, ESQL2: An Object-Oriented SQL with F-Logic Semantics, Proceedings of the Eighth International Conference on Data Engineering, p.320-327, February 03-07, 1992
• Gardarin92b: Georges Gardarin , Rosana S. G. Lanzelotte, Optimizing Object-Oriented Datbase Queries using Cost-Controlled Rewriting, Proceedings of the 3rd International Conference on Extending Database Technology: Advances in Database Technology, p.534-549, March 23-27, 1992
• Gardarin94: Gardarin G,, Machuca F., Pucheral P,, "A Functional Traversal Graph Optimization Strategy for OQL-hke Query Optimizers", Technical Report, PRISM Laboratory, (submitted for rpublication), 1994.
• Jenq90: B. Paul Jenq , Darrell Woelk , Won Kim , Wan-Lik Lee, Query processing in distributed ORION, Proceedings of the international conference on extending database technology on Advances in database technology, p.169-187, March 1990, Venice, Italy
• Kemper90: Alfons Kemper , Guido Moerkotte, Advanced query processing in object bases using access support relations, Proceedings of the sixteenth international conference on Very large databases, p.290-301, September 1990, Brisbane, Australia
• Kilger94: Christoph Kilger , Guido Moerkotte, Indexing Multiple Sets, Proceedings of the 20th International Conference on Very Large Data Bases, p.180-191, September 12-15, 1994
• Kim89: Won Kim , Kyung-Chang Kim , Alfred Dale, Indexing techniques for object-oriented databases, Object-oriented concepts, databases, and applications, ACM Press, New York, NY, 1989 [doi>10.1145/63320.66510]
• Kim92: Michael Kifer , Won Kim , Yehoshua Sagiv, Querying object-oriented databases, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.393-402, June 02-05, 1992, San Diego, California, United States
• Lanzelotte93: Lanzelotte R., Cheiney J.P., "Vers une nouvelle g~n~ration d'optimiseurs pour les SGBD orient, s objet," Tecnique et Science Informatique~, Volume 12(4), 1993.
• Lehman86: Tobin J. Lehman , Michael J. Carey, Query processing in main memory database management systems, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.239-250, May 28-30, 1986, Washington, D.C., United States
• Machuca94: Machuca F., Gardarin G., Pucherat P., "A Functional Execution Model for Complex Object Algebras," Technical Report, PRISM Laboratory, University of Versailles Saint-Quentin, Versailles, France, February, 1994.
• Michie68: Michie D., "Memo Functions and Machine Learning," Nature, (218), 1968. pp. 19-22,
• Orenstein92: Jack Orenstein , Sam Haradhvala , Benson Margulies , Don Sakahara, Query processing in the ObjectStore database system, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.403-412, June 02-05, 1992, San Diego, California, United States
• Pucheral92: Philippe Pucheral , Jean-Marc Thévenin, Pipelined Query Processing in the DBGraph Storage Model, Proceedings of the 3rd International Conference on Extending Database Technology: Advances in Database Technology, p.516-533, March 23-27, 1992
• Selinger87: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• Shaw90: Shaw G., Zdonik S., "A Query Algebra for Object- Oriented Databases," in IEEE, 1990.
• Shipman81: David W. Shipman, The functional data model and the data languages DAPLEX, ACM Transactions on Database Systems (TODS), v.6 n.1, p.140-173, March 1981 [doi>10.1145/319540.319561]
• Shekita90: Eugene J. Shekita , Michael J. Carey, A performance evaluation of pointer-based joins, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.300-311, May 23-26, 1990, Atlantic City, New Jersey, United States
• Sreenath94: B. Sreenath , S. Seshadri, The hcC-tree: An Efficient Index Structure for Object Oriented Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.203-213, September 12-15, 1994
• Steenhagen94: Hennie J. Steenhagen , Peter M. G. Apers , Henk M. Blanken , Rolf A. de By, From Nested-Loop to Join Queries in OODB, Proceedings of the 20th International Conference on Very Large Data Bases, p.618-629, September 12-15, 1994
• Straube90: Straube D., Ozsu T, "Queries and Query Processing m Object-Oriented Database Systems,"Technical Report, Departement of computing science, university of Alberta, Edmonton, Alberta, Canada, 1990.
• Valduriez86: Patrick Valduriez , Setrag Khoshafian , George P. Copeland, Implementation Techniques of Complex Objects, Proceedings of the 12th International Conference on Very Large Data Bases, p.101-110, August 25-28, 1986
• Valduriez91: Valdunez P., Lanzelotte R,, Ziane M, and Chelney J.P., "Optimization of non Recursive Queries in OODB," In Proc. DOOD, Munich, Germany, 1991.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Retrieval models

General Terms:
Algorithms, Languages, Measurement, Performance