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.8819812e-05 |
| 5,748 | A Decision Procedure for Conjunctive Query Disjointness | 1989 | PODS | 5.3426438e-05 |
| 10,743 | TreeCat: Standalone Catalog Engine for Large Data Systems | 2025 | VLDB | 4.1905499e-05 |
| 13,011 | Adaptive Predicate Managers in Database Systems | 1986 | VLDB | 4.1905499e-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.00091479494 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 9,544 | An Optimal Algorithm For Testing For Safety And Detecting Deadlocks In Locked Transaction Systems | 1982 | PODS | 4.3223802e-05 |
| 7,603 | Polynomial-time program transformations in deductive databases | 1990 | PODS | 4.6959912e-05 |
| 9,988 | On the Vexing Difficulty of Evaluating IN Predicates | 2026 | CIDR | 4.1905499e-05 |
| 13,022 | DEADLOCK-FREEDOM (AND SAFETY) OF TRANSACTIONS IN A DISTRIBUTED DATABASE (Extended Abstract) | 1985 | PODS | 4.1905499e-05 |
| 13,011 | Adaptive Predicate Managers in Database Systems | 1986 | VLDB | 4.1905499e-05 |
| 3,423 | Is Distributed Locking Harder? | 1982 | PODS | 7.1067614e-05 |
| 6,074 | Solving Implication Problems in Database Applications | 1989 | SIGMOD | 5.2211593e-05 |
| 4,055 | On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates | 1998 | PODS | 6.4906839e-05 |
| 1,734 | Precision Locks | 1981 | SIGMOD | 0.00010715681 |
| 14,290 | Maximal Concurrency By Locking | 1984 | PODS | - |