AI Glossary / Graphs and symbolic AI / Advanced

Predicate indexing

Definition

Predicate indexing organizes facts or clauses by their predicate so a reasoning system can retrieve a relevant group without scanning the entire knowledge base. A query about Supplies, for example, first selects the Supplies group rather than examining unrelated LocatedAt or Approved facts. It is a retrieval technique: it narrows candidates but does not itself prove a query or decide which arguments match.

What it means

A knowledge base may contain many different kinds of assertion. Supplies(Acme, bolts) describes a different relation from LocatedAt(Acme, depot). Grouping assertions by relation lets a system skip those with an incompatible predicate. Within the selected group, it still checks the query's argument requirements. The benefit depends on how much of the knowledge base belongs to that group and what further processing is needed.

How it works

When a fact is added, the system identifies its predicate and places the fact, or a reference to it, in the corresponding index entry. A query uses the same identifying convention to retrieve candidate facts. Matching or unification then determines which candidates can satisfy the query and what variable bindings result.
In a practical implementation, the key may also need arity and namespace information to distinguish relations correctly. Systems can add argument indexes inside a predicate group. For example, after selecting Supplies, an argument index might select only records whose second argument is bolts. That is an additional refinement, not a requirement of simple predicate indexing. Rule-based systems must also consider applicable rules rather than treating the absence of a matching stored fact as proof that no answer can be derived.

Three practical examples

• A supplier knowledge base separates Supplies facts from location facts. A query for suppliers of a part starts with the relevant relationship, then checks the part argument.
• A robot's symbolic state groups At assertions separately from Holding assertions. A query about what a robot holds does not need to examine every location assertion first.
• A rule engine organizes rules by the predicate in their conclusion. When asked to establish a particular relation, it can find potentially relevant rules before examining their premises. Additional reasoning is still required to establish those premises.

Think of it this way

Imagine filing forms by form type before searching for a particular completed form. The 'supplier' drawer saves you from opening the 'location' drawer, but it does not tell you which supplier form contains the requested part. A second arrangement inside the drawer might narrow the search further.

Worked example

Consider a fact-only knowledge base with twelve records. Four use Supplies: Supplies(Acme, bolts), Supplies(Acme, nuts), Supplies(Beta, bolts) and Supplies(Cedar, cable). Five use LocatedAt, and three use Approved. Assume the records are distinct, the predicates have fixed meanings, and the query requests all stored suppliers of bolts.
The query Supplies(x, bolts) has two answers: x = Acme and x = Beta. A simple full-scan procedure examines all twelve records. A predicate-indexed procedure retrieves the four Supplies records and tests their arguments. It avoids examining eight unrelated records, reducing the candidate-record count by eight divided by twelve, or about 66.7%.
Now add an argument index keyed by the supplied part within Supplies. The bolts entry contains two records, so only those two are retrieved. Compared with twelve records, this is an approximately 83.3% reduction in candidates. Compared with the four-record predicate bucket, it halves the candidates. These are counts of records considered, not measured speedups; index lookup, memory access and result construction also take time.
Next add Supplies(Delta, bolts). The knowledge base has thirteen records, the Supplies bucket has five, and the bolts subindex should contain three. A stale subindex that omits Delta would return an incomplete answer even though the fact is stored correctly elsewhere. Index maintenance is therefore part of correctness.
Finally, query Supplies(x, y), with neither argument fixed. The predicate index still selects the five Supplies facts, but the bolts-only subindex cannot supply every answer. Choosing an index must preserve the query's intended result set, not merely minimize the number of records read.

Illustrative case study

In a fictional procurement assistant, the team replaces a full scan with predicate buckets. Tests confirm that supplier queries return the same answers while skipping unrelated location and approval records. The team initially reports the candidate reduction as an equivalent latency improvement, then corrects that claim after measuring actual execution time.
A subsequent update test exposes a different problem: adding Delta updates the main fact store but not the argument index. The assistant silently misses a valid supplier. The team makes updates consistent across the relevant structures and repeats insertion, deletion and unrestricted-query tests.

Common misconceptions and mistakes

Predicate indexing does not infer new facts, rank answers by relevance or make a false statement true. It also does not necessarily isolate one answer: a heavily used predicate may still have a very large bucket.
Do not confuse grouping by predicate with indexing a particular argument. Modern logic systems may use several indexing strategies together. Another error is treating 'no stored matching fact' as equivalent to 'false' without considering inference rules and the knowledge base's treatment of missing information. Finally, inconsistent predicate naming can split one intended relation across separate buckets and produce incomplete retrieval.

Business use

Predicate indexing is useful when structured reasoning repeatedly queries a knowledge base containing many relations. Measure the distribution of records across predicates and the actual query workload before estimating benefits. Check that indexed retrieval preserves results, including after updates. Track memory and maintenance costs alongside response time. If most records share one predicate, argument indexing or other retrieval strategies may matter more than predicate grouping alone. Explicit naming and argument conventions also make the knowledge model easier to maintain.

People also ask

Is predicate indexing the same as database indexing?

It is a particular logical retrieval organization; database indexes can support many other keys and access patterns.

Does it guarantee constant-time query answering?

No. Retrieving a bucket and evaluating all its candidates are different costs.

Can it help when query arguments are variables?

Yes. A known predicate can still select a relevant group even when its arguments are unspecified.

Check your understanding

How many original facts belong to Supplies?

Answer: Four.

Does selecting that bucket immediately answer which suppliers provide bolts?

Answer: No; the argument condition must still be checked.

What goes wrong if Delta is absent from the updated bolts index?

Answer: Retrieval misses a valid stored answer.

Related terms

• Knowledge base
• Predicate (logic)
• Indexing
• Unification
• Inference engine
• predicate
• clause indexing
• argument indexing
• hash table
• query processing

Learn next

Compare queries with a fixed supplier, a fixed part and two variable arguments. Identify which proposed index can preserve all answers in each case, then include update costs in the comparison.

More in Graphs and symbolic AI

• Precomputation - Precomputation means calculating information before the moment it is needed, then storing it for later reuse.
• Precondition - A precondition is a condition that must hold for an action to be applicable in a specified model.
• Precondition axioms - Precondition axioms are logical statements requiring an action's preconditions to hold whenever that action occurs in a planning model.
• Predictive learning - Predictive learning, in the world-model sense associated with Yann LeCun, learns from observations to predict aspects of an environment's future state.
• Preference constraints - Preference constraints express which assignments are more desirable in a constraint problem, rather than simply declaring which assignments are permitted.
• Preference elicitation - Preference elicitation is the process of obtaining information about what a person or group prefers so a system can support decisions on their behalf.

Sources

AIMA glossary, predicate indexing: https://github.com/aimacode/aima-glossary/blob/master/glossary.md SWI-Prolog, Just-in-time clause indexing, for additional argument-based strategies: https://www.swi-prolog.org/pldoc/man?section=jitindex

Previous: Preconditioning Next: Predicate (logic)