Space-Bounded FOIES

Summary: Characterize space of FOIES by maximal auxiliary arity k; define FOIES_k and prove tight arity bounds and separations for standard graph queries via Ehrenfeucht–Fraïssé arguments. Show undirected transitive closure requires k=2, resolving Patnaik–Immerman PODS'94 open problem. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1062
Venue: PODS
Year: 1995
Pagerank: 5.093636e-05
Overall Rank: 12,988 | 10.90%
DOI: 10.1145/212433.220204

Incoming Non-self Citations Over Time

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

Authors

1. Guozhu Dong (University of Melbourne)
2. Jianwen Su (University of California Santa Barbara)

BibTeX Citation

@inproceedings{dong_pods95,
        address = {New York, NY, USA},
        series = {{PODS} '95},
        title = {{Space-Bounded FOIES}},
        url = {https://dl.acm.org/doi/10.1145/212433.220204},
        doi = {10.1145/212433.220204},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Dong, Guozhu and Su, Jianwen},
        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
39	Efficiently Updating Materialized Views	1986	SIGMOD	0.00047309646
61	Maintaining Views Incrementally	1993	SIGMOD	0.00039026867
2,241	Finitely Representable Databases	1994	PODS	8.8845324e-05
2,530	Incremental Evaluation of Rules and its Relationship to Parallelism	1991	SIGMOD	8.458663e-05
5,106	Dyn-FO: A Parallel, Dynamic Complexity Class (Preliminary Version)	1994	PODS	6.3625152e-05
5,729	Maintenance of Stratified Databases Viewed as a Belief Revision System	1987	PODS	6.1072031e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,841	Querying Big Data by Accessing Small Data	2015	PODS
2	4,425	EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract)	1987	PODS
3	143	Optimization of Nonrecursive Queries	1986	VLDB
4	7,028	Semantic Acyclicity on Graph Databases	2013	PODS
5	8,141	First-Order Query Evaluation with Cardinality Conditions	2018	PODS
6	12,920	Dynamic Tree Isomorphism via First-order Updates to a Relational Database	1998	PODS
7	11,753	The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs	2020	PODS
8	5,041	Enumeration of First-Order Queries on Classes of Structures With Bounded Expansion	2013	PODS
9	5,982	Size and Treewidth Bounds for Conjunctive Queries	2009	PODS
10	4,063	Enumeration for FO Queries over Nowhere Dense Graphs	2018	PODS