Fact-checked by Grok 2 weeks ago

Closed-world assumption

The closed-world assumption (CWA) is a foundational principle in knowledge representation, artificial intelligence, and database theory, positing that all relevant facts about a domain are explicitly contained within a given knowledge base or database, such that the absence of a statement implies its falsity.^[1] Formally introduced by Raymond Reiter in his 1977 technical report "On Closed World Data Bases," the CWA enables deductive systems to treat unprovable positive ground literals as negated, effectively augmenting the knowledge base with their negations for query evaluation.^[1] This assumption underpins nonmonotonic reasoning, where conclusions can be revised upon new information, and contrasts sharply with the open-world assumption (OWA), which holds that unstated facts are unknown and potentially true, avoiding premature negation but complicating inference in incomplete datasets.^[2] In practice, the CWA is widely applied in relational databases and logic programming languages like Prolog, where failed queries return "no" as an affirmative denial of existence, assuming complete domain coverage.^[3] For instance, in database query answering, if a tuple does not satisfy a condition, it is deemed absent under CWA, facilitating efficient operations in controlled environments like transaction processing systems.^[4] However, its validity depends on the domain's completeness; in AI applications such as rule-based expert systems, CWA supports decisive decision-making but risks errors in dynamic or uncertain scenarios, prompting hybrid approaches that mix CWA and OWA for predicates with varying knowledge levels.^[5] Reiter's formalization demonstrated that CWA query evaluation reduces to open-world evaluation of atomic queries via set operations, ensuring consistency in Horn clause-based databases while highlighting potential inconsistencies in more expressive ones.^[1]

Fundamentals

Definition

The closed-world assumption (CWA) is a principle in knowledge representation and reasoning that posits all relevant facts are explicitly stated in the knowledge base, such that any proposition not asserted as true is considered false.^[1] This assumption treats the knowledge base as a complete description of the domain, enabling efficient inference by implicitly adding negations for unprovable positive literals.^[1] Under CWA, reasoning incorporates negation as failure, where the absence of a proof for a ground literal implies the truth of its negation, contrasting with monotonic logics that require explicit evidence for negatives.^[1] This mechanism validates conclusions based on incomplete explicit information by assuming the world is "closed" to additional facts.^[6] The CWA has key implications for handling incomplete information, as it simplifies query answering by evaluating the knowledge base as exhaustive, reducing complex deductions to checks against stated facts.^[1] For instance, in an employee database listing only known staff members, the absence of an individual's name implies they are not employed.^[6]

Historical Context

The closed-world assumption originated in the 1970s alongside the development of logic programming and relational database systems. Logic programming, which sought to integrate declarative knowledge representation with procedural computation, implicitly incorporated the assumption through negation as failure—a mechanism where the inability to prove a statement implies its negation. This was evident in early systems like Prolog, implemented by Alain Colmerauer and Philippe Roussel in 1972, and influenced by Robert Kowalski's 1974 procedural interpretation of Horn clause logic, enabling practical AI applications under the premise of a complete knowledge base.^[7] A key formalization occurred in Raymond Reiter's 1977 technical report "On Closed World Data Bases," which defined the assumption for relational databases: a positive atomic formula is true if derivable from the database, and false otherwise. This work addressed negation in deductive databases, reducing closed-world query evaluation to open-world evaluation of atomic queries, and solidified the assumption's role in bridging logic and data management.^[1] The assumption drew early influences from procedural database approaches and the rise of AI expert systems in the 1970s, which shifted from open-world models in general-purpose AI toward closed-world efficiency for domain-specific tasks. Systems like MYCIN, developed at Stanford in 1976, relied on exhaustive rule sets for medical diagnosis, assuming all relevant facts were captured in the knowledge base to support backward-chaining inference without external uncertainties.^[8] In the 1980s, the closed-world assumption evolved in knowledge representation through links to non-monotonic reasoning, allowing defaults and revisions in incomplete domains. Reiter's 1980 paper "A Logic for Default Reasoning" formalized default logic, incorporating closed-world principles to handle provisional assumptions that could be overridden, thus influencing AI frameworks for commonsense reasoning.^[9]

Formalizations

In Logic Programming

