A QUERY LANGUAGE FOR NC

Authors
SUCIU D TANNEN V
Citation
D. Suciu et V. Tannen, A QUERY LANGUAGE FOR NC, Journal of computer and system sciences, 55(2), 1997, pp. 299-321
Citations number
48
Categorie Soggetti
System Science","Computer Science Hardware & Architecture","Computer Science Theory & Methods
Journal title
Journal of computer and system sciences → ACNP
ISSN journal
00220000
Volume
55
Issue
2
Year of publication
1997
Pages
299 - 321
Database
ISI
SICI code
0022-0000(1997)55:2<299:AQLFN>2.0.ZU;2-W
Abstract
We show that a form of divide and conquer recursion on sets, together with the relational algebra, expresses exactly the queries over ordere d relational databases which are NC-computable. At a finer level, we r elate k nested uses of recursion exactly to AC(k), k greater than or e qual to 1. We also give corresponding results for complex objects. (C) 1997 Academic Press.