英语原文共 12 页，剩余内容已隐藏，支付完成后下载完整资料

关系型数据库中的关键词检索

摘要

DISCOVER在关系数据库上运行，并通过允许用户在不了解数据库模式或SQL的情况下发布关键字查询来促进信息发现。 DISCOVER返回被允许加入的元组网络，也就是说，由于它们连接在主键和外键上并且统称包含查询的所有关键字，所以它们是相关联的一组元组。 DISCOVER分两步进行。首先，候选网络生成器生成所有候选的关系网络，即加入生成加入网络的表达式。然后，计划生成器构建有效评估一组候选网络的计划，利用机会重用候选网络的公共子表达式。

我们证明，DISCOVER通过利用模式的结构，发现没有冗余的所有相关候选网络，其大小可以是数据绑定的。我们证明选择最优执行计划（重用普通子表达式的方式）是NP完成的。我们提供一个贪心算法，我们显示它提供了近乎最优的计划执行时间成本。我们的实验还提供了调整贪心算法的提示。

1 介绍

关键字搜索是最受欢迎的信息发现方法，因为用户不需要知道查询语言或数据的基础结构。 今天提供的搜索引擎可以在文档集之上提供关键字搜索。 当用户提供一组关键字时，搜索引擎返回与这些关键字相关联的所有文档。 通常，当关键字包含在文档中时，关键字和文档是相关联的，并且它们的关联程度和彼此的距离有关。

除了文件之外，大量的信息存储在关系数据库中，但在关系数据库对于信息查询的支持并不好。 关系数据库的用户需要知道数据库的模式，SQL或一些类似QBE的接口，以及查询中使用的各种实体和术语的角色。 DISCOVER的用户不需要上述任何知识。 相反，DISCOVER通过向数据库提供简单的关键字搜索界面来实现信息查询。

例如，考虑图1所示的TPC-H模式和图2中的实例。图1中的箭头指向表之间的主键到外键（一对多）关系的方向。 考虑用户搜索关键词“史密斯”和“米勒”关联的信息。 DISCOVER提供了一个简单的界面，用户只需简单地输入关键字，就像他在搜索引擎上一样。 根据DISCOVER，如果两个关键字包含在两个关联的元组中，即两个通过外键加入到主键关系的元组，这可能涉及更多的元组，则存在两个关键字之间的关联。 这种联系形式特别有用且具有挑战性。 （我们最后对其他关联标准进行评论。）DISCOVER不需要用户知道关键字和关键字的属性。

例如，考虑图1所示的TPC-H模式和图2中的实例。图1中的箭头指向表之间的主键到外键（一对多）关系的方向。 考虑用户搜索关键词“Smith”和“Miller”关联的信息。 DISCOVER提供了一个简单的界面，用户只需简单地输入关键字，就像他在搜索引擎上一样。 根据DISCOVER，如果两个关键字包含在两个关联的元组中，即两个通过外键加入到主键关系的元组，这可能涉及更多的元组，则两个关键词之间存在关联。 这种联系形式特别有用且具有挑战性。 （我们最后对其他关联标准进行评论。）DISCOVER不需要用户知道关键字和关键字的属性。

查询的解决方案是包含关键字“Smith”和“Miller”的两个最小连接序列，即和。 它们是最小的，因为不能排除元组，并且仍然包含关键字的序列。 我们使用符号表示元组a与元组b在其主键上与外键关系连接。 第一个加入顺序显示，“Smith”和“Miller”都是为客户Brad Lou服务的文员，而第二个只是说，文员分别为来自美国的Brad Lou和George Walters客户提供服务。 直观地，第一个加入序列比第二个加入序列更有用，因为它显示了“Smith”和“Miller”之间的更紧密的联系。 基于对这种直觉的概括，我们根据它们涉及的联接次数对连接序列进行排序。 DISCOVER首先输出较短的序列。

当涉及两个以上的关键字时，最小连接顺序可能不足以表示解决方案。 因此，我们引入了最小的加入网络，它们是元组的树，其中任何两个相邻元组通过主键加入到外键关系中。

DISCOVER用于查找加入网络的高层次表示如图3所示。 首先，用户给系统提供一组关键词。 这些关键字在主索引中查找，该索引返回每个关系的元组集合。的每个元组包含关键词作为的一部分属性值。 然后，

DISCOVER计算所有候选网络，即，在关系或元组集合的主键关系的外部连接表达式，如图3所示。候选网络集合被保证产生所有最小加入网络。