In logic programming, particularly in systems like Prolog, the closed-world assumption (CWA) is formally realized through negation as failure (NAF), an inference rule where the negation of an atom p (denoted \neg p or \mathrm{not}\ p) is taken as true if there is no finite proof deriving p from the program.^[10] This operational semantics aligns with the declarative interpretation under CWA by assuming that the program's knowledge is complete, so the absence of a derivation implies falsity.^[11] Formally, for a logic program P, the CWA asserts that \mathrm{CWA}(P) \models \neg A if and only if P \not\models A, where A is a ground atom and \models denotes logical entailment in the Herbrand universe of P. The Herbrand universe consists of all ground terms constructible from the program's function symbols, and interpretations are subsets of the Herbrand base (all ground atoms). Under CWA, the closed-world model is the unique minimal Herbrand model of P, in which atoms not entailed by P (i.e., undefined) are assigned false, ensuring a total interpretation without undefined values. This framework enables Clark's completion semantics, which transforms a normal logic program into a set of first-order sentences that treat the program as a complete specification. For a predicate p defined by clauses p(\mathbf{x}) \leftarrow L_1, \dots, L_n, the completion includes the "if" direction p(\mathbf{x}) \leftarrow \bigvee_i (L_{i1} \land \dots \land L_{im}) and the "only if" direction p(\mathbf{x}) \leftrightarrow \bigvee_i (L_{i1} \land \dots \land L_{im}), where negative literals are replaced by classical negation.^[10] To prove the equivalence, note that under CWA, the minimal model satisfies the completion axioms exactly when NAF derivations succeed, as the "only if" clauses exclude unsupported truths, and undefined atoms are falsified by the closed assumption; thus, models of the completion coincide with stable SLDNF computations, validating the program's declarative reading as a closed specification.^[11]

In Database Theory

In relational database theory, the closed-world assumption (CWA) embodies the active domain assumption, positing that the database instance exhaustively captures all facts in the application domain and that any tuple absent from a relation is false. This contrasts with scenarios involving incomplete information, where absent data might merely indicate unknown truth values. The active domain consists of all constants explicitly appearing in the database, delimiting the universe over which the assumption applies and avoiding infinite or irrelevant considerations. Formally, for a relation R of arity k with extension containing the set of tuples R^\downarrow, and letting adb denote the active domain, the CWA asserts \forall \mathbf{t} \in adb^k \setminus R^\downarrow, \neg R(\mathbf{t}). This formulation, introduced by Reiter, ensures that query answers under CWA are "certain" in the sense that they hold definitively given the database's completeness, without needing to explore external or hypothetical facts. It transforms relational query evaluation into a closed semantic framework, where negation arises naturally from non-membership. The CWA extends naturally to deductive databases, integrating with languages like DATALOG to support rule-based inference over relational facts. In such systems, negation is managed via stratified programs, partitioning rules into layers where negated subgoals depend only on prior strata; the CWA then justifies evaluating these negations as failure within each stratum, yielding a unique perfect model that aligns with intuitive closed-world reasoning. This stratification prevents unstratified cycles that could lead to inconsistencies or multiple models under CWA. By assuming database completeness, the CWA streamlines query optimization, particularly for existential queries like those involving \exists, where the absence of matching tuples in the instance directly implies a negative answer without further verification. Standard relational techniques—such as cost-based join ordering, index exploitation, and algebraic rewriting—can thus be applied efficiently, as the optimizer need not account for possible-world semantics or incompleteness repairs that would inflate computational complexity.

Applications

In Artificial Intelligence

