Relational queries computable in polynomial time (Extended Abstract)
Neil Immerman · 1982
Query languages for relational databases have received considerable attention. In 1972 Codd [Cod72] showed that two natural mathematical languages for queries—one algebraic and the other a version of first order predicate calculus—had identical powers of expressibility. Query languages which are as expressive as Codd's Relational Calculus are sometimes called complete. This term is misleading, however, because many interesting queries are not expressible in “complete” languages.