The Boolean Retrieval Model

Which of Shakespeare's plays contain Brutus and Caesar but not Calpurnia? Written as a query, the question is

Brutus AND Caesar AND NOT Calpurnia

and the answer is a set of plays, every one of which satisfies the condition exactly. There is no "best" match and no ranking, and a play that mentions Calpurnia once in passing is excluded as firmly as one about her. This is the Boolean retrieval model, the first model in the course and the one that large commercial search services offered as their main or only option for three decades, until the early 1990s (Manning, Raghavan, and Schütze, 2008, §1.4). This article defines the model and its evaluation, works several queries through by hand, then explains why its exactness is both its main strength and its main weakness.

The model

The model has three parts.

Documents are sets of terms. A document is represented only by which index terms it contains. How often a term occurs, where it occurs, and how long the document is are all ignored.

Queries are Boolean expressions. Terms are combined with three operators:

• A AND B matches documents that contain both $A$ and $B$;
• A OR B matches documents that contain $A$, $B$, or both;
• NOT A matches documents that do not contain $A$.

Parentheses group subexpressions, as in (Brutus OR Cassius) AND Caesar.

Retrieval is satisfaction. A document is retrieved if and only if the query expression is true when each term is replaced by true or false according to whether the document contains it.

Because each term corresponds to the set of documents containing it, the operators correspond exactly to set operations. Writing $D$ for the whole collection and $P(t)$ for the set of documents that contain term $t$, its postings,

$$P(A \text{ AND } B) = P(A) \cap P(B), \qquad P(A \text{ OR } B) = P(A) \cup P(B), \qquad P(\text{NOT } A) = D \setminus P(A).$$

The result of any query is therefore a set built from the postings of its terms by intersection, union, and difference, and the algorithms for computing those operations efficiently are the subject of intersecting postings lists.

The representation is the important simplification. Once a play is reduced to the set of words it contains, two plays with the same vocabulary are indistinguishable, and a word used once counts the same as a word used a hundred times. Every strength and weakness discussed below follows from that choice.

Evaluating a query with the incidence matrix

The term-document incidence matrix makes the correspondence concrete. It has a row for each term and a column for each document, with a 1 where the document contains the term. Each term's row is a bit vector with one bit per document, and each document's column is the set of terms it contains. The inverted index article shows the full matrix for seven terms and six plays, from Manning, Raghavan, and Schütze (2008, Figure 1.1). Read down the columns, it gives each play as a set:

To evaluate a query, read the rows instead. With the plays ordered Antony and Cleopatra, Julius Caesar, The Tempest, Hamlet, Othello, Macbeth, the rows for the opening query are

NOT complements a vector, and AND and OR become bitwise operations, computed one position at a time:

Brutus              110100
Caesar              110111
NOT Calpurnia       101111
AND of all three    100100

The 1s in positions 1 and 4 give the answer: Antony and Cleopatra and Hamlet. Julius Caesar contains all three names and is excluded by the NOT. The answer may be surprising, which shows how a Boolean system interprets a query: Hamlet is retrieved because Polonius mentions having once played Julius Caesar and been killed by Brutus, not because the play concerns either man. The system reports which documents satisfy the expression, not which are about the subject.

Two more queries, step by step

Replacing the first AND with OR, as in Manning, Raghavan, and Schütze's example in §1.3, widens the result:

(Brutus OR Caesar) AND NOT Calpurnia

Brutus                      110100
Caesar                      110111
Brutus OR Caesar            110111
NOT Calpurnia               101111
result                      100111

Four plays now qualify: Antony and Cleopatra, Hamlet, Othello, and Macbeth. Othello and Macbeth mention Caesar but not Brutus, so the OR admits them. One change of operator doubled the result, a small instance of the "feast or famine" behaviour described below.

A NOT can also apply to a whole subexpression. The query from Exercise 1.5 of the same book is evaluated from the inside out:

(Brutus OR Caesar) AND NOT (Antony OR Cleopatra)

Brutus OR Caesar            110111
Antony                      110001
Cleopatra                   100000
Antony OR Cleopatra         110001
NOT (Antony OR Cleopatra)   001110
result                      000110

The answer is Hamlet and Othello. Each line is a single machine operation on a word of bits, which is why bitmap evaluation is fast: a 64-bit processor combines 64 documents per instruction. All numbers in this section are computed by tools/experiments/boolean/boolean_model.py.

Bitwise evaluation is fast, but as the inverted index article explains, the matrix is far too large and sparse to store for a real collection. Practical systems evaluate the same set operations on sorted postings lists instead.

Queries as regions of a Venn diagram

Three terms divide the collection into eight regions, one for each combination of contains and does not contain. Each play falls into exactly one region, determined by its column of the matrix.

The table is a truth table for the query, with the documents sorted into its rows. It makes two facts visible. First, a Boolean query over three terms can do no more than choose a subset of these eight regions, and every document in a chosen region is retrieved. Two documents in the same region cannot be separated by any query on these terms. There are $2^{8} = 256$ such subsets, so 256 logically different queries can be written with three terms, however the operators are arranged. Second, the shape of the query does not matter, only which regions it selects. (Brutus OR Caesar) AND NOT Calpurnia selects the three regions with Brutus or Caesar but no Calpurnia, and the bitwise computation above is just a fast way of finding the documents in them.

Normal forms

Any Boolean expression can be rewritten in two standard shapes. A conjunctive normal form (CNF) query is an AND of OR clauses:

(car OR automobile OR vehicle) AND (insurance OR coverage) AND NOT motorcycle

A disjunctive normal form (DNF) query is an OR of AND clauses. The Venn diagram gives DNF a direct meaning: each fully specified region, such as Brutus AND Caesar AND NOT Calpurnia, is an AND clause, and any query is the OR of the regions it selects.

CNF is the natural form for how expert searchers write queries. Each OR clause gathers the synonyms and variants for one concept of the information need, and the ANDs require every concept to be present. It is also convenient for evaluation, because each clause can be computed once and the clauses intersected in an efficient order, as described in optimizing Boolean queries.

Converting between the forms uses the distributive law, $X \wedge (Y \vee Z) = (X \wedge Y) \vee (X \wedge Z)$. Exercise 1.6 of Manning, Raghavan, and Schütze (2008) asks for the DNF of the query above. De Morgan's law first turns NOT (Antony OR Cleopatra) into NOT Antony AND NOT Cleopatra, and distributing the remaining AND over the OR gives

(Brutus AND NOT Antony AND NOT Cleopatra) OR (Caesar AND NOT Antony AND NOT Cleopatra)

Brutus AND NOT Antony AND NOT Cleopatra    000100
Caesar AND NOT Antony AND NOT Cleopatra    000110
OR of the two                              000110

The same answer, Hamlet and Othello, but the DNF repeats the two negations and has more operations to perform. The cost of conversion can be far worse. A CNF query of $n$ two-term clauses, $(a_1 \text{ OR } b_1) \text{ AND } \dots \text{ AND } (a_n \text{ OR } b_n)$, has $2n$ term occurrences. Distributing it into DNF produces one AND clause for every way of picking $a_i$ or $b_i$ from each clause, $2^n$ clauses of $n$ terms each:

A professional search with six concepts, each with a pair of synonyms, would become 64 conjunctions. Converting an arbitrary expression to either normal form can make it exponentially longer in this way, so systems usually evaluate the expression as written, as a tree (see parsing and evaluating Boolean queries).

Strengths

The Boolean model persisted in commercial systems for decades, and it remains the default for many professional searchers, for these reasons:

