Article

Free access

OFL: a functional execution model for object query languages

Authors:

Georges Gardarin,

Fernando Machuca,

Philippe PucheralAuthors Info & Claims

SIGMOD '95: Proceedings of the 1995 ACM SIGMOD international conference on Management of data

Pages 59 - 70

https://doi.org/10.1145/223784.223791

Published: 22 May 1995 Publication History

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

[1]

Aho A. V., Sethi R, Ullman J. D., "Compilers : Principles, Techniques, and Tools," Book, chapter 1, 8 to 12, Addison-Wesley, 1988.

Digital Library

[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.

Digital Library

[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,

Digital Library

[6]

Bancilhon F., Briggs T., Khoshafian S., Valduriez P., "FAD, a Powerful and Simple Database Language," Intl. Conf. on VLDB, Brighton, England, 1987.

Digital Library

[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.

Digital Library

[8]

Beeri C, Kornatzky Y., "Algebraic Optimisation of Object- Oriented Query Languages," in Proc. ICDT, Paris, France, 1990.

Digital Library

[9]

Bitton D., TurbyfiI1 C., "Performance Evaluation of Main Memory Database Systems", Cornell University, TR 86-73 I.

Digital Library

[10]

Blakeley J., Graefe G., "Experiences Building the Open OODB Query Optimizer," Intl, ACM SIGMOD Conf. on Management of Data, 1993.

Digital Library

[11]

Buneman P., Frankel R.E., "FQL--A functioal query languageB,'' Intl. ACM SIGMOD Conf. on Management of Data, 1979.

Digital Library

[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.

Digital Library

[13]

Cattell R.G.G. Ed., "Object Databases: The ODMG-93 Standard", Book, Morgan & Kaufman, 1993.

Digital Library

[14]

Cluet, S., DelobeI C, "A General Framework for the Optimization of Object-Oriented Queries," Intl. ACM SIGMOD Conf. on Management of Data, 1992.

Digital Library

[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.

Digital Library

[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.

Digital Library

[20]

Frohn J., Lausen G, Uphoff H., "Access to Objects by Path Expressions and Rules", Intl. Conf. on VLDB, Santiago, Chile, August 1994.

Digital Library

[21]

Gardarin G., Valdunez P., "ESQL: An Object-Oriented SQL with F-Logic Semantics," Intl. Conf. on Data Engineering, Phoenix, February 1992.

Digital Library

[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.

Digital Library

[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.

Digital Library

[25]

Kemper A., G. Moerkotte, "Advanced Query processing in Object Bases Using Access Support Relations," Intl. Conf. on VLDB, Brisbane, Australia, 1990.

Digital Library

[26]

Kilger C., Moerkotte G., "Indexing Multiple Sets," Intl. Conf on VLDB, Santiago, Chile, August 1994.

Digital Library

[27]

Kim, W., Kim K., Dale A., "Indexing Techniques for Object- Oriented Databases," Book, chapter 15, Addison-Wesley, 1988.

Digital Library

[28]

Kim, W., Sagiv Y., Kifer M., "Querying Object-Oriented Databases," ACM SIGMOD, USA, June 1992.

Digital Library

[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.

Digital Library

[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.

Digital Library

[34]

Puchcral P., Th6venin J.M., "Pipelined Query Processing in the DBGraph Storage Model," Intl. Conf. on EDBT, Vienna, Austria, March 1992.

Digital Library

[35]

Selinger P, et al, "Acces Path Selection in a Relational Database Managment System," in Proc, of the ACM SIGMOD Conference, New York, 1987.

Digital Library

[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.

Digital Library

[38]

Shekita E. J., Carey M. J., "A Perfomance Evaluation of Pointer-Based Joins," in Proc. of the ACM SIGMOD Conference, 1990.

Digital Library

[39]

Sreenath B., Seshadri S., "The hcC-tree: An Efficient Index Structure For Object Oriented Databases," Intl. Conf. on VLDB, Santiago, Chile, August 1994.

Digital Library

[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.

Digital Library

[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.

Digital Library

[43]

Valdunez P., Lanzelotte R, Ziane M, and Chelney J.P., "Optimization of non Recursive Queries in OODB," In Proc. DOOD, Munich, Germany, 1991.

Cited By

Abbas IBoucelma O(2005)A framework for algebraic optimization of object-oriented query languagesDatabase and Expert Systems Applications10.1007/BFb0022056(478-487)Online publication date: 10-Jun-2005
https://doi.org/10.1007/BFb0022056
Fessy JLepetit YPucheral P(2005)Object query services for telecommunication networksAdvances in Database Technology — EDBT '9610.1007/BFb0014174(490-493)Online publication date: 10-Jun-2005
https://doi.org/10.1007/BFb0014174
Alani HDasmahapatra SGibbins NGlaser HHarris SKalfoglou YO’Hara KShadbolt N(2002)Managing Reference: Ensuring Referential Integrity of Ontologies for the Semantic WebKnowledge Engineering and Knowledge Management: Ontologies and the Semantic Web10.1007/3-540-45810-7_29(317-334)Online publication date: 13-Sep-2002
https://doi.org/10.1007/3-540-45810-7_29
Show More Cited By

Index Terms

OFL: a functional execution model for object query languages

Recommendations

OFL: a functional execution model for object query languages

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 ...
Layout-sensitive language extensibility with SugarHaskell
Haskell '12: Proceedings of the 2012 Haskell Symposium

Programmers 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 ...
Equivalence and minimization of conjunctive queries under combined semantics
ICDT '12: Proceedings of the 15th International Conference on Database Theory

The problems of query containment, equivalence, and minimization are fundamental problems in the context of query processing and optimization. In their classic work [2] published in 1977, Chandra and Merlin solved the three problems for the language of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '95: Proceedings of the 1995 ACM SIGMOD international conference on Management of data

June 1995

508 pages

ISBN:0897917316

DOI:10.1145/223784

Editors:
Michael Carey
Univ. of Wisconsin
,
Donovan Schneider
Red Brick Systems

ACM SIGMOD Record Volume 24, Issue 2
May 1995
490 pages
ISSN:0163-5808
DOI:10.1145/568271
Issue’s Table of Contents

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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 May 1995

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGMOD/PODS95

Sponsor:

SIGMOD/PODS95: Joint ACM SIGMOD Intl Conference on Management of Data and ACM SIGACT-SIGMOD- SIGART Symposium on Principles of Database Systems

May 22 - 25, 1995

California, San Jose, USA

Acceptance Rates

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
492
Total Downloads

Downloads (Last 12 months)115
Downloads (Last 6 weeks)27

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Abbas IBoucelma O(2005)A framework for algebraic optimization of object-oriented query languagesDatabase and Expert Systems Applications10.1007/BFb0022056(478-487)Online publication date: 10-Jun-2005
https://doi.org/10.1007/BFb0022056
Fessy JLepetit YPucheral P(2005)Object query services for telecommunication networksAdvances in Database Technology — EDBT '9610.1007/BFb0014174(490-493)Online publication date: 10-Jun-2005
https://doi.org/10.1007/BFb0014174
Alani HDasmahapatra SGibbins NGlaser HHarris SKalfoglou YO’Hara KShadbolt N(2002)Managing Reference: Ensuring Referential Integrity of Ontologies for the Semantic WebKnowledge Engineering and Knowledge Management: Ontologies and the Semantic Web10.1007/3-540-45810-7_29(317-334)Online publication date: 13-Sep-2002
https://doi.org/10.1007/3-540-45810-7_29
Bercken JBlohsfeld BDittrich JKrämer JSchäfer TSchneider MSeeger B(2001)XXL - A Library Approach to Supporting Efficient Implementations of Advanced Database QueriesProceedings of the 27th International Conference on Very Large Data Bases10.5555/645927.672371(39-48)Online publication date: 11-Sep-2001
https://dl.acm.org/doi/10.5555/645927.672371
Cherniack MZdonik S(1996)Rule languages and internal algebras for rule-based optimizersACM SIGMOD Record10.1145/235968.23335625:2(401-412)Online publication date: 1-Jun-1996
https://dl.acm.org/doi/10.1145/235968.233356
Cherniack MZdonik S(1996)Rule languages and internal algebras for rule-based optimizersProceedings of the 1996 ACM SIGMOD international conference on Management of data10.1145/233269.233356(401-412)Online publication date: 1-Jun-1996
https://dl.acm.org/doi/10.1145/233269.233356
Kiernan JCarey M(1995)Extending SQL-92 for OODB accessACM SIGPLAN Notices10.1145/217839.21788330:10(467-480)Online publication date: 17-Oct-1995
https://dl.acm.org/doi/10.1145/217839.217883
Kiernan JCarey MWirfs-Brock R(1995)Extending SQL-92 for OODB accessProceedings of the tenth annual conference on Object-oriented programming systems, languages, and applications10.1145/217838.217883(467-480)Online publication date: 17-Oct-1995
https://dl.acm.org/doi/10.1145/217838.217883

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents