This alert has been successfully added and will be sent to: You will be notified whenever a record that you have chosen has been cited.
To manage your alert preferences, click on the button below. Manage my AlertsIn the past few years, query languages featuring generalized path expressions have been proposed. These languages allow the interrogation of both data and structure. They are powerful and essential for a number of applications. However, until now, their evaluation has relied on a rather naive and inefficient algorithm.In this paper, we extend an object algebra with two new operators and present some interesting rewriting techniques for queries featuring generalized path expressions. We also show how a query optimizer can integrate the new techniques.
D. Batory. Extensible cost models and quely optimization in Genesis. IEEE Database Engneerzng, 10(4), November 1987.
E. Bertino. I~sues in indexing techniques for object-oriented databases. In Proc. of Advanced Database,System Sgmpos~um, pages 151-160, 1989.
E. Bertino and P. Foscoli. An analytical cost model of object-oriented queiy costs In Proc. Pers,stent Object Systems, pages 151-160, 199'2.
J. Blaketey, \V. McKenna, and G graefe. Experiences building the Open GOD>3 query optimizer. In Proc. o,f the A CM,5IGAfOD gaul, on Management oJ Data, pages 287-295, 1993.
E. BettinG, F. Rabitti, and S. Gibbs. Query Processing in a Multimedia Document System. A CM Transact~on~ on Office Information Sgstem~, 6(1)'1-41, January 1988.
V. Christophides, S. Abiteboul, S. Cluet, and M. Schoi1. From structured documents to novel query facilities. In Proc. of the A 6'M SIGMOD Conf. on Management of Data, pages 3t3-324, Minneapolis, Minnesota, May 1994.
S. Cluet and G Moerkotte. ChLssifica~tion amd optimization of nested queries in object, b~ses. Technical Report 95-6, RWTH Aachen, 1995.
S. Chet and G. Moerkotte. Query optimization techmques exploiting class hierarchies. Technical Report 95-7, R\~TH-Aachen, 1995.
G. Graefe and D. DeWitt. The EXODUS optimizer generator In Proc. of the A CM SIGMOD Conj, on Management of Data, pa.ges 160-172, San Francisco, 1987.
G. Grade and W McI(enna. The Volcano optimizer generator. Tech. Report 563, University of Colorado, Boulder, 1991.
G. Graefe and K. Ward. Dynamic query evaluation plans In Proc. of the ACM SIGMOD Conf on Management of Data, pages,358-366, 1989.
L. M. Haas, J.C. Freytag, G.M. Lohman, emd H. Pirahesh. Extensible query processing in Starburst. In Proc. of the A CM SIGMOD Conf. on Management of Data, pages 377-388, 1989.
P. Jenq, D. Woelk, W. Kiin, and W. Lee. Query processing in distributed ORION. In Proc. Int Conf. on Extended Database Technology (EDBT), pages 169-187, Venice, 1990.
MI(ifer, \\:. I<im, and Y. Sagiv. Qumymg object-oriented databases. In Proc. of the ACM,5'IGMOD Conf. on 3
A. Kemper and G. Moerkotte. Access suppmt in object bases. In Proc. of the A CM SIGMOD Conf. on :lganagement of Data., pages 364-374, 1990.
A. Kemper and G. Moerkotte. Query optimization m object bases: Exploiting relational techniques. In Proc. Dagatuhl Workshop on Query Optimization (J.-C. Freytag, D. Maier und G. Vossen (ads.)). Morgan-Kaufman, 1993.
A. Kemper, G. Moerkotte, and K. Peithner. A blackboard architecture for query optimization in object bases. In Proc. Int. Conf. on Very Large Data Bases (VLDB), pages 543-554, t993.
G.M. Lohman. Grammar-like functional rules for representing query optimization alternatives. In Proc. of the A CM SIGMOD Conf. on Management of Data, pages 18-27, 1988.
G. Mitchell, S. Zdonik, and U. Dayal An architecture for query processing in persistent object stores. In Proc. of the Hawaiian Conf. on Computer and System Sc2enee~, pa.ges 787-798, 1992.
D. Quass, A. Rajaraman, Y. Sagiv, J. Ullman, and J. Widom. Querying semistructured heterogeneous information. In Proc. Int. Conf. on Deductive and Object-Oriented Databases (DOOD), pages 319-344, Dec. 1995.
J. Sim4on. Recherche en texte intdgrM et bases de donn4es orient~es-objet.Master's thesis, Universit4 de Nancy I, 1995
In the past few years, query languages featuring generalized path expressions have been proposed. These languages allow the interrogation of both data and structure. They are powerful and essential for a number of applications. However, until now, their .
Recent work on semi-structured data has revitalized the interest in path queries, i.e., queries that ask for all pairs of objects in the database that are connected by a path conforming to a certain specification, in particular to a regular expression. .
PODS '00: Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems
View-based query processing is the problem of computing the answer to a query based on a set of materialized views, rather than on the raw data in the database. The problem comes in two different forms, called query rewriting and query answering, .
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]
Association for Computing Machinery
New York, NY, United States
