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.0001090256
Overall Rank: 1,687 | 88.28%
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.0001342924
2,836	Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions	1993	PODS	8.0466188e-05
2,887	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS	7.9640219e-05
2,964	Method Schemas	1990	PODS	7.8060034e-05
3,859	Constraints and Redundancy in Datalog	1992	PODS	6.6875648e-05
5,874	Query Automata (extended abstract)	1999	PODS	5.2893146e-05
5,875	Expressiveness of Structured Document Query Languages Based on Attribute Grammars (extended abstract)	1998	PODS	5.2893146e-05
6,312	Type Inference for Datalog and its Application to Query Optimisation	2008	PODS	5.1109656e-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
79	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00056010993
612	A Time Bound on the Materialization of Some Recursively Defined Views	1985	VLDB	0.0001915957
1,049	Safety of Recursive Horn Clauses With Infinite Relations	1987	PODS	0.00014426218
1,167	On Computing Restricted Projections of Representative Instances	1985	PODS	0.0001354084
1,200	Data Independent Recursion in Deductive Databases	1986	PODS	0.00013342243
1,532	The Parallel Complexity of Simple Chain Queries (Extended Abstract)	1987	PODS	0.00011466849
1,636	Bounds on the Propagation of Selection into Logic Programs	1987	PODS	0.00011058643
1,997	Decidability and Undecidability Results for Boundedness of Linear Recursive Queries	1988	PODS	9.837483e-05
2,212	A Decidable Class of Bounded Recursions	1987	PODS	9.2818302e-05
2,790	An Axiomatic Approach to Deciding Query Safety in Deductive Databases	1988	PODS	8.1203289e-05
3,012	A Framework for Testing Safety and Effective Computability of Extended Datalog (Extended Abstract)	1988	SIGMOD	7.7129076e-05
4,138	Safety of Datalog Queries over Infinite Databases	1989	PODS	6.4127061e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
13,011	Adaptive Predicate Managers in Database Systems	1986	VLDB	4.1905499e-05
7,603	Polynomial-time program transformations in deductive databases	1990	PODS	4.6959912e-05
1,450	Theory of Database Queries (Extended Abstract)	1988	PODS	0.00011926567
6,934	Database Updates in Logic Programming	1988	PODS	4.8878659e-05
4,631	Tools for Datalog Boundedness	1991	PODS	6.0289457e-05
12,300	The Finite Model Theory Toolbox of a Database Theoretician	2009	PODS	4.1905499e-05
11,328	Data Path Queries over Embedded Graph Databases	2022	PODS	4.1905499e-05
11,559	Projection Views of Register Automata	2020	PODS	4.1905499e-05
2,473	Graph-Theoretic Methods In Database Theory	1990	PODS	8.7048914e-05
5,874	Query Automata (extended abstract)	1999	PODS	5.2893146e-05