The state of the art in distributed query processing

ABSTRACT

Distributed data processing is becoming a reality. Businesses want to do it for many reasons, and they often must do it in order to stay competitive. While much of the infrastructure for distributed data processing is already there (e.g., modern network technology), a number of issues make distributed data processing still a complex undertaking: (1) distributed systems can become very large, involving thousands of heterogeneous sites including PCs and mainframe server machines; (2) the state of a distributed system changes rapidly because the load of sites varies over time and new sites are added to the system; (3) legacy systems need to be integrated—such legacy systems usually have not been designed for distributed data processing and now need to interact with other (modern) systems in a distributed environment. This paper presents the state of the art of query processing for distributed database and information systems. The paper presents the “textbook” architecture for distributed query processing and a series of techniques that are particularly useful for distributed database systems. These techniques include special join techniques, techniques to exploit intraquery paralleli sm, techniques to reduce communication costs, and techniques to exploit caching and replication of data. Furthermore, the paper discusses different kinds of distributed systems such as client-server, middleware (multitier), and heterogeneous database systems, and shows how query processing works in these systems.

REFERENCES

• 1: Serge Abiteboul, Querying Semi-Structured Data, Proceedings of the 6th International Conference on Database Theory, p.1-18, January 08-10, 1997
• 2: Serge Abiteboul , Peter Buneman , Dan Suciu, Data on the Web: from relations to semistructured data and XML, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 3: Swarup Acharya , Rafael Alonso , Michael Franklin , Stanley Zdonik, Broadcast disks: data management for asymmetric communication environments, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.199-210, May 22-25, 1995, San Jose, California, United States
• 4: Swarup Acharya , Michael J. Franklin , Stanley B. Zdonik, Prefetching from Broadcast Disks, Proceedings of the Twelfth International Conference on Data Engineering, p.276-285, February 26-March 01, 1996
• 5: Swarup Acharya , Michael Franklin , Stanley Zdonik, Balancing push and pull for data broadcast, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.183-194, May 11-15, 1997, Tucson, Arizona, United States
• 6: ACM Computing Surveys. 1990. Special issue on heterogeneous databases. ACM Computing Surveys, 22, 13.
• 7: S. Adali , K. S. Candan , Y. Papakonstantinou , V. S. Subrahmanian, Query caching and optimization in distributed mediator systems, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.137-146, June 04-06, 1996, Montreal, Quebec, Canada
• 8: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 9: AKSOY,D.AND FRANKLIN, M. 1998. Scheduling for large-scale on-demand data broadcasting. In Proceedings IEEE INFOCOM Conference (San Francisco, CA, March).
• 10: Peter M. G. Apers, Data allocation in distributed database systems, ACM Transactions on Database Systems (TODS), v.13 n.3, p.263-304, Sept. 1988 [doi>10.1145/44498.45063]
• 11: E. Babb, Implementing a relational database by means of specialzed hardware, ACM Transactions on Database Systems (TODS), v.4 n.1, p.1-29, March 1979 [doi>10.1145/320064.320065]
• 12: Randall G. Bello , Karl Dias , Alan Downing , James J. Feenan, Jr. , James L. Finnerty , William D. Norcott , Harry Sun , Andrew Witkowski , Mohamed Ziauddin, Materialized Views in Oracle, Proceedings of the 24rd International Conference on Very Large Data Bases, p.659-664, August 24-27, 1998
• 13: Philip A. Bernstein , Nathan Goodman , Eugene Wong , Christopher L. Reeve , James B. Rothnie, Jr., Query processing in a system for distributed databases (SDD-1), ACM Transactions on Database Systems (TODS), v.6 n.4, p.602-625, Dec. 1981 [doi>10.1145/319628.319650]
• 14: BESTAVROS,A.AND CUNHA, C. 1996. Server-initiated document dissemination for the WWW. IEEE Data Engeneering Bulletin 19, 3 (Sept.), 3- 11.
• 15: Phillip Bogle , Barbara Liskov, Reducing cross domain call overhead using batched futures, Proceedings of the ninth annual conference on Object-oriented programming systems, language, and applications, p.341-354, October 23-28, 1994, Portland, Oregon, United States
• 16: R. Braumandl , J. Claussen , A. Kemper , D. Kossmann, Functional-join processing, The VLDB Journal — The International Journal on Very Large Data Bases, v.8 n.3-4, p.156-177, February 2000 [doi>10.1007/s007780050002]
• 17: Reinhard Braumandl , Alfons Kemper , Donald Kossmann, Database patchwork on the Internet, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.550-552, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 18: Yuri Breitbart , Hector Garcia-Molina , Avi Silberschatz, Overview of multidatabase transaction management, The VLDB Journal — The International Journal on Very Large Data Bases, v.1 n.2, p.181-240, October 1992 [doi>10.1007/BF01231700]
• 19: Reudiger Buck-Emden , Jurgen Galimow, Sap R\3 System: A Client/Server Technology, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 20: Peter Buneman, Semistructured data, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.117-121, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263675]
• 21: M. J. Carey , L. M. Haas , P. M. Schwarz , M. Arya , W. F. Cody , R. Fagin , M. Flickner , A. W. Luniewski , W. Niblack , D. Petkovic , J. Thomas , J. H. Williams , E. L. Wimmers, Towards heterogeneous multimedia information systems: the Garlic approach, Proceedings of the 5th International Workshop on Research Issues in Data Engineering-Distributed Object Management (RIDE-DOM'95), p.124, March 06-07, 1995
• 22: Michael J. Carey , David J. DeWitt , Michael J. Franklin , Nancy E. Hall , Mark L. McAuliffe , Jeffrey F. Naughton , Daniel T. Schuh , Marvin H. Solomon , C. K. Tan , Odysseas G. Tsatalos , Seth J. White , Michael J. Zwilling, Shoring up persistent applications, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.383-394, May 24-27, 1994, Minneapolis, Minnesota, United States
• 23: Michael J. Carey , Donald Kossmann, On saying “Enough already!” in SQL, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.219-230, May 11-15, 1997, Tucson, Arizona, United States
• 24: Michael J. Carey , Donald Kossmann, Reducing the Braking Distance of an SQL Query Engine, Proceedings of the 24rd International Conference on Very Large Data Bases, p.158-169, August 24-27, 1998
• 25: Michael J. Carey , Hongjun Lu, Load balancing in a locally distributed DB system, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.108-119, May 28-30, 1986, Washington, D.C., United States
• 26: R. G. G. Cattell , Douglas K. Barry , Dirk Bartels , Mark Berler , Jeff Eastman , Sophie Gamerman , David Jordan , Adam Springer , Henry Strickland , Drew Wade, The object database standard: ODMG 2.0, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 27: Stefano Ceri , Giuseppe Pelagatti, Distributed databases principles and systems, McGraw-Hill, Inc., New York, NY, 1984
• 28: D. D. Chamberlin , M. M. Astrahan , W. F. King , R. A. Lorie , J. W. Mehl , T. G. Price , M. Schkolnick , P. Griffiths Selinger , D. R. Slutz , B. W. Wade , R. A. Yost, Support for repetitive transactions and ad hoc queries in System R, ACM Transactions on Database Systems (TODS), v.6 n.1, p.70-94, March 1981 [doi>10.1145/319540.319550]
• 29: Surajit Chaudhuri , Luis Gravano, Optimizing queries over multimedia repositories, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.91-102, June 04-06, 1996, Montreal, Quebec, Canada
• 30: Chungmin Melvin Chen , Nick Roussopoulos, Adaptive selectivity estimation using query feedback, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.161-172, May 24-27, 1994, Minneapolis, Minnesota, United States
• 31: Richard L. Cole , Goetz Graefe, Optimization of dynamic query evaluation plans, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.150-160, May 24-27, 1994, Minneapolis, Minnesota, United States
• 32: George Copeland , William Alexander , Ellen Boughter , Tom Keller, Data placement in Bubba, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.99-108, June 01-03, 1988, Chicago, Illinois, United States
• 33: Albert D'Andrea , Phil Janus, UniSQL's next-generation object-relational database management system, ACM SIGMOD Record, v.25 n.3, p.70-76, Sept. 1996 [doi>10.1145/234889.234902]
• 34: Shaul Dar , Michael J. Franklin , Björn Þór Jónsson , Divesh Srivastava , Michael Tan, Semantic Data Caching and Replacement, Proceedings of the 22th International Conference on Very Large Data Bases, p.330-341, September 03-06, 1996
• 35: Susan B. Davidson , Hector Garcia-Molina , Dale Skeen, Consistency in a partitioned network: a survey, ACM Computing Surveys (CSUR), v.17 n.3, p.341-370, Sept. 1985 [doi>10.1145/5505.5508]
• 36: Umeshwar Dayal, Processing Queries Over Generalization Hierarchies in a Multidatabase System, Proceedings of the 9th International Conference on Very Large Data Bases, p.342-353, October 31-November 02, 1983
• 37: Prasad M. Deshpande , Karthikeyan Ramasamy , Amit Shukla , Jeffrey F. Naughton, Caching multidimensional queries using chunks, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.259-270, June 01-04, 1998, Seattle, Washington, United States
• 38: Stefan Deßloch , Theo Härder , Nelson Mattos , Bernhard Mitschang , Joachim Thomas, Advanced data processing in KRISYS: modeling concepts, implementation techniques, and client/server issues, The VLDB Journal — The International Journal on Very Large Data Bases, v.7 n.2, p.79-95, May 1998 [doi>10.1007/s007780050055]
• 39: David J. DeWitt , Philippe Futtersack , David Maier , Fernando Velez, A study of three alternative workstation server architectures for object-oriented database systems, Proceedings of the sixteenth international conference on Very large databases, p.107-121, September 1990, Brisbane, Australia
• 40: David DeWitt , Jim Gray, Parallel database systems: the future of high performance database systems, Communications of the ACM, v.35 n.6, p.85-98, June 1992 [doi>10.1145/129888.129894]
• 41: Daniel F. Lieuwen , David J. DeWitt , Manish Mahta, Parallel pointer-based join techniques for object-oriented database, Proceedings of the second international conference on Parallel and distributed information systems, p.172-181, January 1993, San Diego, California, United States
• 42: Asuman Dogac , Ugur Halici , Ebru Kilic , Gokhan Ozhan , Fatma Ozcan , Sena Nural , Cevdet Dengi , Sema Mancuhan , Budak Arpinar , Pinar Koksal , Cem Evrendilek, METU interoperable database system, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.552, June 04-06, 1996, Montreal, Quebec, Canada
• 43: Joachen Doppelhammer , Thomas Höppler , Alfons Kemper , Donald Kossmann, Database performance in the real world: TPC-D and SAP R/3, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.123-134, May 11-15, 1997, Tucson, Arizona, United States
• 44: Weimin Du , Ravi Krishnamurthy , Ming-Chien Shan, Query Optimization in a Heterogeneous DBMS, Proceedings of the 18th International Conference on Very Large Data Bases, p.277-291, August 23-27, 1992
• 45: Weimin Du , Ming-Chien Shan , Umeshwar Dayal, Reducing multidatabase query response time by tree balancing, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.293-303, May 22-25, 1995, San Jose, California, United States
• 46: André Eickler , Carsten Andreas Gerlhof , Donald Kossmann, A Performance Evaluation of OID Mapping Techniques, Proceedings of the 21th International Conference on Very Large Data Bases, p.18-29, September 11-15, 1995
• 47: André Eickler , Alfons Kemper , Donald Kossmann, Finding Data in the Neighborhood, Proceedings of the 23rd International Conference on Very Large Data Bases, p.336-345, August 25-29, 1997
• 48: EPSTEIN, R., STONEBRAKER, M., AND WONG, E. 1978. Query processing in a distributed relational database system. In Proceedings of the ACM SIGMOD Conference on Management of Data (Austin, TX, June), 169-180.
• 49: Cem Evrendilek , Asuman Dogac , Sena Nural , Fatma Ozcan, Multidatabase Query Optimization, Distributed and Parallel Databases, v.5 n.1, p.77-114, Jan. 1997 [doi>10.1023/A:1008674905987]
• 50: Ronald Fagin, Combining fuzzy information from multiple systems (extended abstract), Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.216-226, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237715]
• 51: Ronald Fagin , Edward L. Wimmers, Incorporating User Preferences in Multimedia Queries, Proceedings of the 6th International Conference on Database Theory, p.247-261, January 08-10, 1997
• 52: Donald F. Ferguson , Christos Nikolaou , Jakka Sairamesh , Yechiam Yemini, Economic models for allocating resources in computer systems, Market-based control: a paradigm for distributed resource allocation, World Scientific Publishing Co., Inc., River Edge, NJ, 1996
• 53: FERGUSON, D., NIKOLAOU,C.,AND YEMINI, Y. 1993. An economy for managing replicated data in autonomous decentralized systems. In Proceedings International Symposium on Autonomous and Decentralized Systems (Kawasaki, Japan).
• 54: Daniela Florescu , Donald Kossmann , Ioana Manolescu, Integrating keyword search into XML query processing, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.119-135, June 2000, Amsterdam, The Netherlands
• 55: Daniela Florescu , Alon Levy , Alberto Mendelzon, Database techniques for the World-Wide Web: a survey, ACM SIGMOD Record, v.27 n.3, p.59-74, Sept. 1, 1998 [doi>10.1145/290593.290605]
• 56: Michael J. Franklin , Michael J. Carey , Miron Livny, Local Disk Caching for Client-Server Database Systems, Proceedings of the 19th International Conference on Very Large Data Bases, p.641-655, August 24-27, 1993
• 57: Michael J. Franklin , Michael J. Carey , Miron Livny, Transactional client-server cache consistency: alternatives and performance, ACM Transactions on Database Systems (TODS), v.22 n.3, p.315-363, Sept. 1997 [doi>10.1145/261124.261125]
• 58: Michael J. Franklin , Björn Thór Jónsson , Donald Kossmann, Performance tradeoffs for client-server query processing, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.149-160, June 04-06, 1996, Montreal, Quebec, Canada
• 59: Michael Franklin , Stan Zdonik, “Data in your face”: push technology in perspective, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.516-519, June 01-04, 1998, Seattle, Washington, United States
• 60: Sumit Ganguly , Akshay Goel , Avi Silberschatz, Efficient and accurate cost models for parallel query optimization (extended abstract), Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.172-181, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237707]
• 61: Sumit Ganguly , Waqar Hasan , Ravi Krishnamurthy, Query optimization for parallel execution, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.9-18, June 02-05, 1992, San Diego, California, United States
• 62: Georges Gardarin , Jean-Robert Gruser , Zhao-Hui Tang, Cost-based Selection of Path Expression Processing Algorithms in Object-Oriented Databases, Proceedings of the 22th International Conference on Very Large Data Bases, p.390-401, September 03-06, 1996
• 63: Goetz Graefe, Encapsulation of parallelism in the Volcano query processing system, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.102-111, May 23-26, 1990, Atlantic City, New Jersey, United States
• 64: Goetz Graefe, Query evaluation techniques for large databases, ACM Computing Surveys (CSUR), v.25 n.2, p.73-169, June 1993 [doi>10.1145/152610.152611]
• 65: GRAEFE, G. 1995. The cascades framework for query optimization. IEEE Data Engeneering Bulletin 18, 3 (Sept.), 19-29.
• 66: Goetz Graefe, Iterators, schedulers, and distributed-memory parallelism, Software—Practice & Experience, v.26 n.4, p.427-452, April 1996 [doi>10.1002/(SICI)1097-024X(199604)26:4<427::AID-SPE20>3.3.CO;2-8]
• 67: Goetz Graefe , David J. DeWitt, The EXODUS optimizer generator, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.160-172, May 27-29, 1987, San Francisco, California, United States
• 68: Goetz Graefe , William J. McKenna, The Volcano Optimizer Generator: Extensibility and Efficient Search, Proceedings of the Ninth International Conference on Data Engineering, p.209-218, April 19-23, 1993
• 69: G. Graefe , K. Ward, Dynamic query evaluation plans, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.358-366, June 1989, Portland, Oregon, United States
• 70: Luis Gravano , Chen-Chuan K. Chang , Héctor García-Molina , Andreas Paepcke, STARTS: Stanford proposal for Internet meta-searching, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.207-218, May 11-15, 1997, Tucson, Arizona, United States
• 71: Luis Gravano , Hector Garcia-Molina, Merging Ranks from Heterogeneous Internet Sources, Proceedings of the 23rd International Conference on Very Large Data Bases, p.196-205, August 25-29, 1997
• 72: Jim Gray , Adam Bosworth , Andrew Layman , Hamid Pirahesh, Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Total, Proceedings of the Twelfth International Conference on Data Engineering, p.152-159, February 26-March 01, 1996
• 73: Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 74: Ashish Gupta , Venky Harinarayan , Anand Rajaraman, Virtual database technology, ACM SIGMOD Record, v.26 n.4, p.57-61, Dec. 1997 [doi>10.1145/271074.271093]
• 75: GWERTZMAN,J.AND SELTZER, M. 1994. The Case for Geographical Push-Caching. Technical Report HU TR-34-94, Harvard University, Cambridge, MA.
• 76: L. M. Haas , J. C. Freytag , G. M. Lohman , H. Pirahesh, Extensible query processing in starburst, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.377-388, June 1989, Portland, Oregon, United States
• 77: Laura M. Haas , Donald Kossmann , Edward L. Wimmers , Jun Yang, Optimizing Queries Across Diverse Data Sources, Proceedings of the 23rd International Conference on Very Large Data Bases, p.276-285, August 25-29, 1997
• 78: Robert Brian Hagmann , Domenico Ferrari, Performance analysis of several back-end database architectures, ACM Transactions on Database Systems (TODS), v.11 n.1, p.1-26, March 1986 [doi>10.1145/5236.5242]
• 79: Graham Hamilton , Rick Cattell , Maydene Fisher, Jdbc Database Access with Java: A Tutorial and Annotated Reference, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 80: HARDER, T., MITSCHANG, B., NINK,U.,AND RITTER,N. 1995. Workstation/server-architekturen fur datenbankbasierte ingenieuranwendungen. Informatik-Forschung und Entwicklung 10,2 (May), 55-72.
• 81: Venky Harinarayan , Anand Rajaraman , Jeffrey D. Ullman, Implementing data cubes efficiently, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.205-216, June 04-06, 1996, Montreal, Quebec, Canada
• 82: Waqar Hasan , Rajeev Motwani, Coloring Away Communication in Parallel Query Optimization, Proceedings of the 21th International Conference on Very Large Data Bases, p.239-250, September 11-15, 1995
• 83: HONG,W.AND STONEBRAKER, M. 1990. Parallel Query Processing in XPRS. Technical report UCB/ERL M90/47 (May), Department of Industrial Engineering and Operations Research and School of Business Administration, University of California, Berkeley, CA.
• 84: IEEE Data Engineering Bulletin. 1998. Special issue on interoperability. IEEE Data Engineering Bulleting, 21, 3.
• 85: Yannis E. Ioannidis , Younkyung Cha Kang, Left-deep vs. bushy trees: an analysis of strategy spaces and its implications for query optimization, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.168-177, May 29-31, 1991, Denver, Colorado, United States
• 86: Yannis E. Ioannidis , Raymond T. Ng , Kyuseok Shim , Timos K. Sellis, Parametric Query Optimization, Proceedings of the 18th International Conference on Very Large Data Bases, p.103-114, August 23-27, 1992
• 87: Zachary G. Ives , Daniela Florescu , Marc Friedman , Alon Levy , Daniel S. Weld, An adaptive query execution system for data integration, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.299-310, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 88: 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
• 89: Navin Kabra , David J. DeWitt, Efficient mid-query re-optimization of sub-optimal query execution plans, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.106-117, June 01-04, 1998, Seattle, Washington, United States
• 90: Arthur M. Keller , Julie Basu, A predicate-based caching scheme for client-server database architectures, Proceedings of the third international conference on on Parallel and distributed information systems, p.229-238, October 1994, Autin, Texas, United States
• 91: Arthur M. Keller , Richard Jensen , Shailesh Agarwal, Persistence software: bridging object-oriented programming and relational databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.523-528, May 25-28, 1993, Washington, D.C., United States
• 92: Tom Keller , Goetz Graefe , David Maier, Efficient assembly for complex objects, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.148-157, May 29-31, 1991, Denver, Colorado, United States
• 93: Alfons Kemper , Donald Kossmann, Dual-Buffering Strategies in Object Bases, Proceedings of the 20th International Conference on Very Large Data Bases, p.427-438, September 12-15, 1994
• 94: Alfons Kemper , Donald Kossmann , Florian Matthes, SAP R/3 (tutorial): a database application system, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.499, June 01-04, 1998, Seattle, Washington, United States
• 95: W. Kim , J. F. Garza , N. Ballou , D. Woelk, Architecture of the ORION Next-Generation Database System, IEEE Transactions on Knowledge and Data Engineering, v.2 n.1, p.109-124, March 1990 [doi>10.1109/69.50909]
• 96: Ralph Kimball , Kevin Strehlo, Why decision support fails and how to fix it, ACM SIGMOD Record, v.24 n.3, p.92-97, Sept. 1995 [doi>10.1145/211990.212023]
• 97: Donald Kossmann , Michael J. Franklin , Gerhard Drasch , Wig Ag, Cache investment: integrating query optimization and distributed data placement, ACM Transactions on Database Systems (TODS), v.25 n.4, p.517-558, Dec. 2000 [doi>10.1145/377674.377677]
• 98: Donald Kossmann , Konrad Stocker, Iterative dynamic programming: a new class of query optimization algorithms, ACM Transactions on Database Systems (TODS), v.25 n.1, p.43-82, March 2000 [doi>10.1145/352958.352982]
• 99: Tirthankar Lahiri , Ashok Joshi , Amit Jasuja , Sumanta Chatterjee, 50,000 users on an Oracle8 universal server database, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.528-530, June 01-04, 1998, Seattle, Washington, United States
• 100: Rosana S. G. Lanzelotte , Patrick Valduriez , Mohamed Zaït, On the Effectiveness of Optimization Search Strategies for Parallel Execution Spaces, Proceedings of the 19th International Conference on Very Large Data Bases, p.493-504, August 24-27, 1993
• 101: LEVY, A. 1999. Answering Queries Using Views: A Survey. In preparation.
• 102: Alon Y. Levy , Anand Rajaraman , Joann J. Ordille, Querying Heterogeneous Information Sources Using Source Descriptions, Proceedings of the 22th International Conference on Very Large Data Bases, p.251-262, September 03-06, 1996
• 103: Guy M. Lohman, Grammar-like functional rules for representing query optimization alternatives, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.18-27, June 01-03, 1988, Chicago, Illinois, United States
• 104: David Lomet, Replicated indexes for distributed data, Proceedings of the fourth international conference on on Parallel and distributed information systems, p.108-119, December 18-20, 1996, Miami Beach, Florida, United States
• 105: LORIE,R.AND WADE, B. 1979. The Compilation of a High Level Data Language. Technical Report RJ 2598, IBM Research, San Jose, CA.
• 106: LU,H.AND CAREY, M. 1985. Some experimental results on distributed join algorithms in a local network. In Proceedings of the Conference on Very Large Data Bases (VLDB) (Stockholm, Sweden), 229-304.
• 107: LUOTONEN,A.AND ALTIS, K. 1994. World-Wide Web Proxies. Technical report (April), CERN, Geneva, Switzerland.
• 108: Lothar F. Mackert , Guy M. Lohman, R* Optimizer Validation and Performance Evaluation for Distributed Queries, Proceedings of the 12th International Conference on Very Large Data Bases, p.149-159, August 25-28, 1986
• 109: MAIER, D., GRAEFE, G., SHAPIRO, L., DANIELS, S., KELLER, T. , AND VANCE, B. 1994. Issues in distributed object assembly. In T. OZSU,U.DAYAL, AND P. VAL- DURIEZ EDS., Distributed Object Management (San Mateo, CA, May 1994), 165-181. Morgan Kaufmann Publishers. International Workshop on Distributed Object Management.
• 110: Jason McHugh , Jennifer Widom, Query Optimization for XML, Proceedings of the 25th International Conference on Very Large Data Bases, p.315-326, September 07-10, 1999
• 111: Jim Melton , Alan R. Simon, Understanding the new SQL: a complete guide, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 112: Priti Mishra , Margaret H. Eich, Join processing in relational databases, ACM Computing Surveys (CSUR), v.24 n.1, p.63-113, March 1992 [doi>10.1145/128762.128764]
• 113: Hubert Naacke , Georges Gardarin , Anthony Tomasic, Leveraging Mediator Cost Models with Heterogeneous Data Sources, Proceedings of the Fourteenth International Conference on Data Engineering, p.351-360, February 23-27, 1998
• 114: J. O''Toole , Shrira, L, Opportunistic Log: Efficient Installation Reads in a Reliable Object Server, Massachusetts Institute of Technology, Cambridge, MA, 1994
• 115: Fatma Ozcan , Sena Nural , Pinar Koksal , Cem Evrendilek , Asuman Dogac, Dynamic query optimization on a distributed object management platform, Proceedings of the fifth international conference on Information and knowledge management, p.117-124, November 12-16, 1996, Rockville, Maryland, United States [doi>10.1145/238355.238460]
• 116: OZCAN, F., NURAL, S., KOKSAL, P., EVRENDILEK,C.,AND DOGAC, A. 1997. Dynamic query optimization in multidatabases. IEEE Data Engineering Bulletin 20, 3 (Sept.), 38-45.
• 117: M. Tamer Özsu , Patrick Valduriez, Principles of distributed database systems (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1999
• 118: Yannis Papakonstantinou , Hector Garcia-Molina , Jennifer Widom, Object Exchange Across Heterogeneous Information Sources, Proceedings of the Eleventh International Conference on Data Engineering, p.251-260, March 06-10, 1995
• 119: Yannis Papakonstantinou , Ashish Gupta , Hector Garcia-Molina , Jeffrey D. Ullman, A Query Translation Scheme for Rapid Implementation of Wrappers, Proceedings of the Fourth International Conference on Deductive and Object-Oriented Databases, p.161-186, December 04-07, 1995
• 120: Yannis Papakonstantinou , Ashish Gupta , Laura Haas, Capabilities-based query rewriting in mediator systems, Proceedings of the fourth international conference on on Parallel and distributed information systems, p.170-183, December 18-20, 1996, Miami Beach, Florida, United States
• 121: Hamid Pirahesh , Joseph M. Hellerstein , Waqar Hasan, Extensible/rule based query rewrite optimization in Starburst, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.39-48, June 02-05, 1992, San Diego, California, United States
• 122: Dallan Quass , Jennifer Widom, On-line warehouse view maintenance, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.393-404, May 11-15, 1997, Tucson, Arizona, United States
• 123: Raghu Ramakrishnan, Database management systems, McGraw-Hill, Inc., New York, NY, 1997
• 124: RELLY, L., SCHULDT, H., AND SCHEK, H.-J. 1998. Exporting database functionality-the concert way. IEEE Data Engeneering Bulletin 21,3 (Sept.), 40-48.
• 125: Mary Tork Roth , Fatma Ozcan , Laura M. Haas, Cost Models DO Matter: Providing Cost Information for Diverse Data Sources in a Federated System, Proceedings of the 25th International Conference on Very Large Data Bases, p.599-610, September 07-10, 1999
• 126: Mary Tork Roth , Peter M. Schwarz, Don't Scrap It, Wrap It! A Wrapper Architecture for Legacy Data Sources, Proceedings of the 23rd International Conference on Very Large Data Bases, p.266-275, August 25-29, 1997
• 127: Nicholas Roussopoulos, An incremental access method for ViewCache: concept, algorithms, and cost analysis, ACM Transactions on Database Systems (TODS), v.16 n.3, p.535-563, Sept. 1991 [doi>10.1145/111197.111215]
• 128: ROUSSOPOULOS, N., CHEN, C., KELLEY, S., DELIS, A., AND PAPAKONSTANTINOU, Y. 1995. The adms project: views r us. IEEE Data Engeneering Bulletin 18,2 (June), 19-28.
• 129: Peter Scheuermann , Junho Shim , Radek Vingralek, WATCHMAN: A Data Warehouse Intelligent Cache Manager, Proceedings of the 22th International Conference on Very Large Data Bases, p.51-62, September 03-06, 1996
• 130: Donovan A. Schneider , David J. DeWitt, Tradeoffs in processing complex join queries via hashing in multiprocessor database machines, Proceedings of the sixteenth international conference on Very large databases, p.469-480, September 1990, Brisbane, Australia
• 131: 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]
• 132: Timos K. Sellis, Multiple-query optimization, ACM Transactions on Database Systems (TODS), v.13 n.1, p.23-52, March 1988 [doi>10.1145/42201.42203]
• 133: Ming-Chien Shan , Rafi Ahmed , Jim Davis , Weimin Du , William Kent, Pegasus: a heterogeneous information management system, Modern database systems: the object model, interoperability, and beyond, ACM Press/Addison-Wesley Publishing Co., New York, NY, 1995
• 134: 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
• 135: Amit P. Sheth , James A. Larson, Federated database systems for managing distributed, heterogeneous, and autonomous databases, ACM Computing Surveys (CSUR), v.22 n.3, p.183-236, Sept. 1990 [doi>10.1145/96602.96604]
• 136: Jeff Sidell , Paul M. Aoki , Adam Sah , Carl Staelin , Michael Stonebraker , Andrew Yu, Data Replication in Mariposa, Proceedings of the Twelfth International Conference on Data Engineering, p.485-494, February 26-March 01, 1996
• 137: Abraham Silberschatz , Henry F. Korth , S. Sudershan, Database System Concepts, McGraw-Hill, Inc., New York, NY, 1998
• 138: V. Srinivasan , Michael J. Carey, Compensation-based on-line query processing, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.331-340, June 02-05, 1992, San Diego, California, United States
• 139: Michael Steinbrunn , Guido Moerkotte , Alfons Kemper, Heuristic and randomized optimization for the join ordering problem, The VLDB Journal — The International Journal on Very Large Data Bases, v.6 n.3, p.191-208, August 1997 [doi>10.1007/s007780050040]
• 140: Konrad Stocker , Donald Kossmann , Reinhard Braumandl , Alfons Kemper, Integrating Semi-Join-Reducers into State of the Art Query Processors, Proceedings of the 17th International Conference on Data Engineering, p.575-584, April 02-06, 2001
• 141: STONEBRAKER, M. 1985. The design and implementation of distributed INGRES. Reading, MA. Addison-Wesley.
• 142: STONEBRAKER, M. 1986. The case for shared nothing. IEEE Data Engeneering Bulletin 9, 1 (March), 4-9.
• 143: Michael Stonebraker, Readings in database systems (2nd ed.), Morgan Kaufmann Publishers Inc., San Francisco, CA, 1994
• 144: Michael Stonebraker , Paul M. Aoki , Witold Litwin , Avi Pfeffer , Adam Sah , Jeff Sidell , Carl Staelin , Andrew Yu, Mariposa: a wide-area distributed database system, The VLDB Journal — The International Journal on Very Large Data Bases, v.5 n.1, p.048-063, January 1996 [doi>10.1007/s007780050015]
• 145: A. S. Tanenbaum, Computer networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 146: Andrew S. Tanenbaum, Modern operating systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 147: Joachim Thomas , T. Gerbes , Theo Härder , Bernhard Mitschang, Implementing Dynamic Code Assembly for Client-Based Query Processing, Proceedings of the 4th International Conference on Database Systems for Advanced Applications (DASFAA), p.264-272, April 11-13, 1995
• 148: Anthony Tomasic , Louiqa Raschid , Patrick Valduriez, Scaling Access to Heterogeneous Data Sources with DISCO, IEEE Transactions on Knowledge and Data Engineering, v.10 n.5, p.808-823, September 1998 [doi>10.1109/69.729736]
• 149: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 150: URHAN,T.AND FRANKLIN, M. 1999. Xjoin: Getting Fast Answers from Slow and Bursty Networks. Technical report CS-TR-3994 (Feb.), University of Maryland, College Park.
• 151: Tolga Urhan , Michael J. Franklin , Laurent Amsaleg, Cost-based query scrambling for initial delays, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.130-141, June 01-04, 1998, Seattle, Washington, United States
• 152: Patrick Valduriez , Georges Gardarin, Join and Semijoin Algorithms for a Multiprocessor Database Machine, ACM Transactions on Database Systems (TODS), v.9 n.1, p.133-161, March 1984 [doi>10.1145/348.318590]
• 153: Jennifer Widom, Research problems in data warehousing, Proceedings of the fourth international conference on Information and knowledge management, p.25-30, November 29-December 02, 1995, Baltimore, Maryland, United States [doi>10.1145/221270.221319]
• 154: Gio Wiederhold, Intelligent integration of information, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.434-437, May 25-28, 1993, Washington, D.C., United States
• 155: R. Williams , D. Daniels , L. Haas , G. Lapis , B. Lindsay , P. Ng , R. Obermarck , P. Selinger , A. Walker , P. Wilms , R. Yost, R: an overview of the architecture, Readings in database systems (2nd ed.), Morgan Kaufmann Publishers Inc., San Francisco, CA, 1994
• 156: Annita N. Wilschut , Peter M. G. Apers, Dataflow query execution in a parallel main-memory environment, Proceedings of the first international conference on Parallel and distributed information systems, p.68-77, December 1991, Miami, Florida, United States
• 157: Ouri Wolfson , Sushil Jajodia , Yixiu Huang, An adaptive data replication algorithm, ACM Transactions on Database Systems (TODS), v.22 n.2, p.255-314, June 1997 [doi>10.1145/249978.249982]
• 158: Jian Yang , Kamalakar Karlapalem , Qing Li, Algorithms for Materialized View Design in Data Warehousing Environment, Proceedings of the 23rd International Conference on Very Large Data Bases, p.136-145, August 25-29, 1997
• 159: C. T. Yu , C. C. Chang, Distributed query processing, ACM Computing Surveys (CSUR), v.16 n.4, p.399-433, Dec. 1984 [doi>10.1145/3872.3874]
• 160: Clement T. Yu , Weiyi Meng, Principles of database query processing for advanced applications, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 161: Markos Zaharioudakis , Michael J. Carey, Highly concurrent cache consistency for indices in client-server database systems, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.50-61, May 11-15, 1997, Tucson, Arizona, United States
• 162: Qiang Zhu , Per-Åke Larson, A Query Sampling Method of Estimating Local Cost Parameters in a Multidatabase System, Proceedings of the Tenth International Conference on Data Engineering, p.144-153, February 14-18, 1994

INDEX TERMS

Primary Classification:
  E. Data

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing; Distributed databases
      H.2.5 Heterogeneous Databases
          Subjects: Data translation**

General Terms:
Algorithms, Performance

Keywords:
caching, client-server databases, database application systems, dissemination-based information systems, economic models for query processing, middleware, multitier architectures, query execution, query optimization, replication, wrappers