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.657754e-05
Overall Rank: 1,781 | 88.07%
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
368	Object Identity As A Query Language Primitive	1989	SIGMOD	0.00019850502
720	PROCEDURAL AND DECLARATIVE DATABASE UPDATE LANGUAGES (Extended Abstract)	1988	PODS	0.0001447659
1,004	ILOG: Declarative Creation and Manipulation of Object Identifiers	1990	VLDB	0.00012557552
2,161	Theory of Database Queries (Extended Abstract)	1988	PODS	8.9203568e-05
2,466	Untyped Sets, Invention, and Computable Queries	1989	PODS	8.4057294e-05
2,723	Foundations of Data-Aware Process Analysis: A Database Theory Perspective	2013	PODS	8.0732695e-05
2,982	On the Expressive Power of Database Queries with Intermediate Types	1988	PODS	7.7719553e-05
4,664	On the Equivalence of Database Restructurings Involving Object Identifiers	1991	PODS	6.4635254e-05
5,089	Datalog Unchained	2021	PODS	6.2661323e-05
5,763	Extending the Relational Algebra to Support Transaction Time	1987	SIGMOD	5.9840569e-05
6,914	Modelling Non Deterministic Queries and Updates In Deductive Databases	1988	VLDB	5.6327494e-05
7,618	A Transaction Logic for Database Specification	1988	SIGMOD	5.4666793e-05
8,074	IDLOG: Extending the Expressive Power of Deductive Database Languages	1990	SIGMOD	5.3791193e-05
10,131	Relational Database Behavior: Utilizing Relational Discrete Event Systems and Models	1989	PODS	5.0614501e-05
13,313	Static Analysis of Intensional Databases in U-Datalog	1996	PODS	4.9605343e-05
13,442	A Non-deterministic Deductive Database Language	1991	SIGMOD	4.9605343e-05
13,468	Declarative Expression of Deductive Database Updates	1989	PODS	4.9605343e-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.00045733094
145	A Language Facility for Designing Interactive Database-Intensive Applications	1978	SIGMOD	0.00028989663
428	Relative Information Capacity of Simple Relational Database Schemata	1984	PODS	0.00018419906
5,105	Transactions And Integrity Constraints	1985	PODS	6.2611181e-05
6,230	Dynamic Constraints And Database Evolution	1983	PODS	5.8259308e-05
7,790	Deciding Properties of Transactional Schemas	1986	PODS	5.4354537e-05

Semantically Similar Papers

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