A Transaction Language Complete for Database Update and Specification

Summary: Introduce TL, a minimal transaction language built from tuple insertion/deletion, a while construct, and a bounded number of temporary domain values to express database updates. Define update- and specification-completeness and prove TL satisfies both, analyze safety and negation-vs-deletion trade-offs, and position results relative to prior work (e.g., Chandra–Harel). (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h9ad2a60ddcc6df47
Venue: PODS
Year: 1987
Pagerank: 9.6894e-05
Overall Rank: 1,768 | 88.12%
DOI: 10.1145/28659.28688

Incoming Non-self Citations Over Time

Authors

1. Serge Abiteboul (INRIA)
2. Victor Vianu (University of California San Diego)

BibTeX Citation

@inproceedings{abiteboul_pods87,
        address = {New York, NY, USA},
        series = {{PODS} '87},
        title = {{A Transaction Language Complete for Database Update and Specification}},
        url = {https://dl.acm.org/doi/10.1145/28659.28688},
        doi = {10.1145/28659.28688},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Abiteboul, Serge and Vianu, Victor},
        year = {1987}
}

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
366	Object Identity As A Query Language Primitive	1989	SIGMOD	0.00019914615
719	PROCEDURAL AND DECLARATIVE DATABASE UPDATE LANGUAGES (Extended Abstract)	1988	PODS	0.0001452391
1,003	ILOG: Declarative Creation and Manipulation of Object Identifiers	1990	VLDB	0.00012591126
2,152	Theory of Database Queries (Extended Abstract)	1988	PODS	8.9497631e-05
2,457	Untyped Sets, Invention, and Computable Queries	1989	PODS	8.4335382e-05
2,711	Foundations of Data-Aware Process Analysis: A Database Theory Perspective	2013	PODS	8.1000533e-05
2,970	On the Expressive Power of Database Queries with Intermediate Types	1988	PODS	7.7976956e-05
4,648	On the Equivalence of Database Restructurings Involving Object Identifiers	1991	PODS	6.4847033e-05
5,070	Datalog Unchained	2021	PODS	6.2869206e-05
5,759	Extending the Relational Algebra to Support Transaction Time	1987	SIGMOD	6.0025251e-05
6,895	Modelling Non Deterministic Queries and Updates In Deductive Databases	1988	VLDB	5.6514321e-05
7,601	A Transaction Logic for Database Specification	1988	SIGMOD	5.4848155e-05
8,057	IDLOG: Extending the Expressive Power of Deductive Database Languages	1990	SIGMOD	5.3966955e-05
10,097	Relational Database Behavior: Utilizing Relational Discrete Event Systems and Models	1989	PODS	5.078242e-05
13,272	Static Analysis of Intensional Databases in U-Datalog	1996	PODS	4.9769913e-05
13,401	A Non-deterministic Deductive Database Language	1991	SIGMOD	4.9769913e-05
13,427	Declarative Expression of Deductive Database Updates	1989	PODS	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
41	Testing Implications Of Data Dependencies	1979	SIGMOD	0.00045878061
145	A Language Facility for Designing Interactive Database-Intensive Applications	1978	SIGMOD	0.00029083502
426	Relative Information Capacity of Simple Relational Database Schemata	1984	PODS	0.00018477356
5,085	Transactions And Integrity Constraints	1985	PODS	6.2817401e-05
6,217	Dynamic Constraints And Database Evolution	1983	PODS	5.8451723e-05
7,775	Deciding Properties of Transactional Schemas	1986	PODS	5.4533998e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,862	A Model-Theoretic Approach to Updating Logical Databases (Extended Abstract)	1986	PODS
2	7,775	Deciding Properties of Transactional Schemas	1986	PODS
3	13,473	Axiomatization and Simplification Rules for Relational Transactions (Extended Abstract)	1987	PODS
4	13,522	Coping with Complexity in Automated Reasoning about Database Systems	1985	VLDB
5	13,528	Specification and Verification of Abstract Database Types	1984	PODS
6	5,603	Verifiable Properties of Database Transactions	1996	PODS
7	5,085	Transactions And Integrity Constraints	1985	PODS
8	14,735	Synthesizing Database Transactions	1990	VLDB
9	7,601	A Transaction Logic for Database Specification	1988	SIGMOD
10	719	PROCEDURAL AND DECLARATIVE DATABASE UPDATE LANGUAGES (Extended Abstract)	1988	PODS