Cached Queries in the Stack-Based Approach

• Autorzy: Cybula P. , Subieta K.
• Języki publikacji: EN

Abstrakty

EN

We present a new approach to optimization of ąuery languages using materialization of resułts previously answered ąueries. It is based on the stack-based approach (SBA) to object-oriented ąuery languages, which assumes the description of semantics in the form of abstract implementation of ąuery/programming language constructs. The semantics is expressed in terms of naming, scoping and binding. It involves an environmental stack - a basie mechanism of majority of programming languages. Novelty of our approach concerns methods and data structures proposed to realize the optimization method. The main properties of the structures as well as its essential problems arę outlined, particularly the problem of updating cached ąueries after changes of database content. In the report we present detailed description of our approach including all necessary information on the syntax, semantics, implementation and pragmatics of corresponding language constructs.

PL

Przedstawiamy nowe rozwiązanie optymalizacji języków zapytań z wykorzystaniem materializacji wyników wcześniej zrealizowanych zapytań. Rozwiązanie to bazuje na podejściu stosowym (SBA) do obiektowych języków zapytań wprowadzającym opis semantyki w formie abstrakcyjnej implementacji konstrukcji języka zapytań lub programowania. Semantyka ta jest wyrażana za pomocą trzech terminów: nazw, zakresu i wiązania. Wykorzystywany jest stos środowiskowy - podstawowy mechanizm większości języków programowania. Oryginalność naszego rozwiązania dotyczy metod i struktur danych proponowanych do realizacji wspomnianej metody optymalizacyjnej. Zostały opisane główne własności tych struktur danych, jak również istotne problemy, w szczególności problem aktualizacji zapamiętanych zapytań po zmianach zawartości bazy danych. W raporcie przedstawiamy szczegółowy opis naszego rozwiązania, w tym wszystkie niezbędne informacje dotyczące składni, semantyki, implementacji i pragmatyki odpowiednich konstrukcji językowych.

Słowa kluczowe

EN

query optimization; cached queries; object-orientedness; query language; stack-based approach

PL

optymalizacja zadań; zapamiętane zapytania; obiektowość; język zapytań; baza danych; podejście stosowe

• Wydawca: Instytut Podstaw Informatyki PAN
• Czasopismo: Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk
• Rocznik: 2005
• Tom: Nr 985
• Strony: 1--56
• Opis fizyczny: Bibliogr. 49 poz., rys.

Twórcy

autor

Cybula P.

• institute of Mathematics, University of Łódź, ul. Banacha 22, 90-238, Łódź, Poland

autor

Subieta K.

• Institute of Computer Science Polish Academy of Sciences, ul. Ordona 21, 01-237 Warszawa, Polska
• Polish-Japanese Institute of Information Technology, ul. Koszykowa 86, 02-008 Warsaw, Poland

• institute of Mathematics, University of Łódź ul. Banacha 22, 90-238 Łódź, Poland,

Bibliografia