In artificial intelligence, the closed-world assumption (CWA) plays a pivotal role in expert systems, where it enables diagnostic reasoning by treating the absence of information as definitive evidence of negation. This assumption underpins rule-based inference in systems like MYCIN, an early expert system developed for diagnosing bacterial infections and recommending antibiotic therapies, which infers the absence of symptoms or pathogens when they are not explicitly reported in the patient's data. By assuming a complete and exhaustive knowledge base, MYCIN could efficiently apply production rules to reach conclusions without needing to query for every possible condition, streamlining medical decision-making in controlled clinical scenarios.^[12]^[13] The CWA also facilitates planning and robotics by presupposing a fully specified world model, allowing agents to reason about actions and states without ambiguity from unknown elements. In classical planning frameworks such as STRIPS (Stanford Research Institute Problem Solver), the assumption that unmentioned facts or objects are false supports pathfinding and goal achievement; for instance, a robot navigating a warehouse assumes that obstacles not listed in the state description do not exist, enabling the generation of efficient action sequences through theorem-proving techniques. This approach has been foundational in AI planning since the 1970s, promoting deterministic outcomes in environments where the model encompasses all relevant details.^[14] However, over-reliance on the CWA in real-world AI applications often results in brittleness, as systems fail when confronted with incomplete or dynamic information beyond their predefined models. Expert systems and planners built under this assumption, such as early diagnostic tools, exhibit fragility in uncertain environments like open-ended robotics tasks, where unexpected changes (e.g., novel obstacles) violate the completeness premise and lead to erroneous decisions or planning failures. This limitation has driven research toward hybrid approaches that mitigate such rigidity while retaining CWA benefits in bounded domains.^[15] A notable case study of CWA application appears in natural language processing (NLP), particularly for named entity recognition (NER), where systems assume a closed vocabulary of entity types to classify mentions in text. In role-based NER models, the assumption restricts outputs to a predefined set of entities (e.g., persons, organizations), treating unrecognized types as absent; this enhances precision in domain-specific tasks like information extraction from legal documents but can overlook novel entities in broader corpora. Such implementations demonstrate CWA's utility for efficient, constrained inference in NLP pipelines.

In Semantic Web and Knowledge Representation

In the Semantic Web, the closed-world assumption (CWA) is not natively supported by core standards like OWL and RDF, which adhere to the open-world assumption (OWA) to accommodate potentially incomplete and distributed knowledge. However, local closed-world reasoning can be applied within ontologies where explicit assertions are treated as complete for specific predicates or classes, enabling negation as failure for targeted inferences. For instance, in OWL ontologies, integrity constraints or specific ABox assertions may invoke local CWA to validate completeness, such as assuming that all members of a class are exhaustively listed unless additional facts are added. This approach is facilitated by reasoners like Stardog, which extend OWL with closed-world interpretations for constraint validation.^[16]^[17] In knowledge representation frameworks based on description logics (DLs), such as ALC, the standard semantics follow the OWA, where absence of evidence does not imply evidence of absence, ensuring monotonicity in terminological reasoning. To incorporate CWA, extensions introduce local closed-world modules that allow well-founded semantics for hybrid knowledge bases, combining open-world DL rules with closed-world negation for specific assertions without violating overall consistency. These frameworks enable closed interpretations in terminological reasoning by scoping CWA to designated predicates, supporting applications like default reasoning in ontologies while preserving the Semantic Web's distributed nature. Seminal work in this area demonstrates that such local CWA can be integrated into ALC-like logics via well-founded semantics, allowing derivation of negative facts from incomplete knowledge bases.^[18]^[19] In linked data environments, CWA is applied to handle incomplete RDF triples by assuming closure over named graphs, treating each graph as a self-contained dataset where unasserted facts within its scope are false. This scoped closure facilitates constraint checking and validation in RDF datasets, using description logic axioms under closed-world semantics to enforce completeness for specific relations or entities. For example, named graphs can delineate boundaries for CWA in SPARQL queries, enabling reliable negation over localized data while the broader RDF ecosystem remains open-world. Such techniques are particularly useful in ontology-based data access, where hybrid assumptions ensure accurate reasoning over distributed linked data sources.^[20]^[21] Despite these adaptations, pure CWA is rare in distributed Semantic Web settings due to the inherent incompleteness and dynamism of web-scale data, where global closure assumptions risk incorrect negations from partial knowledge. This limitation often leads to hybrid approaches that blend local CWA with OWA, such as in agent planning or constraint validation, to balance completeness in controlled scopes with openness across the web. Research highlights that enforcing full CWA in such environments can hinder interoperability, prompting frameworks that dynamically switch assumptions based on data provenance.^[22]^[18]

Variations

Partial Closed-World Assumption

