英语原文共 6 页
SQL可能和确定的关键词
摘要
在关系模型的主导地位和现代应用程序的要求的驱动下，我们重新审视了关系数据库中具有NULL的密钥的基本概念。在SQL中，主键列是NOT NULL，UNIQUE约束仅保证没有NULL的元组的唯一性。我们研究了可能和某些键的概念，这些键分别是源自SQL表的一些或所有可能世界中的键。可能的键与UNIQUE重合，从而为SQL标准中的语法定义提供语义。某些键扩展主键包括NULL列，并且可以在可行时唯一地标识实体，而主键可以不会。除了基本特征描述，公理化，发现和极端组合问题，我们研究了Armstrong表的存在和构造，并描述了用于强制执行某些键的索引方案。我们的实验表明，某些具有NULL的键出现在实际数据中，并且可以有效地解决相关的计算问题。因此，某些密钥具有良好的基础，能够满足Codd的实体完整性规则，同时处理来自不同格式的大量不完整数据。
关键词：Armstrong数据库、公理化、数据剖析、发现、极值组合、蕴涵问题、索引、密钥、空标记、SQL
1简介
密钥始终是数据管理的核心推动者。它们是理解数据结构和语义的基础。给定一组实体，密钥是一组属性，其值唯一地标识集合中的实体。例如，关系表的键是一组列，使得在每个键列中没有两个不同的行具有匹配值。密钥对于许多其他数据模型至关重要，包括语义模型，对象模型，XML和RDF。它们是许多经典数据管理领域的基础，包括数据建模，数据库设计，索引和查询优化。关于密钥的知识使我们能够（i）跨数据存储库唯一地引用实体，（ii）在模式设计时最小化数据冗余以在运行时有效地处理更新，（iii）在基于成本的查询优化中提供更好的选择性估计，（iv） 为查询优化器提供新的访问路径，可以在查询处理中实现大幅加速，（v）允许数据库管理员（DBA）通过物理设计技术（如数据分区或索引和物化视图的创建）提高数据访问效率，（vi）提供有关应用程序数据的新见解。现代应用程序进一步提高了密钥的重要性，他们能方便数据集成过程，有助于检测重复和异常，提供修复指导和清理数据，并返回一致的查询答案过脏的数据。从数据中发现密钥是其中之一数据分析中的核心活动。
据Gartner称，到2018年，NoSQL市场每年的价值将达到35亿美元，但对于相对数据库技术而言每年将价值400亿美元[12]。这强调了“关系数据库是
没有替代的重要数据“[12]。出于这些原因，关系数据库必须满足现代应用程序的基本要求，包括大数据。一方面，关系技术必须处理数据量，种类和速度的增加。另一方面，仍然必须强制执行数据的准确性和质量，以支持数据驱动的决策。因此，关系数据库必须具备这一点：在不牺牲可靠的数据质量水平的情况下获取尽可能多的数据。 Null构成了一种方便的关系工具，可以容纳来自不同格式的大量不完整数据。遗憾的是，nulls反对当前关键数据质量的黄金标准，即Codd的实体完整性规则。实体完整性声明每个表必须具有主键，并且构成主键的列必须是唯一的而不是null [10]。实体完整性的目标是确保可以在数据库表中有效地识别真实世界的实体。在SQL中，通过向模式定义添加主键子句来实施实体完整性。
表1 literature_references表的片段I
我们通过以下示例来说明这种权衡。在表1中的RFAM（RNA系列）数据集中，包含了arts_references表的快照I。该表违反了实体完整性，因为I违反了模式上的每个潜在主键。特别是，列日志带有空标记perp;。尽管如此，I中的每个元组都可以通过列对的组合进行唯一标识，例如（标题，期刊）或（作者，期刊）.因此，句法主键要求禁止在没有充分理由的情况下输入某些数据。无法将重要数据插入数据库可能会迫使组织放弃密钥验证，将其未来数据暴露于质量较低，数据处理效率低下，资源浪费和数据驱动决策不良的情况。找到更自由的密钥概念将带来一种新技术，它比主键更能满足现代应用程序的要求。这些观察结果促使我们引入具有良好基础语义的SQL密钥。为此，我们将occurrence的出现解释为无信息[36]。我们使用SQL表中产生的可能世界，通过相应域中的值独立地替换每次出现的perp;，并且缺失信息由区分域“值”N / A表示不适用。因此，我们的数据模型可以容纳未知和缺失的信息，并且是第一个通过无信息解释来分析可能的世界语义。在每个可能的世界中，N / A的出现与每个其他域值一样被处理。特别是，两个域值之间的等式关系延伸到N / A。也就是说，当且仅当v = N / A时，N / A等于域值v。这是完全合理的，因为在每个可能的世界中，由represented代表的每个未知信息已经被不同于N / A的实际域值所取代。然而，如果我们将可能世界中两种不同的N / A解释为不相等，我们的所有结果也都成立。总之，每个可能的世界都可以作为可能发生重复元组的总元组的关系处理。像往常一样，当且仅当w中没有两个元组具有不同的元组标识并且在X中的所有属性上匹配值时，可能的世界w满足键X.例如，表2中的I的可能世界w1满足{journal}，{author，journal}和{title，journal}等密钥，以及表3中I的可能世界w2满足密钥{author，journal}和{title，journal}，但违反了密钥{journal}。特别是，世界w1模拟了Genom广泛检测的纸张的情况。由Ragh,R尚未在期刊上发表。如果需要，我们还可以规定密钥的最低要求。
表2 表1中代码片段I的可能世界w1
表3 表1中的片段I的可能世界w2
我们的方法自然建议使用SQL键的两种语义。一个可能的键p (X)由一个SQL表I来满足，如果存在某个可能的I世界，其中键X得到满足。如果某个键X在I的每个可能的世界中都满足，那么SQL表I就满足某个键c (X)。特别是,某些键不会阻止进入仍然可以确定唯一的不完整的元组,独立perp;事件代表的信息。例如，表1中的snapshot I满足表2中world w1所见的可能key p journal，但违反了表3中world w2所见的特定key c journal。此外，我还满足某些键c title, journal和c author, journal。该示例说明主键仅满足于唯一标识SQL表中的元组，而某些键也是必需的。也就是说，主键在其所有键列中都没有perp;时唯一标识所有元组。但是，有一些SQL表，在这些表中，不必在关键列中禁止出现空标记，以便识别每个元组。如前所述，密钥和唯一性约束的影响区域适用于某些和可能的密钥。因此，重要的是要研究关于可能和某些键的基本问题，从它们的语义定义和句法表征，到它们相关的跟踪问题的计算复杂性，从给定的SQL发现它们的能力。
表和识别在给定应用程序域中有意义的键，最大系列非冗余键的描述，以及有助于有效验证密钥的索引设计的标识。我们的贡献可归纳如下：
1.我们在空标记出现的最基本解释下提出了SQL表上第一个可能的世界语义perp;作为无信息。在这里，由Codd的空标记N / A替换perp;不适用意味着这种出现的perp;表示缺失信息，而用实际域值替换perp;意味着这种出现的perp;表示未知信息。当密钥在某个可能的世界中占据时，密钥是可能的，而当密钥在所有可能的世界中保持时，密钥是确定的。
2.我们为vali建立简单的语法特征，直接在给定的SQL表上记录可能和某些键的满足。允许可能的世界成为多集合意味着可能的键为UNIQUE约束提供语义。
3.我们通过一种在输入中以线性时间工作的算法来表征可能的和某些键的组合以及NOT NULL约束的蕴涵问题。因此，我们可以有效地计算约束的最小覆盖率，从而将完整性维护的数量减少到必要的最低水平。我们的算法只需要很少的时间来完成所有未来的密钥冗余强制执行，这样可以在数据集变大时节省更多时间。
4.我们解决了可能和某些键的数据驱动发现问题。利用超图横向，我们建立了一个紧凑的算法来计算保留给定表的可能和某些键的覆盖。我们将算法应用于实际数据，表明在实践中可能和某些键经常发生。
5.我们通过模式驱动的方法来补充数据驱动的可能和某些密钥的发现。为此，我们研究了Armstrong表的结构和计算方面。给定一些可能的键，某些键和NOT NULL约束，此集合的Armstrong表是一个SQL表，它满足此集合中的约束但违反了所有可能的键，某些键和NOT NULL约束，这些都不是由集合。例如，表1中的快照I是针对Plt;journalgt;，clt;titlegt;，journalgt;，clt;author，journalgt;的Armstrong表。和标题和作者的NOT NULL约束。尽管在理想化的关系特殊情况下遇到了更多涉及的挑战，但我们描述了何时存在Armstrong表以及如何在这些情况下计算它们。理论上，在输入中是最坏情况的双重指数，实验表明我们的算法
在平均几毫秒内产生少于十行的表格。
6.有意义的密钥很少包含所有具有少量域值的属性。尽管如此，我们还是根据小域要求（例如布尔值）来调查可能的和某些键。虽然我们对某些键的句法表征仍然存在，但我们表明决定可能的键集的满意度变得非常难以理解。首先，这意味着某些键的概念是健壮的。其次，NP-硬度结果促使我们采用 - 对于有限域 UNIQUE的句法概念而不是可能键的语义概念。这确保了我们对有限域的推理和发现的贡献。最后，我们的结果也从一个组合的角度证明了UNIQUE的句法概念。另外，我们展示当某个键包含一些具有无限域的NOT NULL属性并且每个可能的键包含一些具有无限域的属性时，如何构造Armstrong表。
7.对于数据库设计者来说，询问有多大的非冗余系列完整性约束可能是一个自然的问题。这个问题的答案为设计者提供了复杂完整性的上限维护。这可能导致要求限制密钥的大小。然后可以询问有限大小的密钥可以变成多大的非冗余族。使用极值集理论，我们识别可能的密钥的非冗余族和在给定的NOT NULL约束下获得最大基数的某些密钥，即使我们将密钥限制为那些遵循属性数量上限的密钥。换句话说，我们的结果表征了最大基数的最小覆盖。
8.我们为某些密钥提出索引方案。与在具有1亿个元组且没有索引的数据集上强制执行密钥相比，我们的方案将插入上的某些密钥的执行提高了104倍。
它的工作速度只比主键强制慢一些，前提是某些键只有少量列可以出现空标记。利用我们之前的数据驱动发现算法，我们发现只有某些键，其中最多两列具有空标记。我们的研究结果表明，在现代应用的要求下，某些键如何达到Codd实体完整性原则的黄金标准。
组织
第2节讨论相关工作，Sect.2中引入了可能的和某些键。在这里，我们还建立了他们的语法特征和解决方案，以解释他们的暗示和发现问题。阿姆斯壮表的结构和计算方面在Sect.3中进行了研究。所有这些结果都在Sect.4的一个小领域的假设下进行了审查。在Sect.5中研究了极值问题。 在Sect.6中建立了一种用于执行某些密钥的有效索引方案。我们的实验结果见Sect.7我们在Sect.8中得出结论。第5节使用Sect.9的材料。 基于Sect.5。.第6节可以在Sect.4之后阅读。.第7节可以在Sect.3之后阅读。最后Sect.8指的是Sects的不同结果:3,4和7。
表4 ncbi_taxonomy数据集的片段
2相关工作
完整性约束强制实施数据库系统中应用程序域的语义。它们构成了数据库技术的基石。实体完整性是Codd 提出的三个固有完整性规则之一。密钥和外键是约100类约束中唯一享受SQL数据库系统内置支持的约束和外键。特别是，实体完整性由主键强制执行。核心问题调查推理armstrong数据库核心问题发现。应用包括一致的查询答案，数据清理，交换，融合，集成，分析，质量和安全，模式设计，查询优化，查看维护。代理键（“自动增量”字段）通常被视为实施实体完整性的实用解决方案。频繁的论点是在架构更改下的性能改进和稳健性。实际上，语义键也可以归结为。我们说明了代理键如何导致实体重复。表4显示了来自PFAM（蛋白质家族）的ncbi_taxonomy表的真实样本S数据集。在这里ncbi_taxid是一个代理主键。S的前两行说明尽管存在代理键，但某些实体，即物种和分类的组合，是重复的。相反，如果有意义的某些关键词c species, taxonomy 已经执行，则可以避免违反实体完整性。这种情况也不例外。在新西兰，医院患者通过其国家健康指数（NHI）数字进行鉴定。在2003年的12个月重复解决方案中，解决了超过125,000个重复的NHI号码。这意味着有多个NHI号码的人。同一患者的所有NHI数字不可用意味着健康史不完整，这可能导致致命的错误决定。然而，密钥并不旨在解决重复检测问题。直观地说，有意义的密钥的违反应该只导致一小部分元组复制实体。
关系模型最重要的扩展之一是不完整的信息，因为在应用程序中对这种信息的正确处理有很高的要求。用于扩展代数运算符以获取信息的具有里程碑意义的论文是。空标记解释的两个最多产的提议是“目前未知的价值”和“无信息”。前者有一个很好的建立了的可能的世界语义，但没有涵盖缺失的信息，虽然后者可以表达未知和缺失的信息，但以前的研究没有将可能的世界语义与它联系起来。在我们的知识方面，我们的研究首先结合了两者的优点：SQL表可以使用“无信息”空来表示未知和缺失的信息，并且我们通过替换perp;从SQL表中获取可能的世界使用N / A表示缺失信息，并将perp;替换为实际域值以表示未知信息。
表5 SQL表I1和I2
因此，我们的数据模型构成了约束语义的原则性通用方法。 Levene和Loizou引入了强弱函数依赖（FD）。弱势FD占据了一些可能的世界，而强大的FD占据了每个可能的世界。因此，强/弱FD和可能/某些密钥密切相关。然而，既不是某些特殊情况下强FD的特殊情况，也不是可能的弱FD特殊情况
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
