Does listing P(a) prove NOT P(b)?

Not in ordinary first-order logic. Additional assumptions, such as a completed definition and suitable identity information, are needed.

Is completion the same as filling missing spreadsheet cells?

No. This entry concerns logical definitions, not estimating missing data values.

Does Clark completion always match stable-model semantics?

No. They are distinct semantics and can differ, especially with recursive definitions.

AI Glossary / Graphs and symbolic AI / Intermediate

Completion

Definition

Completion, in the logical database and rule-program sense, makes explicit that the listed facts or defining rules provide all the ways a specified relation can hold. It typically strengthens one-way implications into an if-and-only-if definition. This supports reasoning about what does not hold under an explicit completeness assumption about that relation.

What it means

A list saying that two objects have a property establishes positive information about those objects. Ordinary first-order logic does not automatically conclude that every unlisted object lacks the property.

Completion adds an only-if direction: an object has the property only through one of the stated cases. For a rule-defined predicate, those cases are the bodies of the rules defining it, combined appropriately.

The supplied term refers to database completion, not language-model text completion, data imputation, or finishing a task. The related Clark completion gives a formal account of completed predicate definitions in logic programming. Its assumptions should be distinguished from the quality or completeness of the real-world evidence stored in a database.

How it works

Start with all the clauses defining a predicate. Standardize their argument positions and account for variables that appear only in rule bodies. Combine the alternative defining conditions using OR, then relate the predicate to that combined condition using if and only if.

For a simple propositional example, rules P if Q and P if R become P if and only if Q OR R. The original rules establish sufficient conditions for P. The added reverse direction says that Q or R must hold whenever P holds.

For factual relations, equality conditions identify the listed tuples. Reasoning that an unlisted name is different from listed names requires appropriate identity assumptions or explicit inequalities. Different names do not automatically denote different objects in unrestricted first-order logic.

Recursive programs require additional care. Completion is not universally interchangeable with minimal-model or stable-model semantics, and it does not guarantee that a particular query procedure terminates or decides every question.

Three practical examples

1. A small catalog model states that the explicitly listed categories are the only categories assigned to each item within that catalog snapshot.

2. A rule designer checks whether a condition is intended as one sufficient route to eligibility or as an exhaustive definition of eligibility.

3. A logic-programming lesson compares ordinary implications with their completed definition to show why additional negative conclusions become available.

Think of it this way

Think of a guest list accompanied by an explicit statement that it lists everyone invited to one particular event. The names alone give positive information; the exhaustive-list statement supplies the basis for excluding others.

The analogy depends on the list actually being authoritative for that event. A partial or outdated list does not become reliable merely because a system treats it as exhaustive.

Worked example

Suppose the database contains archived(report1) and archived(report2). The domain also contains report3, and the three identifiers are stipulated to denote distinct reports.

Without completion, the facts establish that report1 and report2 are archived. They do not establish that report3 is unarchived: a model in which all three are archived still satisfies the two facts.

Complete the predicate with the statement: for every x, archived(x) holds if and only if x equals report1 or x equals report2. Substituting report3 and using the stated inequalities now gives NOT archived(report3).

The negative conclusion depends on the added exhaustive-definition assumption. If report3 is later archived, the completed definition must be updated to include it. Simply adding archived(report3) while retaining the old exhaustive definition would create a contradiction under these identity assumptions.

This example makes the added information visible instead of treating absence from a list as an automatic logical negation.

Illustrative case study

Fictional case: Cedar Records maintains a snapshot of documents archived during a particular processing run. Its internal query model treats the snapshot's archived relation as exhaustive for that run.

A developer applies the same assumption to an incomplete import from another repository and reports every missing document as unarchived. A reviewer identifies the mistake: the source was partial, so its missing entries did not support that conclusion.

The team restricts the completed relation to the authoritative snapshot and keeps the partial import under a different interpretation. The fictional lesson is that completion is a modeling commitment whose scope must follow the evidence source.

Common misconceptions and mistakes

Completion is not just a harmless rewriting of implications. Adding an only-if direction generally strengthens the theory and can produce conclusions unavailable before.

It is not a method for discovering omitted facts. It declares defining cases exhaustive; whether that declaration is justified is a separate question.

Do not assume that every recursive completion determines a unique intended model. For example, completing the sole propositional rule P if P gives P if and only if P, which does not determine P's truth value.

Finally, query failure or a timeout should not be treated casually as classical falsity. The relationship between negation as failure and completion depends on the program and procedural conditions.

Business use

For business rule systems, completion helps clarify whether a policy definition lists all qualifying cases or merely some known sufficient cases. That difference can change who or what is excluded by a query.

Record which predicates are treated as exhaustively defined, the scope and date of their source data, and how updates revise the completed theory. Test unlisted cases explicitly. When integrating partial sources, preserve unknown status unless the application has a justified basis for treating absence as negative information.

Check your understanding

Why could NOT archived(report3) be inferred only after completion in the worked example?

Answer: Completion added that report1 and report2 were the only archived reports, and report3 was explicitly distinct from both. The original positive facts alone did not exclude it.

Related terms

Closed-world assumption
Stable model
Clark completion
predicate definition
negation as failure
logical database
equality
open-world assumption

Learn next

Convert two rules with the same head into one completed definition. Compare its models with those of the original implications. Then examine a recursive rule to see why completion does not always select the intended minimal interpretation.

Sources

Primary sources consulted: Robert Kowalski, Logic Programming, section on Clark completion, https://www.doc.ic.ac.uk/~rak/papers/History.pdf ; Abiteboul, Hull, and Vianu, Foundations of Databases, negation and completion discussion, https://cs.uwaterloo.ca/~david/fdb/D.pdf . The supplied AIMA index identifies the database sense. Examples are original.

Previous: Completeness Next: Complex inverse Wishart distribution