open_world_query_answering (2161B)
1 # Open world query answering 2 3 This gets its name from the [open_world_semantics], which is that of databases 4 which may be missing some information. (Think of a [knowledge_base], like 5 [Wikidata]: you can hope that the facts of Wikidata are true, but there are 6 some true facts that are not in Wikidata.) You may have some integrity 7 constraints and reasoning rules (e.g., father(x,y) -> parent(x,y), or 8 locatedIn(x,y) locatedIn(y,z) -> locatedIn(x,z)) and the database doesn't 9 necessarily satisfy these constraints directly (e.g., some of the entailed 10 facts may not be materialized in the data) 11 12 Formally, you have a [database] D, a set of database constraints Σ (e.g., 13 [database_dependencies], [integrity_constraints], an [ontology], etc.), and a 14 query Q. You want to consider all possible completions D' of D (i.e., D 15 subseteq D') subject to the constraints (i.e., D' \models Σ) and you want to 16 know whether all of these completions satisfy the query Q. (So that Q is not 17 necessarily true on D but is "entailed" in the sense that every completion of 18 D satisfying Σ must satisfy Q -- note that Q is typically monotone.) The 19 negation of the problem asks whether there is a counterexample model, i.e., a 20 completion D' of D that satisfies Σ but not Q (equivalently, that satisfies Σ 21 \land \neg Q). So this is the question of asking whether a superset of some 22 extensional data satisfies a logical formula (of a somewhat weird kind -- 23 typically Σ would consist of [tuple_generating_dependencies], 24 [existential_rules], or [description_logic] rules, whereas \neg Q would be the 25 negation of a [conjunctive_query] or [union_of_conjunctive_queries]). 26 27 Also called "ontology-based data access", see also [ontology_mediated_query] 28 29 - [query_rewriting] 30 - [chase] 31 - [combined_complexity] approaches, for instance [gottlob2023polynomial] 32 33 By [constraint_language]: 34 35 - [open_world_query_answering_fds] 36 - [open_world_query_answering_rpqs] 37 38 Related to [query_containment] 39 40 References: [imielinski1984incomplete], [arenas1999consistent], [cali2003decidability], [xiao2018ontology] 41 42 See also: [query_evaluation], [satisfiability], [open_world_semantics] 43 44 Up: [database_theory]