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: 1027
Venue: PODS
Year: 1994
Pagerank: 5.7073076e-05
Overall Rank: 7,086 | 51.39%
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,702	On the Complexity of Nonrecursive XQuery and Functional Query Languages on Complex Values	2005	PODS	6.5549225e-05
6,193	Incremental View Maintenance For Collection Programming	2016	PODS	5.9471978e-05
7,339	Any Algorithm in the Complex Object Algebra with Powerset Needs Exponential Space to Compute Transitive Closure	1994	PODS	5.6393827e-05
7,849	New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions	1994	PODS	5.5324391e-05
13,022	Tutorial: Languages for Collection Types	1994	PODS	5.093636e-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
782	FAD, a Powerful and Simple Database Language	1987	VLDB	0.00014080876
1,864	The Expressiveness of a Family of Finite Set Languages	1991	PODS	9.5928463e-05
2,130	Normal Forms and Conservative Properties for Query Languages over Collection Types	1993	PODS	9.1244275e-05
2,248	Database Programming in Machiavelli - a Polymorphic Language with Static Type Inference	1989	SIGMOD	8.8703718e-05
2,701	Possibilities and Limitations of Using Flat Operators in Nested Algebra Expressions	1988	PODS	8.240179e-05
2,986	Tractable Query Languages for Complex Object Databases	1991	PODS	7.8912631e-05
3,299	SVP - a Model Capturing Sets, Streams, and Parallelism	1992	VLDB	7.5418401e-05
8,569	The Power of Methods With Parallel Semantics	1991	VLDB	5.4107086e-05

Semantically Similar Papers

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