Non-Linear Prefixes in Query Languages

Summary: Introduce non-linear quantifier prefixes (branching and cumulation) for query languages, focusing on monadic quantifiers to control complexity; show branching adds no power over finite models and cumulation none over bounded models. Both give succinct encodings, embed into Libkin's infinitary logic over infinite models, and the paper discusses algorithmic consequences. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1427
Venue: PODS
Year: 2007
Pagerank: 5.0723324e-05
Overall Rank: 12,680 | 13.31%
DOI: 10.1145/1265530.1265556

Incoming Non-self Citations Over Time

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

Authors

1. Antonio Badia (University of Louisville)
2. Stijn Vansummeren (Hasselt University; Transnational University of Limburg)

BibTeX Citation

@inproceedings{badia_pods07,
        address = {New York, NY, USA},
        series = {{PODS} '07},
        title = {{Non-Linear Prefixes in Query Languages}},
        url = {https://dl.acm.org/doi/10.1145/1265530.1265556},
        doi = {10.1145/1265530.1265556},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Badia, Antonio and Vansummeren, Stijn},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

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
2,395	Groupwise Processing of Relational Queries	1997	VLDB	8.6138728e-05
3,725	Providing Better Support for a Class of Decision Support Queries	1996	SIGMOD	7.1515567e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	415	On the Complexity of Database Queries (Extended Abstract)	1997	PODS
2	4,348	Languages for Relational Databases over Interpreted Structures	1997	PODS
3	6,641	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS
4	4,215	An Expressive Language for Linear Spatial Database Queries (extended abstract)	1998	PODS
5	6,593	Functional Database Query Languages as Typed Lambda Calculi of Fixed Order (Extended Abstract)	1994	PODS
6	12,910	String Operations in Query Languages	2001	PODS
7	6,215	Expressive power and data complexity of nonrecursive query languages for lists and trees (Extended Abstract)	2000	PODS
8	14,474	Expressibility of Bounded-Arity Fixed-Point Query Hierarchies	1989	PODS
9	634	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS
10	7,688	Positive Higher-Order Queries	2010	PODS