数据库关键词搜索系统是目前的一个研究热点。首先，数据库关键词搜索系统为用户分析和探索数据库中的信息提供了极大的方便。从用户界面的角度来说，用关键词来查询数据库，用户既不需要学习像SQL这样复杂的查询语言，也不需要事先了解数据库的模式，而只需要关心如何用关键词来表达自己的信息需要。大多数用户在互联网上查找信息的时候都会使用搜索引擎。用户输入一些关键词，搜索引擎就能返回一个排序后的相关文档列表。数据库关键词搜索系统使得用户也能以同样的方式来查询数据库。　　其次，数据库关键词搜索系统为解决所谓的Hidden Web问题提供了一条可能的途径。在互联网上，通过搜索引擎只能找到一小部分数据。大量的数据则是被存储在数据库当中，只能通过特定的查询界面来查找。这些互联网上搜索引擎搜索不到的数据构成了所谓的Hidden Web。造成数据库中的数据被隐藏的原因之一就是搜索引擎和数据库系统采用不同的数据查询语言。因此，如果数据库系统能支持关键词搜索，那么在互联网上发布数据库和在互联网上找到存储在数据库中大量信息的过程就会变得更为简单容易。　　最后，也许是最重要的一个方面，现在已经有很多应用需要同时管理多种类型的数据。这些应用需要集成不同种类的信息管理系统，以便同时管理结构化的关系数据、半结构化的XML数据和非结构化的文本数据。同时管理多种类型数据时遇到的问题之一是查询不同种类的数据时要使用不同的查询语言:关系数据使用SQL; XML数据使用XQuery;文本数据使用关键词搜索。因此，在信息系统集成时，将关键词搜索作为一种统一的数据查询语言来查询不同种类的数据，是一个很有吸引力的方案。研究数据库关键词搜索系统可以为实现这个方案做出必要的准备。　　由于研究数据库关键词搜索系统具有上述重要意义，所以近年来数据库关键词搜索技术的研究受到了研究人员的广泛关注，已经开发出来了一些原型系统，如BANKS，DBXplorer，DISCOVER，ObjectRank等等。　　目前已有的数据库关键词搜索原型系统都包含预处理模块和查询处理模块两个组成部分，其中预处理模块负责在执行第一个用户查询前预先对数据库进行处理，以便生成查询处理模块需要的各种信息，加快系统处理用户查询的速度。在DISCOVER系统中，预处理模块只负责生成模式图，从模式图生成所有候选元组集连接树的工作是由查询处理模块完成的。能否对DISCOVER系统进行改进，将从模式图生成所有候选元组集连接树的工作从查询处理阶段转移到预处理阶段来做？论文的主要研究内容就是提出一种用于数据库关键词搜索系统的预处理新技术，给这个问题一个肯定的答案。　　在查询处理模块中从模式图生成所有候选元组集连接树时，要经历三个阶段。首先是读取数据库中的元数据建立数据库模式图，然后基于要搜索的关键词生成一个元组集图，最后使用一个启发式的搜索算法从元组集图中找出所有候选元组集连接树。　　直接将查询处理模块中从模式图生成所有候选元组集连接树的算法搬迁到预处理模块中是不可行的，这是因为以下三个原因:第一个原因是在预处理关系数据库时，由于不知道要搜索的关键词，所以只能生成规模巨大的元组集图。假设模式图中有两个关系，一个关系包含n个元组，另一个关系包含m个元组，则从该模式图生成的元组集图将包含2m+2n-2个结点和(2m-1)(2n-1)条边。第二个原因是对于规模巨大的元组集图，要从中找出所有的候选元组集连接树，启发式搜索算法的效率难以令人满意。第三个原因是启发式搜索算法找出的结果中存在大量同构的候选元组集连接树。　　论文最主要的创新是提出了候选元组集连接树模式的概念，并且以此概念为桥梁将模式图和候选元组集连接树联系起来。论文提出了一个基于产生式的扩展算法和和一个赋值算法。基于产生式的扩展算法用于从一个模式图生成所有候选元组集连接树模式，赋值算法用于从一个候选元组集连接树模式生成所有候选元组集连接树。通过这两个算法，论文就避免了元组集图的生成，解决了在预处理模块中如何从模式图有效地生成所有候选元组集连接树的问题。　　基于产生式的扩展算法分成三个步骤进行。首先是从数据库的模式图生成产生式的集合。其次是从模式图中选择一个结点，从这个结点开始扩展，生成包含它的所有不同构候选元组集连接树模式，并在扩展结束后将该结点从模式图中删除。最后是反复进行第二个步骤，直到模式图中不包含任何结点。为了能够有效地从模式图生成所有不同构候选元组集连接树模式，论文提出了三个产生式选用规则、从一个结点开始生成所有标准有根有序树的最右边路径扩展算法、和判别两棵无根无序树是否同构的方法。　　赋值算法分成两个步骤进行，首先对候选元组集连接树模式的叶子结点赋值，然后对它的内部结点赋值。设计赋值算法的难点在于要保证生成的所有候选元组集连接树互不同构。由于候选元组集连接树模式中存在等价结点，对叶子结点赋值可能生成同构的中间模式。为了解决这个问题，论文提出了先序分配的方法，该方法在先序遍历候选元组集连接树模式的过程中，每当遇到一个内部结点，就将分配给该结点的所有元组集分配给它的孩子，并且这种分配不会生成同构的中间模式。由于在对叶子结点赋值之后得到的所有中间模式是互不同构的，对内部结点赋值可以转换为一个数学上的排列问题。　　在预处理阶段生成的所有候选元组集连接树需要存储起来以备关键词查询处理时选用。由于在对候选元组集连接树模式的赋值中包含排列组合运算，可以预期随着候选元组集连接树模式中包含结点个数的增加，生成的候选元组集连接树的总数将快速增长，并且这种增长将导致存储候选元组集连接树占用的存储容量过于庞大。在关键词查询处理时，庞大的存储容量占用将极大地降低查找候选元组集连接树的效率。为了解决这个问题，论文提出了存储中间模式的方法，该方法避免了候选元组集连接树的存储。　　实验结果表明，论文提出的预处理新技术是可行的，它能够使得数据库关键词搜索系统的可扩展性更好。论文的创新包括:　　1)提出了一种新的数据库关键词搜索系统分类方法。这种分类方法基于一个查询结果中包含的数据图结点个数和查询算法是否需要遍历数据图，将已有的数据库关键词搜索系统分为四个类别，有助于研究人员了解数据库关键词搜索系统的研究现状和研究新的数据库关键词搜索系统。　　2)提出了一种新的预处理技术来提高数据库关键词搜索系统的性能。这种新的预处理技术从模式图生成所有的候选元组集连接树，从而避免了在处理用户查询时遍历临时构造的元组集图，加快了系统处理用户查询的速度。　　3)第一个提出了一种查询结果分类方法。目前已有的数据库关键词搜索系统都不支持对查询结果分类。类似的查询结果太多，将对用户产生消极的影响。由于一个候选元组集连接树模式生成的所有候选元组集连接树同构，所以论文提出的分类方法使用候选元组集连接树模式作为查询结果分类标准。　　4)提出了新的查询结果计分公式。查询结果计分公式决定了查询结果的排列顺序。不同的数据库关键词搜索系统有不同的查询结果计分公式。论文提出的查询结果计分公式综合了已有的查询结果计分公式的优点。如果不考虑数据库系统全文搜索功能返回的分数值，则论文提出的计分公式类似于BANKS系统的计分公式。如果只考虑数据库系统全文搜索功能返回的分数值和元组连接树的大小，则论文提出的计分公式就演变成了DISCOVER系统的计分公式。　　5)提出了一个新的数据库关键词搜索系统体系结构。在这个体系结构中，采用了论文提出的预处理新技术，可以对查询结果进行分类浏览，并在查询处理时实现了基于新的查询结果计分公式的top-k关键词查询。　　6)论文将研究成果运用到实际当中，设计和实现了一个名为Hunter的数据库关键词搜索系统。