arXiv:2603.13603cs.DBcs.AI2026-03

四维关系能力缺一不可,构建完整数据库系统

The Equivalence Theorem: First-Class Relationships for Structurally Complete Database Systems

  • 提出四重互含关系能力:属性、时间有效性、不确定性量化、因果关系
  • 证明四者共同等价于关系作为首级对象,缺失任一即不完整
  • 给出可落地的ATCH框架,支持复杂查询与实际系统实现

本文证明了结构完整性知识表示需恰好具备四种相互蕴含的能力:带属性的多值关系、时间有效性、不确定性量化以及关系间的因果关系,这四者共同等价于将关系视为首级对象。任何系统若实现其中一项,就必须具备全部四项;缺少任一都无法达到结构完整性。该结论具有构造性:我们提出了一个属性化时间因果超图(ATCH)框架,同时满足四项条件。该定理建立了严格的表达力层级——SQL < LPG < TypeDB < ATCH,且提供在较低层级上无法表达的验证查询。计算复杂度分析表明,一般查询为NP完全,但实用查询类(无环模式、有限深度因果链、窗口化时间查询)可在多项式时间内求解。作为直接推论,解决了经典人工智能问题:帧问题(默认持续性来自时间有效性)、冲突消解(矛盾作为未解决元数据并发现隐变量)、常识推理(带因果抑制器的默认规则)。一个基于C语言的PostgreSQL原型扩展验证了实际可行性,符合既定复杂度边界。

原文摘要 · Abstract (English)

We prove The Equivalence Theorem: structurally complete knowledge representation requires exactly four mutually entailing capabilities -- n-ary relationships with attributes, temporal validity, uncertainty quantification, and causal relationships between relationships -- collectively equivalent to treating relationships as first-class objects. Any system implementing one capability necessarily requires all four; any system missing one cannot achieve structural completeness. This result is constructive: we exhibit an Attributed Temporal Causal Hypergraph (ATCH) framework satisfying all four conditions simultaneously. The theorem yields a strict expressiveness hierarchy -- SQL < LPG < TypeDB < ATCH -- with witness queries that are structurally inexpressible at each lower level. We establish computational complexity bounds showing NP-completeness for general queries but polynomial-time tractability for practical query classes (acyclic patterns, bounded-depth causal chains, windowed temporal queries). As direct corollaries, we derive solutions to classical AI problems: the Frame Problem (persistence by default from temporal validity), conflict resolution (contradictions as unresolved metadata with hidden variable discovery), and common sense reasoning (defaults with causal inhibitors). A prototype PostgreSQL extension in C validates practical feasibility within the established complexity bounds.

数据库系统知识表示关系建模形式理论

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。