The partial closed-world assumption (PCWA) relaxes the full closed-world assumption by applying closure only to designated subsets of predicates, relations, or domains within a knowledge base or database, while treating the remaining elements as potentially incomplete or open. This approach acknowledges that not all information is exhaustively known, enabling more flexible reasoning in scenarios where completeness holds locally but not globally.^[23] Formally, PCWA can be modeled using completeness statements over partial databases, defined as a pair (D_i, D_a) where D_i represents the ideal complete instance and D_a \subseteq D_i is the available possibly incomplete instance. Building on Reiter's foundational closed-world assumption, query completeness (QC) requires that for a query Q, Q(D_a) = Q(D_i), ensuring the available data yields the same results as the complete data. Similarly, table completeness (TC) specifies that for a relation R and condition G, the projection Q_R(\bar{s}; G)(D_i) \subseteq R(D_a), formalized as tuple-generating dependencies to enforce local closure. These statements allow explicit designation of closed components without assuming global completeness.^[23]^[24] In database applications, PCWA supports schema-specific closure, such as assuming completeness for an employee relation (e.g., all staff records are fully captured) while leaving supplier information open to potential additions. For instance, in a school management system, the person relation might be closed with respect to student entries—ensuring all students' gender and name details are complete—but open for other attributes like external contacts. This has been applied in RDF stores for semantic data integration, geographic information systems for localized completeness, and SQL databases handling nulls to improve query reliability.^[23] Compared to the full closed-world assumption, PCWA reduces false negatives by avoiding blanket negation of absent facts in incomplete domains, thereby enhancing accuracy in real-world incomplete data scenarios without sacrificing soundness in verified closed subsets.^[23]

Comparison with Open-World Assumption

The open-world assumption (OWA) posits that a knowledge base represents incomplete information about the domain, such that the absence of evidence for a statement does not constitute evidence of its absence; negation of a proposition p (i.e., \neg p) is only entailed if explicitly stated or logically derived.^[1] In contrast to the closed-world assumption (CWA), which treats unmentioned facts as false, OWA maintains that unknown facts may simply be missing from the current representation and could be true elsewhere.^[2] Key differences between CWA and OWA lie in their reasoning paradigms and applicability. CWA enables non-monotonic reasoning, where adding new information can retract prior conclusions (e.g., a fact assumed false under CWA may become true, invalidating negations derived from it), making it suitable for environments with complete, finite data like relational databases.^[6] Conversely, OWA supports monotonic reasoning, preserving all prior entailments upon knowledge expansion, which aligns with distributed systems such as the Semantic Web where data from multiple sources must integrate without assuming completeness.^[25] This monotonicity in OWA facilitates scalable ontology merging but requires explicit handling of negatives to avoid under-entailment.^[26] The trade-offs highlight contextual suitability: CWA excels in efficiency for closed domains, enabling straightforward query negation and fast inference, but risks erroneous conclusions in open environments where overlooked facts exist.^[23] OWA offers greater flexibility for evolving, incomplete knowledge but imposes higher computational costs, as reasoning must account for potential external truths without defaulting to negation.^[26] Hybrid approaches, such as partial CWA, address these by applying closure selectively to subsets of the knowledge base, allowing domain-specific choices—e.g., CWA for exhaustive e-commerce product catalogs where all attributes are presumed listed, while OWA suits broader inventory discovery.^[23]

References

