Combinatorial Games in Database Theory

Summary: Survey of combinatorial games—Ehrenfeucht–Fraïssé, pebble games, and monadic-NP games—as core tools for characterizing the expressive power of rule-based query languages. Shows representative applications to relational calculus, Datalog, and fixpoint logics and pinpoints methodological limitations. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1050
Venue: PODS
Year: 1995
Pagerank: 5.093636e-05
Overall Rank: 12,986 | 10.91%
DOI: 10.1145/212433.212461

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Phokion G. Kolaitis (University of California Santa Cruz)

BibTeX Citation

@inproceedings{kolaitis_pods95,
        address = {New York, NY, USA},
        series = {{PODS} '95},
        title = {{Combinatorial Games in Database Theory}},
        url = {https://dl.acm.org/doi/10.1145/212433.212461},
        doi = {10.1145/212433.212461},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Kolaitis, Phokion G.},
        year = {1995}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1,653	Bounds on the Propagation of Selection into Logic Programs	1987	PODS	0.000101081
2,110	Theory of Database Queries (Extended Abstract)	1988	PODS	9.1532803e-05
2,763	Inductive Pebble Games And The Expressive Power Of Datalog	1989	PODS	8.1537086e-05
3,800	On the Expressive Power of Datalog: Tools and a Case Study	1990	PODS	7.1130834e-05
6,209	On Datalog vs. Polynomial Time	1991	PODS	5.9425753e-05
6,690	Can Datalog be approximated?	1994	PODS	5.8012926e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,235	Relational Specifications of Infinite Query Answers	1989	SIGMOD
2	1,856	Automata Theory for Database Theoreticians	1989	PODS
3	6,286	Finite Queries do not Have Effective Syntax	1995	PODS
4	11,525	Data Path Queries over Embedded Graph Databases	2022	PODS
5	13,022	Tutorial: Languages for Collection Types	1994	PODS
6	6,278	Constraint Satisfaction and Database Theory: a Tutorial	2000	PODS
7	2,241	Finitely Representable Databases	1994	PODS
8	2,763	Inductive Pebble Games And The Expressive Power Of Datalog	1989	PODS
9	2,110	Theory of Database Queries (Extended Abstract)	1988	PODS
10	12,487	The Finite Model Theory Toolbox of a Database Theoretician	2009	PODS