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: 800
Venue: PODS
Year: 1987
Pagerank: 9.9156202e-05
Overall Rank: 1,726 | 88.16%
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
355	Object Identity As A Query Language Primitive	1989	SIGMOD	0.00020351749
702	PROCEDURAL AND DECLARATIVE DATABASE UPDATE LANGUAGES (Extended Abstract)	1988	PODS	0.00014855299
971	ILOG: Declarative Creation and Manipulation of Object Identifiers	1990	VLDB	0.00012875736
2,110	Theory of Database Queries (Extended Abstract)	1988	PODS	9.1532803e-05
2,400	Untyped Sets, Invention, and Computable Queries	1989	PODS	8.6299917e-05
2,653	Foundations of Data-Aware Process Analysis: A Database Theory Perspective	2013	PODS	8.2898925e-05
2,897	On the Expressive Power of Database Queries with Intermediate Types	1988	PODS	7.9790527e-05
4,555	On the Equivalence of Database Restructurings Involving Object Identifiers	1991	PODS	6.6344715e-05
4,943	Datalog Unchained	2021	PODS	6.4332239e-05
5,632	Extending the Relational Algebra to Support Transaction Time	1987	SIGMOD	6.1421602e-05
6,752	Modelling Non Deterministic Queries and Updates In Deductive Databases	1988	VLDB	5.7837368e-05
7,452	A Transaction Logic for Database Specification	1988	SIGMOD	5.6133619e-05
7,885	IDLOG: Extending the Expressive Power of Deductive Database Languages	1990	SIGMOD	5.5228272e-05
9,906	Relational Database Behavior: Utilizing Relational Discrete Event Systems and Models	1989	PODS	5.1972596e-05
12,976	Static Analysis of Intensional Databases in U-Datalog	1996	PODS	5.093636e-05
13,105	A Non-deterministic Deductive Database Language	1991	SIGMOD	5.093636e-05
13,131	Declarative Expression of Deductive Database Updates	1989	PODS	5.093636e-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
40	Testing Implications Of Data Dependencies	1979	SIGMOD	0.00046918506
139	A Language Facility for Designing Interactive Database-Intensive Applications	1978	SIGMOD	0.00029742792
413	Relative Information Capacity of Simple Relational Database Schemata	1984	PODS	0.00018894294
4,962	Transactions And Integrity Constraints	1985	PODS	6.4273819e-05
6,085	Dynamic Constraints And Database Evolution	1983	PODS	5.9820991e-05
7,615	Deciding Properties of Transactional Schemas	1986	PODS	5.5811446e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,722	A Model-Theoretic Approach to Updating Logical Databases (Extended Abstract)	1986	PODS
2	7,615	Deciding Properties of Transactional Schemas	1986	PODS
3	13,177	Axiomatization and Simplification Rules for Relational Transactions (Extended Abstract)	1987	PODS
4	13,226	Coping with Complexity in Automated Reasoning about Database Systems	1985	VLDB
5	13,232	Specification and Verification of Abstract Database Types	1984	PODS
6	5,475	Verifiable Properties of Database Transactions	1996	PODS
7	4,962	Transactions And Integrity Constraints	1985	PODS
8	14,419	Synthesizing Database Transactions	1990	VLDB
9	7,452	A Transaction Logic for Database Specification	1988	SIGMOD
10	702	PROCEDURAL AND DECLARATIVE DATABASE UPDATE LANGUAGES (Extended Abstract)	1988	PODS