A magic approach to optimizing incremental relational expressions

ABSTRACT

This paper is concerned with a transformation-based approach to update propagation in an extended version of Codd's relational algebra which allows for defining derived relations (even recursively). It is shown that the desired optimization effects of update propagation may be lost if no generalized selection pushing strategy is employed to the transformed algebra expressions. A possible solution is the application of the Magic Sets rewriting but this may lead to unstratifiability of the incremental expressions. For the efficient evaluation of Magic Sets transformed algebra expressions we propose to use the soft stratification approach because of the simplicity and efficiency of this technique.

REFERENCES

• 1: Krzysztof R. Apt, Howard A. Blair, and Adrian Walker. Towards a theory of declarative knowledge. Foundations of Deductive Databases and Logic Programs, pages 89--148, M. Kaufmann, 1988.
• 2: Agrawal R. Alpha: An Extension of Relational Algebra to Express a Class of Recursive Queries. IEEE TSE 14(7): 879--885 (1988).
• 3: I. Balbin, G. S. Port, K. Ramamohanarao, and K. Meenakshi. Efficient bottom-up computation of queries. JLP, 11(3&4): 295--344, October 1991.
• 4: Bancilhon, F., Maier, D., Sagiv, Y., Ullman, J. D.: Magic Sets and Other Strange Ways to Implement Logic Programs. PODS 1986: 1--16.
• 5: E. Baralis and J. Widom. A rewriting technique for using delta relations to improve condition evaluation in active databases. Technical Report CS-93-1495, Stanford University, November 1993.
• 6: Andreas Behrend. Soft stratification for magic set based query evaluation in deductive databases. PODS 2003, New York, June 9--12, pages 102--110.
• 7: A. Behrend, C. Dorau, R. Manthey, and G. Schüller: Incremental View-Based Analysis of Stock Market Data Streams. IDEAS, 2008: 269--275.
• 8: A. Behrend and R. Manthey: Update Propagation in Deductive Databases Using Soft Stratification. ADBIS 2004: 22--36.
• 9: Colby, L. S., Griffin, T., Libkin, L., Mumick, I. S., and Trickey, H. Algorithms for Deferred View Maintenance. SIGMOD 1996: 469--480.
• 10: Colby, L. S., Kawaguchi, A., Lieuwen, D. F., Mumick, I. S., and Ross, K. A. Supporting Multiple View Maintenance Policies. SIGMOD 1997: 405--416.
• 11: Stefano Ceri and Jennifer Widom. Deriving production rules for incremental view maintenance. VLDB 1991, September 3--6, pages 577--589.
• 12: Dong, G. and Su, J. Incremental Maintenance of Recursive Views Using Relational Calculus/SQL. SIGMOD Record 29(1): 44--51, (2000).
• 13: Thanaa M. Ghanem et al. Incremental Evaluation of Sliding-Window Queries over Data Streams. IEEE TKDE, Volumne 19(1): 57--72, 2007.
• 14: Ulrike Griefahn. Reactive Model Computation--A Uniform Approach to the Implementation of Deductive Databases. PhD Thesis, University of Bonn, 1997.
• 15: Timothy Griffin and Leonid Libkin. Incremental maintenance of views with duplicates. SIGMOD 1995, May 23--25, 1995, San Jose, pages 328--339.
• 16: Ashish Gupta and Inderpal Singh Mumick Magic-Sets Transformation in Non-Recursive Systems. PODS 1992, 354--367.
• 17: Ashish Gupta, Inderpal Singh Mumick, and V. S. Subrahmanian. Maintaining views incrementally. SIGMOD 1993, volume 22(2), pages 157--166.
• 18: Volker Küchenhoff. On the efficient computation of the difference between consecutive database states. DOOD 1991, pages 478--502.
• 19: Koenig S., Paige R. A Transformational Framework for the Automatic Control of Derived Data. VLDB 1981: 306--318.
• 20: Rainer Manthey. Beyond Data Dictionaries: Towards a Reflective Architecture of Intelligent Database Systems. DOOD 1993: 328--339.
• 21: Rainer Manthey. Reflections on some fundamental issues of rule-based incremental update propagation. DAISD 1994: 255--276, September 19--21, Universitat Politècnica de Catalunya.
• 22: Bern Martens and Maurice Bruynooghe. Integrity constraint checking in deductive databases using a rule/goal graph. EDS 1988, pages 567--601.
• 23: I. S. Mumick and S. J. Finkelstein and Hamid Pirahesh and Raghu Ramakrishnan. Magic is relevant. SIGMOD Record 19(2): 247--258, 1990.
• 24: I. S. Mumick and H. Pirahesh. Implementation of Magic-sets in a Relational Database System. SIGMOD Conference 1994: 103--114
• 25: Antoni Olivé. Integrity constraints checking in deductive databases. VLDB 1991, pages 513--523.
• 26: X. Qian and G. Wiederhold. Incremental Recomputation of Active Relational Expressions. IEEE TKDE 3: 337--341 (1991).
• 27: Salem, K., Beyer, K., Lindsay, B., and Cochrane, R. How To Roll a Join: Asynchronous Incremental View Maintenance. SIGMOD 2000: 129--140.
• 28: S. Subramanian et al. Continuous Queries in Oracle. VLDB 2007, pages 1173--1184.
• 29: F. Sadri and R. A. Kowalski. A theorem proving approach to database integrity. Foundations of Deductive Databases and Logic Programs, pages 313--362, M. Kaufmann, 1988.
• 30: Martin Sköld and Tore Risch. Using Partial Differencing for Efficient Monitoring of Deferred Complex Rule Conditions. ICDE 1996: 392--401.
• 31: Toni Urpí and Antoni Olivé. A method for change computation in deductive databases. VLDB 1992, August 23--27, Vancouver, pages 225--237.
• 32: Allen van Gelder. The alternating fixpoint of logic programs with negation. Journal of Computer and System Sciences, 47(1):185--221, August 1993.
• 33: van Emden, M. H., Kowalski, R.: The Semantics of Predicate Logic as Programming Language. Journal of ACM 23(4): 733--743 (1976).

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases

General Terms:
Design, Performance

Keywords:
deductive databases, incremental evaluation, relational algebra, update propagation