The Complexity Of Testing Predicate Locks

Summary: NP-complete for satisfiability of predicates, even simple ones, in predicate locks. With fixed-degree relations, a polynomial-time algorithm in predicate length exists, even for field-field comparisons with offsets; satisfiable predicates have witnesses whose values are tied to the predicate constants. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2166
Venue: SIGMOD
Year: 1979
Pagerank: 6.7495011e-05
Overall Rank: 4,351 | 70.15%
DOI: 10.1145/582095.582115

Incoming Non-self Citations Over Time

Authors

1. Harry B. Hunt (Columbia University)
2. Daniel J. Rosenkrantz (State University of New York at Albany)

BibTeX Citation

@inproceedings{hunt_sigmod79,
        title = {{THE COMPLEXITY OF TESTING PREDICATE LOCKS}},
        author = {Hunt, Harry B. and Rosenkrantz, Daniel J.},
        series = {{SIGMOD} '79},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/582095.582115},
        url = {https://dl.acm.org/doi/10.1145/582095.582115},
        year = {1979}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,718	Solving the Phantom Problem by Predicative Optimistic Concurrency Control	1983	VLDB	6.5468872e-05
6,731	A Decision Procedure for Conjunctive Query Disjointness	1989	PODS	5.7885617e-05
10,976	TreeCat: Standalone Catalog Engine for Large Data Systems	2025	VLDB	5.093636e-05
13,199	Adaptive Predicate Managers in Database Systems	1986	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
113	Interval Hierarchies And Their Application To Predicate Files	1977	SIGMOD	0.00032684992

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,911	An Optimal Algorithm For Testing For Safety And Detecting Deadlocks In Locked Transaction Systems	1982	PODS
2	7,886	Polynomial-time program transformations in deductive databases	1990	PODS
3	10,136	On the Vexing Difficulty of Evaluating IN Predicates	2026	CIDR
4	13,210	DEADLOCK-FREEDOM (AND SAFETY) OF TRANSACTIONS IN A DISTRIBUTED DATABASE (Extended Abstract)	1985	PODS
5	13,199	Adaptive Predicate Managers in Database Systems	1986	VLDB
6	4,777	Is Distributed Locking Harder?	1982	PODS
7	6,282	Solving Implication Problems in Database Applications	1989	SIGMOD
8	3,801	On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates	1998	PODS
9	2,166	Precision Locks	1981	SIGMOD
10	14,477	Maximal Concurrency By Locking	1984	PODS