  Distributional compositional (DisCo) models are functors that compute the
meaning of a sentence from the meaning of its words. We show that DisCo models
in the category of sets and relations correspond precisely to relational
databases. As a consequence, we get complexity-theoretic reductions from
semantics and entailment of a fragment of natural language to evaluation and
containment of conjunctive queries, respectively. Finally, we define question
answering as an NP-complete problem.

Computation and Language;Databases;Logic in Computer Science;Category Theory