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.6939822e-05
Overall Rank: 1,767 | 88.13%
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.00019923978
718	PROCEDURAL AND DECLARATIVE DATABASE UPDATE LANGUAGES (Extended Abstract)	1988	PODS	0.00014530776
1,003	ILOG: Declarative Creation and Manipulation of Object Identifiers	1990	VLDB	0.00012597028
2,150	Theory of Database Queries (Extended Abstract)	1988	PODS	8.953998e-05
2,457	Untyped Sets, Invention, and Computable Queries	1989	PODS	8.4375276e-05
2,711	Foundations of Data-Aware Process Analysis: A Database Theory Perspective	2013	PODS	8.1038896e-05
2,968	On the Expressive Power of Database Queries with Intermediate Types	1988	PODS	7.8013847e-05
4,646	On the Equivalence of Database Restructurings Involving Object Identifiers	1991	PODS	6.4877004e-05
5,067	Datalog Unchained	2021	PODS	6.2898972e-05
5,757	Extending the Relational Algebra to Support Transaction Time	1987	SIGMOD	6.0053627e-05
6,892	Modelling Non Deterministic Queries and Updates In Deductive Databases	1988	VLDB	5.6541068e-05
7,595	A Transaction Logic for Database Specification	1988	SIGMOD	5.4874132e-05
8,051	IDLOG: Extending the Expressive Power of Deductive Database Languages	1990	SIGMOD	5.3992494e-05
10,093	Relational Database Behavior: Utilizing Relational Discrete Event Systems and Models	1989	PODS	5.0806471e-05
13,266	Static Analysis of Intensional Databases in U-Datalog	1996	PODS	4.9793485e-05
13,395	A Non-deterministic Deductive Database Language	1991	SIGMOD	4.9793485e-05
13,421	Declarative Expression of Deductive Database Updates	1989	PODS	4.9793485e-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.00045899672
144	A Language Facility for Designing Interactive Database-Intensive Applications	1978	SIGMOD	0.00029097107
425	Relative Information Capacity of Simple Relational Database Schemata	1984	PODS	0.00018486061
5,082	Transactions And Integrity Constraints	1985	PODS	6.2847136e-05
6,214	Dynamic Constraints And Database Evolution	1983	PODS	5.8479403e-05
7,766	Deciding Properties of Transactional Schemas	1986	PODS	5.4559822e-05

Semantically Similar Papers

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