A Query Language for NC

Summary: Query language extending relational algebra with divide-and-conquer set recursion that exactly captures NC on ordered relational databases. k nested recursion levels correspond precisely to AC^k; results extended to complex objects. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h49695733ecf140bb
Venue: PODS
Year: 1994
Pagerank: 5.576635e-05
Overall Rank: 7,234 | 51.38%
DOI: 10.1145/182591.182610

Incoming Non-self Citations Over Time

Authors

1. Dan Suciu (University of Pennsylvania)
2. Val Breazu-Tannen (University of Pennsylvania)

BibTeX Citation

@inproceedings{suciu_pods94,
        address = {New York, NY, USA},
        series = {{PODS} '94},
        title = {{A Query Language for NC}},
        url = {https://dl.acm.org/doi/10.1145/182591.182610},
        doi = {10.1145/182591.182610},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Suciu, Dan and Breazu-Tannen, Val},
        year = {1994}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,810	On the Complexity of Nonrecursive XQuery and Functional Query Languages on Complex Values	2005	PODS	6.4049669e-05
6,223	Incremental View Maintenance For Collection Programming	2016	PODS	5.8443814e-05
7,487	Any Algorithm in the Complex Object Algebra with Powerset Needs Exponential Space to Compute Transitive Closure	1994	PODS	5.5102404e-05
8,010	New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions	1994	PODS	5.4060276e-05
13,318	Tutorial: Languages for Collection Types	1994	PODS	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
809	FAD, a Powerful and Simple Database Language	1987	VLDB	0.00013771533
1,921	The Expressiveness of a Family of Finite Set Languages	1991	PODS	9.3737469e-05
2,171	Normal Forms and Conservative Properties for Query Languages over Collection Types	1993	PODS	8.9205772e-05
2,306	Database Programming in Machiavelli - a Polymorphic Language with Static Type Inference	1989	SIGMOD	8.6673254e-05
2,751	Possibilities and Limitations of Using Flat Operators in Nested Algebra Expressions	1988	PODS	8.0523904e-05
3,047	Tractable Query Languages for Complex Object Databases	1991	PODS	7.7108309e-05
3,365	SVP - a Model Capturing Sets, Streams, and Parallelism	1992	VLDB	7.3707699e-05
8,748	The Power of Methods With Parallel Semantics	1991	VLDB	5.2868043e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,483	EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract)	1987	PODS
2	1,818	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS
3	4,230	Completeness Results for Recursive Data Bases	1993	PODS
4	305	A Graphical Query Language Supporting Recursion	1987	SIGMOD
5	7,812	Positive Higher-Order Queries	2010	PODS
6	421	On the Complexity of Database Queries (Extended Abstract)	1997	PODS
7	2,100	Evaluation Of Database Recursive Logic Programs As Recurrent Function Series	1986	SIGMOD
8	9,145	Equivalence of Nested Queries with Mixed Semantics	2009	PODS
9	2,156	A Recursive Algebra and Query Optimization for Nested Relations	1989	SIGMOD
10	13,938	A Dichotomy in the Intensional Expressive Power of Nested Relational Calculi augmented with Aggregate Functions and a Powerset Operator	2013	PODS