结合查询相关性的关键词查询排序方法

杨书新，徐慧琴，谭 伟

（江西理工大学 信息工程学院，江西 赣州341000）

0 引 言

关系数据库关键词查询旨在为用户提供类搜索引擎的方法实现基于关键词的数据库内容查询，它不要求用户熟悉复杂的结构化查询语言 （如SQL，SPARQL等）和底层数据库模式的知识。关系数据库关键词查询枚举所有查询结果的方法主要由两部分组成：根据用户给定的关键词集合Q，产生一系列候选结果集合；对候选结果集进行相关度降序排序。一个优秀的关键词查询系统必需满足以下三点要求：①查询效率高；②能枚举所有与查询相关的结果；③一个满足用户需求的相关性评分函数。然而，要很好的满足以上三点要求依然存在很大的挑战，因此，关系数据库关键词查询方法的研究依然是数据库研究领域的一个重点。

文中针对要求③中的排序问题研究如何有效的对结果进行排序，目前已有的排序方法通常考虑的影响因素比较单一，因此，文中提出结合结果树结构权重和关键词与包含关键词元组之间的相关性对结果进行排序的方法。在基于结构权重的排序方法基础上引入相关性权重，可以使排列在前面的结果树不仅结构紧凑而且与查询条件高度相关。

1 相关工作

目前，已有的研究通常将关系数据库关键词查询转换为对图的查询，基于图关键词查询的结果排序主要有两种：基于图结构权重的方法和基于IR式排序的方法。

文献 ［1－2］采用路径代价来衡量结果的质量，当所有关键词节点到中心节点的总路径权重越小，查询到的结果树就越紧凑，结果质量也就越高。

不同于以上采用基于图结构权重的排序方法，文献［3－4］采用IR式排序方法，为结果中的每个元组附一个IR分值，结果树的IR分值取结果树中所有元组IR分值的平均值。F.Liu等人在文献 ［3］中对KQORD和传统的IR排序方法进行分析，将一种结合了规范化因子的IR评分方法应用于结果排序中。在IR式结果排序的基础上，Y.Luo等人在文献 ［4］的排序方法中引入虚拟文档模型的概念，计算查询结果与关键词的相关度。

文献 ［5－7］为了完整表达关键词之间的语义关系，受Steiner树的启发提出了Steiner图问题。

由上述可知，很多研究在结果排序方面考虑的元素比较单一，因此，在接下来的篇幅中，文中将在查询结果的呈现方面联合基于图结构权重和基于IR式排序方法的优点，提出一种新的排序方法，采用结合结果树的结构权重和查询相关性的方法对结果进行排序。

2 数据模型

许多领域中的大量数据 （例如生物网络，社会网络等）都可以建模成图的结构。基于图数据结构的关系数据库关键词查询方法可以根据用户给定的一组查询关键词Q产生由核心节点 （所有关键词节点所能到达的节点），信息节点（关键词节点），路径节点和相关边构成的一系列子树作为查询结果。查询结果必须满足如下两个约束：①完全性约束：结果中必须包含用户给定的所有关键词；②非冗余性约束：当结果子树的子树依然包含所有的关键词，或者一个结果包含于另一个查询结果时，都属于冗余结果，必须进行剪枝。

现有方法中的数据模型主要可分为两大类：模式图和数据图。在模式图中，节点对应数据库中的关系表，边对应表与表之间的主外码引用关系；在数据图中，节点表示关系表中元组记录，边表示元组与元组之间的主外码关系。数据图可表示非结构化数据，半结构化数据和结构化数据。由于数据图广泛的应用性，基于数据图的关键词查询方法备受关注，基于数据图的查询系统有BANKS－Ⅰ，BANK－Ⅱ，EASE［5］等。

定义1 数据图：假设G＝（V，E）是关系数据库对应的数据图，G表示一个有向带权图，V为图中节点集合，E为图中边的集合，数据库中的每条元组记录看作是图中的节点，如果存在表中任意两个元组ti，tj存在主外码引用关系，则有 ＜ti，tj＞∈E或 ＜tj，ti＞∈E。

