Is indexing the same as inference?

No; it organizes access for inference.

Can an unbound query use an index?

A predicate index can still help.

Must every argument be indexed?

No; workload and implementation determine useful choices.

AI Glossary / Graphs and symbolic AI / Advanced

Indexing

Definition

Indexing is the process of organizing a knowledge base so that a reasoning system can fetch potentially relevant facts or rules efficiently. In this entry, it concerns logical knowledge bases: grouping clauses by their predicate and, where useful, by argument values. Indexing narrows the candidates a query must examine; it does not replace the reasoning needed to establish an answer.

What it means

A knowledge base may contain statements about ownership, locations, permissions, and many other relationships. A query about ownership should not usually require testing every location statement first.
Predicate indexing puts clauses with the same predicate into a common group. More selective indexing can distinguish clauses by known arguments, such as the particular item whose owner is requested.
The essential requirement is to retain every clause that could match the query under the system's logical rules. A fast lookup that silently discards a valid match changes the answer rather than merely improving access to it.

How it works

When clauses enter the knowledge base, the system records associations between index keys and clause references. A basic key identifies the predicate and its number of arguments. A more detailed key can include an argument's constant or structured value.
At query time, available bindings determine which keys are useful. Asking who owns parcel7 provides a different opportunity from asking for every ownership relationship, because the first query already identifies an item.
The index returns candidates. Unification then checks whether their terms can consistently match the query, producing variable bindings where appropriate. If a candidate is a rule, its body still needs to be satisfied. Finding the rule's head is not enough to prove its conclusion.
Clauses containing variables need special care. Such a clause may match several specific keys, so indexing must preserve access to it for those queries. Implementations can maintain wildcard candidates or use another sound arrangement.
Index design trades selectivity against construction, storage, and update costs. Combining argument positions can help some workloads, while maintaining every possible combination can be expensive. Adaptive systems may build indexes around observed calls.

Three practical examples

A warehouse assistant asks which recorded location belongs to one parcel. An argument index narrows the location facts before the system checks the requested relationship.
A diagnostic knowledge base retrieves rules whose conclusions concern a particular fault. The reasoning engine must still evaluate those rules' conditions against the available evidence.
A configuration checker asks whether two components share a connector type. Predicate indexing avoids unrelated statements, while subsequent matching enforces the bindings shared across the query.

Think of it this way

Think of sorting a workshop's job cards first by service type and then by equipment identifier. The sorting helps you find promising cards quickly. You must still read them: a general instruction may apply to every machine, and a card's heading does not prove that its conditions hold.

Worked example

Consider an invented knowledge base containing these six ground facts:
owns(ada, parcel7).
owns(ben, parcel8).
owns(ada, parcel9).
stored_at(parcel7, north).
stored_at(parcel8, south).
paired(parcel7, parcel8).
Use Prolog-style notation: lowercase names are constants, uppercase names are variables, and owns has two arguments.
The query owns(Who, parcel7) seeks an owner of parcel7. A scan of all six facts would test unrelated predicates as well. A predicate index identifies the three owns facts as candidates. An index on owns' second argument can narrow the ground-fact candidates to owns(ada, parcel7).
Unification binds Who to ada. The result follows from matching the retrieved fact, not from the mere existence of an index bucket.
Now add the rule owns(custodian, Item) :- unclaimed(Item), together with the fact unclaimed(parcel7). The rule says that the custodian owns an item if it is unclaimed in this invented model. Its variable Item can match parcel7, parcel8, or another item.
A correct indexed lookup for owns(Who, parcel7) must therefore retain both the specific fact and the variable-containing rule as candidates. Checking the rule's body succeeds for parcel7, producing the additional answer Who = custodian. If the index stores this rule under a variable marker that constant lookups never consult, it loses a valid answer.
For owns(Who, parcel8), the rule remains a candidate, but its body has no supporting unclaimed(parcel8) fact in this tiny knowledge base. The supplied facts support Who = ben; retrieval of the rule alone does not support custodian.
Finally, consider paired(X, X). Predicate indexing retrieves paired(parcel7, parcel8). However, unification rejects it: the same X cannot simultaneously equal two different constants. Candidate selection has done useful work without completing the logical check.
These candidate counts illustrate access paths, not measured runtime improvements. The example is too small to establish whether maintaining an additional index pays off.

Illustrative case study

Fictional Cedar Rules adds argument indexing to a support-routing knowledge base. Tests with specific customer facts pass, but a general rule disappears from some answers.
The team finds that constant lookups omit clauses containing a variable in the indexed position. It repairs candidate retrieval and compares answers with an unindexed reference evaluation.
Cedar also tests rule updates and repeated-variable queries. It measures lookup speed only after confirming that the answer sets remain consistent for its test cases.

Common misconceptions and mistakes

“An indexed clause proves the query.” Matching and rule conditions still matter.
“Variables belong only in a separate bucket.” Specific queries must still reach compatible variable-containing clauses.
“Predicate indexing checks all arguments.” It may only select the predicate group.
“Every additional index helps.” Maintenance and storage can outweigh lookup savings.
“Indexing guarantees constant-time reasoning.” Candidate retrieval is only part of evaluation.

Business use

Choose indexes from actual query patterns and bindings. Compare indexed and reference answers, including general rules, updates, deletions, and queries with repeated variables. Track candidate counts alongside end-to-end evaluation time. Keep correctness checks separate from performance measurements so that a missing answer cannot masquerade as a speed improvement.

Check your understanding

Why retain the custodian rule?

Answer: Its variable can match parcel7.

Why is custodian not established for parcel8?

Answer: Its rule condition lacks support here.

Why does paired(X, X) fail?

Answer: Its repeated variable requires identical arguments.

Related terms

Knowledge base
Predicate (logic)
Clause
Unification
predicate
variable binding
query evaluation
argument indexing

Learn next

Remove unclaimed(parcel7), then compare candidates and established answers. Explain why the rule can remain retrievable while its previous conclusion loses support.

Sources

AIMA glossary, indexing: https://github.com/aimacode/aima-glossary/blob/master/glossary.md Russell and Norvig, storage and retrieval in first-order inference: https://aima.cs.berkeley.edu/4th-ed/pdfs/newchap09.pdf SWI-Prolog documentation, just-in-time clause indexing: https://www.swi-prolog.org/pldoc/man?section=jitindex

Previous: Indexed random variable Next: Indian buffet process