然后DISCOVER评估候选网络。由于问题的性质，候选网络共享连接表达式。 这提供了构建一组中间结果并将其用于计算多个候选网络的机会。 计划生成器生成一个计划并使用中间结果来评估候选网络的执行计划。 最初为执行计划的每一行生成一个SQL语句，并将这些语句传递给DBMS。 DBMS返回作为解决问题的元组的连接网络。

注意候选网络可以具有仅由数据集约束的多个连接，如稍后解释的。 在这些情况下，用户提供最大数量的联接，并且DISCOVER递增地输出所有直到T大小的网络。

上述过程中涉及的挑战和本文的贡献如下：

• 我们在关系数据库中形成关键字搜索，并提供直观的语义。
• 我们提出了一个模块化的架构，并基于它实现了DISCOVER。
• 我们提出一种有效的候选网络生成算法。原始的方法是生成包含所有关键字的所有连接表达式，直到大小为T，然后评估它们。 但是，我们通过利用数据库模式的属性和主索引重新生成的信息来删减了许多内容。例如在关键词查询“Smith，Miller”中，候选网络被删减了因为没有关键字，并且它在连接序列链的最后，它不能帮助连接任何可能导致关键字的元组。 由于更复杂的原因，关于稍后讨论的外键关系的主要关键字的结构，候选网络也被排除在外。
• 我们证明候选网络生成算法创建了一个完整和非冗余的候选网络集合，其中“完整”意味着该组候选网络产生所有最小连接的元组网络（达到给定大小T）和“ 非冗余“意味着如果该集合的任何候选网络被排除，则存在数据库实例，其中没有发现元组的最小加入网络。 还显示候选网络的结果总是最小化连接元组的网络。
• 我们指定何时最大的网络由数据库模式的大小和数据库实例的大小绑定。 对于前一种情况，我们提供了定义作为数据库模式的函数的元组的最小连接网络的最大大小的定理。
• 我们提出一个成本模型。计划生成器模块使用中间结果来最小化所有候选网络的评估总成本。我们表明，选择最优中间结果集合的问题是对候选网络规模的NP-完成。然后，我们提出一种可调节的贪心算法，发现近似最优的计划，而不会受到最优规划算法所引起的不可接受的优化时间成本的影响。
• DISCOVER已经在Oracle 8i之上实现。 我们对DISCOVER和整个系统的模块进行了详细的实验评估。 显示了大部分生成的候选网络被删减。 此外，我们展示了如何调整贪心算法以实现最佳性能，并且我们显示整体性能远远超过明显的直接方法的性能。

在第2节中，我们将DISCOVER与其他相关工作进行比较。 第4节和第5节分别提出了候选网络发生器和计划生成器模块。 在第6节中，我们通过实验来评估DISCOVER的性能。 最后，在第7节中，我们总结并讨论了DISCOVER的未来扩展和改进。

2 相关工作

[MV00b，MV00a]中提供了当用户对该模式不了解的数据库关键字搜索框架。 引入了称为反射SQL（RSQL）的SQL的扩展，它统一地处理数据和查询。 这项工作的主要限制是所有关键字必须包含在同一个元组中。 也就是说，不考虑来自不同关系的元组之间的关系。

在[GSVGM98]和[ 02]中，数据库被视为具有对象/元组的图，作为边缘的节点和关系。关系根据每个应用程序的属性进行定义。例如，边缘可以表示主要到外键关系。在[GSVGM98]中，用户查询指定了两组对象，即Find和Near对象。这些对象可以由两个对应的关键字组生成。系统根据距离Near中的对象的距离，在“查找”中对对象进行排名。提出了一种通过构建集线器索引来有效地计算这些距离的算法。在[ 02]中，通过搜索包含所有关键字的Steiner树[Ple81]来提供关键字查询。使用感知法近似Steiner树问题。这些方法的缺点是必须为数据库创建和维护元组的图形。此外，数据库模式提供的重要结构信息被忽略，它们的算法适用于巨大的数据图。相比之下，DISCOVER被调整到关系数据库上的关键字搜索，并使用数据库模式的属性。它的关键算法在模式图上工作，比数据图小得多，并且不需要保留任何额外的数据表示。它利用数据库模式的属性来生成回答关键字查询所需的最少数量的SQL查询。此外，DISCOVER直接在数据库上运行，因此它不具有主存储空间限制。