• Control. The searcher states exactly which documents qualify. Nothing is retrieved for reasons the searcher cannot see.
• Predictability and reproducibility. The same query on the same collection always returns the same set. A systematic review can report its search and others can rerun it, as described in search in professional domains.
• Explainability. Every retrieved document can be justified by pointing at the terms that satisfied the query.
• Efficiency. Set operations on sorted lists are fast and need only document identifiers in the index, not frequencies or positions.
• Natural fit for structured conditions. Restrictions such as a date range, a document type, or a jurisdiction are exact conditions, and search engines apply them as Boolean filters, even when they rank the text matches.

Weaknesses

The same exactness creates the model's characteristic problems (Manning, Raghavan, and Schütze, 2008, §1.4).

Feast or famine. Boolean queries tend to return either too many results or too few. A query of a few terms joined by AND may match nothing, and relaxing one AND to an OR may match thousands. Because there is no ranking, a large result set must be read in arbitrary order, and the searcher's only remedy is to add terms until the set is small enough. Finding a query that returns a manageable number of relevant documents takes skill and repeated attempts.

No degrees of match. A document that satisfies four of five ANDed conditions is excluded as completely as one that satisfies none. A document that contains a query term once is treated the same as one that contains it fifty times. In the Venn diagram, every region is either fully in or fully out.

All terms count equally. There is no way to say that one concept matters more than another, except by making it mandatory.

NOT removes relevant documents. A document that mentions an excluded term once, in passing, is lost, even if it is otherwise the best match.

Satisfaction is not relevance. As the Hamlet example shows, a document can satisfy a query without being about its subject, and a relevant document that uses different words fails it. The Boolean model does nothing about the vocabulary mismatch problem beyond what the searcher builds into OR clauses.

William Cooper (1988) argued that these problems are inherent in the model rather than defects of particular systems. Relevance comes in degrees and depends on many weak pieces of evidence, while Boolean logic deals only in strict yes-or-no conditions. Blair and Maron's study of a legal Boolean system, described in search in professional domains, showed the practical consequence: expert searchers believed they had found most relevant documents while actually finding about a fifth of them.

Common misreadings

A few points trip up newcomers to Boolean queries.

• AND narrows, OR widens. In everyday speech, "plays about Brutus and Caesar" can mean plays about either. In a query, AND requires both and shrinks the result, while OR accepts either and grows it. The two example queries above differ by one operator and by a factor of two in result size.
• NOT is relative to the whole collection. NOT Calpurnia alone matches every play without Calpurnia, five of the six here, including The Tempest, which mentions none of the other names. A NOT is useful as a filter on something already selected, which is why systems evaluate X AND NOT Y as a difference rather than computing the complement (see intersecting postings lists).
• Precedence is a convention. Brutus OR Caesar AND Calpurnia means Brutus OR (Caesar AND Calpurnia) in most systems, because AND binds more tightly than OR, but not in all. Parentheses remove the doubt. Parsing and evaluating Boolean queries shows how a parser settles it.

The Boolean model inside ranked systems

The model did not disappear when ranked retrieval replaced it as the default. It survives in three roles:

1. Candidate selection. Ranked systems first gather candidate documents from the postings of the query terms, then score only those candidates. Web search engines typically require all the terms, an implicit AND, while many other engines accept documents containing any of them, an OR, and rely on ranking to order them. Either way, the operations of this topic produce the candidate set.
2. Filters and facets. Structured restrictions are applied exactly, as Boolean conditions on fields.
3. Explicit operators. Quotation marks, minus signs, and advanced-search forms on web search engines are Boolean and phrase operators offered to users who want control.

Boolean search in practice describes these uses, and the vector space model takes up the alternative: a graded score that ranks every document by how well it matches.

References

• Blair, D. C., and Maron, M. E. (1985). An evaluation of retrieval effectiveness for a full-text document-retrieval system. Communications of the ACM, 28(3), 289–299.
• Cooper, W. S. (1988). Getting beyond Boole. Information Processing and Management, 24(3), 243–248.
• Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, sections 1.1, 1.3, and 1.4, and exercises 1.5 and 1.6. Cambridge University Press.