On Datalog vs. polynomial time

Foto Afrati; Stavros S. Cosmadakis; Mihalis Yannakakis

doi:10.1145/113413.113415

SIGMOD/PODS/ 1991

Conference paper

01 Apr 1991

On Datalog vs. polynomial time

View publication

Abstract

We show that certain monotonie polynomial time queries are not expressible in variants of Datalog. The proof techniques include lower bounds for monotone circuit size and a "Pumping Lemma" for Datalog queries.

Conference paper

Parallel Evaluation of Recursive Rule Queries

Stavros S. Cosmadakis, Paris C. Kanellakis

SIGMOD/PODS 1986

Conference paper

On rewriting Xpath Queries Using Views

Foto Afrati, Rada Chirkova, et al.

EDBT 2009

Conference paper

Tools for datalog boundedness

Gerd G. Hillebrand, Paris C Kanellakis, et al.

SIGMOD/PODS/ 1991

Conference paper

Constraint-based query optimization for spatial databases

Richard Helm, Kim Marriott, et al.

SIGMOD/PODS/ 1991

View all publications

Abstract

Related

Parallel Evaluation of Recursive Rule Queries

On rewriting Xpath Queries Using Views

Tools for datalog boundedness

Constraint-based query optimization for spatial databases