Are the nodes necessarily facts about real objects?

No. They are symbolic expressions or query patterns arranged by a formal generality relation.

Does changing x to z alter the pattern?

Not if the renaming is consistent and preserves which occurrences share a variable.

Does Ships(x,x) match every two-argument Ships fact?

No. It requires compatible identical terms in both positions under the stated syntactic matching rules.

AI Glossary / Graphs and symbolic AI / Advanced

Subsumption lattice

Definition

A subsumption lattice organizes symbolic expressions by how general or specific they are under substitution. In the first-order fact-indexing setting used here, more general query patterns appear above their instances, with links showing specialization. The structure helps explain which queries can match a stored fact and how different query patterns are related. Its exact form depends on the expression language and the ordering convention.

What it means

A pattern such as Ships(x,y) permits two argument positions to vary. Ships(DepotA,y) fixes the sender, while Ships(x,StoreB) fixes the recipient. Ships(DepotA,StoreB) fixes both. These are different ways of asking about the same possible relationship, arranged from less specific to more specific.

The lattice is not a map of actual deliveries or an organization chart. Its nodes are expressions or patterns. Variable names are treated up to consistent renaming, so Ships(x,y) and Ships(u,v) represent the same general pattern when both use distinct variables. Reusing one variable twice, however, imposes a constraint and changes the pattern.

How it works

Choose an expression language and a subsumption order. For the simple atomic patterns here, a pattern subsumes another when substituting for its variables produces the other pattern. Use one direction consistently in the diagram; this entry places general patterns above specific ones.

For a stored ground fact, construct relevant generalizations by replacing suitable terms with variables. Connect patterns through specialization. Where compatible patterns have a most general common instance, unification describes their convergence toward a more specific expression. A common generalization moves in the opposite direction.

An indexing system can associate a stored fact with selected matching patterns or equivalent keys, reducing the need to scan unrelated facts. Maintaining every possible index can be expensive. Repeated constants, shared variables, and nested function terms introduce structures beyond the simplest four-node example, so a flat “replace each argument independently” rule is not universally sufficient.

Three practical examples

Logical database design: organize retrieval by predicate and known argument positions so questions about a named supplier need not scan every relationship.
Theorem-proving education: show how substitutions connect general patterns with particular instances and distinguish matching from informal similarity.
Query-system testing: check that repeated-variable queries enforce equality of their matched terms rather than treating every variable occurrence as an independent wildcard.

Think of it this way

Think of a set of labeled search forms, some with no fields filled in, some with one field fixed, and some with both fixed. More completed fields usually narrow the search. The analogy is limited because repeated variables and function terms create logical relationships that ordinary independent form fields may not express.

Worked example

Consider the original ground fact Ships(DepotA,StoreB), with DepotA and StoreB distinct constant symbols and no function terms or equality reasoning. Its basic matching patterns are Ships(x,y), Ships(DepotA,y), Ships(x,StoreB), and Ships(DepotA,StoreB).

Place Ships(x,y) at the top and the ground fact at the bottom. The two one-constant patterns form the middle level. Ships(DepotA,y) and Ships(x,StoreB) are incomparable: neither can be turned into the other by substituting only its own variables, because each fixes a different constant position.

They do have a common instance. The substitution x→DepotA and y→StoreB makes both patterns Ships(DepotA,StoreB). Their common generalization within this simple arrangement is Ships(x,y). Thus the diagram is a diamond, not a chain.

Now examine a separate fact Ships(DepotA,DepotA). In addition to the patterns obtained by independently replacing each argument, Ships(x,x) matches it. That pattern requires the same term in both positions and does not match Ships(DepotA,StoreB) under ordinary syntactic matching. Treating x's two occurrences as unrelated wildcards would incorrectly accept the latter fact.

This calculation describes a small portion of the symbolic ordering used for indexing. It is not a claim that every collection of arbitrary expressions forms this diamond or that all first-order indexing schemes must explicitly store a lattice.

Illustrative case study

Fictional case: a rule-engine team adds a query asking which service component communicates with itself. Its prototype turns both occurrences of the query variable into independent wildcard fields and returns many ordinary component-to-component records.

The team adds a repeated-variable check after candidate retrieval and creates tests separating same-endpoint from different-endpoint facts. It uses the small subsumption diagram to explain the mistake to reviewers. The fictional case illustrates a correctness issue in pattern matching; it does not claim the team implemented a complete lattice-based index or achieved a measured speed improvement.

Common misconceptions and mistakes

A subsumption lattice is not a taxonomy of real-world object types unless that is the separately defined application. The direction of a diagram matters: authors can reverse the order, changing which operation is described as a meet or join.

Variable renaming is harmless only when it preserves repeated-variable relationships. Unification does not mean two patterns have the same meaning in natural language. Finally, a convenient finite diagram above one fact should not be confused with the full, potentially much larger ordering over a language with function symbols and variables.

Business use

The business relevance is indirect but practical in symbolic knowledge systems: indexing choices affect retrieval speed, storage, and correctness. Identify actual query patterns before maintaining every conceivable index. Queries that usually fix a customer identifier may need different support from queries that compare two argument positions.

Keep candidate retrieval separate from final logical checks. An index may deliberately return a superset of possible matches, but the matching stage must enforce substitutions and shared-variable constraints. Measure the complete query behavior rather than assuming a richer index always performs better.

Check your understanding

Are Ships(DepotA,y) and Ships(x,StoreB) ordered one above the other in the simple example?

Answer: No. They are incomparable middle patterns, although they share the more general Ships(x,y) and the common instance Ships(DepotA,StoreB).

Related terms

Subsumption
Unification
Most general unifier
Generalization
Predicate indexing
substitution
partial order
lattice
logical database

Learn next

Draw the diamond for a two-argument ground fact with distinct constants. Repeat with the same constant in both positions and add the shared-variable pattern. Then introduce a function term and examine why indexing needs more than a choice of fixed argument positions.

Sources

Russell and Norvig, Inference in First-Order Logic, subsumption lattices and fact indexing: https://aima.cs.berkeley.edu/4th-ed/pdfs/newchap09.pdf Scope: the source's first-order query-pattern indexing sense. General-to-specific orientation is stated explicitly. The Ships examples and fictional query-engine case are original illustrations.

Previous: Subsumption architecture Next: Subvocal recognition