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.3940283e-05
Overall Rank: 1,908 | 87.18%
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.00010951176
2,716	Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions	1993	PODS	8.1006747e-05
2,923	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS	7.8518874e-05
3,264	Method Schemas	1990	PODS	7.4808695e-05
3,886	Constraints and Redundancy in Datalog	1992	PODS	6.9461797e-05
6,437	Type Inference for Datalog and its Application to Query Optimisation	2008	PODS	5.7853525e-05
6,445	Query Automata (extended abstract)	1999	PODS	5.7823766e-05
6,446	Expressiveness of Structured Document Query Languages Based on Attribute Grammars (extended abstract)	1998	PODS	5.7823766e-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.00038009523
946	A Time Bound on the Materialization of Some Recursively Defined Views	1985	VLDB	0.00012936921
1,201	Data Independent Recursion in Deductive Databases	1986	PODS	0.00011560838
1,455	On Computing Restricted Projections of Representative Instances	1985	PODS	0.00010599099
1,534	Safety of Recursive Horn Clauses With Infinite Relations	1987	PODS	0.00010331296
1,682	Bounds on the Propagation of Selection into Logic Programs	1987	PODS	9.8850863e-05
1,830	Decidability and Undecidability Results for Boundedness of Linear Recursive Queries	1988	PODS	9.5498891e-05
2,005	The Parallel Complexity of Simple Chain Queries (Extended Abstract)	1987	PODS	9.2054933e-05
2,062	A Decidable Class of Bounded Recursions	1987	PODS	9.0974416e-05
3,083	An Axiomatic Approach to Deciding Query Safety in Deductive Databases	1988	PODS	7.6632607e-05
3,415	A Framework for Testing Safety and Effective Computability of Extended Datalog (Extended Abstract)	1988	SIGMOD	7.3235908e-05
6,201	Safety of Datalog Queries over Infinite Databases	1989	PODS	5.8507344e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,489	Adaptive Predicate Managers in Database Systems	1986	VLDB
2	8,053	Polynomial-time program transformations in deductive databases	1990	PODS
3	2,150	Theory of Database Queries (Extended Abstract)	1988	PODS
4	7,682	Database Updates in Logic Programming	1988	PODS
5	4,712	Tools for Datalog Boundedness	1991	PODS
6	12,778	The Finite Model Theory Toolbox of a Database Theoretician	2009	PODS
7	11,834	Data Path Queries over Embedded Graph Databases	2022	PODS
8	12,055	Projection Views of Register Automata	2020	PODS
9	3,020	Graph-Theoretic Methods In Database Theory	1990	PODS
10	6,445	Query Automata (extended abstract)	1999	PODS