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: 852
Venue: PODS
Year: 1989
Pagerank: 9.6053834e-05
Overall Rank: 1,856 | 87.27%
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,314	Independence of Logic Database Queries and Updates	1990	PODS	0.00011182427
2,662	Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions	1993	PODS	8.2831426e-05
2,883	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS	8.0012184e-05
3,191	Method Schemas	1990	PODS	7.6525725e-05
3,812	Constraints and Redundancy in Datalog	1992	PODS	7.105413e-05
6,310	Type Inference for Datalog and its Application to Query Optimisation	2008	PODS	5.9176726e-05
6,318	Query Automata (extended abstract)	1999	PODS	5.9150511e-05
6,319	Expressiveness of Structured Document Query Languages Based on Attribute Grammars (extended abstract)	1998	PODS	5.9150511e-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
63	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00038782376
916	A Time Bound on the Materialization of Some Recursively Defined Views	1985	VLDB	0.00013224702
1,173	Data Independent Recursion in Deductive Databases	1986	PODS	0.00011822695
1,417	On Computing Restricted Projections of Representative Instances	1985	PODS	0.00010839353
1,498	Safety of Recursive Horn Clauses With Infinite Relations	1987	PODS	0.00010567892
1,653	Bounds on the Propagation of Selection into Logic Programs	1987	PODS	0.000101081
1,788	Decidability and Undecidability Results for Boundedness of Linear Recursive Queries	1988	PODS	9.7653696e-05
1,957	The Parallel Complexity of Simple Chain Queries (Extended Abstract)	1987	PODS	9.4146943e-05
2,015	A Decidable Class of Bounded Recursions	1987	PODS	9.3047297e-05
3,025	An Axiomatic Approach to Deciding Query Safety in Deductive Databases	1988	PODS	7.8386928e-05
3,355	A Framework for Testing Safety and Effective Computability of Extended Datalog (Extended Abstract)	1988	SIGMOD	7.4912272e-05
6,077	Safety of Datalog Queries over Infinite Databases	1989	PODS	5.9850223e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,199	Adaptive Predicate Managers in Database Systems	1986	VLDB
2	7,886	Polynomial-time program transformations in deductive databases	1990	PODS
3	2,110	Theory of Database Queries (Extended Abstract)	1988	PODS
4	7,536	Database Updates in Logic Programming	1988	PODS
5	4,615	Tools for Datalog Boundedness	1991	PODS
6	12,487	The Finite Model Theory Toolbox of a Database Theoretician	2009	PODS
7	11,525	Data Path Queries over Embedded Graph Databases	2022	PODS
8	11,752	Projection Views of Register Automata	2020	PODS
9	2,957	Graph-Theoretic Methods In Database Theory	1990	PODS
10	6,318	Query Automata (extended abstract)	1999	PODS