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)
Incoming Non-self Citations Over Time
Authors
Incoming Citations (Sorted by Pagerank)
Showing 4 of 4 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 4,840 | Solving the Phantom Problem by Predicative Optimistic Concurrency Control | 1983 | VLDB | 5.8864974e-05 |
| 5,735 | A Decision Procedure for Conjunctive Query Disjointness | 1989 | PODS | 5.3482653e-05 |
| 10,736 | TreeCat: Standalone Catalog Engine for Large Data Systems | 2025 | VLDB | 4.1945683e-05 |
| 13,000 | Adaptive Predicate Managers in Database Systems | 1986 | VLDB | 4.1945683e-05 |
Previous
Page 1 / 1
Next
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 |
|---|---|---|---|---|
| 19 | Interval Hierarchies And Their Application To Predicate Files | 1977 | SIGMOD | 0.00091625014 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 9,543 | An Optimal Algorithm For Testing For Safety And Detecting Deadlocks In Locked Transaction Systems | 1982 | PODS | 4.3265281e-05 |
| 9,989 | On the Vexing Difficulty of Evaluating IN Predicates | 2026 | CIDR | 4.1945683e-05 |
| 7,598 | Polynomial-time program transformations in deductive databases | 1990 | PODS | 4.7004867e-05 |
| 13,011 | DEADLOCK-FREEDOM (AND SAFETY) OF TRANSACTIONS IN A DISTRIBUTED DATABASE (Extended Abstract) | 1985 | PODS | 4.1945683e-05 |
| 13,000 | Adaptive Predicate Managers in Database Systems | 1986 | VLDB | 4.1945683e-05 |
| 3,423 | Is Distributed Locking Harder? | 1982 | PODS | 7.1133874e-05 |
| 6,070 | Solving Implication Problems in Database Applications | 1989 | SIGMOD | 5.2263865e-05 |
| 4,048 | On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates | 1998 | PODS | 6.4968603e-05 |
| 1,739 | Precision Locks | 1981 | SIGMOD | 0.00010719584 |
| 14,276 | Maximal Concurrency By Locking | 1984 | PODS | - |