[1]
[PDF] ON CLOSED WORLD DATA BASES by RAYMOND REITER ...
In this paper, we show that closed world evaluation of an arbitrary query may be reduced to open world evaluation of so-called atomic queries. We then show that.Missing: original | Show results with:original
[2]
Open World Assumption - an overview | ScienceDirect Topics
Open World Assumption in computer science refers to a reasoning approach where the facts asserted in a model are not assumed to be complete.
[3]
Closed World Assumption - an overview | ScienceDirect Topics
The 'Closed World Assumption' in computer science refers to the belief that all relevant knowledge is contained within a database.
[4]
Open World Assumption vs. Closed World Assumption - Dataversity
Nov 30, 2012 · When Do CWA and OWA Apply? The CWA applies when a system has complete information. This is the case for many database applications. · CWA vs. OWA ...
[5]
Understanding closed-world assumptions in AI - IndiaAI
Feb 13, 2023 · The Closed World Assumption (CWA) is the belief that what is not known to be true is false and that the absence of information is viewed ...Missing: definition | Show results with:definition
[6]
Non-monotonic Logic - Stanford Encyclopedia of Philosophy
Dec 11, 2001 · 3.1 The closed-world assumption. Since one of the goals of non-monotonic logic is to provide an adequate account of defeasible reasoning, it is ...
[7]
[PDF] LOGIC PROGRAMMING - Department of Computing
Ray Reiter [1978] investigated NAF in the context of a first-order database D, interpreting it as the closed world assumption (CWA) that the negation not p of a ...
[8]
Logic-Based Artificial Intelligence
Aug 27, 2003 · It is the closed world assumption that justifies a negative answer ... definition of logical consequence, appealing to a preference relation over ...
[9]
A logic for default reasoning - ScienceDirect.com
In this paper we propose a logic for default reasoning. We then specialize our treatment to a very large class of commonly occuring defaults.
[10]
[PDF] Negation as failure - Department of Computing
whose construction depends on at most n failure proofs n > 0. ....& ~ P&.... fail. A query evaluation for P succeeds ...
[11]
https://doi.org/10.1016/0743-1066(84)90023-2
[12]
[PDF] Rule-Based Expert Systems: The MYCIN Experiments of the ...
Even though the MYCIN world can be considered to be closed, there is no strong model for ordering the collection of evidence. 5 Medical problem solving is ...
[13]
[PDF] Principles of Expert Systems
This book treats formalisms and methods for expert systems, focusing on theory and implementation, and establishing relationships between logic and rule-based ...
[14]
[PDF] 11 PLANNING
The closed-world assumption is used, meaning that any conditions that are not mentioned in a state are assumed false.
[15]
[PDF] Learning and the Unknown: Surveying Steps toward Open World ...
The closed world assumption led to fragile systems that failed, and so fell ... Expert Systems with Ap- plications 84:1–11. Fu, Y.; Xiang, T.; Jiang, Y ...
[16]
OWL 2 Web Ontology Language Primer (Second Edition) - W3C
Dec 11, 2012 · If some fact is not present in a database, it is usually considered false (the so-called closed-world assumption) whereas in the case of an OWL ...
[17]
[PDF] Mixing Open and Closed World Assumption in Ontology-Based Data ...
Abstract. When using ontologies to access instance data, it can be useful to make a closed world assumption (CWA) for some predicates and an open world.
[18]
[PDF] Local Closed-World Reasoning with Description Logics under the ...
Jan 21, 2011 · DLs are monotonic and adhere to the Open World Assumption (OWA). This means that (negative) conclusions drawn from a knowledge base must be.Missing: seminal | Show results with:seminal
[19]
Local closed world reasoning with description logics under the well ...
Local closed world reasoning with description logics under the well-founded semantics ... In this paper we propose a well-founded semantics for ...
[20]
Using Description Logics for RDF Constraint Checking and Closed ...
Nov 15, 2014 · Nevertheless, Description Logic axioms can be interpreted in a closed-world setting and in this setting they can be used for both constraint ...
[21]
[PDF] Position paper: Named Graphs in Linked Data - W3C
On the other hand, if we treat graphs with the open world assumption, never assuming that the full extent of a graph is known, then there is no need for ...
[22]
[PDF] LCW-Based Agent Planning for the Semantic Web
Jan 2, 2002 · The closed-world assumption is inappropriate for the. Semantic Web due to its size and rate of change. Since the. Web, is so large, no single ...
[23]
[PDF] Databases under the Partial Closed-world Assumption: A Survey
In this survey we review foundational and work on the partial closed-world assumption and then discuss work done ... [16] Raymond Reiter. On closed world data ...
[24]
On Closed World Data Bases - SpringerLink
In this paper, we show that closed world evaluation of an arbitrary query may be reduced to open world evaluation of so-called atomic queries.Missing: original | Show results with:original
[25]
What the Semantic Web can represent
One consistent difference between the Semantic Web and many data models for programming langauges is the "closed world assumption". A Semantic Web is not ...<|control11|><|separator|>
[26]
https://ieeexplore.ieee.org/document/4591590