Does reversing two logical conjuncts change their truth value?

No, for ordinary logical conjunction. It can still change the work required by a particular evaluation procedure.

Should the smallest relation always be evaluated first?

Not necessarily. Predicate cost, indexes, shared variables, and already-known bindings can change the best order.

Is this only a database issue?

No. Similar choices arise when matching inference-rule premises and evaluating relational goals in logic programming.

AI Glossary / Graphs and symbolic AI / Intermediate

Conjunct ordering

Definition

Conjunct ordering is the choice of the sequence in which a reasoning or query system evaluates conditions joined by logical AND. Equivalent logical orders can require very different amounts of computation. A useful ordering restricts candidate variable assignments early, so later conditions are checked against fewer possibilities while preserving the intended answers.

What it means

A rule premise such as Archived(x) AND Tagged(x) contains two conjuncts that must both hold for the same object x. As a logical formula, reversing their order does not change its meaning.

An implementation still needs a way to find matching objects. It might enumerate archived objects and test whether they are tagged, or enumerate tagged objects and test whether they are archived. If one group is much smaller and both tests are efficient, the second approach can require much less work.

The issue is therefore operational rather than a change to the truth conditions of AND. It appears in inference-rule matching, logic programming, and database-style joins, where the intermediate candidate sets can dominate cost.

How it works

The system considers the available predicates, current variable bindings, indexes, and estimates of how many matches each condition will produce. A condition with few matching candidates may be a good starting point, especially when its results bind variables used by later conditions.

After one conjunct is evaluated, each compatible binding is passed to the next. That next condition can extend, filter, or reject the binding. Shared variables must retain consistent values across the entire conjunction.

Selectivity alone is not the complete cost model. An apparently restrictive condition may be expensive to evaluate, while a larger indexed relation may be cheap to access. The best order can also change after some variables have already been bound.

For pure logical conditions, a valid reordering preserves the answers. In a programming system with side effects, arithmetic requirements, cuts, or other control behavior, moving goals can change execution or even correctness. Those operational restrictions must be respected rather than justified by logical commutativity alone.

Three practical examples

1. A rule engine starts with a rare document tag before checking a broad archived-status predicate, reducing the number of candidate documents it examines.

2. A query optimizer selects a join order that keeps intermediate result sets small instead of combining large relations unnecessarily early.

3. A logic-program developer arranges a pure relational query so an early goal binds an identifier used efficiently by subsequent lookups.

Think of it this way

Think of searching a filing cabinet by applying useful filters in an efficient order. If only a few records have a rare marker, starting with that marker can avoid inspecting a much larger group first.

The analogy has limits. In formal queries, conditions may share several variables, create new bindings, or have different access costs. A filter's apparent narrowness does not alone determine the best execution order.

Worked example

Suppose a toy knowledge base contains 800 archived documents and 20 tagged documents. Exactly 8 belong to both groups. We want every x satisfying Archived(x) AND Tagged(x).

Assume either group can be enumerated at one work unit per member, and membership in the other group can be tested through an index at one additional unit per candidate. Ignore fixed setup costs.

Starting with Archived enumerates 800 candidates and performs 800 Tagged lookups, for 1,600 units. Starting with Tagged enumerates 20 candidates and performs 20 Archived lookups, for 40 units. Both orders return the same 8 document identifiers under the stated assumptions.

The ratio of these modeled costs is 40, but that is not a measured speedup. Different indexes, storage behavior, or predicate costs could change the comparison.

The shared x is essential: finding one archived document and a different tagged document would not satisfy this query. Each successful binding must make both conditions true for the same document.

Illustrative case study

Fictional case: Fir Knowledge uses the two-predicate query in a rules demonstration. A slow trace begins by enumerating the larger archived collection even though the tagged collection has an efficient index.

The team compares both orders under the simplified cost model and confirms that the resulting identifier sets agree. It then evaluates the actual implementation separately, because the example's work-unit assumptions do not establish real elapsed time.

The case illustrates an optimization opportunity and a correctness check. It does not claim production performance results or imply that rarest-first is universally optimal.

Common misconceptions and mistakes

Do not confuse changing evaluation order with weakening a conjunction. Every required condition must still be satisfied by a compatible binding.

Do not assume the first written conjunct must execute first in every system. Some engines choose their own execution plan, while others expose goal order directly.

Do not treat rarest-first as an unconditional rule. Access paths, existing bindings, and evaluation costs matter. Also avoid reordering effectful program operations as though they were pure logical predicates.

Business use

For business teams, conjunct ordering explains why two requests with the same logical meaning can have different operational costs. It can help identify whether a slow reasoning workflow is spending time generating avoidable intermediate candidates.

Reviews should compare answer equivalence as well as runtime and resource use. Keep the data distribution and indexing assumptions visible, because a good order for one workload may become poor after the data changes. The useful objective is efficient evaluation of the same requirement, not merely a shorter-looking rule.

Check your understanding

Archived(x) AND Tagged(x) finds an archived record A and a tagged record B, with A different from B. Is that enough to return a match?

Answer: No. The shared variable x requires one compatible object that satisfies both predicates.

Related terms

Conjunction
Predicate (logic)
Forward-chaining
predicate
variable binding
join ordering
query optimization
logic programming
selectivity

Learn next

Add a third predicate to the toy query and compare the sizes of intermediate candidate sets under several orders. Then study indexed joins and goal evaluation to understand how bound variables and access costs influence the planner's choices.

Sources

Russell and Norvig, Artificial Intelligence: A Modern Approach, Inference in First-Order Logic: https://aima.cs.berkeley.edu/4th-ed/pdfs/newchap09.pdf . The primary discussion of conjunct ordering and rule matching was consulted. The document counts, cost assumptions, and fictional performance review are original teaching examples.

Previous: Conjugate transpose Next: Conjunction