关系数据库关键词查询中，给定一组查询条件Q＝（q1，q2，…qn），系统找到包含关键词的信息碎片 （包含关键词的元组记录），合理的组织这些信息碎片，构成非冗余的结果组Steiner树，一个查询条件通常会产生大量结果，随机排列结果显然不符合用户的需求，因此，定义一个相关性评分函数很有必要，使结果集按照某种特定的顺序呈现在客户端，将用户感兴趣的结果靠前排列。

3 结果排序方法

到目前为止，一些基于最小Steiner树问题以及它的变型通常只考虑边的权重而忽视了节点权重或者考虑了节点权重也只是假设它们的权重是相等的，但实际上，包含关键词节点和关键词可达节点的重要性并不是等同的，因此，在本节中，结果树评分函数将结合结构权重和节点的相关性权重。

3.1 基于结构的权重计算

根据权威度的定义，当一个参与者有许多的链入链接时，它就是权威的。对于数据图而言，一个节点的入度越大，它的权威度就越高。因此，用节点权威度可以很理想的表示节点的权重，式 （1）给出单个节点的权重计算公式，用平均节点权重表示结果树的节点权重，如式 （2）所示

式中：incom（v）——节点v的入度，incommax——数据图中的节点最大入度，｜T｜——结果子树中的节点个数。

以往的一些研究对有向图G的正反向边的权值并未给予区分，这显然不符合实际应用，文中在对数据进行预处理时，为正向边和反向边设定不同的权值，如式 （3）所示，正向边设权值为1，式 （4）给出结果树中边权重分量的计算方法，边权重越小，结果树分数越大，采用log函数求边权重和可以有效减小结果树评分函数中边权重部分的变化幅度，其中Wmin（e）为图中最小边权重

3.2 基于相关性的权重计算

（1）关键词重要性分析

TF－IDF作为一种用于资讯探勘和资讯检索的常用加权技术，可用于评估一个词对于一个文件集 （语料库）中一个文件的重要程度。一个词的重要性与它在文件中出现的次数成正比，但同时与它在语料库中出现的频率成反比。

采用基于TF－IDF的方法计算关键词的重要性［8］，元组与给定的查询关键词的相关性与输入的关键词集合紧密联系，因此该值是动态的，随着给定的关键词变化而变化。

文中将每个元组单元建模成一个虚拟文档d，式 （5）给出求文档d中关键词qi的重要性标准化公式

ntf（qi，d）（标准词频），ndl（标准文档长度）和nidfqi（标准逆文档频率）［8］3个因子的计算公式如下

其中，tf（qi，d）为词频，表示关键词qi在文档 （元组）d中出现的次数，一个词在文档中出现得越频繁，重要性越大。dl表示文档长度，即元组中包含术语的个数，dl的出现可以有效降低长文本中关键词qi的重要性。avgdl表示文档的平均长度，s为0～1的平滑参数，通常取值为0.2。idfqi为逆文档频率，用文档频率的倒数表示，文档频率为包含某特定关键词的文档在总的文档集中出现次数，式 （8）给出了逆文档频率的标准化计算公式，D为文档d的集合，｜D｜表示总的文档数量，｜dfqi｜为包含关键词qi的元组数量。这里文档进行了分类，针对DBLP数据集而言，文档有author和paper两个类，如果关键词qi属于anthor类，那么｜D｜就为author元组的数量，否则就为paper元组的数量。

以图1中的数据子图为例，当查询条件Q＝ ｛Keyword，Relational｝时，包含关键词的节点为p1，p2和p3，下面分别给出这3个节点与查询条件相关性的计算过程。

图1 数据图子样

词频tf（qi，d）见表1。

表1 词频tf（qi，d）

逆文档频率idfqi见表2。

表2 逆文档频率idfqi

标准文档长度ndl见表3。

表3 标准文档长度ndl

节点与查询条件的相关性分数见表4。

表4 节点与查询条件的相关性分数

（2）节点与关键词相关性分析

