Recursive Query Processing in SBQL

• Autorzy: Pieciukiewicz T. , Subieta K.
• Języki publikacji: EN

Abstrakty

EN

Recursive queries arę reąuired for many tasks of database applications. Among them we can mention Bill-Of-Material (BOM), various kinds of networks (transportation, telecommunication, etc.), processing semi-structured data (XML, RDF), and so on. The support for recursive queries in current query languages is limited and lacks of theoretical foundations. In particular, this concerns corresponding extensions of SQL in Oracle and DB2 systems. In this report we present recursive query processing capabilities for the object-oriented Stack-Based Query Language (SBQL) and compare them with similar capabilities in yariants of SQL. SBQL offers very powerful and flexible recursive querying capabilities due to the fact that recursive processing operators arę fully orthogonal to other features of this language. This report specifies corresponding SBQL constructs, such as transitive closures and fixed point equations. We compare them to other query languages, in particular to Datalog. We also present briefly optimization possibilities for recursive queries.

PL

Rekurencyjne zapytania są wymagane dla wielu zadań występujących w rzeczywistych aplikacjach baz danych. Wśród nich możemy wymienić rachunek materiałów (BOM), różne typy sieci (transportowa, telekomunikacyjna, itp.), przetwarzanie danych półstrukturalnych (XML, RDF) itd. Wspomaganie dla rekurencyjnych zapytań w obecnych językach zapytań jest ograniczone i pozbawione podstaw teoretycznych. W szczególności, dotyczy to odpowiednich rozszerzeń SQL w systemach Oracle i DB2. W raporcie przedstawiamy możliwości w zakresie rekurencyjnych zapytań w języku zorientowanym obiektowo Stack-Based Query Language (SBQL) i porównujemy je do podobnych możliwości w wariantach SQL. SBQL oferuje bardzo mocne i elastyczne możliwości w zakresie rekurencyjnych zapytań dzięki temu, że operatory służące do przetwarzania rekurencyjnego są całkowicie ortogonalne w stosunku do innych cech języka. Raport specyfikuje odpowiednie konstrukcje SBQL, takie jak tranzytywne domknięcia oraz równania stałopunktowe. Porównujemy je do innych języków zapytań, w szczególności do Datalogu. Na zakończenie prezentujemy krótko możliwości optymalizacji zapytań rekurencyjnych.

Słowa kluczowe

EN

Stack-Based Approach (SBA); query languages; SBQL; object-orientedness; transitive closures; fixed point equations; deductive rules; recursive functions; recursive views

PL

podejście stosowe; SBA; języki zapytań; SBQL; obiektowość; tranzytywne domknięcia; równania stałopunktowe; reguły dedukcyjne; rekurencyjne funkcje; rekurencyjne perspektywy

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

Twórcy

autor

Pieciukiewicz T.

• Polish-Japanese Institute of Information Technology ul.Koszykowa 86, 02-008 Warszawa, Poland

autor

Subieta K.

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

Bibliografia

