LOW-COMPLEXITY AGGREGATION IN GRAPHLOG AND DATALOG

We present constructs for computing aggregate functions over sets of t uples and along paths in a database graph. We show how Datalog can be extended to compute a large class of queries with aggregates without i ncurring the large expense of a language with general set maniputation capabilities. In particular, we aim for queries that can be executed efficiently in parallel, using the claSS Nc and its various subclasses as formal models of low parallel complexity. Our approach retains the standard relational notion of relations as sets of tuples, not requir ing the introduction of multisets. In the case where no rules are recu rsive, the language is exactly as expressive as Klug's first-order lan guage with aggregates. We show that this class of nonrecursive program s cannot express transitive closure (unless LOGSPACE = NLOGSPACE) thus providing evidence for a widely believed but never proven folk result . We also study the expressive power and complexity of languages that support aggregation over recursion. We then describe how these constru cts, as well as manipulating the length of paths in database graphs, a re incorporated into our visual query language GraphLog. While GraphLo g could easily be extended to handle all the queries described above, we prefer to restrict the language in a natural way to avoid explicit recursion; all recursion is expressed as transitive closure. We show t hat this guarantees that all expressible queries are in NC. We analyze other proposals and show that they can express queries that are logsp ace-complete for P and, thus, unlikely to be parallelizable efficientl y.