Is a binding list the same as a substitution?

In this context it is a representation of one.

Can a query return several lists?

Yes. Different satisfying assignments can produce separate answers.

Does a binding have to be numeric?

No. It can refer to symbols, structured terms or other variables, depending on the logic system.

AI Glossary / Graphs and symbolic AI / Intermediate

Binding list

Definition

A binding list is a collection of associations between logical variables and the terms or values that replace them. In symbolic reasoning it commonly represents a substitution produced by unification or a query, such as x → Parcel7 and y → Shelf2.

What it means

A logical query can ask for values rather than just a yes-or-no result. Located(x, Shelf2) asks which objects are located on Shelf2. A successful answer may include a binding for x, allowing the caller to identify the object that satisfied the query.

The list records a consistent assignment within a particular reasoning context. It is not a ranked list of probable answers, a permanent change to every variable with the same printed name or a statement that all listed associations describe independent alternatives.

One query can produce several separate binding lists. Each list represents one compatible solution. Combining values from different solutions without checking their relationships can create an answer that the knowledge base never supported.

The word list describes a traditional representation. Implementations may use dictionaries, association lists or internal environments. The important concept is the variable-to-term relationship and how it is applied, not the particular container used by a programming language.

How it works

Unification compares expressions and looks for a substitution that makes their structures agree. Matching Located(x, y) with Located(Parcel7, Shelf2) yields x → Parcel7 and y → Shelf2.

Bindings must remain consistent across repeated occurrences. Pair(x, x) cannot match Pair(Red, Blue) when Red and Blue are distinct constants, because the same x cannot take both values in one substitution. Different variables may share the same value unless an explicit inequality forbids it.

A binding can point to another variable or a compound term, not only a concrete constant. A later binding may require following and composing earlier substitutions. For example, x → y followed by y → Parcel7 makes the resolved value of x Parcel7.

In search, alternative branches need separate environments or careful restoration when backtracking. Variables belonging to different rule uses may need renaming to prevent accidental capture. A failed match must not leave partial bindings that contaminate another candidate.

Finite-term unification also needs to address self-reference. The occurs check prevents binding x to a term containing x, such as Box(x), under ordinary finite-tree semantics. Systems that support cyclic terms have different conventions that must be made explicit.

Three practical examples

A warehouse query returns one binding list for each item and shelf pair satisfying a location relationship.
A grammar parser unifies feature variables so a subject and verb share compatible number features.
A rule-based assistant returns the object identifiers that make a prerequisite rule true, keeping each supported combination together.

Think of it this way

Think of filling named blanks in a form. Every occurrence of the same blank name must receive the same entry within that completed form. Two completed forms can contain different entries without either being inconsistent.

The analogy does not capture all symbolic structure: a logical variable can refer to another variable or a nested term. It also does not mean filling the form creates the facts that justify the entries.

Worked example

Keeping query answers together

Suppose the knowledge base contains Located(Parcel7, Shelf2), Located(Parcel8, Shelf3), and ApprovedShelf(Shelf2). Ask for Located(x, y) AND ApprovedShelf(y).

The first location fact produces {x → Parcel7, y → Shelf2}. Applying that substitution to the second condition gives ApprovedShelf(Shelf2), which succeeds. This binding list is a complete answer.

The second location fact produces {x → Parcel8, y → Shelf3}. The remaining condition becomes ApprovedShelf(Shelf3), for which the stated facts provide no proof. That branch does not yield an answer.

It would be wrong to combine x → Parcel8 from the second branch with y → Shelf2 from the first. The knowledge base does not state that Parcel8 is on Shelf2. The binding list preserves the relationship between values, not merely membership in separate collections.

If the query contains no variables and succeeds, a system may return an empty substitution. That means no replacements are needed. It must be distinguished from failure, even though both can look empty in a poorly designed interface.

Illustrative case study

Fictional case: Cedar Queries displays the results of a compatibility query in two independent dropdowns. It collects all returned product values and all returned accessory values, losing the pairing within each answer.

Users can then select combinations that were never proved compatible. The team changes the interface to preserve complete answer tuples and reruns the actual query when a selection changes.

The lesson is that the structure of a reasoning result carries meaning. Flattening binding lists into unrelated value sets can discard the very constraint the query established.

Common misconceptions and mistakes

Every variable must bind to a unique value distinct from all others. Distinctness requires an additional constraint.
A successful empty substitution means failure. It can represent success with no variables to instantiate.
Unification verifies facts about the world. It establishes structural compatibility; proof and evidence are separate matters.
Values from different answers can be freely mixed. Each answer's bindings must remain consistent together.
Printed variable names are globally shared. Their scope and renaming rules determine identity.

Business use

Binding lists make symbolic answers actionable because they identify which entities satisfy a rule. They are useful wherever a service needs both an explanation and the specific objects involved.

Design result formats that preserve complete substitutions, distinguish no answer from an answer requiring no bindings, and retain identifiers rather than ambiguous display labels. Test repeated variables, multiple solutions and failed branches. If an application paginates results, ensure that each displayed row remains one coherent solution rather than a mixture of values gathered across pages.

Check your understanding

Can Pair(x, x) unify with Pair(A, B) when A and B are distinct constants?

Answer: No. A single substitution would have to give x two conflicting values.

Related terms

Unification
Horn clause
Occur check
Substitution
logical variable
variable scope
backtracking
query answering
occurs check

Learn next

Write three relationship facts and a query with two shared variables. List each candidate substitution, then apply it to every condition. Mark which complete substitutions survive and explain why mixing bindings from rejected and accepted branches is invalid.

Sources

AIMA glossary, binding list and substitution: https://github.com/aimacode/aima-glossary/blob/master/glossary.md?plain=1

AIMA logic implementation documents substitution dictionaries and multiple query answers: https://aima.cs.berkeley.edu/python/logic.html

University of Miami unification notes, including the occurs check: https://www.cs.miami.edu/home/geoff/Courses/TPTPSYS/FirstOrder/Resolution.shtml

The parcel query and fictional interface are original examples.

Previous: Binary variable Next: Binocular disparity