• S.Abiteboul, R.Hull, V.Vianu. Foundations of Databases, ch. 12, Addison-Wesley (1995)
• A.V.Aho, J.D.UIlman: The Universality of Data Retrieval Languages, Conference Record of the Sixth Annual ACM Symposium on Principles of Programming Languages: 110-120, ACM (1979)
• M.P. Atkinson, P.Buneman. Types and Persistence in Database Programming Languages. ACM Computing Surveys 19(2): 105-190, ACM (1987)
• F.Bancilhon: On the Completeness of Query Languages for Relational Data Bases. Lecture Notes in Computer Science 64: 112- 123, Springer (1978)
• S.Ceri, G.Gottlob, L.Tanca. What You Always Wanted to Know About Datalog (And Never Dared to Ask). IEEE Transactions on Knowledge and Data Engineering 1(1): 146-167, IEEE Computer Society (1989)
• F.Fotouhi, A.Johnson, S.P.Rana. A hash-based approach for computing the transitive closure of database relations, The Computer Journal vol. 35 no. 3: A251—A259, Oxford University Press (1992)
• H.Gallaire, J.Minker, J.-M.Nicolas: Logic and Databases: A Deductive Approach. ACM Comput. Surv. 16(2): 153-185, ACM (1984)
• H.Kozankiewicz, J.Leszczyłowski, J.Płodzień, K.Subieta. Updateable Object Views. Institute of Computer Science, Polish Academy of Sciences, Report 950, Warsaw, Poland (2002)
• H.Kozankiewicz, J.Leszczyłowski, K.Subieta. Updateable XML Views. Proc. of Advances in Databases and Information Systems (ADBIS), , Lecture Notes in Computer Science 2798: 385-399, Springer (2003)
• H.Kozankiewicz, J.Leszczyłowski, K.Subieta. Implementing Mediators through Virtual Updateable Views. Proc. of the 5th International Workshop on Engineering Federated Information Systems (EFIS): 52-62, IOS Press, Coventry, UK (2003)
• H.Kozankiewicz, K.Subieta. SBQL Views -Prototype of Updateable Views. Proc. 8th East-European Conference on Advances in Databases and Information Systems (ADBIS), September 2004, Budapest, Hungary, to appear
• PL/SQL User's Guide and Reference (9.2), Oracle, available online: http://www.oracle.com/pls/db92/db92.docindex
• J.Płodzień, K.Subieta. Optimization of Object-Oriented Queries by Factoring Out Independent Subqueries. Institute of Computer Science Polish Academy of Sciences, Report 889, November 1999
• J.Płodzień, A.Kraken. Object Query Optimization through Detecting Independent Subqueries. Information Systems, Pergamon Press, September 2000.
• J.Płodzień. Optimization Methods in Object Query Languages. Ph.D. Thesis. Institute of Computer Science, Polish Academy of Sciences (2000), available via http://www.ipipan.waw.pl/~jpl
• J.Płodzień, K.Subieta. Applying Low-Level Query Optimization Techniques by Rewriting, Proc. DEXA Conf., Lecture Notes in Computer Science 2113: 867-876, Springer (2001)
• J.Płodzień, K.Subieta. Static Analysis of Queries as aTool for Static Optimization, Proceedings of IDEAS Conference: 117-122, IEEE Computer Society (2001)
• K.Subieta . Semantics of Query Languages for Network Databases, ACM Transactions on Database Systems, Vol. 10, No. 3: 347-394, ACM (1985)
• K.Subieta. Denotational Semantics of Query Languages, Information Systems, Vol. 12, No. 1 (1987)
• 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. LOQIS: The Object-Oriented Database Programming System, Proceedings of the 1st Intl. East/West Database Workshop on Next Generation Information System Technology, Lecture Notes in Computer Science 504: 403-421, Springer (1991)
• K.Subieta, J.Płodzień Object Views and Query Modification, Databases and Information Systems: 3-14, Kluwer Academic Publishers, (2001)
• K.Subieta, C.Beeri, F.Matthes, J.W.Schmidt. A Stack-Based Approach to Query Languages. Proc. East-West Database Workshop, 1994, Springer Workshops in Computing (1995)
• K.Subieta, Y.Kambayashi, and J.Leszczyłowski. Procedures in Object-Oriented Query Languages. Proc. VLDB Conf., 182-193, Morgan Kaufmann (1995)
• K.Subieta. Theory and Construction of Object-Oriented Query Languages. Editors of Polish-Japanese Institute of Information Technology, Warsaw 2004, 522 pages, (in Polish)
• S.Taylor, N.I.Hachem, A Direct Algorithm for Computing the Transitive Closure of a Two-Dimensionally Structured File, Lccture Notes in Computer Science 495: 146-159, Springer (1991)
• J.D.Ullman. Principles of Database and Knowledge-Base Systems, volume II, ch. 13, W H Freeman, 1990
• J.D.Ullman. J.Widom. A First Course in Database Systems, ch.5, Prentice Hall, 1997
• XQuery 1.0: An XML Query Language, http://www.w3.org/TR/xquery/, working draft
• XML Query Use Cases, http://www.w3.org/TR/xquery-use-cases/, working draft
• W.Yan, N.M.Mattos. Transitive Closure and the {LOGA} + - Strategy for its Efficient Evaluation, Mathematical Fundamentals of Database Systems, Lecture Notes in Computer Science 364: 415- 428, Springer (1989)
• P.R. Falcone Sampaio, N.W. Paton Deductive Object-Oriented Database Systems: A Survey, LNCS: Proceedings of the Third International Workshop on Rules in Database Systems: 1-19, Springer-Verlag (1997)
• Z. Li, K. A. Ross, On the Cost of Transitive Closures in Relational Databases, Columbia University Technical Report CUCS-004-93, April, 1993
• G. Dong, L. Libkin, L. Wong, Properties of Languages That Make Recursive Views Unmaintainable, available online: http ://ci teseer. ist.psu .edu/4739.htm 1
• G. Dong, L. Libkin, J. Su, L. Wong, Maintaining transitive closure of graphs in SQL, Int. Journal of Information Technology, Singapore Computer Society (1999)
• L. Libkin and L. Wong, Incremental recomputation of recursive queries with nested sets and aggregate functions. LNCS 1369: Proceedings of 6th International Workshop on Database Programming Languages: 222-238 Springer Verlag (1997)
• N. Immerman, Relational Queries Computable in Polynominal Time, ACM Symposium on Theory of Computing: 147-152. ACM (1982)
• P. R. F. Sampaio, N. W. Paton, Deductive Queries in ODMG Databases: the DOQL Approach, Proceedings of the 5th Internationa] Conference on Object-Oriented Information Systems (OOIS: 57-74, Springer-Verlag (1998)
• M. Dobrovnik, R. T. Mittermeir, Architectural Considerations for Extending a Relational DBMS with Deductive Capabilities, Proceedings of SPSF. '92, Springer Verlag (1992)
• J. Han, L. V. S. Lakshmanan, Evaluation of Regular Nonlinear Recursion by Deductive Database Techniques, Information Systems 20, Pergamon Press (1995)
• D. B. Kemp, D. Srivastava, P. J. Stuckey, Bottom-up Evaluation and Query Optimization of Well-Founded Models, Theoretical Computer Science 146: 145-184, Elsevier Science Publishers. (1995).
• J. Lu, L. Chen, K. Symara, J. Lu, Recursive Query Rewriting by Transforming Logic Program, International Workshops on Logic- based Program Synthesis and Transformation, Manchester, United Kingdom, June 1998.
• S. Abiteboul, M. Y. Vardi, V. Vianu, Fixpoint Logics, Relational Machines and Computational Complexity, Journal of ACM, ACM (1997)
• J. Freire, Practical Problems in Coupling Deductive Engines with Relational Databases, Proceedings of the 5th KRDB Workshop, Seattle 1998, Swiss Life, Information Systems Research, Report 18, Zurich 1998
• O. M. Duschka, M. R. Genesereth, Answering Recursive Queries Using Views, Proceedings of the 16th ACM SIGACT-SIGMOD- SIGART Conference on Principles of Database Systems: 109-116, ACM Press (1997)
• F. N. Afrati, M. Gergatsoulis, T. Kavalieros, Answering Queries Using Materialized Views with Disjunctions, Lecture Notes in Computer Science 1540: 435-452, Springer (1999)
• B. Nag, Implementing Generalized Transitive Closure in the Paradise Geographical Information System, available online: http://citeseer.ist.psu.edu/nag95implementing.html
• H. He, Implementation of Nested Relations in a Database Programming Language, available online: http://www.cs.mcgill.ca/~tim/cv/students.html
• B. Hao, Implementation of The Nested Relational Algebra in Java, available online: http://www.cs.mcgill.ca/~tim/cv/students.html
• G. Z. Qadah, L. J. Henschen, J. J. Kim, Efficient Algorithms for the Instantiated Transitive Closure Queries, IEEE Transactions on Software Engineering archive, Volume 17 , Issue 3, 1991
• R. Agrawal, S. Dar, H. V. Jagadish: Direct Transitive Closure Algorithms: Design and Performance Evaluation, ACM Trans. Database Syst. 15(3): 427-458 (1990)