ON DATALOG VS POLYNOMIAL-TIME

Authors
AFRATI F COSMADAKIS SS YANNAKAKIS M
Citation
F. Afrati et al., ON DATALOG VS POLYNOMIAL-TIME, Journal of computer and system sciences, 51(2), 1995, pp. 177-196
Citations number
26
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
51
Issue
2
Year of publication
1995
Pages
177 - 196
Database
ISI
SICI code
0022-0000(1995)51:2<177:ODVP>2.0.ZU;2-B
Abstract
We show that certain monotonic polynomial time queries are not express ible in variants of Datalog. The proof techniques include lower bounds for monotone circuit size and a ''Pumping Lemma'' for Datalog queries . (C) 1995 Academic Press, Inc.