Data processing: database and file management or data structures – Database design – Data structure types
Patent
1997-05-07
1999-11-02
Amsbury, Wayne
Data processing: database and file management or data structures
Database design
Data structure types
706 51, G06F 1730
Patent
active
059787899
ABSTRACT:
A hypothetical query in a database system is transformed using algebraic equivalences involving explicit substitutions so as to produce one or more equivalent queries which can be evaluated more efficiently than the original hypothetical query. The hypothetical query may be of the form Q when {U} where Q is a relational algebra query and U is an update expression. The value assigned to the hypothetical query in a database state DB is the value that Q would return in the database state reached from DB by executing update U. One or more explicit substitutions are used to represent hypothetical database state changes, and algebraic equivalences involving the explicit substitutions are applied to the hypothetical query in order to generate at least one additional query which is equivalent to the hypothetical query. Several equivalent queries may be generated, and their estimated computation times compared, in order to select a particular equivalent query for direct evaluation. The use of explicit substitutions to represent hypothetical database state changes allows when constructs or other similar hypothetical programming constructs to be eliminated from the equivalent query. The evaluation process may be facilitated by configuring the original hypothetical query into an evaluable normal form, such that one or more hypothetical state expressions of the query correspond to explicit substitutions, and the hypothetical query does not utilize a composition operator. The selected equivalent query can be evaluated using a purely lazy evaluation strategy, or a hybrid lazy-eager evaluation strategy.
REFERENCES:
patent: 5276775 (1994-01-01), Meng
patent: 5393062 (1995-02-01), Cember
patent: 5418942 (1995-05-01), Krawchuk et al.
patent: 5745889 (1998-04-01), Burrows
patent: 5778355 (1998-07-01), Boyer et al.
M. Abadi, L. Cardelli, P. Curien and J. Levy, "Explicit Substitutions," Journal of Functional Programming, 1(4):375-416, 1991.
M. Benedikt, T. Griffin and L. Libkin, "Verifiable Properties of Database Transactions," Proc. ACM Symp. on Principles of Database Systems, pp. 117-127, 1991.
A.J. Bonner, "Hypothetical Datalog: Complexity and Expressibility," Theoretical Computer Science, 76:3-51, 1990.
A.J. Bonner, "The Logical Semantics of Hypothetical Rulebases with Deletion," Journal of Logic Programming, 1995.
G. Dowek, T. Hardin and C. Kirchner, "Higher-Order Unification via Explicit Substitutions," IEEE Symposium on Logic in Computer Science, pp. 366-374, 1995.
M. Doherty, R. Hull and M. Rupawalla, "Structures for Manipulating Proposed Updates in Object-Oriented Databases," Proc. ACM SIGMOD Symp. on the Management of Data, pp. 306-317, 1996.
G. Graefe and D.J. DeWitt, "The EXODUS Optimizer Generator," Proc. ACM SIGMOD Symp. on the Management of Data, pp. 160-172, 1987.
S. Ghandeharizadeh et al., "On Implementing a Language for Specifying Active Database Execution Models," Proc. of Intl. Conf. on Very Large Data Bases, pp. 441-454, 1993.
S. Ghandeharizadeh, R. Hull and D. Jacobs, "Heraclitus: Elevating Deltas to be First-Class Citizens in a Database Programming Language," ACM Trans. on Database Systems, 21(3): 370-426, 1996.
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.
D.M. Gabbay, "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.
G. Graefe, "Query Evaluation Techniques for Large Databases," ACM Computing Surveys, 25(2):73-170, 1993.
D. Gries, "The Science of Programming," Ch. 7, pp. 108-113, Springer-Verlag, 1981.
S. Horowitz and T. Reps, "The Use of Program Dependence Graphs in Software Engineering," Proceedings of the 14.sup.th International Conference on Software Engineering, 1992.
J.R. Hindley and J.P. Seldin, "Introduction to Combinators and .lambda.-Calculus," Cambridge University Press, 1986.
P. Lescanne, "From .lambda..sigma. to .lambda..nu.--A Journey Through Calculi of Explicit Substitutions," ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), pp. 60-69, 1994.
J.W. Lloyd, "Foundations of Logic Programming," Second Edition, pp. 20-22, Springer-Verlag, Berlin, 1987.
X. Qian, "An Axiom System of Database Transactions," Information Processing Letters, 36:183-189, 1990.
X. Qian, "The Expressive Power of the Bounded-Iteration Construct," Acta Informatica, 28(7):631-656, Oct. 1991.
Jeffrey D. Ullman, "Principles of Database and Knowledgebase Systems," vol. II, pp. 664-667, Computer Science Press, Potomac, Maryland, 1988.
J. Woodfill and M. Stonebraker, "An Implementation of Hypothetical Relations," Proc. of Intl. Conf. on Very Large Databases, pp. 157-165, Sep. 1983.
Griffin Timothy G.
Hull Richard Baxter
Amsbury Wayne
Lucent Technologies - Inc.
LandOfFree
Efficient hypothetical query evaluation in a database system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient hypothetical query evaluation in a database system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient hypothetical query evaluation in a database system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2149709