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: 853
Venue: PODS
Year: 1989
Pagerank: 0.00010913301
Overall Rank: 1,688 | 88.26%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Moshe Y. Vardi

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,189	Independence of Logic Database Queries and Updates	1990	PODS	0.00013441514
2,830	Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions	1993	PODS	8.054172e-05
2,877	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS	7.9715251e-05
2,960	Method Schemas	1990	PODS	7.8135404e-05
3,857	Constraints and Redundancy in Datalog	1992	PODS	6.6939005e-05
5,870	Query Automata (extended abstract)	1999	PODS	5.2943906e-05
5,871	Expressiveness of Structured Document Query Languages Based on Attribute Grammars (extended abstract)	1998	PODS	5.2943906e-05
6,312	Type Inference for Datalog and its Application to Query Optimisation	2008	PODS	5.1158809e-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
77	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00057043861
617	A Time Bound on the Materialization of Some Recursively Defined Views	1985	VLDB	0.00019090876
1,051	Safety of Recursive Horn Clauses With Infinite Relations	1987	PODS	0.00014440736
1,185	Data Independent Recursion in Deductive Databases	1986	PODS	0.00013445831
1,196	On Computing Restricted Projections of Representative Instances	1985	PODS	0.00013403617
1,545	The Parallel Complexity of Simple Chain Queries (Extended Abstract)	1987	PODS	0.0001144821
1,712	Bounds on the Propagation of Selection into Logic Programs	1987	PODS	0.00010804573
1,991	Decidability and Undecidability Results for Boundedness of Linear Recursive Queries	1988	PODS	9.84713e-05
2,206	A Decidable Class of Bounded Recursions	1987	PODS	9.2910236e-05
2,786	An Axiomatic Approach to Deciding Query Safety in Deductive Databases	1988	PODS	8.1283801e-05
3,010	A Framework for Testing Safety and Effective Computability of Extended Datalog (Extended Abstract)	1988	SIGMOD	7.7205569e-05
4,136	Safety of Datalog Queries over Infinite Databases	1989	PODS	6.4188795e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
13,000	Adaptive Predicate Managers in Database Systems	1986	VLDB	4.1945683e-05
7,598	Polynomial-time program transformations in deductive databases	1990	PODS	4.7004867e-05
1,448	Theory of Database Queries (Extended Abstract)	1988	PODS	0.00011938045
6,932	Database Updates in Logic Programming	1988	PODS	4.8925595e-05
4,631	Tools for Datalog Boundedness	1991	PODS	6.0347472e-05
12,292	The Finite Model Theory Toolbox of a Database Theoretician	2009	PODS	4.1945683e-05
11,326	Data Path Queries over Embedded Graph Databases	2022	PODS	4.1945683e-05
11,555	Projection Views of Register Automata	2020	PODS	4.1945683e-05
2,474	Graph-Theoretic Methods In Database Theory	1990	PODS	8.7135761e-05
5,870	Query Automata (extended abstract)	1999	PODS	5.2943906e-05