conjunctive query

1 Overview and definitions

1.1 Definition in database theory

In database theory, a conjunctive query is a logical formula built from atomic predicates (e.g., equality, comparison) that are combined only by the conjunction (AND) operator. Typically, a conjunctive query over a relational database takes the form of a first-order logic expression with existential quantifiers, where each atom references a relation and specifies conditions on its attributes. The query returns all tuples that satisfy every condition simultaneously. Conjunctive queries form the core of many database query languages because they correspond to simple select-project-join operations in relational algebra.

1.2 Definition in information retrieval

In information retrieval, a conjunctive query is a Boolean expression in which all query terms are linked by the AND operator. For a document to be retrieved, it must contain every one of the specified terms. This strict requirement is the foundation of the Boolean retrieval model, one of the earliest and most intuitive models for document search. For example, a query “cat AND dog” returns only documents that contain both words.

1.3 Conjunctive vs. disjunctive queries

A conjunctive query requires all conditions to be true, whereas a disjunctive query (using OR) requires at least one condition to be true. In database systems, disjunctive queries can be more complex to optimize because they may involve union operations. In information retrieval, disjunctive queries increase recall but may reduce precision. Many modern search engines use a hybrid approach, where a conjunctive query is treated as a base filter and then results are ranked by additional relevance measures.

2 Formal syntax

2.1 Relational algebra representation

In relational algebra, a conjunctive query corresponds to a sequence of selection operations (σ) with conditions connected by ∧, followed by projection (π) and possibly join (⨝). For example, the query “find all employees who work in department ‘Sales’ and have a salary greater than 50,000” is expressed as:

π_{employee_name}(σ_{department=‘Sales’ ∧ salary>50000}(Employees))

Only the Cartesian product of joined relations combined with selections over conjunction conditions yields a result set that matches the conjunctive query semantics.

2.2 SQL representation

In SQL, a conjunctive query is naturally expressed by a WHERE clause containing multiple conditions separated by the AND keyword. For instance:

SELECT * FROM Employees WHERE department = ‘Sales’ AND salary > 50000;

Each additional AND condition further restricts the result set. SQL also allows implicit conjunction in join conditions (e.g., in the ON clause), which are evaluated as simultaneous constraints.

2.3 Boolean query model

The Boolean query model formalizes a query as a Boolean expression over a set of terms. Conjunctive queries are a special case where all terms are connected by AND. In this model, the relevance of a document is binary: either all terms are present (match) or not (no match). The model does not assign scores, making it unsuitable for ranking but useful for structured retrieval tasks such as filtering.

3 Semantics and evaluation

3.1 Set semantics

Under set semantics, a conjunctive query returns a set of distinct tuples or documents that satisfy all conditions. Duplicates are eliminated. This is the default semantics in relational database systems (unless otherwise specified) and in Boolean retrieval systems where each document is either in the result set or not.

3.2 Bag semantics

Bag semantics allows duplicate tuples in the result, reflecting the multiplicity of matching records. In databases, bag semantics is common when the query does not include DISTINCT, and in SQL the default is bag semantics. In information retrieval, bag semantics is less common for conjunctive queries, but it appears when evaluating queries over inverted lists that may contain duplicate doc IDs (e.g., from multiple positions of the same term). However, standard retrieval models treat each document once.

3.3 Satisfiability and containment

3.3.1 Homomorphism theorem

A fundamental result for conjunctive queries is the *homomorphism theorem*: a conjunctive query Q1 is contained in another conjunctive query Q2 (Q1 ⊆ Q2) if and only if there exists a homomorphism from the body of Q2 to the body of Q1. This theorem provides a logical characterization of query containment, which is crucial for query optimization and view-based rewriting.

3.3.2 Query containment problem

The query containment problem asks whether the result set of one conjunctive query is always a subset of that of another, for all databases. For conjunctive queries without negation, this problem is NP-complete in general, but tractable for certain subclasses (e.g., queries with no repeated relation symbols). Containment is used to detect redundant queries and to decide whether a query can be answered using materialized views.

4 Applications in information retrieval

4.1 Boolean retrieval systems