为了描述元组与关键词的相关性，用RE（t，Q）表示元组t与查询条件Q的相关度，式 （9）分别给出包含关键词和不包含关键词的元组相关度计算方法，当元组不包含关键词时，相关度值为0

其中，包含给定关键词元组的相关性计算如式 （10）所示。假设t是关系数据库中基本数据表中的元组，对于DBLP数据集来讲，它们是来自表Author和Pape

式 （11）为基于节点相关性的权重分量计算方法

3.3 线性结合

下式给出结果树的相关性评分函数计算公式，其中0＜λ，β＜1，通常λ取值0.2，分数越高，表明结果与查询相关性就越大，越符合用户查询要求。

在实际应用中，关键词表示的语义可能不同，例如关键词 “于丹”，它可以是一个作者名，也可是一本书名中的术语。为了提高查询灵活性，确定关键词所属类型，可将关键词表示成 “作者：于丹”，说明查询的关键词类型为作者。关键词类型的设置对于不熟悉系统的用户来说会存在一定偏差，作者可能被描述成作家，写书人等，系统应结合这种情况将这一类描述智能统一成作者。虽然该种表示方式包含两个术语，但由于冒号前面用于标注关键词类型，因而冒号前后做一个关键词看待，只有当元组与关键词内容和类型属性完全匹配的时候，相关度的值为一个非零实数。

当输入查询关键词时，只找到包含关键词的元组远不能满足用户的信息需求，表5定义了几种针对DBLP数据集设置查询条件的方式供用户选择。＜＃style＞表示附加条件，＃后面标注的是要查找的信息类型，只有当输入的关键词出现在同一个元组中时才考虑该附加条件。

表5 查询条件的设置

4 实 验

4.1 实验环境

为了验证文中提出的结果评分函数的有效性，做了一系列的实验数据分析，本次实验开发环境为Myeclipse＋jdk1.6＋tomcat6.0，基于postgreSQL数据库用java语言实现功能，为了避免查询过程中出现内存溢出的问题，在Myeclipse平台下设置java虚拟机参数为 “－Xms256MXmx512M”，实验设备为一台内存为2G，CPU为酷睿双核2.1GHz，操作系统为 Windows XP的PC机。

4.2 实验结果

4.2.1 查询结果的产生

查询结果的获取采用图遍历和位标记的方法，首先根据用户输入的关键词找到包含关键词的节点并采用n位二进制数对其进行位标记 （n值为关键词个数），其它不包含关键词节点的位标记值初始化为0，然后对图遍历并更新节点位标记值，遍历过的节点位标记值更新为其可达关键词节点的位标记值求或运算后的值，当节点的位标记值为所有关键词节点位标记的或运算结果时，则称该节点为能连接所有关键词节点的中心节点，由中心节点，关键词节点和它们之间的路径便能得到一个结果组stenier树。图2为结果获取的一个简单实例。

图2 查询结果树的获取

图2中黑色节点为关键词节点，灰色节点为可达所有关键词节点的中心节点，虚线为节点之间的路径。

4.2.2 实验结果及分析

系统以文献索引数据库DBLP （digital bibliography ＆library project）作为实验数据集对评分函数进行评估。实验采用标准的IR评价指标 MRR （mean reciprocal rank），RR定义为1／rbest，即把最符合查询条件的答案在被评价系统给出结果中的排序取倒数作为它的准确度，MRR则为多次求得RR的平均值。为了说明文中提出的结果评估函数（search EValution，SEV）的有效性，将在结果评分函数中参数值的估计和结果查准率两个方面进行实验。

（1）参数值的估算

评分函数中参数λ取值为0.2，该值参考经典的BANKS系统中的值，设置参数β值分别为0，0.002，0.004，0.006，0.008和0.01进行实验，实验每次输入两个关键词，使用系统进行查询操作并记录最符合查询条件的结果排序序号，对应不同的参数β，进行20组实验，分别在系统查询到的结果集中找到与输入关键词最相关的结果和它所排在的位置，通过最佳结果排序序号的倒数计算得到MRR值，实验结果如图3所示，从实验结果可以看出，β最好的取值在0.002～0.006之间，因此，为了方便实验数据的比较，后期将β参数值设为0.005。

