Query caching and optimization in distributed mediator systems

ABSTRACT

Query processing and optimization in mediator systems that access distributed non-proprietary sources pose many novel problems. Cost-based query optimization is hard because the mediator does not have access to source statistics information and furthermore it may not be easy to model the source's performance. At the same time, querying remote sources may be very expensive because of high connection overhead, long computation time, financial charges, and temporary unavailability. We propose a cost-based optimization technique that caches statistics of actual calls to the sources and consequently estimates the cost of the possible execution plans based on the statistics cache. We investigate issues pertaining to the design of the statistics cache and experimentally analyze various tradeoffs. We also present a query result caching mechanism that allows us to effectively use results of prior queries when the source is not readily available. We employ the novel invariants mechanism, which shows how semantic information about data sources may be used to discover cached query results of interest.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Serge Abiteboul , Anthony Bonner, Objects and views, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.238-247, May 29-31, 1991, Denver, Colorado, United States
	2	Serge Abiteboul , Sophie Cluet , Tova Milo, Querying and Updating the File, Proceedings of the 19th International Conference on Very Large Data Bases, p.73-84, August 24-27, 1993
	3	Sibel Adali , K. Selçuk Candan , Su-Shing Chen , Kutluhan Erol , V. S. Subrahmanian, The advanced video information system: data structures and query processing, Multimedia Systems, v.4 n.4, p.172-186, Aug. 1996 [doi>10.1007/s005300050021]
	4	[4] S. Adah and V.S. Subrahmanian. (1994) Amalgamating Knowledge Bases, III: Algorithms, data structures and query processing. Technical Report CS-TR-3124, Computer Science Department, University of Maryland, Aug. 1993. Accepted for publication in Journal of Logic Programming. (http://www.cs.umd.edu/projects/hermes/publications/abstracts/akbiii.ps)
	5	Sibel Adali , Ross Emery, A Uniform Framework for Integrating Knowledge in Heterogeneous Knowledge Systems, Proceedings of the Eleventh International Conference on Data Engineering, p.513-520, March 06-10, 1995
	6	[6] S. Adah and V.S. Subrahmanian. (1995) Intelligent Caching in Heterogeneous Reasoning and Mediator Systems, Proc. of the Second International Conference on Building and Sharing of Very Large-Scale Knowledge Bases (cd. N. Mars), pps 247-256, IOS Press, Twente, The Netherlands, May 1995.
	7	José A. Blakeley , Neil Coburn , Per-:1Vke Larson, Updating derived relations: detecting irrelevant and autonomously computable updates, ACM Transactions on Database Systems (TODS), v.14 n.3, p.369-400, Sept. 1989 [doi>10.1145/68012.68015]
	8	Stefano Ceri , Jennifer Widom, Deriving Production Rules for Incremental View Maintenance, Proceedings of the 17th International Conference on Very Large Data Bases, p.577-589, September 03-06, 1991
	9	Umeshwar Dayal, Queries and views in an object-oriented data model, Proceedings of the second international workshop on Database programming languages, p.80-102, December 1989, Salishan Lodge, Gleneden Beach, Oregon, United States
	10	[10] U. Dayal and H. Hwang. (1984) View definition and generalization for database integration in a multidatabase system., IEEE Trans. Software Eng., SE- 10(6):628-644, 1984.
	11	Narain H. Gehani , H. V. Jagadish , William D. Roome, OdeFS: A File System Interface to an Object-Oriented Database, Proceedings of the 20th International Conference on Very Large Data Bases, p.249-260, September 12-15, 1994
	12	[12] Ashish Gupta, Dinesh Katiyar, and Inderpal Singh Mumick. (1992) Counting Solutions to the View Maintenance Problem., In Workshop on Deductive Databases, JICSLP, 1992.
	13	Ashish Gupta , Inderpal Singh Mumick , V. S. Subrahmanian, Maintaining views incrementally, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.157-166, May 25-28, 1993, Washington, D.C., United States
	14	Eric N. Hanson, A performance analysis of view materialization strategies, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.440-453, May 27-29, 1987, San Francisco, California, United States
	15	A. Kemper , C. Kilger , G. Moerkotte, Function Materialization in Object Bases: Design, Realization, and Evaluation, IEEE Transactions on Knowledge and Data Engineering, v.6 n.4, p.587-608, August 1994 [doi>10.1109/69.298175]
	16	[16] Laks V.S. Lakshmanan, F. Sadri amd I.N. Subramanian. (1993) On the logical foundations of schema integration and evolution in Heterogeneous Database Systems. , Proc. DOOD-93, Phoenix, Arizona.
	17	[17] Laks V.S. Lakshmanan, F. Sadri and I.N. Subramanian. (1995) Logic and Algebraic Languages for Interoperability in Multidatabase Systems, submitted to Journal of Logic Programming.
	18	Sonia M. Leach , James J. Lu, Computing annotated logic programs, Proceedings of the eleventh international conference on Logic programming, p.257-271, August 1994
	19	James J. Lu , Guido Moerkotte , Joachim Schue , V. S. Subrahmanian, Efficient maintenance of materialized mediated views, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.340-351, May 22-25, 1995, San Jose, California, United States
	20	James J. Lu , Anil Nerode , V. s. Subrahmanian, Hybrid Knowledge Bases, IEEE Transactions on Knowledge and Data Engineering, v.8 n.5, p.773-785, October 1996 [doi>10.1109/69.542029]
	21	A. Motro, Superviews: Virtual Integration of Multiple Databases, IEEE Transactions on Software Engineering, v.13 n.7, p.785-798, July 1987 [doi>10.1109/TSE.1987.233490]
	22	Inderpal Singh Mumick, Query optimization in deductive and relational databases, Stanford University, Stanford, CA, 1992
	23	[23] M. Scholl, C. Laasch, and M. Tresch. (1991) Updatable views in object-oriented databases., In Proc. Int. Conf. on Deductive and Object-Oriented Databases (DOOD), 1991.
	24	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]
	25	Oded Shmueli , Alon Itai, Maintenance of views, ACM SIGMOD Record, v.14 n.2, June 1984
	26	Michael Stonebraker , Anant Jhingran , Jeffrey Goh , Spyros Potamianos, On rules, procedure, caching and views in data base systems, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.281-290, May 23-26, 1990, Atlantic City, New Jersey, United States
	27	V. S. Subrahmanian, Amalgamating knowledge bases, ACM Transactions on Database Systems (TODS), v.19 n.2, p.291-331, June 1994 [doi>10.1145/176567.176571]
	28	[28] V.S. Subrahmanian, S. Adah, A. Brink, R. Emery, J. Lu, A. Rajput, T.J. Rogers, R. Ross. (1994) HERMES: A Heterogeneous Reasoning and Mediator System, submitted for publication. (http://www.cs.umd.edu/projects/hermes/ overview/paper)
	29	Gio Wiederhold, Mediators in the Architecture of Future Information Systems, Computer, v.25 n.3, p.38-49, March 1992 [doi>10.1109/2.121508]
	30	[30] G. Wiederhold, S. Jajodia, and W. Litwin. (1993) Integrating temporal data in a heterogeneous environment. , In Temporal Databases Benjamin/Cummings, Jan. 1993.
	31	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]
	32	D. Chimenti , R. Gamboa , R. Krishnamurthy, Towards an open architecture for LDL, Proceedings of the 15th international conference on Very large data bases, p.195-203, July 1989, Amsterdam, The Netherlands
	33	Surajit Chaudhuri , Kyuseok Shim, Query Optimization in the Presence of Foreign Functions, Proceedings of the 19th International Conference on Very Large Data Bases, p.529-542, August 24-27, 1993
	34	Surajit Chaudhuri , Ravi Krishnamurthy , Spyros Potamianos , Kyuseok Shim, Optimizing Queries with Materialized Views, Proceedings of the Eleventh International Conference on Data Engineering, p.190-200, March 06-10, 1995
	35	Jeffrey D. Ullman, Principles of Database and Knowledge-Base Systems: Volume II: The New Technologies, W. H. Freeman & Co., New York, NY, 1990
	36	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
	37	Hisao Tamaki , Taisuke Sato, OLD resolution with tabulation, Proceedings on Third international conference on logic programming, p.84-98, September 1986, London, United Kingdom
	38	David S. Warren, Memoing for logic programs, Communications of the ACM, v.35 n.3, p.93-111, March 1992 [doi>10.1145/131295.131299]
	39	Xiaolei Qian, Query Folding, Proceedings of the Twelfth International Conference on Data Engineering, p.48-55, February 26-March 01, 1996
	40	[40] S. Adah and X. Qian. (1995) Query Transformation in Heterogeneous Reasoning Systems., Submitted for publication.
	41	[41] S. Chawathe, H. Garcia-Molina, J. Hammer, K. Ireland, Y. Papakonstantinou, J. Ullman, and J. Widom. (1994) The TSIMMIS Project: Integration of Heterogeneous Information Sources., In Proceedings of IPSJ Conference, Tokyo, Japan, October 1994. (Also available via anonymous FTP from host db.stanford.edu, file/pub/chawathe/1994/tsimmis-overview.ps.)
	42	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
	43	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
	44	[44] H. Lu and B.-C. Ooi and C.-H. Goh. (1993) Multidatabase Query Optimization: Issues and Solutions., Proc. RIDE-IMS '93, pp. 137-143, 1993.