4.1.1 Inverted index evaluation

In Boolean retrieval systems, conjunctive queries are evaluated using an inverted index: a data structure mapping each term to a list of document identifiers (postings list). For a conjunction of terms, the system intersects the corresponding postings lists to find documents that appear in all of them. This operation is typically performed by merging sorted lists.

4.1.2 Query optimization for AND queries

Optimization of conjunctive queries in Boolean retrieval includes choosing the order of term processing to minimize the number of comparisons. The classic approach is to process the rarest term first (shortest postings list), thereby reducing the size of intermediate candidate sets. Other optimizations include using skip pointers and precomputed intersection counts.

4.2 Limitation of strict conjunction

4.2.1 The need for ranked retrieval

Strict conjunction yields zero results if a document lacks even one query term, which is undesirable for large-scale web search where users may miss relevant documents due to vocabulary mismatch. This limitation motivates ranked retrieval models (e.g., vector space model, BM25) that allow partial matches and assign relevance scores.

4.2.2 Soft conjunctive models (e.g., extended Boolean)

Extended Boolean models relax the strict AND requirement by introducing a notion of proximity or weighting. For example, the p-norm model and fuzzy set models allow query terms to be partially satisfied. In practice, search engines often use a conjunction as a base filter but then apply ranking over the filtered set, effectively implementing a “soft AND”.

5 Optimization techniques

5.1 Term ordering for early termination

When processing a conjunctive query over postings lists, sorting terms by increasing doc frequency (or list length) minimizes the number of comparisons. This heuristic, known as “least frequent term first”, drastically reduces the cost of intersection.

5.2 Skipping and compression strategies

Postings lists can be compressed using techniques such as gap encoding (storing differences between consecutive doc IDs) and variable-byte encoding. Additionally, skip pointers allow the intersection algorithm to skip over large gaps in a list when the other list’s current pointer is far ahead, reducing the number of lookups.

5.3 Index intersection algorithms

5.3.1 Merge-based intersection

The classic merge intersection algorithm takes two sorted postings lists and traverses them with two pointers, advancing the pointer with the smaller doc ID. Whenever both pointers are at the same ID, that ID is output and both pointers advance. This algorithm runs in O(n + m) time, where n and m are the list lengths.

5.3.2 Skip-pointer intersection

To improve upon linear merge, skip pointers (or “skip lists”) allow the algorithm to skip over sections of a list that cannot contain matches. For example, if list A has a skip pointer to doc ID 100 and the current doc ID in list B is 50, the algorithm can jump to the skip target in list A if the next element after the pointer is still ≤ 100. This reduces the number of comparisons, especially when one list is much longer.

6 Extensions and related concepts

6.1 Conjunctive normal form (CNF)

Conjunctive normal form is a Boolean expression where a conjunction of clauses (each clause is a disjunction of literals) is used. In database query optimization, queries are often converted to CNF to allow independent evaluation of each clause. Conjunctive queries are a special case of CNF where each clause contains a single positive literal.

6.2 Conjunctive query with negation

Conjunctive queries may be extended to include negated atoms (e.g., NOT conditions). For example, “SELECT * FROM Employees WHERE department = ‘Sales’ AND NOT (salary < 30000)”. Such queries are still evaluated as a conjunction, but the negation is applied to the selection condition. In Boolean retrieval, NOT terms are handled by excluding documents that contain the negated term.

6.3 Top-k conjunctive queries

A top-k conjunctive query returns the k best results according to a scoring function while still respecting the conjunction semantics. This is common in search engines that first apply a Boolean filter (all query terms must appear) and then rank the remaining documents by, for example, TF-IDF or PageRank. The challenge is to efficiently find the top-k without fully evaluating all candidates.

6.4 Datalog conjunctive queries

Datalog is a declarative logic programming language used for querying deductive databases. A Datalog conjunctive query is a rule of the form q(X) :- r1(X1), r2(X2), ..., rn(Xn), where the body is a conjunction of atoms. Such queries are evaluated by fixpoint iteration or by rewriting into conjunctive SQL queries. Datalog conjunctive queries capture the same expressive power as the relational algebra select-project-join fragment.