（2）结果查准率

SEV评分函数的有效性采用信息检索领域的查准率（precision）来评估，计算方法如下

图3 参数β取值0～0.01时的查询结果MRR值

式中：rs （relevant results）——查询到的与关键词相关的结果数，is（irrelevant results）——查询到的与关键词不相关的结果数。

参数λ为0.2，β为0.005，当输入关键词个数分别为1，2和3时，计算top－k个查询结果的查准率，实验结果如图4所示。

图4 top－k结果查准率

实验结果表明，当输入关键词个数为1时，输出的top－k个结果几乎都是与查询相关的结果，当输入多个关键词时，输出的结果有高度相似和冗余情况，使得结果查准率略微下降。

运行实验系统，当输入关键词为2，3，4和5时，分别进行20次查询，并求得平均查准率，将求得的平均查准率和SPARK［4］，BLINKS［9］方法的平均查准率进行比较，SPARK和BLINKS方法的查准率参考文献 ［10］。比较结果如图5所示，实验结果表明文中所提方法的平均查准率比SPARK和BLINKS有所提高。

图5 查询结果在DBLP数据集中的平均查准率

5 结束语

SEV排序方法不仅考虑结果的结构权重，而且结合了查询相关性的元组IR式权重，当元组同时包含多个关键词时，元组权重明显增加，相关的结果排序越靠前。该方法相比于BANKS系统中的排序方法，在输入若干个查询关键词并且其中的两个或两个以上的关键词出现在同一个元组的情况下，文中提出的方法能更有效的对结果进行排序。由于关键词的选取对于用户来说有一定的难度，因此，关键词查询过程的研究还有一定的空间，今后的工作将从查询重写和查询提示方面开展。

［1］Wang Meirong，Jiang Lijun，Zhang Liru，et al.Exact top－k keyword search on graph databases ［C］／／Taichung，Taiwan：SAC，2011：985－986.

［2］Ding Bolin，Jeffrey Xu Yu，Wang Shan，et al.Finding top－k min－cost connected trees in databases ［C］／／Istanbul：Data Engineering，2007：836－845.

［3］Liu F，Yu C，Meng W.Effective keyword search in relational databases［C］／／Chicago，Illinois，USA：The ACM SIGMOD International Conference on Manament of Data，2006：563－574.

［4］Luo Y，Lin X，Wang W.SPARK：Top－k keyword query in relational databases ［C］／／Cancun：ICDE，2007：115－126.

［5］Li G，Ooi B C，Feng J.EASE：An effective 3－in－1keyword search method for unstructured，semi－structured and structured data ［C］／／New York，NY，USA：SIGMOD，2008：903－914.

［6］Kasneci G，Ramanath M，Sozio M.STAR：Steiner－tree approximation in relationship graphs ［C］／／Shanghai，China：ICDE，2009：868－879.

［7］Günter Ladwig，Thanh Tran.Index structures and top－k join algorithms for native keyword search databases ［C］／／New York，NY，USA：ACM，2011：1505－1514.

［8］WANG Jiayi，YANG Luming，XIE Dong，et al.Ranking strategy of keyword search over relational databases ［J］.Computer Engineering and Design，2008，29 （10）：2566－2569 （in Chinese）.［王佳宜，杨路明，谢东，等.基于关系数据库的关键词查找排序策略 ［J］.计算机工程与设计，2008，29（10）：2566－2569.］

［9］He H，Wang H，Yang J.BLINKS：Ranked keyword searches on graphs ［C］／／New York，NY，USA：Proceedings of the ACM SIGMOD International Conference on Management of Data，2007：305－316.

［10］Feng Jianhua，Guoliang L，Wang Jianyong.Finding top－k answers in keyword search over relational databases using tuple units ［J］.Knowledge and Data Engineering，2011，23（12）：1781－1794.