nucleation

LIT-1088: On Closed World Data Bases

2 min read

Properties4
StatusActive — read in full 2026-10-15 from the author's preprint as presented at the 1977 Toulouse workshop, University of British Columbia Department of Computer Science Technical Report 77-16 (October 1977), served by UBC's technical-report archive (www.cs.ubc.ca/sites/default/files/tr/1977/TR-77-16.pdf); the published Plenum chapter (pp. 55–76) is closed (Unpaywall and OpenAlex: closed; Semantic Scholar: no open PDF) and was not seen. Worth reading as the source of the open/closed-world distinction and of the closed-world assumption as a formal object: add the negation of every ground atom the database does not entail, a convention Reiter says "presumes total knowledge about the domain". It shows that closed-world evaluation of any existential query reduces to open-world evaluation of atomic queries when the database stays consistent under the assumption, that consistent Horn and all definite databases do, and that a disjunctive database such as Pa ∨ Pb does not. For CLAIM-306 it supplies the definition and the completeness assumption (stated, not proved as a soundness condition; a formal soundness result would be Clark's), and nothing about search time: non-entailment is a fixed relation, so "a closed-world assumption taken on a time bound" is the record's extension. It also cuts against reading CASE-085 as a closed-world inference: a medic who knows the item is stocked holds a disjunction over compartments, Reiter's Example 5.1, where the assumption is inconsistent.
Tagslogic
Cited as “paper” byNOTE-899 — Reiter — On closed world data bases
Cited as “source” byTHEORY-341 — Inferring not-P from failure to prove P is a deduction only under two separate conditions: Clark shows that when every branch of the search for a proof of P ends in failure, not-P is a theorem of the completed database, and a search that does not finish licenses nothing; Reiter's closed-world assumption, adding the negation of every ground atom the database does not entail, keeps a consistent Horn database consistent and can make a disjunctive one inconsistent

Graph View

Reiter, R. (1978). On closed world data bases. In H. Gallaire and J. Minker (eds.), Logic and Data Bases, pp. 55–76. New York: Plenum. DOI 10.1007/978-1-4684-3384-5_3

Key takeaways

Read in full (NOTE-899), from Reiter’s 1977 workshop report, not the printed chapter. Reiter defines the closed-world assumption (CWA) for a function-free first-order database as reasoning from DB together with the negation of every ground atom that DB does not entail, and contrasts it with the open-world assumption (OWA), under which only what DB entails is an answer. He shows that, when DB with these added negations is consistent, closed-world evaluation of any existential query reduces to ordinary (open-world) evaluation of atomic queries combined by union, intersection, difference and projection, so the negations never need to be listed. The CWA can make a consistent database inconsistent (Pa ∨ Pb yields ¬Pa and ¬Pb); consistent Horn databases, and all definite databases, stay consistent. Nothing in the paper concerns how long a search takes: non-entailment is a fixed logical relation, and the CWA’s justification is stated as an assumption of total knowledge of the domain, not proved as a soundness condition.

Why this is here

CLAIM-306: the medic’s “If I can’t find it, it isn’t there” (CASE-085) acts on a failed search as if it showed absence. This is the inference, and its soundness condition is the one CLAIM-306 needs.

Backlinks