On the Expressive Power of Datalog: Tools and a Case Study

Summary: Characterizes Datalog(!=) as a fragment of infinitary logic L^infty via pebble games, giving tools for expressiveness analysis. Applies them to classify fixed directed subgraph homeomorphism queries and proves Fortune et al.'s dichotomies proper for Datalog(!=) expressibility without complexity assumptions. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: hdea53a9bf37accf3
Venue: PODS
Year: 1990
Pagerank: 6.9501939e-05
Overall Rank: 3,876 | 73.95%
DOI: 10.1145/298514.298542

Incoming Non-self Citations Over Time

Authors

1. Phokion G. Kolaitis (University of California Santa Cruz)
2. Moshe Y. Vardi (IBM)

BibTeX Citation

@inproceedings{kolaitis_pods90,
        address = {New York, NY, USA},
        series = {{PODS} '90},
        title = {{On the Expressive Power of Datalog: Tools and a Case Study}},
        url = {https://dl.acm.org/doi/10.1145/298514.298542},
        doi = {10.1145/298514.298542},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Kolaitis, Phokion G. and Vardi, Moshe Y.},
        year = {1990}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,374	On Datalog vs. Polynomial Time	1991	PODS	5.8064898e-05
6,826	Can Datalog be approximated?	1994	PODS	5.6695242e-05
8,058	Weaker Forms of Monotonicity for Declarative Networking: a More Fine-grained Answer to the CALM-conjecture	2014	PODS	5.3964484e-05
12,333	Logical Aspects of Massively Parallel and Distributed Systems	2016	PODS	4.9769913e-05
13,282	Combinatorial Games in Database Theory	1995	PODS	4.9769913e-05
13,316	Bounded Arity Datalog(!=) Queries on Graphs (Extended Abstract)	1994	PODS	4.9769913e-05
13,323	Adding Disjunction to Datalog (Extended Abstract)	1994	PODS	4.9769913e-05
13,374	Datalog Expressiveness of Chain Queries: Grammar Tools and Characterizations	1992	PODS	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
177	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.00026648806
2,822	Inductive Pebble Games And The Expressive Power Of Datalog	1989	PODS	7.9669896e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,921	The Expressiveness of a Family of Finite Set Languages	1991	PODS
2	13,316	Bounded Arity Datalog(!=) Queries on Graphs (Extended Abstract)	1994	PODS
3	6,354	Well-Founded Semantics for Extended Datalog and Ontological Reasoning	2013	PODS
4	9,902	Expressiveness within Sequence Datalog	2021	PODS
5	13,323	Adding Disjunction to Datalog (Extended Abstract)	1994	PODS
6	6,746	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS
7	8,142	On the First-Order Expressibility of Recursive Queries	1989	PODS
8	6,919	Expressiveness of Guarded Existential Rule Languages	2014	PODS
9	13,374	Datalog Expressiveness of Chain Queries: Grammar Tools and Characterizations	1992	PODS
10	2,822	Inductive Pebble Games And The Expressive Power Of Datalog	1989	PODS