Automata Theory for Database Theoreticians

Summary: Argues for (re)adoption of automata theory—word and tree automata, constructions, closures—as core tools for DB theory. Shows concrete automata-based analyses and decidability techniques to address Datalog predicate emptiness, termination, and boundedness. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h9d69769d681d2673
Venue: PODS
Year: 1989
Pagerank: 9.3895837e-05
Overall Rank: 1,910 | 87.17%
DOI: 10.1145/73721.73729

Incoming Non-self Citations Over Time

Authors

1. Moshe Y. Vardi (IBM)

BibTeX Citation

@inproceedings{vardi_pods89,
        address = {New York, NY, USA},
        series = {{PODS} '89},
        title = {{Automata Theory for Database Theoreticians}},
        url = {https://dl.acm.org/doi/10.1145/73721.73729},
        doi = {10.1145/73721.73729},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Vardi, Moshe Y.},
        year = {1989}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,346	Independence of Logic Database Queries and Updates	1990	PODS	0.00010946011
2,716	Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions	1993	PODS	8.0968483e-05
2,924	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS	7.8481787e-05
3,265	Method Schemas	1990	PODS	7.4773282e-05
3,887	Constraints and Redundancy in Datalog	1992	PODS	6.9428919e-05
6,439	Type Inference for Datalog and its Application to Query Optimisation	2008	PODS	5.7826139e-05
6,448	Query Automata (extended abstract)	1999	PODS	5.7796393e-05
6,449	Expressiveness of Structured Document Query Languages Based on Attribute Grammars (extended abstract)	1998	PODS	5.7796393e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
67	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00037991902
946	A Time Bound on the Materialization of Some Recursively Defined Views	1985	VLDB	0.00012930818
1,201	Data Independent Recursion in Deductive Databases	1986	PODS	0.00011555372
1,455	On Computing Restricted Projections of Representative Instances	1985	PODS	0.00010594127
1,536	Safety of Recursive Horn Clauses With Infinite Relations	1987	PODS	0.00010326412
1,682	Bounds on the Propagation of Selection into Logic Programs	1987	PODS	9.8804595e-05
1,830	Decidability and Undecidability Results for Boundedness of Linear Recursive Queries	1988	PODS	9.5453747e-05
2,007	The Parallel Complexity of Simple Chain Queries (Extended Abstract)	1987	PODS	9.2011602e-05
2,064	A Decidable Class of Bounded Recursions	1987	PODS	9.0931389e-05
3,087	An Axiomatic Approach to Deciding Query Safety in Deductive Databases	1988	PODS	7.6596386e-05
3,415	A Framework for Testing Safety and Effective Computability of Extended Datalog (Extended Abstract)	1988	SIGMOD	7.3201296e-05
6,206	Safety of Datalog Queries over Infinite Databases	1989	PODS	5.8479648e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,495	Adaptive Predicate Managers in Database Systems	1986	VLDB
2	8,059	Polynomial-time program transformations in deductive databases	1990	PODS
3	2,152	Theory of Database Queries (Extended Abstract)	1988	PODS
4	7,688	Database Updates in Logic Programming	1988	PODS
5	4,714	Tools for Datalog Boundedness	1991	PODS
6	12,784	The Finite Model Theory Toolbox of a Database Theoretician	2009	PODS
7	11,840	Data Path Queries over Embedded Graph Databases	2022	PODS
8	12,061	Projection Views of Register Automata	2020	PODS
9	3,021	Graph-Theoretic Methods In Database Theory	1990	PODS
10	6,448	Query Automata (extended abstract)	1999	PODS