Conjunctive Query

Horn clause query; SPC query

Conjunctive queries are first-order queries that both practically expressive and algorithmically relatively tractable. They were studied first in [2] and they have played an important role in database systems since then.

As a subset of the relational calculus, conjunctive queries are defined by formulae that make only use of atoms, conjunction, and existential quantification. As such they are closely related to Horn clauses and hence to logic programming. A single Datalog rule can be seen as a conjunctive query [1].

Optimization and reformulation for various purposes is quite feasible for conjunctive queries, as opposed to general relational calculus/algebra queries. The equivalence (and indeed the containment) of conjunctive queries is decidable, albeit NP-complete [1].

This entry uses terminology defined in the entry Relational Calculus.

Conjunctive queries are first-order queries of a particular form: {〈e₁, … , e_n〉 ∣ ∃ x₁...

Authors and Affiliations

1. Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA, USA

   Val Tannen

Corresponding author

Correspondence to Val Tannen .

Editors and Affiliations

1. Georgia Institute of Technology College of Computing, Atlanta, GA, USA

   Ling Liu

2. University of Waterloo School of Computer Science, Waterloo, ON, Canada

   M. Tamer Özsu

1. Dept. of Computer and Inf. Science, Univ. of Pennsylvania, Philadelphia, PA, USA

   Val Tannen

Reprints and permissions

© 2018 Springer Science+Business Media, LLC, part of Springer Nature

Policies and ethics