• S. Adali, K.S. Candan, Y. Papakonstantinou, V.S. Subrahmanian. Query Caching and Optimization in Distributed Mediator Systems, Proc. of ACM S1GMOD, pp. 137-148, 1996
• M. Adiba. Derived Relations: A Unified Mechanism for Views, Snapshots and Distributed Data, Proc. of VLDB, 1981
• M. Adiba, B.G. l.indsay. Database Snapshots, Proc. of VLDB, pp. 86-91, 1980
• M.A. Ali, A.A.A. Fernandes, N.W. Paton. MOVIE: An Incremental Maintenance System for Materialized Object Views, Proc. of Data & Knowledge Engineering, Vol. 47, pp. 131-166, 2003
• J.A. Blakeley, P. Larson, W.M. Tompa. Efficiently Updating Materialized Views, Proc. of ACM SIGMOD, pp. 61-71, 1986
• S. Chaudhuri, R. Krishnamurthy, S. Potamianos, K. Shim. Optimizing Queries with Materialized Views, Proc. of Intl. Conf. on Data Engineering, pp. 190-200, 1995
• C.M. Chen, N. Roussopoulos. The Implementation and Performance Evaluation of the ADMS Query Optimizer: Integrating Query Result Caching and Matching, Proc. of Intl. Conf. On Extending Database Technology, 1994
• L. Chen, E.A. Rundensteiner. ACE-XQ: A CachE-ware XQuery Answering System, Proc. of WebDB. pp. 31-36, 2002
• R. Choenni, M.L. Kersten, J.F.P. van der Akker, A. Saad. On Multi-Query Optimizalion, National Research Institute for Mathematics and Computer Science, Report CS-R9638, Amsterdam, 1996
• D.Comer. The Ubiquitous B-Tree, Computing Surveys, Vol. 11, No. 2, pp. 121-137, 1979
• S. Dar, M.J. Franklin, B.T. Jonsson, D. Srivastava, M. Tan. Semantic Data Caching and Replacement, Proc. of VLDB, 1996
• S. Finkelstein. Common Expression Analysis in Database Applications, Proc. of ACM SIGMOD, pp. 235-245, 1982
• R. Goldman, J. Widom. DataGuides: Enabling Query Formulation and Optimization Semistructured Databases, Proc. of VLDB, pp. 436-445, 1997
• A. Gupta, J.A. Blakeley. Using Partial Information to Update Materialized Views, Information Systems 20 (8), pp. 641-662, 1995
• A. Gupta, I. Mumick. Maintenance of Materialized Views: Problems, Techniques, and Applications, IEEE Data Engineering Bulletin, Special Issue on Materialized Views and Data Warehousing, Vol. 18, No. 2, pp. 3-18, 1995
• E. N. Hanson. A Performance Analysis of View Materialization Strategies, Proc. of ACM SIGMOD, pp. 440-453, 1987
• J.M. Hellerstein, A. Pfeffer. The RD-Tree: An Index Structure for Sets, University of Wisconsin, Technical Report #1252, Madison, October 1994
• IBM DB2 Universal Database SQL Reference, Vol. 2, Version 8, 2002, http://www.ibm.com/software/data/db2/udb
• Faster Federated Queries with MQTs, DB2 Magazine, Vol. 8, No. 3, 2003, http://www.db2mag.com/db area/archives/2003/Q3
• C.S. Jensen, L. Mark, N. Roussopoulos, T. Sellis. Using Differential Techniques to Efficiently Support Transaction Time, VLDB Journal, Vol. 2, No. 1, pp. 75-111, 1993
• A. Kemper, G. Moerkotte. Access Support in Object Bases, Proc. of ACM SIGMOD, pp. 364-376, 1990
• D. Kossman, MJ. Franklin, G. Drasch. Cache Investment: Integrating Query Optimization and Distributed Data Placement, ACM Transactions on Database Systems, 1997
• D.E. Knuth. The Art of Computer Programming, Addison-Wesley Publishing Co., 1973
• P. Larson. H. Yang. Computing Queries from Derived Relations, Proc. of VLDB, pp. 259-269, 1985
• B. Lindsay, L. Haas, C. Mohan, H. Pirahesh, P. Wilms. A Snapshot Differential Refresh Algorithm, Proc. of ACM SIGMOD, pp. 53-60, 1986
• A. Labrinidis, N. Roussopoulos. Update Propagation Strategies for Improving the Quality of Data on the Web, Proc. of VLDB, 2001
• H. Mistry, P. Roy, S. Sudarshan, K. Ramamritham. Materialized View Selection and Maintenance Using Multi-Query Optimization, Proc. of ACM SIGMOD, pp. 307-318, 2001
• Oracle 9i Materialized Views, An Oracle White Paper, May 2001 Oracle 9i OLAP User's Guide, Release 2 (9.2.0.2), September 2002, http://www.oracle.com/database
• J. Plodzien. Optimization Methods in Object Query Languages. Ph.D. Thesis. Institute of Computer Science, Polish Academy of Sciences, 2000
• N. Roussopoulos. An Incremental Access Method for ViewCache: Concept, Algorithms and Cost Analysis, ACM Transactions on Database Systems, Vol. 16, No. 3, pp. 535-563, 1991
• N. Roussopoulos. Materialized Views and Data Warehouses, Proc. of KRDB Workshop, 1997
• [K.A. Ross, D. Srivastava, S. Sudarshan. Materialized Views
• Maintenance and Integrity Constraint Checking: Trading Space for Time, Proc. of ACM SIGMOD, pp. 447-458, 1996
• P. Roy, S. Seshadri, S. Sudarshan, S. Bhobe. Efficient and Extensible Algorithms for Multi Query Optimization, Proc. of ACM SIGMOD, 2000
• W. Rzeczkowski, K. Subieta. Stored Queries - a Data Organization for Query Optimization, Proc. of Data & Knowledge Engineering, Vol. 3, pp. 29-48, 1988
• 02M.L-Sayed, L. Wang, L. Ding, E.A. Rundensteiner. An Algebraic Approach for Incremental Maintenance of Materialized XQuery Views, Proc. of WIDM, 2002
• T.K. Sellis. Multiple-Query Optimization, ACM Transactions on Database Systems, Vol. 13, No. 1, pp. 23-52, 1988
• K.Shim, T. Sellis, D. Nau. Improvements on a Heuristic Algorithm for Multiple-Query Optimization, Proc. of Data & Knowledge Engineering, Vol. 12, pp. 197-222, 1994
• O. Shmueli, A. Itai. Maintenance of Views, Proc. of ACM SIGMOD, pp. 240-255, 1984
• K.Subieta. Semantics of Query Languages for Network Databases, ACM Transactions on Database Systems, Vol. 10, No. 3, pp. 347-394, 1985
• K.Subieta. Denotational Semantics of Query Languages, Information Systems, Vol. 12, No. 1, 1987
• K.Subieta. LOQIS: The Programming System Having Database Capabilities, Institute of Computer Science, Polish Academy of Sciences, Report 694, Warsaw, October 1990 (in Polish)
• K.Subieta. LOQIS: The Object-Oriented Database Programming System, Proceedings of the 1st Intl. East/West Database Workshop on Next Generation Information System Technology, Springer LNCS 504, pp. 403-421, 1991
• K.Subieta. Theory and practice of object query languages, Polish-Japanese Institute of Information Technology, 2004 (in Polish)
• K.Subieta, C. Beeri, F. Matthes, J.W. Schmidt. A Stack Based Approach to Query Languages, Proc. of 2nd Intl. East-West Database Workshop, Klagenfurt, Austria, September 1994, Springer Workshops in Computing, 1995
• K.Subieta, Y. Kambayashi, J. Leszczylowski. Procedures in Object-Oriented Query Languages, Proc. of VLDB, pp. 182--193, 1995
• K. Subieta, J. Karczewski. NETUL - an Integrated End User Interface for CODASYL Databases, Institute of Computer Science, Polish Academy of Sciences, Report 539, Warsaw, 1984
• K. Subieta, M. Missala, K. Anacki. The LOQIS System. Description and Programmer Manual, Institute of Computer Science, Polish Academy of Sciences, Report 695, Warsaw, November 1990
• K. Subieta, J. Plodzien. Object Views and Query Modification. In Databases and Information Systems (eds. J. Barzdins, A. Caplinskas), Kluwer Academic Publishers, 2001, 3-14
• K. Subieta, W. Rzeczkowski. Query Optimization by Stored Queries, Proc. Of VLDB, pp. 369-380, 1987
• S.N. Subramanian, S. Venkataraman. Cost-Based Optimization of Decision Support Queries Using Transient-Vicws, Proc. of ACM SIGMOD, pp. 319-330, 1998