The complexity of testing predicate locks

ABSTRACT

The problem of testing predicates for satisfiability arises in several aspects of database systems such as the use of predicate locks in concurrency control [7]. Such problems are NP-complete even for "simple predicates", i.e. predicates consisting of Boolean combinations of comparisons between a field of a tuple and a constant. However, when the relations referred to by the predicates are of fixed degree, there is an algorithm whose runtime is bounded by a polynomial in the length of the predicate. This is true not only for "simple predicates" but also for predicates containing comparisons between a field and another field, possibly offset by a constant. The proofs involve showing that if a predicate is satisfiable, then it is satisfiable by a tuple whose field values are related to constants occurring in the predicate.

REFERENCES

• 1: M. M. Astrahan , M. W. Blasgen , D. D. Chamberlin , K. P. Eswaran , J. N. Gray , P. P. Griffiths , W. F. King , R. A. Lorie , P. R. McJones , J. W. Mehl , G. R. Putzolu , I. L. Traiger , B. W. Wade , V. Watson, System R: relational approach to database management, ACM Transactions on Database Systems (TODS), v.1 n.2, p.97-137, June 1976 [doi>10.1145/320455.320457]
• 2: Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
• 3: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 4: Cooper, D.C. Theorem-proving in arithmetic without multiplication. Machine Intelligence 7, B. Meltzer and D. Michie (eds.), John Wiley & Sons, New York, 1972, pp. 91--99.
• 5: Kapali P. Eswaran, Aspects of a trigger subsystem in an integrated database system, Proceedings of the 2nd international conference on Software engineering, p.243-250, October 13-15, 1976, San Francisco, California, United States
• 6: Eswaran, K.P., and Chamberlain, D.D. Functional specifications of a subsystem for database integrity. Proc. Int. Conf. on Very Large Data Bases, Framingham, Mass., Sept. 1975, pp. 48--68. (Available from ACM, New York)
• 7: K. P. Eswaran , J. N. Gray , R. A. Lorie , I. L. Traiger, The notions of consistency and predicate locks in a database system, Communications of the ACM, v.19 n.11, p.624-633, Nov. 1976 [doi>10.1145/360363.360369]
• 8: Finkel, R.A., and Bentley, J.L. Quad trees: a data structure for retrieval on composite keys, Acta Inf., 4 (1974), 1--9.
• 9: Karp, R.M. Reducibility among combinatorial problems, In Complexity of Computer Computations, Miller, R.E. and Thatcher, J.W. (eds.) Plenum Press, New York, 1972, pp. 85--104.
• 10: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 11: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 12: Rivest, R. Partial match retrieval algorithms, SIAM J. Computing 5, 1 (March 1976), 19--50.
• 13: John E. Savage, The Complexity of Computing, Krieger Publishing Co., Inc., Melbourne, FL, 1987
• 14: Stonebraker, M., and Nuehold, E. A distributed database version of INGRES. Rep. ERL-M612, Electron. Res. Lab., U. of Calif., Berkeley, Sept. 1976.
• 15: Kai C. Wong , Murray Edelberg, Interval hierarchies and their application to predicate files, ACM Transactions on Database Systems (TODS), v.2 n.3, p.223-232, Sept. 1977 [doi>10.1145/320557.320562]