约束数据库的正交维度研究

# 约束数据库的正交维度研究 ## 1. 线性约束下的正交维度问题 对于特定的语言 $L$ 和结构 $A$ 的选择，可以得到更精确的结果。例如，在有理数上的线性约束情况下，两个正交维度问题都可以在多项式时间内得到解决。 ### 1.1 线性约束关系的正交维度求解 线性公式 $\phi$ 定义的线性约束关系的显式和隐式正交维度问题可以在多项式时间内解决。这一结果推广了之前的相关研究。 ## 2. 查询语言 我们考虑可以在结构 $A$ 的上下文中用语言 $L$ 中的一阶公式表示的查询。 ### 2.1 查询的定义与转换 如果 $s$ 是一个模式，$L \cup s$ 中带有自由变量 $x_1, \ldots, x_n$（$n > 0$）的每个公式 $\phi$ 都定义了一个在结构 $A$ 上下文中对模式 $s$ 的查询，将模式 $s$ 的实例 $I$ 映射到由 $\{(a_1, \ldots, a_n) | A \cup I \models \phi(a_1, \ldots, a_n)\}$ 定义的 $n$ 元关系。对于查询 $q = \{(x_1, \ldots, x_n) | \phi\}$ 和模式 $s$ 的实例 $I$，由于 $I$ 中的每个关系 $R$ 都可以用 $L$ 中的无量词公式定义，我们可以将 $\phi$ 中每个关系符号 $R \in s$ 的出现替换为定义 $R$ 的公式，得到的公式 $\phi'$ 是 $L$ 中的公式，它定义了查询 $q$ 在实例 $I$ 上的答案 $q(I)$。 ### 2.2 正交分解的保留 为了避免一些查询操作导致输出的正交维度与输入不一致的问题，我们将注意力限制在保留正交分解的查询上。 - **定义**：设 $s$ 是一个数据库模式，$P$ 是 $s$ 中关系的正交分解。如果对于正交分解为 $P$ 的每个实例 $I$，$q(I)$ 都有一个细化 $P$ 的正交分解，那么模式 $s$ 上的查询 $Q$ 保留正交分解 $P$。 - **可判定性**： - 在 o - 最小上下文结构和至少有一个二元关系符号的模式下，保留正交分解的查询是不可判定的。 - 对于合取查询，保留正交分解是可判定的。可以将合取查询递归地转换为 $\pi_A \sigma_F R_1 \times \ldots \times R_n$ 的形式，通过计算 $F$ 引入的不同组件变量对之间的非矩形连接，并检查这些连接是否被投影 $A$ 破坏来判断是否保留正交分解。 ### 2.3 正交分解保留查询的句法特征 - **分解受限查询**：设 $\mu_P$ 是一个布尔公式，如果 $\phi$ 定义的关系允许分解 $P$，则该公式成立。形如 $\phi(y_1, \ldots, y_k) \land (\mu_P(\Phi_I) \to \mu_P(\phi))$ 的公式称为分解 $P$ 受限的。正交分解保留查询类与分解受限查询类是重合的。 - **P - 安全查询**：为了更直观地判断查询是否保留正交分解，我们引入了一个代数，包含笛卡尔积（$\times$）、投影（$\pi$）、并集（$\cup$）、集合差（$-$）等操作。通过递归定义代数表达式 $E$ 的坏绑定集合 $BB(E)$，如果 $BB(E) = \varnothing$，则 $E$ 是无坏绑定的。$P$ - 安全查询定义为无坏绑定的代数查询集合，每个 $P$ - 安全查询都保留正交分解。而且，每个保留正交分解 $P$ 的合取查询都等价于一个 $P$ - 安全查询。 ## 3. 线性约束数据库 在上下文结构为 $A = (Q, \leq, +)$ 的情况下，有限可表示的关系称为线性约束关系。我们研究线性实例的各种参数（如变量数量、正交维度、约束数量等）对查询复杂度的影响，并展示查询评估过程如何利用输入的正交维度。 ### 3.1 代数操作的复杂度 | 维度 \ 操作符 | 1 | 2 | 3 | d | | --- | --- | --- | --- | --- | | $\times$ | $t^2$