データベース理論において、連言問合せ（れんげんといあわせ、）は、論理積演算子を用いた一階論理問合せの制限された形式である。多くの一階論理問合せは連言問合せとして書ける。特に、関係データベースに対して発行される問合せの大部分はこの形式で表現できる。連言問合せはまた、より大きな問合せクラス（例えば関係代数問合せ）が共有しない多くの望ましい理論的性質を持つ。
定義 連言問合せは、（領域独立の）一階論理の、原子論理式から論理積 ∧ と存在量化 ∃ を用いて構成でき、論理和 ∨、否定 ¬、全称量化 ∀ を用いずに構成される論理式の集合として与えられる断片である。それぞれのそのような論理式は同値な冠頭標準形の論理式に（効率的に）書き直せるので、この形式は通常単純に仮定される。
したがって連言問合せは次の一般形をとる。
ここで自由変数 は区別変数、束縛変数 は非区別変数と呼ばれる。 は原子論理式である。
連言問合せは関係データベースに頻繁に発行される問合せの大部分を表現できる。たとえば、学生・その住所・受講科目・性別の情報を格納する関係データベースを想定する。女子学生も受講しているある科目を受講している男子学生とその住所すべてを見つけることは、次の連言問合せで表される。
(student, address) . ∃ (student2, course) . attends(student, course) ∧ gender(student, 'male') ∧ attends(student2, course) ∧ gender(student2, 'female') ∧ lives(student, address)
関心のあるエンティティは男子学生とその住所のみなので、それらだけが区別変数であり、変数 course, student2 は存在量化のみ、すなわち非区別変数である。
断片 区別変数を持たない連言問合せはと呼ばれる。すべての変数が区別変数である（束縛変数がない）連言問合せは等結合問合せと呼ばれるDan Olteanu, Jakub Závodný, Size Bounds for Factorised Representations of Query Results, 2015, DOI 10.1145/2656335。これはにおける、関係代数の問合せの等価物である（結果のすべての列を選択する場合）。
他の問合せ言語との関係 連言問合せは、関係代数における選択・射影・結合問合せ（すなわち和や差の演算を用いない関係代数問合せ）と、SQL の select-from-where 問合せで where 条件が原子等式条件の連言のみを用いるもの（すなわち列名と定数から「=」以外の比較演算子を用いず「and」で結合されて構成される条件）とに対応する。集約や副問合せは含まない。上記の問合せは、たとえば SQL の連言問合せ断片として次のように書ける。
select l.student, l.address from attends a1, gender g1, attends a2, gender g2, lives l where a1.student = g1.student and a2.student = g2.student and l.student = g1.student and a1.course = a2.course and g1.gender = 'male' and g2.gender = 'female';
Datalog 論理的表記のほか、連言問合せはDatalog 規則としても書ける。多くの著者は、実際には上記の問合せについて次の Datalog 表記のほうを好む。 result(student, address) :- attends(student, course), gender(student, male), attends(student2, course), gender(student2, female), lives(student, address). この表記には量化子はないが、規則の頭部（head）に現れる変数はやはり暗黙に全称量化され、規則の本体（body）にのみ現れる変数は暗黙に存在量化されている。
いかなる連言問合せも Datalog 規則として書けるが、あらゆる Datalog プログラムを連言問合せとして書けるわけではない。実際、外延述語記号上の単一規則のみが同値な連言問合せに容易に書き換えられる。与えられた Datalog プログラムに対して、同値な非再帰プログラム（正の関係代数問合せ、あるいは同値な正の存在的一階論理論理式、特殊例として連言問合せ）が存在するかを判定する問題は Datalog 有界性問題として知られ、決定不能であるGerd G. Hillebrand, Paris C. Kanellakis, Harry G. Mairson, Moshe Y. Vardi: Undecidable Boundedness Problems for Datalog Programs. J. Log. Program. 25(2): 163-190 (1995)。
拡張 より大きなを捉える連言問合せの拡張には次のものがある。
連言問合せの和（正の（すなわち否定を含まない）関係代数と同値） 和と否定で拡張された連言問合せ（により関係代数および一階論理に対応） 組込み述語（算術述語など）を持つ連言問合せ 集約関数を持つ連言問合せ
これらすべての拡張の形式的研究は、関係データベースにおける応用によって正当化され、データベース理論の領域に属する。
計算量
連言問合せの評価の計算量の研究では、二つの問題を区別しなければならない。第一は、関係データベース上での連言問合せの評価問題であり、問合せとデータベースの双方が入力の一部と見なされる。この問題の計算量は通常「総合計算量（combined complexity）」と呼ばれ、問合せが固定と仮定される場合の関係データベース上の問合せ評価問題の計算量は「データ計算量（data complexity）」と呼ばれる。
連言問合せは総合計算量に関してはNP完全であるAshok K. Chandra and Philip M. Merlin, 1977. Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC '77.。他方、連言問合せのデータ計算量は非常に低く、並列計算量クラスに属し、これは、したがって多項式時間に含まれる。連言問合せのNP困難性は驚くべきことに思えるかもしれない。関係代数やSQL は厳密に連言問合せを包含し、したがって少なくとも同程度に難しい（実際、関係代数は総合計算量に関してはPSPACE完全である）ためである。しかし通常の応用シナリオでは、データベースは大規模で問合せは非常に小さく、それらの困難さを研究し記述するにはデータ計算量モデルが適切であろう。
非真偽の連言問合せへのすべての解を列挙する問題は、の文脈で研究されており、（一定のの下で）線形時間の前処理と各解の間で定数時間の遅延で列挙できる問合せの特徴づけが得られている。具体的にはこれらは非循環的連言問合せであって、さらに「自由連結（free-connex）」条件を満たすものである。
形式的性質 連言問合せはデータベース理論の大きな成功例のひとつであり、より大きな問合せクラスにとっては計算的に困難であるかである多くの興味深い問題が、連言問合せについては解決可能であるSerge Abiteboul, Richard B. Hull, Victor Vianu: Foundations of Databases. Addison-Wesley, 1995.。たとえばを考える。同じスキーマの二つのデータベース関係 について、 と書くのは、 に現れる各タプルが にも現れる場合、かつその場合に限る、というときである。問合せ と関係データベースインスタンス が与えられたとき、インスタンス上での問合せ評価の結果関係を単に と書く。二つの問合せ と およびデータベーススキーマが与えられたとき、問合せ包含問題は入力データベーススキーマ上のあらゆる可能なデータベースインスタンス について が成り立つかを判定する問題である。問合せ包含の主な応用は問合せ最適化にある。二つの問合せが同値かどうかは、単に相互包含を確認することで判定できる。
問合せ包含問題は関係代数と SQL に対しては決定不能だが、連言問合せに対しては決定可能かつNP完全である。実際、連言問合せの問合せ包含問題は問合せ評価問題とまったく同じ問題であることが分かる。問合せは小さい傾向にあるので、ここでの NP完全性は通常許容されると考えられている。連言問合せの問合せ包含問題はまた制約充足問題と同値である。
多項式時間の総合計算量を持つ連言問合せの重要なクラスに非循環的連言問合せがあるMihalis Yannakakis: Algorithms for Acyclic Database Schemes. Proc. VLDB 1981: 82-94.。問合せ評価、したがって問合せ包含はLOGCFL完全であり、したがって多項式時間内であるGeorg Gottlob, Nicola Leone, Francesco Scarcello (2001). "The complexity of acyclic conjunctive queries". Journal of the ACM 48 (3): 431–498. .。連言問合せの非循環性は、問合せのハイパーグラフに関して定義される、問合せの構造的性質である。連言問合せが非循環的であるのは、そのハイパーツリー幅が 1 の場合、かつその場合に限る。
非循環性の重要な一般化がの概念であり、これはグラフにおける有界に類似して、ハイパーグラフが非循環的にどれだけ近いかを測る指標である。有界木幅の連言問合せは LOGCFL 総合計算量を持つGeorg Gottlob, Nicola Leone, Francesco Scarcello: Hypertree Decompositions and Tractable Queries. J. Comput. Syst. Sci. 64(3): 579-627 (2002)。
木データ上の制限のない連言問合せ（すなわち、木の二項子関係と木ノードのラベル付けのための単項関係からなる関係データベース）は多項式時間の総合計算量を持つGeorg Gottlob, Christoph Koch, Klaus U. Schulz: Conjunctive queries over trees. J. ACM 53(2): 238-272 (2006)。
脚注
外部リンク , Presentation on structural decomposition methods for the efficient evaluation of conjunctive queries (PDF)