关系数据库上基于索引的Top-N关键词查询.pdfVIP

第 37卷 第 6期 北 京 工 业 大 学 学 报 VOl_37 No．6 2011年 6月 JOURNALOFBEIJING UNIVERSITY OFTECHN0L0GY Jun．2011 关系数据库上基于索引的Top．N关键词查询 朱 亮 ，姬慎达 ，刘椿年 ，杨文柱 (1．河北大学 数学与计算机学院 河北省机器学习与计算智能重点实验室，河北 保定 071002； 2．北京工业大学 计算机学院，北京 100124) 摘 要 ：为了实现关系数据库上 自由态的关键词查询 ，通过创建索引表并运用其存储 的知识为每个属性赋予不 同的权值来改进信息检索 中传统的排序方法 ．对每个查询用索引表和改进的排序方法来获得 TopN答案．用实 际数据集进行 了实验 ，实验结果表明此方法在查询时间和准确性上是有效的． 关键词 ：查询 ；索引；元组树 ；排序策略 中图分类号 ：TP311．13 文献标志码 ：A 文章编号：0254—0037(2011)06—0940—07 传统关系数据库查询需要用户知道详细 的数据库模式和 SQL语言，这对于普通用户很困难．鉴于信 息检索(IR)和文档数据库中关键词查询的研究和应用 ，近年来对关系数据库 自由态的关键词查询的研究 成为热点之一．关键词查询能使用关键词从关系数据库中检索信息，而无需用户了解数据库模式和SQL 语言．文献[1]提出了实现关键词查询的一种框架 ，并提出了一种递增遍历查询结果的启发式算法．对于 查询结果 ，用查询结点的邻近度和结点间关联 的优先级 2个 因子计算适应度并排序 ；文献 [2]用符号表 (symboltable)存储关键词和相应的出现位置 ，通过维持符号表把要查询的多个关键词所在的关系作为图 结点连接起来 ，生成模式图的多个子图，每个子图转化为一个 SQL语句进行查询 ；文献 [3]考虑了用户对 数据库中关系名、属性名等元数据的查询 ；文献[4]改进 了文献 [1]的算法 ，提 出双向扩展查询算法 ；文献 [5]对返回的元组树进行聚类 ，把结构相似或同构 的元组树分为一组 ；对于查询效率 ，文献 [1—2]有 了改 进 ，但是计算查询结果的排序策略过于简单 ，都没有考虑借鉴信息检索中的排序方法．为 了提高查询 的准 确性 ，本文鉴于Top—N查询处理的方法 。，讨论了关系数据库中文本属性的Top．N关键词查询处理 ，通过 建立索引表存储相应元组词所在元组的词频 、元组中单词长度及元组词总的出现次数等 ，并且改进信息检 索中的排序方法 ，进而获得查询结果并排序得到 Top—N答案． 1 概念和术语 考虑 1个数据库有 n个关系 一， ，每个关系 有m 个属性 ，分别为 n；，…，n ． 1)模式图 。G是 1个连接数据库模式中外键一主键关联的有 向图．对于每个关系R，G中存在 1个 结点与之对应 ，图中的每条边 R一 ，表示数据库 中的 1个从 R 的属性集 (n 一，oi)到 的属性集 (n ，…，aJb)的外键一主键关联 ，其中。 。 (k=1，…，t)．另外 ，定义图G为图G的无 向图． 2)1棵元组树 是 1个查询结果，其树的结点为数据库 中的 1个元组．每对相邻的元组 t和t，分 别属于 R 和 f，存在 G中的 1条无向边 (R，R，)且 t t，ER Ri．元组树的大小是其包含结点(元组) 的个数． 3)1个元组集网络 。I，是 1棵元组集生成树．对于J中每对相邻的元组集R和 M，G有边(R，R，) 对其连接．其大小是包含结点(元组集)的个数． 收稿 日期 ：2009—03—28． 基金项 目：国家 自然科学基金资助项 目；河北大学博士基金资助项 目(2009—260) 作者简介 ：朱 亮 (1964一)，男 ，河北滦县人 ，教授． 第 6期 朱 亮 ，等：关系数据库上基于索引的Top—N关键词查询 94l 4)设 t是关系R的 1个元组 ，规范化后包含 n个不同的词 ，表示为 =(加 ， ，…， )，每个 称为 1个元组词．关系 所有元组词组成的集合记为：珂R)=U {zc，I ∈ }