Research map / Learning theory and algorithms / Prediction and decision losses
What Does a Query Answer Tell You? Informativeness of Query Answers for Knowledge Bases
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a formal framework for the informativeness of KB query answers, analyzes certain, possible and wildcard (partial) answers within it, and introduces V-table-style n-connected certain/possible answers with their data complexity.
Problem
Certain and possible answers to queries over knowledge bases with multiple or infinite models are lossy: they fail to represent much of the knowledge a query extracts from the KB's models, and no formal framework existed to characterize or compare the informativeness of answer objects.
Approach
Define query answering systems (QAS) as evaluation functions plus answer domains, and measure informativeness by which first-order properties of the set of complete answers across models an answer object preserves (certain or possible). Within this framework, introduce n-connected answers with variables shared across answer tuples (V-table style) that preserve bounded-variable existential positive
Key results
- Proves certain n-answers (Cn) preserve the certain knowledge of ∃Pos[n] sentences, and possible n-answers (Pn) preserve possible knowledge of constant-free ∃Pos[n] sentences (Theorems 1-2).
- Shows finite tuple-set answers cannot preserve certain ∃Pos knowledge of UCQs over DL-Lite-core KBs (Proposition 8), and tuple-set answers cannot preserve possible ∃PosG knowledge (Proposition 9).
- Shows recognition of certain and possible n-connected answers reduces to Boolean UCQ entailment / consistency checking, giving AC0 or P-complete data complexity depending on KB language.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use certain n-connected answers instead of classical certain answers | UCQs over KBs with the universal model property · ∃Pos[n](ANS) properties | certain-knowledge preservation | Helped |
| Use possible n-connected answers instead of ordinary possible answers | UCQs over KBs with the disjoint-union property · ∃Posv[n](ANS) properties | possible-knowledge preservation | Helped |
| Add variable repetition across answer tuples using certain answers with wildcards | CQ over DL-Litecore · ∃Poslocal(ANS) properties | certain-knowledge preservation | Helped |
| Use classical certain answers | CQ over DL-Litecore · ∃Pos[1](ANS) and ∃Poslocal(ANS) properties | certain-knowledge preservation | Hurt |
| Use certain answers with wildcards, without cross-tuple variable repetition | CQ over DL-Litecore · ∃Pos[1](ANS) properties | certain-knowledge preservation | Hurt |
| Restrict possible answers to constants occurring explicitly in the KB | CQ over DL-Litecore · GA(ANS) properties | possible-knowledge preservation | Hurt |
| Represent possible answers as ordinary tuples | CQ over DL-Litecore · ∃PosG(ANS) properties | possible-knowledge preservation | Hurt |
Surprising findings
- Finite tuple-set answers, even for simple DL-Lite-core KBs and conjunctive queries, cannot preserve certain existential positive knowledge.
- Restricting possible answers to constants occurring in the KB (as practical systems do) prevents them from preserving even ground-atom possible knowledge.
Limitations
- Results are theoretical; no implementation or empirical evaluation is provided.
- Possible-answer preservation is restricted to constant-free n-connected answers and to bounded-variable languages; full ∃Pos possible knowledge cannot be preserved.
Experimental setup
Metrics: preservation of first-order properties of complete answers ( data complexity
Baselines: certain answers possible answers certain answers with wildcards minimal partial answers
Builds on: representation systems (Libkin 2016) Imielinski-Lipski weak representation systems minimal partial answers (Lutz and Przybylko) V-tables
Closest papers by meaning
- Expressive Recursive Answers for Ontological Knowledge Bases (AAAI 2026 · similarity 0.89)
- Is Complex Query Answering Really Complex? (ICML 2025 · similarity 0.85)
- Consistent Query Answering over Existential Rules with Open and Closed Predicates (AAAI 2025 · similarity 0.85)
- Promoting Knowledge Base Question Answering by Directing LLMs to Generate Task-relevant Logical Forms (AAAI 2025 · similarity 0.84)
- A Foundation Model for Zero-shot Logical Query Reasoning (NeurIPS 2024 · similarity 0.83)
- Explore What LLM Does Not Know in Complex Question Answering (AAAI 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.