The Finite Model Theory Toolbox of a Database Theoretician

Summary: Practical survey presenting a ready-to-use finite model theory toolbox for database theorists, emphasizing usable results (locality, preservation, definability, model-theoretic reductions) rather than proofs or combinatorial games. Equips DB researchers to apply these tools directly to expressiveness, query languages, and complexity/decidability questions. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1477
Venue: PODS
Year: 2009
Pagerank: 5.093636e-05
Overall Rank: 12,487 | 14.33%
DOI: 10.1145/1559795.1559807

Incoming Non-self Citations Over Time

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

Authors

1. Leonid Libkin (University of Edinburgh)

BibTeX Citation

@inproceedings{libkin_pods09,
        address = {New York, NY, USA},
        series = {{PODS} '09},
        title = {{The Finite Model Theory Toolbox of a Database Theoretician}},
        url = {https://dl.acm.org/doi/10.1145/1559795.1559807},
        doi = {10.1145/1559795.1559807},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Libkin, Leonid},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
763	On the Complexity of Bounded-Variable Queries	1995	PODS	0.00014230134
2,180	Monadic Datalog and the Expressive Power of Languages for Web Information Extraction	2002	PODS	9.0110009e-05
4,071	Two-Variable Logic on Data Trees and XML Reasoning	2006	PODS	6.927159e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	14,506	Database Theory: Where Has It Been? Where Is It Going?	1983	SIGMOD
2	2,110	Theory of Database Queries (Extended Abstract)	1988	PODS
3	6,286	Finite Queries do not Have Effective Syntax	1995	PODS
4	14,504	Information Theoretic Aspects Of Data Bases	1983	PODS
5	4,184	On Preservation under Homomorphisms and Unions of Conjunctive Queries	2004	PODS
6	14,249	Database Metatheory: Asking the Big Queries	1995	PODS
7	2,957	Graph-Theoretic Methods In Database Theory	1990	PODS
8	1,856	Automata Theory for Database Theoreticians	1989	PODS
9	2,241	Finitely Representable Databases	1994	PODS
10	12,986	Combinatorial Games in Database Theory	1995	PODS