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" 2 in functional languages.
References
[1]
Aho A. V., Sethi R, Ullman J. D., "Compilers : Principles, Techniques, and Tools," Book, chapter 1, 8 to 12, Addison-Wesley, 1988.
[2]
Amman A., Hanrahan M., and Knshnamurthy R, "Design of a Memory Resident DBMS", IEEE COMPCON, San Francisco, California, February 1985.
[3]
Amman B., SchoI M., "Gram: A Graph Data Model and Query Language", ACM ECHT'92, Milan, December 1992.
[4]
Bakus J., "Function Level Program as Mathematical Objects," ACM Transactions on Database Systems, 6(1), October 1981.
[5]
Bancilhon F., "An amateur's Introduction to Recursive Query processing Strategies," Intl. ACM SIGMOD Conf. on Management of Data, Washington D.C., May 1986,
[6]
Bancilhon F., Briggs T., Khoshafian S., Valduriez P., "FAD, a Powerful and Simple Database Language," Intl. Conf. on VLDB, Brighton, England, 1987.
[7]
Batory D., Leung T., and Wise T., "Implementation Concepts for an Extensible Data Model and Data Language," ACM Transactions on Database Systems, 13(3), September 1988.
[8]
Beeri C, Kornatzky Y., "Algebraic Optimisation of Object- Oriented Query Languages," in Proc. ICDT, Paris, France, 1990.
[9]
Bitton D., TurbyfiI1 C., "Performance Evaluation of Main Memory Database Systems", Cornell University, TR 86-73 I.
[10]
Blakeley J., Graefe G., "Experiences Building the Open OODB Query Optimizer," Intl, ACM SIGMOD Conf. on Management of Data, 1993.
[11]
Buneman P., Frankel R.E., "FQL--A functioal query languageB,'' Intl. ACM SIGMOD Conf. on Management of Data, 1979.
[12]
Carey, M. J., Dewitt D., Vandenberg S. L., "A Data Model and Query Language for EXODUS," Intl. ACM SIGMOD Conf. on Management of Data, 1988.
[13]
Cattell R.G.G. Ed., "Object Databases: The ODMG-93 Standard", Book, Morgan & Kaufman, 1993.
[14]
Cluet, S., DelobeI C, "A General Framework for the Optimization of Object-Oriented Queries," Intl. ACM SIGMOD Conf. on Management of Data, 1992.
[15]
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.
[16]
Dar S., Agrawal R., Jagadish H.V., "Optimization of Generalized Transitive Closure Queries," Intl. Conf. on Data Engineering, Kobe, Japan, April 1991.
[17]
Delobel, C., Lecluse C., Richard P., "Bases de Donn6es : des Systtmes Relationels aux Systtmes h Objects," Book, InterEditions, Paris.
[18]
Field, A., Harrison P., "Functional Programming," chapter 11 and 12, Book, Addison Wesley 1988.
[19]
Finance, B., Gardarin G., "A rule-based optimizer with multiple search strategies," Data & Knowledge Engineering 13, 1994.
[20]
Frohn J., Lausen G, Uphoff H., "Access to Objects by Path Expressions and Rules", Intl. Conf. on VLDB, Santiago, Chile, August 1994.
[21]
Gardarin G., Valdunez P., "ESQL: An Object-Oriented SQL with F-Logic Semantics," Intl. Conf. on Data Engineering, Phoenix, February 1992.
[22]
Gardarin G., Lanzelotte R., "Optimlzing Object- Oriented Database Queries using Cost-Controlled Rewriting" 3rd Intl. Conf. conference on Extended Data Base Technology, (EDBT), Springer-Verlag Ed.,Vienna, Austria, March 1992.
[23]
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.
[24]
Jenq, B. P., Woelk, D, Kim, W., Lee, W., "Query Processing in Distributed ORION," Intl. Conf. EDBT, Venice, Italy, March 1990.
[25]
Kemper A., G. Moerkotte, "Advanced Query processing in Object Bases Using Access Support Relations," Intl. Conf. on VLDB, Brisbane, Australia, 1990.
[26]
Kilger C., Moerkotte G., "Indexing Multiple Sets," Intl. Conf on VLDB, Santiago, Chile, August 1994.
[27]
Kim, W., Kim K., Dale A., "Indexing Techniques for Object- Oriented Databases," Book, chapter 15, Addison-Wesley, 1988.
[28]
Kim, W., Sagiv Y., Kifer M., "Querying Object-Oriented Databases," ACM SIGMOD, USA, June 1992.
[29]
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.
[30]
Lehman T., Carey M., "Query Processing in Main Memory Database Management Systems", ACM SIGMOD Int. Conf, Washington, D.C., May 1986.
[31]
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.
[32]
Michie D., "Memo Functions and Machine Learning," Nature, (218), 1968. pp. 19-22,
[33]
Orenstein J, Haradhvala S., Margulies B., Sakahara D., "Query Processing in the ObjectStore Database System," Intl. ACM SIGMOD Conf. on Management of Data, 1992.
[34]
Puchcral P., Th6venin J.M., "Pipelined Query Processing in the DBGraph Storage Model," Intl. Conf. on EDBT, Vienna, Austria, March 1992.
[35]
Selinger P, et al, "Acces Path Selection in a Relational Database Managment System," in Proc, of the ACM SIGMOD Conference, New York, 1987.
[36]
Shaw G., Zdonik S., "A Query Algebra for Object- Oriented Databases," in IEEE, 1990.
[37]
Shipman, D., "The functional Data Model and the Data Language DAPLEX," ACM Transactions on Database Systems, 6(1), March 1981.
[38]
Shekita E. J., Carey M. J., "A Perfomance Evaluation of Pointer-Based Joins," in Proc. of the ACM SIGMOD Conference, 1990.
[39]
Sreenath B., Seshadri S., "The hcC-tree: An Efficient Index Structure For Object Oriented Databases," Intl. Conf. on VLDB, Santiago, Chile, August 1994.
[40]
Steenhagen H. J., Apers P. M.G., Blanken H., de By R. A., "From Nested-Loop to Join Queries in OODB," Intl. Conf, on VLDB, Santiago de Chile, Chile, September 1994.
[41]
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.
[42]
Valduriez P., Khoshafian S., Copeland G., "Implementation Techniques of Complex Objects," intl. Conf. on VLDB, Kyoto, August 1986.
[43]
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
- OFL: a functional execution model for object query languages
Recommendations
OFL: a functional execution model for object query languages
SIGMOD '95: Proceedings of the 1995 ACM SIGMOD international conference on Management of dataWe 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 ...
Layout-sensitive language extensibility with SugarHaskell
Haskell '12: Proceedings of the 2012 Haskell SymposiumProgrammers need convenient syntax to write elegant and concise programs. Consequently, the Haskell standard provides syntactic sugar for some scenarios (e.g., do notation for monadic code), authors of Haskell compilers provide syntactic sugar for more ...
Layout-sensitive language extensibility with SugarHaskell
Haskell '12Programmers need convenient syntax to write elegant and concise programs. Consequently, the Haskell standard provides syntactic sugar for some scenarios (e.g., do notation for monadic code), authors of Haskell compilers provide syntactic sugar for more ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 1995 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 22 May 1995
Published in SIGMOD Volume 24, Issue 2
Check for updates
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations8Total Citations
- 492Total Downloads
- Downloads (Last 12 months)115
- Downloads (Last 6 weeks)27
Reflects downloads up to 16 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in