ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

A Query Language for NC.

Dan Suciu, Val Tannen: A Query Language for NC. PODS 1994: 167-178
@inproceedings{DBLP:conf/pods/SuciuT94,
  author    = {Dan Suciu and
               Val Tannen},
  title     = {A Query Language for NC},
  booktitle = {Proceedings of the Thirteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 24-26, 1994, Minneapolis,
               Minnesota},
  publisher = {ACM Press},
  year      = {1994},
  isbn      = {0-89791-642-5},
  pages     = {167-178},
  ee        = {http://doi.acm.org/10.1145/182591.182610, db/conf/pods/pods94-167.html},
  crossref  = {DBLP:conf/pods/94},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

We show that a form of divide and conquer recursion on sets together with the relational algebra expresses exactly the queries over ordered relational databases which are NC-computable. At a finer level, we relate k nested uses of recursion exactly to ACk, k >= 1. We also give corresponding results for complex objects.

Copyright © 1994 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.


Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Thirteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 24-26, 1994, Minneapolis, Minnesota. ACM Press 1994, ISBN 0-89791-642-5
Contents BibTeX

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 1232 KB]

Journal Edition

Dan Suciu, Val Tannen: A Query Language for NC. J. Comput. Syst. Sci. 55(2): 299-321(1997) BibTeX

References

[AB88]
Serge Abiteboul, Catriel Beeri: The Power of Languages for the Manipulation of Complex Values. VLDB J. 4(4): 727-794(1995) BibTeX
[AV91]
Serge Abiteboul, Victor Vianu: Generic Computation and Its Complexity. STOC 1991: 209-219 BibTeX
[AVV92]
...
[BBKV88]
François Bancilhon, Ted Briggs, Setrag Khoshafian, Patrick Valduriez: FAD, a Powerful and Simple Database Language. VLDB 1987: 97-105 BibTeX
[BBW92]
Val Tannen, Peter Buneman, Limsoon Wong: Naturally Embedded Query Languages. ICDT 1992: 140-154 BibTeX
[BIS90]
David A. Mix Barrington, Neil Immerman, Howard Straubing: On Uniformity within NC¹. J. Comput. Syst. Sci. 41(3): 274-306(1990) BibTeX
[BT92]
...
[BTBN91]
Val Tannen, Peter Buneman, Shamim A. Naqvi: Structural Recursion as a Query Language. DBPL 1991: 9-19 BibTeX
[BTS91]
Val Tannen, Ramesh Subrahmanyam: Logical and Computational Aspects of Programming with Sets/Bags/Lists. ICALP 1991: 60-75 BibTeX
[CFI92]
...
[CH80]
Ashok K. Chandra, David Harel: Computable Queries for Relational Data Bases. J. Comput. Syst. Sci. 21(2): 156-178(1980) BibTeX
[CL90]
Kevin J. Compton, Claude Laflamme: An Algebra and a Logic for NC¹. Inf. Comput. 87(1/2): 240-262(1990) BibTeX
[Clo90]
...
[Coo85]
Stephen A. Cook: A Taxonomy of Problems with Fast Parallel Algorithms. Information and Control 64(1-3): 2-21(1985) BibTeX
[DLW93]
Anuj Dawar, Steven Lindell, Scott Weinstein: Infinitary Logic and Inductive Definability over Finite Structures. Inf. Comput. 119(2): 160-175(1995) BibTeX
[DV91]
Karl Denninghoff, Victor Vianu: The Power of Methods With Parallel Semantics. VLDB 1991: 221-232 BibTeX
[Gur83]
Yuri Gurevich: Algebras of Feasible Functions. FOCS 1983: 210-214 BibTeX
[GV91a]
Stéphane Grumbach, Victor Vianu: Expressiveness and Complexity of Restricted Languages for Complex Objects. DBPL 1991: 111-122 BibTeX
[GV91b]
Stéphane Grumbach, Victor Vianu: Tractable Query Languages for Complex Object Databases. PODS 1991: 315-327 BibTeX
[Imm86]
Neil Immerman: Relational Queries Computable in Polynomial Time. Information and Control 68(1-3): 86-104(1986) BibTeX
[Imm87a]
...
[Imm87b]
Neil Immerman: Languages that Capture Complexity Classes. SIAM J. Comput. 16(4): 760-778(1987) BibTeX
[Imm89]
Neil Immerman: Expressibility and Parallel Complexity. SIAM J. Comput. 18(3): 625-638(1989) BibTeX
[IPS91]
Neil Immerman, Sushant Patnaik, David W. Stemple: The Expressiveness of a Family of Finite Set Languages. PODS 1991: 37-52 BibTeX
[LW94]
Leonid Libkin, Limsoon Wong: Aggregate Functions, Conservative Extensions, and Linear Orders. DBPL 1993: 282-294 BibTeX
[Mos74]
...
[OBB89]
Atsushi Ohori, Peter Buneman, Val Tannen: Database Programming in Machiavelli - a Polymorphic Language with Static Type Inference. SIGMOD Conference 1989: 46-57 BibTeX
[PG88]
Jan Paredaens, Dirk Van Gucht: Possibilities and Limitations of Using Flat Operators in Nested Algebra Expressions. PODS 1988: 29-38 BibTeX
[PG92]
Jan Paredaens, Dirk Van Gucht: Converting Nested Algebra Expressions into Flat Algebra Expressions. ACM Trans. Database Syst. 17(1): 65-93(1992) BibTeX
[PSV92]
Douglas Stott Parker Jr., Eric Simon, Patrick Valduriez: SVP: A Model Capturing Sets, Lists, Streams, and Parallelism. VLDB 1992: 115-126 BibTeX
[Sar92]
...
[SS86]
Hans-Jörg Schek, Marc H. Scholl: The relational model with relation-valued attributes. Inf. Syst. 11(2): 137-147(1986) BibTeX
[Suc94]
Dan Suciu: Bounded Fixpoints for Complex Objects. DBPL 1993: 263-281 BibTeX
[SV84]
Larry J. Stockmeyer, Uzi Vishkin: Simulation of Parallel Random Access Machines by Circuits. SIAM J. Comput. 13(2): 409-422(1984) BibTeX
[TF86]
...
[Var82]
Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 BibTeX
[Won93]
Limsoon Wong: Normal Forms and Conservative Properties for Query Languages over Collection Types. PODS 1993: 26-36 BibTeX

Referenced by

  1. Latha S. Colby, Leonid Libkin: Tractable Iteration Mechanisms for Bag Languages. ICDT 1997: 461-475
  2. Dan Suciu, Limsoon Wong: On Two Forms of Structural Recursion. ICDT 1995: 111-124
  3. Dan Suciu: Domain-Independent Queries on Databases with External Functions. ICDT 1995: 177-190
  4. Val Tannen: Tutorial: Languages for Collection Types. PODS 1994: 150-154
  5. Dan Suciu, Jan Paredaens: Any Algorithm in the Complex Object Algebra with Powerset Needs Exponential Space to Compute Transitive Closure. PODS 1994: 201-209
  6. Leonid Libkin, Limsoon Wong: New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions. PODS 1994: 155-166
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:34:10 2009