Deleting Completed Transactions (Extended Abstract)

Summary: Gives a necessary and sufficient condition characterizing when a conflict-graph–based scheduler can safely forget (remove) a completed transaction without violating correctness. Condition is testable in polynomial time and supports repeated application for incremental garbage collection. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 746
Venue: PODS
Year: 1986
Pagerank: 5.545175e-05
Overall Rank: 7,784 | 46.60%
DOI: 10.1145/6012.15402

Incoming Non-self Citations Over Time

Authors

1. Thanasis Hadzilacos (National Technical University of Athens)
2. Mihalis Yannakakis (AT&T)

BibTeX Citation

@inproceedings{hadzilacos_pods86,
        address = {New York, NY, USA},
        series = {{PODS} '86},
        title = {{Deleting Completed Transactions (Extended Abstract)}},
        url = {https://dl.acm.org/doi/10.1145/6012.15402},
        doi = {10.1145/6012.15402},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Hadzilacos, Thanasis and Yannakakis, Mihalis},
        year = {1986}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,675	Serialization Graph Algorithms for Multiversion Concurrency Control	1988	PODS	8.2707581e-05
8,469	Reducing Recovery Constraints on Locking based Protocols	1994	PODS	5.4184681e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
405	Distributed Database Concurrency Controls Using Before-Values	1981	SIGMOD	0.00019061195
1,383	A Sophisticate's Introduction to Distributed Database Concurrency Control	1982	VLDB	0.0001096307
4,275	Towards a Self-Adapting Centralized Concurrency Control Algorithm	1984	SIGMOD	6.7887944e-05
6,526	Algorithmic Aspects of Multiversion Concurrency Control	1985	PODS	5.8509221e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	14,477	Maximal Concurrency By Locking	1984	PODS
2	5,430	Real-Time Transaction Scheduling: A Cost Conscious Approach	1993	SIGMOD
3	12,900	Concurrency Control and Recovery in Transactional Process Management	1999	PODS
4	2,654	Scheduling Real-Time Transactions with Disk Resident Data	1989	VLDB
5	3,384	Towards a Unified Theory of Concurrency Control and Recovery	1993	PODS
6	1,148	Scheduling Real-time Transactions: a Performance Evaluation	1988	VLDB
7	14,468	The Complexity of Reliable Concurrency Control	1985	PODS
8	13,210	DEADLOCK-FREEDOM (AND SAFETY) OF TRANSACTIONS IN A DISTRIBUTED DATABASE (Extended Abstract)	1985	PODS
9	14,538	A Formal Model for Maximum Concurrency in Transaction Systems with Predeclared Writesets	1982	VLDB
10	7,159	Transaction Scheduling: From Conflicts to Runtime Conflicts	2023	SIGMOD