https://theses.hal.science/tel-03859885Ousmane Issa0HAL编号：tel-038598850提交日期：2022年11月18日0HAL是一个多学科开放存取档案，用于存储和传播科学研究文档，无论其是否发表。这些文档可以来自法国或国外的教育和研究机构，也可以来自公共或私人研究中心0HAL多学科开放存取档案，旨在存储和传播法国或国外教育和研究机构、公共或私人实验室发表或未发表的研究级科学文献0关系数据库中的不一致感知量化、查询回答和排序0引用此版本：0Ousmane Issa. 关系数据库中的不一致感知量化、查询回答和排序. 数据库 [cs.DB]. Université ClermontAuvergne, 2022. 英文. �NNT : 2022UCFAC010�. �tel-03859885�Université Clermont AuvergneLIMOS, UMR-6158, CNRS21/02/202210工程科学博士学位0博士学位论文0关系数据库中的不一致感知量化、查询回答和排序0以满足University Clermont Auvergne博士学位要求提交的论文0作者：Ousmane ISSA0导师：FaroukTOUMANI和AngelaBONIFATI0评审委员会：François Goasdoué教授，审稿人 LaureBerti女士，研究主任，审稿人 StefaniaDumbrava女士，副教授，考官 Farouk Toumani教授，导师Angela Bonifati教授，导师0计算机科学与技术实验室0法国克莱蒙费朗20摘要0在过去的四十年中，数据库和知识库中的不一致问题已经得到了广泛的解决和讨论。不一致性是数据质量的主要维度之一。在我们的时代，数据是新的黄金，但是没有质量或缺乏质量措施的数据会导致错误和无信息的数据分析结果。当数据库实例违反了一组必须满足的约束条件时，就会出现不一致性问题。以往处理不一致性问题的所有工作都集中在修复不一致的数据库以获得一致的新数据库（即没有违反约束条件），或者在整个数据库上量化不一致性。在本论文中，我们提出了一种处理关系数据库中不一致性的新方法，通过在元组级别上对其进行量化，然后根据不一致性对元组/答案进行排序，以便在查询答案中选择最一致/不一致的答案。因此，我们定义了不同的不一致性度量方法，基于元组违反（基于元组的方法）或约束违反（基于约束的方法）。我们将拒绝约束类作为约束类，将合取查询类作为查询类。我们利用为什么起源和多项式起源来识别不一致的元组和计算查询答案的不一致性度量。我们将每个拒绝约束转换为布尔合取查询，并在数据库上评估该查询以计算真实答案的为什么起源。使用为什么起源，数据库中的每个元组都被注释为它违反的约束集合和以单项式形式的标识符（否则，即元组不涉及违反任何约束，则由单项式1注释），然后我们获得了一个带注释的数据库。给定一个合取查询Q，Q在带注释的数据库上进行评估，每个答案都使用多项式起源计算，该多项式公式编码了答案违反的约束集合以及用于计算答案并涉及违反这些约束的元组集合。然后，我们使用答案的多项式起源定义了十二种不一致性度量。一旦定义了不一致性度量，就可以根据其不一致性度量对答案（数据库中的元组）进行排序是有趣的。我们设计了一组top-k算法，包括TopINC，其他算法的思想都基于此算法，可以根据其不一致性度量对查询答案进行排序。我们引入了一类新的算法和一种新的成本模型，并在某些特定条件下证明了这些top-k算法的最优性。此外，对于每个top-k算法，我们给出了其理论复杂度。我们进行了大量实验，以展示我们的方法在实践中的可行性，并展示了我们开发的top-k算法的效率。关键词：不一致性，不一致性度量，Top-K算法，起源，合取查询，拒绝约束30摘要0在过去的四十年中，关于数据库和知识库中不一致性的问题已经得到广泛讨论。不一致性是数据质量的主要维度之一。在我们这个时代，数据是新的黄金，但是没有质量的数据或者缺乏质量度量可能会导致其他负担，从而导致从数据中得出错误和无信息的分析结果。当数据库实例违反了一组必须满足的约束条件时，就会出现不一致性问题。以前处理不一致性问题的工作要么关注修复不一致的数据库以获得一组一致的新数据库（即没有违反约束条件），要么关注在整个数据库中量化不一致性。在这篇论文中，我们提出了一种新的方法来处理关系数据库中的不一致性，将其量化为元组级别，然后根据不一致性对元组/响应进行分类，以便从查询的响应中选择最一致/不一致的响应。因此，我们基于元组违反来定义不同的不一致性程度度量。我们考虑了否定约束（denialconstraint）类和连词查询类。我们利用why-provenance和polynomialprovenance方法来识别不一致的元组并计算查询响应的不一致程度。我们将每个否定约束转换为连词布尔查询，并在数据库上评估该查询以计算响应的why-provenance。使用why-provenance，数据库的每一行都被注释为违反的约束集合及其标识的单项式形式（否则，即如果数据行没有涉及任何约束违反，则用单项式1进行注释），然后得到一个带注释的数据库。给定一个连词查询Q，我们在带注释的数据库上评估Q，并计算每个响应的多项式provenance，该provenance在一个多项式公式中编码了响应违反的约束集合以及用于计算响应并涉及违反这些约束的数据行集合。然后，我们使用响应的多项式provenance定义了十二个不一致程度度量。一旦定义了不一致度量，就有必要根据其不一致程度对查询的响应进行排序。我们设计了一组top-k算法，其中TopINC是其他算法的基础，用于根据其不一致程度对查询的响应进行排序。我们引入了一种新的算法类和一种新的成本模型，并证明了这些top-k算法在特定条件下的最优性。40此外，对于每个前k个算法，我们给出了它的理论复杂度。我们进行了大量实验，以展示我们的方法在实践中的可行性，并展示我们开发的前k个算法的效率。50献给我的爸爸们：我已故的爸爸IssaOUSMANE，我已故的叔叔IssiakaNOUHOU，我已故的舅舅OusmaneDOUMBIA60«只有当它被维持时才会有缺陷»。«掌握不一致性就是接近完美»。0«但是不一致性并不是疯子的专利：一个健康人的所有重要思想都是非理性的构建»。AndréMaurois70致谢80目录01 引言 1302 初步概念 18 2.1 关系数据库 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1802.2 连接查询 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1902.3 否定约束 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1902.4 关系数据库中的溯源 . . . . . . . . . . . . . . . . . . . . . . . 2002.5 超图和连接树 . . . . . . . . . . . . . . . . . . . . . . . . . . 2203 现有技术 27 3.1 数据不一致性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2703.1.1 知识库中的不一致性 . . . . . . . . . . . . . . . . . . 2703.1.2 关系数据库中的不一致性 . . . . . . . . . . . . . . . . . 2803.2 Top-k 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2903.2.1 基于磁盘的算法 . . . . . . . . . . . . . . . . . . . . . . . . 2903.2.2 基于内存的算法 . . . . . . . . . . . . . . . . . . . . . . 2903.3 结论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3004 量化不一致性 31 4.1 举例说明 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3204.2 识别不一致的元组 . . . . . . . . . . . . . . . . . . . . . . . . 3304.3 数据库的注释 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3404.4 查询答案的不一致性 . . . . . . . . . . . . . . . . . . . . . . . . . 3604.4.1 度量的定义 . . . . . . . . . . . . . . . . . . . . . . . . . 3704.5 结论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4305 基于不一致性的查询答案 44 5.1 基于成本的查询答案枚举 . . . . . . . . . . . . . . . . . . . 4605.1.1 问题维度 . . . . . . . . . . . . . . . . . . . . . . . . . . 4605.1.2 成本模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4805.2 基于约束的度量算法 . . . . . . . . . . . . . . . . . . 5105.2.1 基于磁盘的算法 . . . . . . . . . . . . . . . . . . . . . . . . 5105.2.2 基于内存的算法 . . . . . . . . . . . . . . . . . . . . . . . 5705.3 基于元组的度量算法 . . . . . . . . . . . . . . . . . . . . . 6705.3.1 TupIncRank 算法 . . . . . . . . . . . . . . . . . . . . . . . . . 6705.4 结论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72906 约束集中的不一致性存在 73 6.1 修复不一致性问题 . . . . . . . . . . . . . . . . . . . . . . . . . 7306.1.1 强一致的查询答案 (SCQA) . . . . . . . . . . . . . . . . . . . . . 7406.1.2 量化查询答案的不一致程度 . . . . . . . . . . . . . . . . . . . . 7506.2 根据不一致程度对查询答案进行排序 . . . . . . . . . . . . . . . . . . . . . 7606.2.1 基于 R f CBS 的 Top-k 算法 . . . . . . . . . . . . . . . . . . . . . . 7606.3 结论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7707 实证评估 79 7.1 评估措施 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8007.1.1 数据库注释 . . . . . . . . . . . . . . . . . . . . . . . . . . 8007.1.2 计算措施 . . . . . . . . . . . . . . . . . . . . . . . . 8207.1.3 定性研究 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8207.2 Top-k算法评估 . . . . . . . . . . . . . . . . . . . . . . . . . 8407.2.1 TopINC算法性能与基准算法对比 . . . . . . . . . . . . . . . . . . 8407.2.2 TupIncRank算法性能 . . . . . . . . . . . . . . . . . . . . . . . 8507.3 结论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9008 INCA: 不一致感知数据分析和查询 94 8.1 INCA概述 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9508.1.1 INCA系统架构 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9508.2 INCA的实现 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9608.3 用户与INCA的交互 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9608.3.1 对初始数据库进行注释 . . . . . . . . . . . . . . . . . . . . 9708.3.2 数据I-分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9708.3.3 不一致感知的查询回答 . . . . . . . . . . . . . . . . 10008.4 结论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10109 结论和展望 102100算法列表01 TopINC算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5302 IterateJoin算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5503 TopIncMem算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5804 TopMultiSet算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6205 partition算法（T ′，Ans，Attr） . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6306 TupIncRank算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6807 performJoin算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6908 RTopINC算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78110图表列表01.1 关系数据库中的一致性问题框架 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1604.1 带有一组否定约束（DCs）和查询Q ex 的医院数据库hdb . . . . . . . . . . . . . . . . . . . . . . . .04.2 从医院数据库hdb获得的Lineage溯源数据库hdb LP . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . 3404.3 K-实例hdb LP（不包含prov列）和hdb Υ（不包含lprov列） . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . 3504.4 可以获得的不一致性的各种量化及其标准 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3604.5 查询Q ex 在hdb Γ上的答案及其不一致度 . . . . . . . . . . . . . . . . . . . . . . . 4105.1 基于约束的度量算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5205.2 TopINC算法的示例 . . . . . . . . . . . . . . . . . . . . . . . . . 5405.3 用于说明基于内存的top-k算法的数据示例（a.）。树示例（b.）。带有数据的树（c.）. . . . . . . . . . . . . . . . . . . . . . . . 5905.4 TopIncMem算法示例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6005.5 用于TopMultiSet算法的连接树及预处理步骤的数据 6405.6 TopMultiSet 算法的示例。计算第一个答案后的树的分区。 . . . . . . . . . . . . . . . . . . . . . . .. . . . 6505.7 基于元组的度量算法。 . . . . . . . . . . . . . . . . . . . . 6707.1 将实例转换为 N [ Υ ∪ Γ ] -实例。 . . . . . . . . . . 8107.2 CBS 和 CBM 的计算开销。 . . . . . . . . . . . . . . . . . . . . 8207.3 TopINC 性能与基准算法 ( α = CBS ) 的比较：运行时间。 . . . . . . . . . . 8607.4 TopINC 性能与基准算法 ( α = CBS ) 的比较：内存占用。 . . . . . 8707.5 TopINC 与基准算法 ( α = CBS ) 的比较。 . . . . . . . . . . . . . . . . . . . . . . . 8807.6 TupIncRank 与其他算法在运行时间方面的性能比较。 . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 8907.7 TupIncRank 与其他算法在内存使用方面的性能比较。 . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 9107.8 TupIncRank 与其他算法在额外计算的答案方面的性能比较。 . . . . . . . . . . . . . . . . . . . . .. . . 9208.1 INCA 的架构。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9608.2 简单统计。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9808.3 基于约束的不一致性探索。 . . . . . . . . . . . . . . . . . . . 9808.4 基于约束子集的不一致性探索。 . . . . . . . . . . . . . . . . . . . . 9908.5 不一致性感知的查询回答。 . . . . . . . . . . . . . . . . . . . . 99120表格清单01.1 带有其关联的前 k 个算法的度量。 . . . . . . . . . . . . . . 1504.1 查询 Q ex 的注释答案。 . . . . . . . . . . . . . . . . . . . . . . . 3204.2 不一致性的不同提出的度量及其形式定义。符号 α ≡ β 表示 α ( t , I , Q , DC ) = β，其中 α 是不一致性度量，β 是其定义。 . . . . . . . . . . . . . . . . . . . . . . . 4005.1 算法及其特性； n 是数据库实例的大小， m 是查询的大小， k是要计算的答案的数量； δ ≤ n 表示中间答案的数量（如果查询是无环的，则为1）。 . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . 5107.1 我们的实证评估中使用的数据集。 . . . . . . . . . . . . . . . . . . 8007.2 具有其否定约束的真实世界数据集。 . . . . . . . . . . . . . 8307.3 定性研究结果。 . . . . . . . . . . . . . . . . . . . . . . . . . 93130第1章0介绍0在过去的二十年中，人们对数据质量问题给予了特别关注[15, 54, 55,99]。糟糕的数据质量可能会在私营公司和公共组织的决策中造成重大问题[57]。因此，缓解这个问题并提供具体的解决方案至关重要。如今，随着人工智能的发展，数据的质量在模型和算法的质量中起着重要作用。数据质量有几个维度[127, 133]，其中最重要的是[133]：0• 数据的完整性：它解决了缺失数据的问题；它还提供了关于现实世界如何完全由数据表示的信息[14]。0• 数据的准确性：它涉及设计一组工具来确保存储数据的正确性[14, 145]。0• 数据的货币性：它涉及数据的新鲜度[14, 127]。0•数据一致性：它涉及数据的可靠性，符合一组必须由数据满足的约束[14]。完整性约束是这类约束的显著类别。0本论文侧重于数据不一致性。当这些数据违反了必须满足的一组约束之一时，数据中存在不一致性。不一致性可能由于各种原因而引入数据库，其中包括：0• 数据集成，即将（异构）数据从多个来源组合起来[46, 100]。0• 关系数据库中约束检查的临时禁用[46]。0• 在数据库中对存储的数据应用新的约束[46]。0• 数据输入错误，例如在数据库中输入错误。0• 数据库上定义的一组约束的不一致性等。0已经进行了许多关于不一致性的研究问题，例如修复知识数据库中的不一致性问题[17, 18, 38,79]，数据库修复和一致的查询答案[9,22]，数据清理[36]，约束检查（例如，在数据库中的任何更新操作之前量化不一致性）[46]。140然而，对于保持数据库实例完整并量化其在不同粒度级别（元组、元组集合、属性、属性集合等）上的不一致性程度，人们付出了很少的关注。这样的特征使得DBMS的用户能够量化他们从查询和操作数据中期望的信任水平。在我们的工作中，我们对关系实例进行了扩充，引入了新的不一致性度量，这些度量也可以传播到查询结果中。给定查询的答案的不一致性程度是通过依赖于计算该答案中涉及的输入元组的基于来源的信息来确定的。我们首先利用为什么来源来识别与一组否定约束相对应的关系实例的不一致基础元组。然后，我们依赖于来源多项式[74]，以便将不一致性的注释从基础元组传播到连词查询的答案元组。基于计算的注释，我们定义了十二种不一致性程度的度量，这些度量考虑了约束和元组的单个和多个违规。由于我们的一些度量是非单调函数，我们设计了新的基于top-k的算法来根据不一致性度量对查询的top-k结果进行排序，如表1.1所示。由于现有的成本模型不适用于我们的情况，我们引入了一类称为SBA的新算法和一个称为cost∆的新成本函数，适用于通用评分函数（单调和非单调）。我们展示了我们的SBA中的top-k算法相对于成本函数cost ∆的最优性。我们设想我们的框架有几个应用，如下所示。用于分析任务的不一致性感知查询，因为我们期望我们的框架能够在数据科学流程中查询和分析任务中量化不一致性。我们的注释不仅仅是数字，还传达了关于违反约束的基于来源的信息，后者对于用户在数据科学任务中是可行的。用于数据清理流程的外部注释，因为我们的方法还可以通过将不一致性指标的外部信息注入到OpenRe�ne、Wrangler和Tableau等工具中，从而简化数据清理任务，并在清理和整理之前提前进行排名。完整性约束的近似方案，这些方案已被用于保证在最近的概率推理方法中进行数据清理的多项式数量的样本[128]。我们相信，与约束近似相比，另一种选择是基于最一致（最不一致）元组的前k个约束构建样本。组合排名，因为我们的质量感知排名可以与其他排名标准结合使用，例如推荐系统中的用户偏好以及市场和搜索网站中的不公平和歧视[5]。0贡献0我们引入了一种管理关系数据库中不一致性的新框架。如图1.1所示，我们将数据库和一组否定约束作为框架的输入，然后进行两步处理：0•预处理步骤，根据否定约束集合将输入数据库转换为另一个数据库，其中每个元组都带有其违反的约束集合的注释。我们依靠why-provenance [49, 73]来计算这样的注释。TBSNATSSminNATSSmax150基于约束的度量方法0度量单调的前k个算法0CBM � NA，TopIncMem，TopINC0CBS � NA，TopINC0CSM min � NA，TopMultiSet，TopINCDE CSM max �0CSS min � NA，TopIncSet，TopINCDE CSS max �基于元组的度量0TBM � NA，TupIncRank0TSM min � NA，TopMultiSet，TopINCDE TSM max �0表1.1：度量及其关联的前k个算法0•查询评估步骤，我们将查询类别定义为连接查询类别。使用多项式溯源[74]在转换后的数据库上对查询进行评估。在查询评估步骤中，可以根据其不一致度对查询答案进行排名，并使用本论文中定义的前k个算法之一选择前k个最有趣的答案（最一致/最不一致）。0在本论文中，我们提出了以下技术贡献：01.我们针对不一致数据库中的连接查询设计了新的查询答案不一致度度量方法，同时考虑了一组否定约束4.4。具体而言，我们考虑了两种方法来量化查询答案的不一致度：0•基于元组的方法，设t为查询答案，这类度量方法计算参与计算t的不一致元组的数量。我们在这个类别中提出了六种不同的查询答案不一致度度量方法[86]。0•基于约束的方法，考虑到一个查询答案t，这类度量方法计算参与计算t的元组违反的约束数量。我们在这个类别中提出了六种查询答案不一致度的度量方法[87]。02. 我们基于这些度量方法定义了前k个问题和阈值问题[87]。0•根据它们所最小化的成本模型的性质，我们将前k个算法分为两类：基于磁盘的算法和基于内存的算法。0•我们设计了新的前k个算法，以高效地计算在输入评分函数为上述度量方法集合的情况下的前k个答案。03. 我们在理论上展示了这些算法的效率160关系型数据库管理系统0数据库注释0否定约束集合0Q：连接查询0查询评估、意识到的不一致性、排名和过滤0Q的答案集及其不一致度0图1.1：关系数据库中意识到的不一致性的框架0•我们定义了一种新的算法类别，称为半盲算法（SBA），包括使用单调评分函数和非单调评分函数的算法。0• 我们引入了一种新的成本模型，称为cost∆，它在避免具有相同分数但不同连接属性值的元组引起的不确定性的同时，最小化了在磁盘上读取的元组数量。0• 我们展示了这些前k个算法在基于磁盘的SBA类中相对于我们的新成本模型cost∆的最优性。对于基于内存的算法，我们证明它们在数据复杂度上是多项式的。04.我们通过实验证明了我们的主要算法[87]的效率。0•对一些度量的运行时间进行了研究和分析。0•还分析了预处理阶段所消耗的时间。0•我们对一些度量进行了质量评估实验。05.我们开发了一个名为INCA系统的工具，允许用户基于不一致性量化来探索数据概要和查询回答概要。06.我们提出了一个初步的工作来处理约束集不一致的情况。0组织结构0本论文的组织结构如下：第2章介绍背景；第3章讨论现有技术；第4章介绍本论文提出的不一致度度量集合；第5章介绍了针对所提出的不一致度度量的不同top-k算法；第6章在约束集存在不一致性的情况下扩展了不一致度度量；第7章致力于对所提出的度量和top-k算法进行实验和评估。170算法；第8章探索我们的不一致性原型INCA系统；第9章总结本论文并提出一些展望。在下一章中，我们将描述数据库管理领域对本论文的必要背景。180第2章0初步概念0本章介绍了本论文中使用的一些基本概念和符号表示法。首先，我们回顾了关系数据库中的一些相关概念，然后介绍了top-k处理和最优连接处理中的不同概念。02.1关系数据库0我们假设读者已经熟悉关系数据库[4]。我们提供关系数据库[4]的形式定义以及本论文中使用的不同符号表示法。数据库的域是一个无限常量集合，用D表示。数据库模式，表示为S = {R1, ...,Rn}，是一个有限的关系/谓词集合，使得D ∩ S =�。设SetAttrs是一个可数的无限属性名称集合，使得S ∩ SetAttrs = �且D ∩ SetAttrs =�。对于每个关系R ∈ S，函数Attr将一组属性从SetAttrs关联到R（即，Attr：S → Pfin(SetAttrs)，其中Pfin(SetAttrs)是SetAttrs的有限幂集）。给定一个关系R，则Attr(R)称为R的属性集。元组t是从P fin(SetAttrs)的有限子集A到域D的函数；我们说t是属性集A的元组。关系R ∈S是属性集Attr(R)的有限元组集。我们用R(t)表示t是关系R的元组，也用t ∈R表示。从模式S和域D构建的关系数据库（或简称数据库或实例）是来自模式S的有限关系集合[4]。数据库实例I中的关系表示为I(R)。设id是将每个元组关联到唯一标识符的函数，因此元组t的标识符表示为id(t)。我们用Γ表示所考虑的数据库实例的所有标识符的集合。0示例2.1.考虑由以下关系education组成的关系模式，education = {Student,Course}，域D来自（无限）字符串集合。我们有Attr(Student) = {Register_Number, Name,Pref_Course}和Attr(Course) = {Course_ID, title}。来自education和D的数据库实例的示例是0R EGISTER _N UMBER N AME P REF _C OURSE0M 01 Alice C 020M 02 Bob C 010COURSE_ID TITLE0C 01 计算机科学0C 02 物理学0C 02 生物学0第一个关系Student记录了学生及其首选课程，第二个关系（Course）记录了课程。̸̸̸1902.2 连词查询0在接下来的内容中，我们介绍连词查询，即本论文中使用的主要查询类。连词查询（CQ）的类被定义为以下形式的查询集合：Q（u）←R 1（u 1），...，R n（u m），φ（u 1，...，um）（2.1）0其中每个R i是S中的关系符号，Q是输出模式O中的关系符号，每个u i是具有与R i相同的元数的变量和/或常量的元组，u是一个特殊变量的元组。这些是在查询中出现在元组u i中的变量，其中i∈{1，...，m}，即Var（u）��0i∈{1，...，m} Var（u0返回元组中的变量集合）和/或常量。公式φ（u 1，...，um）是一个内建原子的合取形式，其中op∈{=，≠，≥，≤，<，>}（op是一个算术谓词），x和y要么是来自�的变量0i∈{1，...，m}0常量。查询Q中的变量集合表示为Vars（Q）。当连词查询不包含内建部分或内建部分仅包含等于（=）谓词时，它被称为等连词查询。任何等连词查询都可以转换为不包含内建公式的等连词查询（通过将y的每个实例重命名为x来消除每个内建谓词x = y）。我们说Q是一个0完全连词查询，如果Var（u）= m �0i = 1 Var（u0在域D上对Q的估值是一个函数v：Vars（Q）→D，扩展为常量的身份，即对于每个e∈D，v（e）= e。对于由变量和/或约束组成的元组t =（a 1，...，a p），v（t）=（v（a1），...，v（a p））。执行查询Q在实例I上的结果（或查询答案）Q（I）是：Q（I）={v（u）| v是Vars（Q）上的估值，对于所有i∈[1，n]，v（u i）∈I（R i）且φ（v（u1），...，v（um））为真}。连词查询的并集，表示为UCQ，是具有相同输出谓词的一组连词查询。设Q为连词查询，如果Q中至少有两个关系原子R i和R j满足R i = Rj，i≠j且i，j∈[1，m]，则查询Q是自连接连词查询。如果Q不是自连接连词查询，则查询Q是自由自连接连词查询。0例2.2 考虑以下查询 Stu_Cour（name，title）：-Student（mat，name，CourID），Course（Cour ID，title），title ≠”Physics”。查询Stu_Cour提取所有学生姓名及其首选课程，仅限于课程不等于”Physics”。0姓名 标题0Bob 计算机科学0只有一个估值v（v（name）= ”Bob”，v（title）= ”计算机科学”，v（mat）= ”M02”，v（Cour ID）= ”C 01”）满足查询Stu_Cour，任何其他估值都无法满足此查询。02.3 否定约束0在关系数据库的上下文中，已经研究了各种类别的数据库约束[16, 37,56]。在本论文中，我们考虑的是否定约束的类别，这是最常用的约束类别之一[126]。否定约束的类别
我的内容管理
收起
我的收益 登录查看自己的收益
我的积分
登录查看自己的积分
我的C币
登录后查看C币余额
我的收藏 
我的下载 
下载帮助 