候选网络生成器的工作提醒了算法来回答关于普遍关系的查询[Ull82]。 然而，普遍关系和发现之间存在许多重要的区别：首先，与DISCOVER的用户相比，通用关系（UR）的用户需要知道关键字的属性有明显的区别。 第二，DISCOVER创建高效的查询，找到包含关键字的元组之间的所有连接。 在这样做时，DIS- COVER与UR不同，必须找到大小可能不是模式绑定的连接，并且许多连接由DISCOVER的候选网络生成器修剪。 最后，除了找到有用的连接之外，DISCOVER利用了这些连接是“相关的”，即它们共享连接表达式的意义。 这导致了一个特殊的查询优化算法，这是针对我们问题的细节。

DBXplorer [ACD02]描述了一个多阶段系统来回答关系数据库中的关键字查询，并使用户免于普遍关系的第一个限制。 然而，它不考虑包括两个相同关系的解决方案。 此外，它们仅仅考虑了精确的匹配，其中关键字必须完全匹配属性值，并且不会利用连接树的可重用性机会，这是在DISCOVER的候选网络附近的简化概念。

Oracle 9i文本（[Ora01]）和IBM DB2文本信息扩展器（[DB201]）使用标准SQL为关系的文本属性创建全文索引。 Microsoft SQL Server 2000（[MSD01]）还提供了生成全文索引的工具，它们存储在数据库外部的文件中。 在所有三个系统中，用户在单个属性上创建全文索引，然后执行关键字查询，返回包含关键字的元组。 此外，关键字邻域查询在元组的单个属性中被支持，但不跨越不同的属性或类型。 正如我们讨论的那样，将关键字搜索推广到跨元组工作是非常具有挑战性的，问题与这些系统解决的文本索引问题不同。

我们用来决定连接表达式J，不是候选网络的标准之一，是J生成的元组的加入网络是否包含不止一次同一个元组。我们的决定这个属性的方法可以被看作是具有包含依赖关系的追逐技术的特殊情况[AHV95]。我们的算法比较简单，快速，可判定，因为它主要关注于主要的外部关键关系。

文献数据库（[Sal89]）已经对关键字搜索进行了很好的研究。例如[BP98]提供Google搜索引擎。[ACGM 01]提供了当前Web搜索引擎设计的概述。它还引入了一般的搜索引擎架构，涵盖了爬虫和索引问题。在[TWW 00]中，提出了算法，数据结构和软件，其处理基于关键字的文档搜索引擎对结构数据库（如解析树，分子图和XML文档）的查询的速度。[FKM99]解决XML数据库中的关键字搜索问题。他们提出扩展XML查询语言，可以以XML元素的粒度进行关键字搜索，这有助于新手用户制定查询，但不要考虑关键字优先级搜索。

计划生成器使用通用子表达式是一种多查询优化的形式[Sel88，Fin82，RSSB00]。 然而，DISCOVER中的候选网络具有特殊的属性，使我们能够开发出更直接和更有效的算法。 第一个属性是候选网络具有很小的关系[Ull82]作为叶子，当应用Wong-Yusefi算法[Ull82]时，这显着地减少了有用的公共子表达式的空间。第二，候选网络不是随机查询，而是按照第4节中所看到的，按照其生成的性质分享共同的子表达式。[Fin82]的技术不能应用于DISCOVER，因为它们专注于查找常见的子表达式作为查询的后期 优化和DISCOVER无法访问DBMS优化器。

3 框架

3.1 数据模型和关键词查询

我们考虑一个具有n个关系的数据库。 每个关系都有属性。 模式图G是一个有向图，它捕获数据库模式中外键关系的主键。 它具有用于数据库的每个关系的节点和用于从的一组属性到一组属性的外键关系的每个主键的边缘，其中表示k=1，hellip;，l。 我们将图定义为G的无向版本。

对于符号简单性，我们假设主对外键关系的属性具有相同的名称，并且在模式图中没有自循环或并行边。 所以边对应主键和外键属性。 我们还假设没有任何关系的属性集合是两个关系的主键和外键，这是任何现实的数据库模式设计的合理假设。 当这些假设不成立时，问题的泛化和解决方案是微不足道的。

我们表示一个元组的主键p(t)和其关键字S的外键。

定义1（连接元组网络）元组j的连接网络是一个元组树，对于每对相邻的元组，其中，在和中存在边。

元组的连接序列是元组网络的特殊情况，其中树的每个内部节点具有两个相邻的节点。 图2中的元组的连接序列的示例是，也表示为。

定义2（关键词队列）关键字查询是一组关键字资料编号：[141290]，资料为PDF文档或Word文档，PDF文档可免费转换为Word