A framework for implementing hypothetical queries

ABSTRACT

Previous approaches to supporting hypothetical queries have been “eager”: some representation of the hypothetical state (or the corresponding delta) is materialized, and query evaluation is filtered through that representation. This paper develops a framework for evaluating hypothetical queries using a “lazy” approach, or using a hybrid of eager and lazy approaches. We focus on queries having the form “Q when {{U}}” where Q is a relational algebra query and U is an update expression. The value assigned to this query in state DB is the value that Q would return in the state resulting from executing U on DB. Nesting of the keyword when is permitted, and U may involve a sequence of several atomic updates. We present an equational theory for queries involving when that can be used as a basis for optimization. This theory is very different from traditional rules for the relational algebra, because the semantics of when is unlike the semantics of the algebra operators. Our theory is based on the observation that hypothetical states can be represented as substitutions, similar to those arising in functional and logic programming. Furthermore, hypothetical queries of the form Q when {{U}} can be thought of as representing the suspended application of a substitution. Using the equational theory we develop an approach to optimizing the evaluation of hypothetical queries that uses deltas in the sense of Heraclitus, and permits a range of evaluation strategies from lazy to eager.

REFERENCES

• ACCL91: M. Abadi, L. Cardelli, P. Curien, and J. Levy. Explicit substitutions. Journal of Functional Programming, 1(4):375-416, 1991.
• BGL96: Michael Benedikt , Timothy Griffin , Leonid Libkin, Verifiable properties of database transactions, Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.117-127, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237692]
• Bon90: Anthony J. Bonner, Hypothetical datalog: complexity and expressibility, Theoretical Computer Science, v.76 n.1, p.3-51, Oct. 31, 1990 [doi>10.1016/0304-3975(90)90011-6]
• Bon95: A.J. Bonner. The logical semantics of hypothetical rulebases with deletion. Journal of Logic Programming, 1995.
• DHK95: Gilles Dowek , Therese Hardin , Claude Kirchner, Higher-order Unification via Explicit Substitutions, Proceedings of the 10th Annual IEEE Symposium on Logic in Computer Science, p.366, June 26-29, 1995
• DHR96: Michael Doherty , Richard Hull , Mohammed Rupawalla, Structures for manipulating proposed updates in object-oriented databases, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.306-317, June 04-06, 1996, Montreal, Quebec, Canada
• Dij75: Edsger W. Dijkstra, Guarded commands, nondeterminacy and formal derivation of programs, Communications of the ACM, v.18 n.8, p.453-457, Aug. 1975 [doi>10.1145/360933.360975]
• Dij76: Edsger Wybe Dijkstra, A Discipline of Programming, Prentice Hall PTR, Upper Saddle River, NJ, 1997
• GD87: 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
• GH97: T. Griffin and R. Hull. A framework for implementing hypothetical queries. Technical report, Bell Laboratories, Lucent Technologies, 1997. In preparation.
• GHJ+93: Shahram Ghandeharizadeh , Richard Hull , Dean Jacobs , Jaime Castillo , Martha Escobar-Molano , Shih-Hui Lu , Junhui Luo , Chiu Tsang , Gang Zhou, On Implementing a Language for Specifying Active Database Execution Models, Proceedings of the 19th International Conference on Very Large Data Bases, p.441-454, August 24-27, 1993
• GHJ96: Shahram Ghandeharizadeh , Richard Hull , Dean Jacobs, Heraclitus: elevating deltas to be first-class citizens in a database programming language, ACM Transactions on Database Systems (TODS), v.21 n.3, p.370-426, Sept. 1996 [doi>10.1145/232753.232801]
• GR84: D.M. Gabbay and U. Reyle. N-Prolog: An extension of prolog with hypothetical implications. I. Journal of Logic Programming, 1(4):319-355, 1984.
• GR85: D.M. Gabbay and U. Reyle. N-Prolog: An extension of prolog with hypothetical implications. II: Logical foundations and negation as failure. Journal of Logic Programming, 2(4):251- 283, 1985.
• Gra93: 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]
• Gri81: David Gries, The Science of Programming, Springer-Verlag New York, Inc., Secaucus, NJ, 1987
• HR92: Susan Horwitz , Thomas Reps, The use of program dependence graphs in software engineering, Proceedings of the 14th international conference on Software engineering, p.392-411, May 11-15, 1992, Melbourne, Australia [doi>10.1145/143062.143156]
• HS86: J. Roger Hindley , Jonathan P. Seldin, Introduction to combinators and &lgr;-calculus, Cambridge University Press, New York, NY, 1986
• Les94: Pierre Lescanne, From λσ to λν: a journey through calculi of explicit substitutions, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.60-69, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.174707]
• Llo87: J. W. Lloyd, Foundations of logic programming; (2nd extended ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• Qia90: X. Qian, An axiom system for database transactions, Information Processing Letters, v.36 n.4, p.183-189, Nov. 1990 [doi>10.1016/0020-0190(90)90070-E]
• Qia91: Xiaolei Qian, The expressive power of the bounded-iteration construct, Acta Informatica, v.28 n.7, p.631-656, Oct. 1991 [doi>10.1007/BF01178680]
• Ull88: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• WS83: John Woodfill , Michael Stonebraker, An Implementation of Hypothetical Relations, Proceedings of the 9th International Conference on Very Large Data Bases, p.157-166, October 31-November 02, 1983

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Schema and subschema
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

General Terms:
Algorithms, Design, Languages, Management, Performance, Theory