PARALLEL COMPLEXITY OF SAMPLE CHAIN QUERIES.

This item is provided by the institution :
National Technical University of Athens

Repository :
Digital Library of National Technical University of Athens | Dspace@NTUA

see the original item page
in the repository's web site and access all digital files if the item^*

Title

PARALLEL COMPLEXITY OF SAMPLE CHAIN QUERIES. (EN)

Creator

Papadimitriou Christos, H (EN)

Afrati, Foto (EN)

Type

conferenceItem (EN)

Conference item (EN)

Issued

2014-03-01T02:40:51Z

1987 (EN)

Year

1987 (EN)

Description

This article discusses parallel complexity issues in chain queries systems and the degree to which such queries are amenable to parallel evaluation. Chain queries are a syntactically simple yet nontrivial class, containing several interesting examples with contrasting parallel complexity. The article reviews the results by Ullman and Van Gelder and proves the Polynomial Stack Theorem for chain rules. Also the article gives a prove of a sequence of P-completeness results which finally carve out all simple chain rules not shown to be in NC by the polynomial stack theorem. (EN)

Subject

COMPUTER PROGRAMMING - Algorithms (EN)

PARALLEL COMPLEXITY (EN)

COMPUTER SYSTEMS, DIGITAL - Parallel Processing (EN)

EXTENDED ABSTRACT (EN)

DATALOG (EN)

PROLOG (EN)

CHAIN QUERIES (EN)

DATABASE SYSTEMS (EN)

Journal

[No source information available] (EN)

Publisher