（计算机应用技术专业论文）web数据库柔性查询结果自动排序方法研究.pdf

毒 i 声 at h e s i sf o rt h ed e g r e eo fm a s t e ri nc o m p u t e r a p p l i c a t i o nt e c h n o l o g y r e s e a r c ho nf l e x i b l eq u e r yr e s u l t s a u t o m a t e d r a n k i n g o v e rw e bd a t a b a s e b yz h a n gx i a o y a n s u p e r v i s o r ：p r o f e s s o rm az o n g m i n n o r t h e a s t e r nu n i v e r s i t y j u n e2 0 0 8 噜文 气， j ，-乜 竹0 ， ，0 f 谴l j l 厶 独创性声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中 取得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表 或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确 的说明并表示谢意。 学位论文作者签名： 弓设噜雁 e l 期： d 乒qzl 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学 位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的 复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学 位论文的全部或部分内容编入有关数据库进行检索、交流。 作者和导师同意网上交流的时间为作者获得学位后： 半年口一年口一年半口两年函 学位论文作者签名：冰棠难 签字日期： 斌令1 9 i 导师签名： 签字日期： 醮氐 w 彦守i l k i l ， 0 葛 ： 1 9 蕾 玲 -lr，-pi一 ， ，f h ， 唧 东北大学项士学位论文摘要 w e b 数据库柔性查询结果自动排序方法研究 摘要 随着i n t e r n e t 的不断发展，网络上的在线数据库越来越多，用户可以通过w e b 站点提供的查询接口访问数据库中的信息，这种在w e b 中可通过查询接口访问的 在线数据库被称为w e b 数据库。然而，由于普通的w e b 用户对数据库的内容和 结构并不了解，或用户对自己的查询意图只有一个模糊概念，不能精确表达查询 要求，因此用户提交的查询条件只是对查询结果的一个柔性要求。同时对于大型 数据库来说，这种柔性查询会产生许多查询结果，而对于用户来说查询结果最好 是一个虽然不精确不完全、但却符合用户期望并按照用户的期望程度从高到低排 列的有序序列，因此对w e b 数据库的大量近似查询结果进行排序显得尤为重要。 本文提出了一种数据库柔性查询下多查询结果的自动排序方法。该方法既不 需要用户参与也不依赖于任何领域知识，它能够根据原始数据和查询历史自动挖 掘用户的偏好信息，从而形成一个用户和领域独立的自动排序方法来为用户返回 柔性查询下的有序查询结果。本文提出的排序函数从元组在用户指定的属性上的 取值对查询要求的满足程度和在未指定属性上的取值对用户偏好的相关程度来衡 量元组对用户期望的满足程度，其中元组对查询要求的满足程度由用户指定属性 的客观权重和用户对指定属性的偏好以及属性值与用户指定属性值的相关度决 定。首先，本文根据查询条件中用户指定的属性值在数据库中的分布状态评估指 定属性的客观权重，然后根据历史查询记录和用户指定的查询值，本文提出了一 种评估用户对不同指定属性的偏好程度的方法。接着对于查询条件中未指定的属 性值，本文提出一种在查询历史和原始数据的基础上利用概率模型来获得元组中 未被查询指定的属性值与查询中指定的属性值之间的关联程度，进而评估柔性查 询结果中未指定的属性值与用户偏好的相关程度的方法。最后，根据元组中指定 的属性值对用户查询要求的满足程度和未指定的属性值与用户偏好的相关程度来 对查询结果进行排序。 实验证明，文章提出的w e b 数据库柔性查询下多查询结果自动排序方法能够 很好的满足用户需求和偏好，与解决同类问题的排序方法相比，具有较高的排序 东北大学硕士学位论文 摘要 质量。 关键词：w e b 数据库；柔性查询；用户偏好；属性权重；查询结果排序 l h 一、 k 东北大学硕士学位论文 a b s t 喇 r e s e a r c ho nf l e x i b l e q u e r y r e s u l t sa u t o m a t e d r a n k i n g o v e rw e bd a t a b a s e a b s t r a c t t h er a p i de x p a n s i o no ft h ei n t e r n e th a sm a d eav a r i e t yo fo n l i n e d a t a b a s e s a c c e s s i b l et oal a r g en u m b e ro fu s e r s u s e r sc a na c c e s st h ed a t a b a s et h r o u g ht h eq u e r y i n t e r f a c e sp r o v i d e db yt h ew e bs i t ea n dt h ed a t a b a s ea v a i l a b l eo nt h ew e b s i t ei sc a l l c d w e bd a t a b a s e h o w e v e r , f o rm o s to r d i n a r y u s e r s ，t h e yo f t e nh a v ei n s u f f i c i e n t k n o w l e d g ea b o u tt h es t r u c t u r ea n dc o n t e n t so fd a t a b a s e ，a n do f t e nh a v ev a g u eo r i m p r e c i s ei d e a sw h e ns e a r c h i n gt h ew e bd a t a b a s e s , s ot h e ym a yn o tb ea b l et o f o r m u l a t eq u e r i e st h a ta c c u r a t e l ye x p r e s st h e i rq u e r yi n t e n t i o n s t h e r e f o r e ，t h eq u e r y u s e rs u b m i t ss h o u l dn o ta c t 嬲r i g i dc o n s t r a i n t sf o rt h eq u e r yr e s u l t s ，i e t h eq u e r yi sa f l e x i b l eq u e r y h o w e v e r , t h ef l e x i b l eq u e r yc a l lr e s u l ti nt o om a n ya n s w e r so v e r l a r g e d a t a b a s e ，a n dt h eu s e r sa r eo n l yi n t e r e s t e di nt h er e s u l t sw h i c hm e e tt h e i ri n t e n t i o n m o s tc l o s e l y s oi ti si m p o r t a n tt or a n kt h eq u e r yr e s u l t so ft h ef l e x i b l eq u e r i e s t h i sa r t i c l ep r o p o s e sa na u t o m a t e dr a n k i n ga p p r o a c hf o rt h ef l e x i b l ea n s w e r sf o r d a t a b a s eq u e r i e s o u rs o l u t i o ni sd o m a i ni n d e p e n d e n ta n dl e v e r a g e sd a t aa n dw o r k l o a d s t a t i s t i c sa n dc o r r e l a t i o n s ，a n ds oi tc a nr e t u r nt h er a n k e df l e x i b l e q u e r yr e s u l t s i n d e p e n d e n to fu s e r sa n dd o m a i n s t h er a n k i n gf u n c t i o nt h i sa r t i c l ep r o p o s e sm e a s u r e s t h ei m p o r t a n c eo ft h et u p l eb yr e g a r d i n gi t ss a t i s f a c t i o nd e g r e eo fs p e c i f i e da t t r i b u t e v a l u e st ot h eq u e r y , a n di t sr e l e v a n c ed e g r e eo f u n s p e c i f i e da t t r i b u t ev a l u e st ot h eu s e r s p r e f e r e n c e s t h es a t i s f a c t i o nd e g r e eo fs p e c i f i e da t t r i b u t ev a l u e si sd e t e r m i n e db yt h e a t t r i b u t ew e i g h t so ft h es p e c i f i e da t t r i b u t e s ，t h e u s e r sp r e f e r e n c e st ot h es p e c i f i e d a t t r i b u t e sa n dt h es i m i l a r i t yb e t w e e nt h ev a l u e so ft h et u p l ea n dt h es p e c i f i e dv a l u e s f i r s t l y , t h ea t t r i b u t ew e i g h t sa r ea s s i g n e da c c o r d i n gt ot h ed a t ad i s t r i b u t i o no ft h e d a t a b a s ea n dt h e nt h eu s e r sp r e f e r e n c e st ot h es p e c i f i e da t t r i b u t e sa r eg i v e n a c c o r d i n g t ot h ew o r k l o a da n dt h eq u e r i e s s e c o n d l y , t oe v a l u a t et h eu s e r s p r e f e r e n c et ot h e u n s p e c i f i e da t t r i b u t e s ，w el o o kb e y o n dt h ea t t r i b u t e ss p e c i f i e di nt h eq u e r ya n df i n dt h e a s s o c i a t i o nd e g r e e sb e t w e e nt h es p e c i f i e da t t r i b u t e sa n dt h eu n s p e c i f i e da t t r i b u t e sb y a d a p t i n ga n da p p l y i n gp r i n c i p l e so fp r o b a b i l i s t i cm o d e l sf r o mi n f o r m a t i o nr e t r i e v a lf o r s t r u c t u r e dd a t a a n df i n a l l y , w er a n kt h eq u e r yr e s u l t sa c c o r d i n gt ot h es a t i s f a c t i o n d e g r e eo ft h es p e c i f i e da t t r i b u t e sa n dt h ea s s o c i a t i o nd e g r e eo ft h eu n s p e c i f i e d a t t r i b u t e s w ee v a l u a t et h eq u a l i t yo fo u r a p p r o a c hw i t ha ne x p e r i m e n to nar e a ld a t a b a s e ，a n d e x p e r i m e n t a lr e s u l t sd e m o n s t r a t et h a tt h ea p p r o a c hf o rt h em a n yf l e x i b l ea n s w e r s p r o b l e mf o rt h ew e bd a t a b a s ep r o p o s e di nt h ea r t i c l ec a nc a p t u r et h eu s e r sp r e f e r e n c e s e f f e c t i v e l ya n dh a v eah i g hr a n k i n gq u a l i t ya sw e l l 东北大学硕士学位论文a b s t r a c t k e yw o r d s ：w e bd a t a b a s e ，f l e x i b l eq u e r y , p r e f e r e n c e ，a u t o m a t i c a l l yr a n k i n g v ，i 一 0 k ， 东北大学硕士学位论文 目录 目录 独创性声明i 摘要i i a b s t r a c t i v 第1 章绪论1 1 1 课题背景。1 1 2 国内外相关研究的现状与分析3 1 2 1 当前数据库查询技术的研究。3 1 2 2 数据库柔性查询的研究3 1 2 3 数据库查询结果排序的研究4 1 3 研究目标与意义6 1 4 本文工作7 1 4 1 研究内容7 1 4 2 组织结构7 第2 章数据库查询及排序相关理论9 2 1 数据库查询9 2 1 1 数据库及查询相关定义9 2 1 2 数据库查询相关技术1 1 2 1 3 数据库查询结果问题1 2 2 2 数据库柔性查询。1 3 2 2 1 柔性查询定义1 3 2 2 2 柔性查询方法1 4 2 3 查询结果排序及评价标准1 6 2 3 1 查询结果排序方法1 6 2 3 2 查询结果排序评价标准1 9 2 4 本章小结2 1 第3 章元组对查询要求的满足程度评估2 3 东北大学硕士学位论文目录 3 1 评估元组对查询满足程度概述。2 4 3 2 客观属性权重评估。2 6 3 2 1 常用的客观属性权重评估方法2 6 3 2 2 基于交叉熵的客观属性权重评估2 7 3 3 主观属性权重评估3 1 3 3 1 常用主观属性权重评估方法3 2 3 3 2 基于查询概率的评估方法3 3 3 4 属性值之间的相似性评估3 5 3 4 1 文本型属性值的相似度3 6 3 4 2 数值型属性值的相似度3 7 3 5 本章小结3 8 第4 章元组对用户偏好的相关程度评估3 9 4 1 元组对用户偏好相关程度评估概述3 9 4 1 1 必要性3 9 4 12 方法的提出4 0 4 2 信息检索概率模型简介4 2 4 2 1 概率模型理论4 2 4 2 2 信息检索中的参数估计。4 3 4 2 3 二项独立模型4 4 4 3 基于概率模型的用户偏好评估。4 4 4 3 1 对精确查询结果排序的概率模型4 4 4 3 2 有限独立模型4 6 4 2 3 消除独立性模型4 6 4 2 4 基于历史查询记录的参数估计4 8 4 4 改进的概率模型4 9 4 4 1 概率模型的改进4 9 4 4 2 数值型属性值的参数估计。5 2 4 4 3 特殊情形5 4 4 5 本章小结5 5 v l i i 1 k 卜h， x ，i*ff 争 r 、 | 、 q 查苎大学硕士学位论文 目录 第5 章系统设计和实验分析二_ 一5 7 5 o l 系统的一般框架5 7 5 2 预处理5 8 5 2 1 原子概率计算模块5 8 5 2 2 属性值相似度计算模块。5 9 5 3 查询处理5 9 0 4 实验及性能分析6 1 5 4 1 测试排序算法质量6 1 0 4 2 测试排序算法性能6 6 5 5 小结矗。6 7 第6 章总结和展望6 9 参考文献7 1 致谢7 5 攻读学位期间发表的论文7 7 i i l 二_ l，0l 9 0 ttj 和 东北大学硕士学位论文第1 章绪论 1 1 课题背景 第1 章绪论 随着w e b 相关技术的日益成熟和w e b 中所蕴含信息量的快速增长，网络上 的在线数据库越来越多，我们把这些可在w e b 中访问的在线数据库称为w e b 数 据库，人们可以通过查询接口对其进行访问。目前，随着i n t e m e t 的不断发展和 普及，通过对w e b 数据库的访问已逐渐成为人们获取信息的主要手段【1 1 。然而， 对于大多数使用w e b 的普通用户来说，一方面由于对数据库的内容和结构并不了 解，难免提出一些与数据库内容相矛盾的查询要求，从而造成空查询结果或者查 询结果不完全以及不能够令人满意；另一方面，他们在查询过程中也并不一定完 全明确自己的查询意图，通常抱着”先查查看”的态度进行查询，也就是说用户的 查询意图本身往往就是模糊的、不精确的以及不完全的，从而使得查询具有一定 的试探性和渐进性的特点。因此，对于体现用户查询意图的查询要求来说，也就 不应该作为查询结果必须完全满足的硬性要求，换句话说，用户提交的查询条件 实际上是对查询结果的一个柔性要求，用于最大限度地为用户提供他们可能感兴 趣的信息【2 】。然而，对于一个大型数据库来说，它里面存储着大量与查询相关的 信息，因此，当一个柔性查询到来时，系统将会返回大量的相关查询结果，这也 就是常说的多查询结果问题。而对于用户来说，他们希望首先看到与自己查询意 图最为相关的查询结果，因此对w e b 数据库的许多近似查询结果进行排序就显得 尤为重要了1 3 j 。 考虑w w w r e a l t o r h o m e s 网站的房地产数据库( 本文以该房地产数据库为例 对研究背景和研究方法加以阐述) ，该数据库包含一个数据库表e s t a t e p r i c e ，s q f t ， c i t y , b e d r o o m s ，b a t h r o o m s ，l i v i n g a r e a , s c h o o l d i s t r i c t ，v i e w , p o o l ，g a r a g e ， b o a t d o c k ，b u i l d y e a r ) 。对于上述的房地产数据库，一方面，当用户输入的查询 要求过于严格或者查询条件之间存在矛盾时，系统就可能返回空查询结果或者少 量查询结果。例如，当用户的查询要求为”s q f t 3 ”时，系统 将返回空查询结果。因为在该房地产数据库中，建筑面积小于8 0 0 英尺的房子的 卧室数目都小于3 个，也就是说查询要求中的两个并列查询条件之间存在矛盾。 东北大学硕士学位论文第1 章绪论 因此，在这种情况下，用户不得不通过反复修改查询条件的方式来获得查询结果， 而且用户很可能在得到理想的查询结果之前就会放弃查询。另一方面，当用户的 查询要求并不苛刻或者系统对用户的查询要求进行了调整和扩展时，由于w e b 数 据库中的数据量巨大，这样的查询往往会导致系统返回大量查询结果。例如，当 用户的查询要求为”p r i c eb e t w e e n $ 5 0 0 0 0a n d $ 1 0 0 0 0 0a n ds q f i 6 0 0 ”，系统将返回 1 0 4 8 3 条查询结果，因为该房地产数据库中有大量价格在$ 5 0 0 0 0 和$ 1 0 0 0 0 0 之间 并且面积大于6 0 0 平方英尺的房子。然而，为了找到自己真正满意的房子，用户 不得不对这1 0 4 8 3 条元组逐一对比，显然，这是一项十分枯燥并耗时的工作，这 时按照用户要求和偏好对查询结果进行排序就很有必要了。 由此可见，查询结果过少( 或为空) 或者查询结果过多都不符合w e b 数据库 用户的查询初衷 4 1 。目前，对于第一种情况的解决方法是基于相似度思想，首先 对用户的初始查询条件进行协调和柔性化处理，( 即用户指定了查询条件，但是他 们并不一定局限于那些完全满足查询条件的元组，相反与指定的属性值相接近的 元组他们也可以接受) ，然后用柔性扩展后的查询条件对数据库进行查询，最后为 用户返回相关的查询结果。对于第二种情况的解决方法是根据用户的查询要求和 偏好，对数据库多查询结果进行分类或排序。对数据库查询结果进行排序，需要 借鉴信息检索领域的思想，信息检索领域的一些研究者认为用户只是对自己的查 询意图有大概的或模糊的概念，却不能精确表达的查询要求，但还是希望系统能 按照顺序返回与查询要求最为匹配的元组。例如在上述房地产数据库中，假设有 一个用户想要购买有四个卧室价格大约$ 3 0 0 ，0 0 0 左右的房子，数据库查询系统会 根据数据库中元组与用户给定的查询条件来对满足查询条件的元组进行排序，最 后返回最符合用户查询条件的前k 个元组。如果没有完全满足查询条件的元组， 系统将会按照近似程度有序地返回近似匹配的元组，例如系统可能将包含6 个卧 室，价格为2 9 9 9 0 0 的房子排在第一位。 总之，正是由于网络中w e b 数据库的大量涌现和普通w e b 用户的不断增多， 传统的数据库查询技术在基于w e b 的应用中将会面临着越来越多地挑战。因此在 数据库研究领域，对于w e b 数据库的柔性查询及查询结果排序技术研究正逐渐成 为人们研究的热点【5 1 1 6 1 1 7 1 。 东北大学硕士学位论文第1 章绪论 1 2 国内外相关研究的现状与分析 1 2 1 当前数据库查询技术的研究 随着数据库技术的不断发展及其在w e b 环境下的大量应用，当前对数据库查 询技术的研究主要集中在以下几个方面： ( 1 ) 基于相似性的数据库不精确和不确定查询【8 】。由于现实生活中许多事物的 表露是不完全，不确定的以及模糊不清的【9 】，因此越来越多的工作集中在处理不 精确数据上【l 们。例如概率数据库查询，该数据模型就可以用来处理不确定数据。 ( 2 ) 结构化数据与非结构化数据的集成查询。为了处理许多应用中既要管理 结构化的数据，又要管理非结构化的数据的任务，把数据库和信息检索技术集成 的技术便应运而生【l ，这种技术的关键问题就是如何把结构化的数据和非结构化 的数据统一标准进行对待，但是为了达到集成目标还需要解决大量的问题，因此 这种技术近年来得到了广泛关注【1 2 】。 ( 3 ) 半结构化数据查询。x m l 文档是半结构化数据，最近，已经有研究工作 把基于信息检索的方法扩展到x m l 检索【1 3 1 。该方法的思想是把x m l 文档看作是 半结构化文档的数据库，并使用相应的数据库风格的查询语言来查询【1 4 】，x m l 文 档中的标签能确定在文档中的哪一部分查找，而不像在h t m l 文档中那样在整个 文档中查找【1 5 1 。目前，随着x m l 文档的大量涌现，针对x m l 的检索查询将成为 数据库的研究热点之一【l6 。 ( 4 ) 关键词查询。在信息检索领域，对于关键词查询已经展开了大量的研究 工作。而在数据库领域，对于关键词的查询技术研究才刚刚开始。实现基于关键 词的数据库信息检索，将使用户不需要任何s q l 语言和数据库模式的知识，像使 用g o o g l e 刃l g 样通过提交关键词来获取数据库中的相关数据1 7 】。 1 2 2 数据库柔性查询的研究 对于数据库柔性查询技术的研究，当前的研究工作主要从两个方面展开。 ( 1 ) 精确查询条件的柔性化处理。当前的w e b 数据库查询研究工作已致力于对 精确查询条件的柔性化处理，主要的研究工作包括 2 】 1 8 】，这类研究工作大都是 基于距离观念，相似度思想等。文献 2 】指出，对于用户的查询要求，应该首先从 东北大学硕士学位论文第1 章绪论 最不重要的属性上扩展查询条件；对于属性权重的评估，提出了一种基于近似函 数依赖的属性权重评估方法，按照属性重要程度排序，然后以此对指定在这些属 性上的查询条件进行扩展；扩展范围由属性值问的相似度和预先设定的阈值决定。 但是，文献 2 提出的属性值间相似度评估方法仅适用于文本型属性值的相似度评 估，而对于数值型属性值并不适用；而且，对于任何查询要求，属性权重都是相 同的，而实际应用中，不同用户对于同一属性的重视程度是不同的，因此在个性 化方面，文献 2 】的方法尚显不足。文献【1 8 】提出了基于贝叶斯网络的查询条件柔 性扩展方法，该文认为，造成空查询结果的原因是同一个查询中的查询条件之间 存在矛盾，首先应该找出具有矛盾性质的查询条件，然后根据属性权重来调整查 询条件上取值范围，从而化解矛盾。但是该方法只能求出属性权重的大小顺序， 无法精确地表达属性值的大小，而属性值大小是影响扩展的重要因素。 ( 2 ) 直接支持模糊查询条件。对于模糊关系数据库的研究已经有很长的历 史，但是对于w e b 数据库中直接支持模糊查询的研究却很少，最近文献【1 9 】提出了 一种基于领域知识和模糊逻辑的模糊查询转换方法，能够处理查询条件中含有复 杂模糊关系和复杂模糊谓词，将用户提出的精确数值区间根据领域知识和模糊逻 辑进行扩展，从而为用户提供更多与查询相关的结果【2 0 】。但是该方法需要一个领 域知识库协助模糊查询条件转换过程，因此在很大程度上需要领域专家的干预， 自动化程度不高。 1 2 3 数据库查询结果排序的研究 在信息检索领域，人们已经对排序函数进行了很多深入具体的研究工作，其 中向量空间模型【2 1 1 ，概率信息模型【2 2 1 和统计语言模型例在现实生活中都已经得到 广泛的应用。基于相关反馈的信息检索( i r ) 系统( 例如，相关性反馈1 2 4 ，伪相 关性反馈【2 5 】) 都以推断项相关性和模拟项依赖为基础，概率信息模型以平衡查询 日志信息为目标【2 6 1 。然而，信息检索中的大多数研究工作都集中在求解文本性的 属性权重，这些技术很难应用到数据库数值型数据的排序当中。另外，排序也是 协同过滤研究中【2 7 】的一个重要组成部分，但是系统过滤中的很多方法都需要训练 结果集。随着w e b 数据库应用的不断发展，越来越多的研究者开始关注数据库查 询结果排序的研究。关于数据库查询结果排序，代表性的研究工作可分为如下几 类： 4 东北大学硕士学位论文第1 章绪论 ( 1 ) 基于相关反馈的排序方法。文献 2 8 】，【2 9 禾1 j 用相关反馈的方法在多媒体 和关系数据库中获取相似度函数。文献【3 0 】提出把传统s q l 进行扩展，允许用户 根据他们的偏好指定排序函数，但是由于数据库系统中的s q l 语言对于普通用户 难于学习和掌握，并且使用者必须知道数据库的模式和内容【3 1 1 ，因此该方法对普 通用户来说并不适用。相关反馈方法存在的不足之处在于，需要参与对查询结果 的反馈，加重系统负担。 ( 2 ) 基于用户偏好的排序方法。文献 3 2 】描述了一个在文本和数值相混合的数 据集上进行排序的方法，该方法以偏好的形式表达软限制条件使用户能够指定排 序函数。文献 3 0 】提出的定性的偏好模型通过扩展传统的s q l 查询语句关键字来 实现关系数据库对用户偏好的支持，在这个模型中，标准s q l 和偏好关键字构成 了偏好s q l ，此模型把关系的属性划分为集合型和数值型两类。使用p o s ，n e g ， p o s n e g ，p o p p o s ，e x p 关键字来处理集合型的属性上的偏好，a r o u n d ， b e t w e e n ，l o w e s t , h i g h e s t 关键字来处理数值型属性上的偏好。文献 3 3 】提 出了一套完整的逻辑框架来定性的形式化偏好并且把形式化后的偏好嵌入到关系 查询语言中，这个框架包括两部分，一部分是提出了一个一元的逻辑符号来表示 偏好关系，另一部分是提出一个算子w i n n o w ，把此算子加入到传统的关系代数中。 基于用户偏好的排序方法，需要用户指定排序函数，然而对于大多数的普通用户， 他们并不清楚应该如何合理的指定属性权重和排序函数，而且让用户来指定属性 权重的方法在文本型属性上并不适用。 ( 3 ) 基于概率模型的排序方法。文献 3 4 ， 3 5 以概率模型( p i r ) 为基础，提出 了数据库精确查询下多查询结果的p r 自动排序方法，该方法利用了历史查询记录 来挖掘用户偏好并以此作为查询结果排序的依据。在p i r 方法中，元组的排序分 数分为两个部分：条件分数和全局分数。条件分数反映了元组中未被查询指定的 属性值与查询指定的属性值之间的依赖程度；全局分数反映了未被查询指定的属 性值在全局中的重要程度。但是p i r 方法存在的缺点是，排序函数仅考虑了元组 中未被查询指定的属性值间的差别，而忽略了被查询指定的属性值间的差别，另 外，p i r 仅能对精确查询下多查询结果进行排序，而对于柔性查询结果的排序并 不适用。 ( 4 ) 基于相似度的空查询结果排序方法。文献 3 6 】在t f i d f 2 1 1 方法的基础上提 东北大学硕士学位论文第1 章绪论 出t q f i d f 方法，该方法通过评估元组中被查询指定的属性值在全局中的重要性 以及属性值间的相似度对查询结果排序。该方法与本文所提的柔性查询结果排序 方法具有一定程度的相似性，都用于柔性查询结果的排序，然而本文方法与q f i d f 方法的不同之处在于，q f i d f 仅考虑了被查询指定的属性值对查询要求的满足程 度，没有考虑查询未指定的属性值在排序中的作用，而本文方法既考虑了被查询 指定的属性值对查询要求的满足程度( 其中包括属性权重的属性值间的相似性) ， 还考虑了未被查询指定的属性值与用户偏好的相关程度。 除了上述所列举的排序研究工作之外，目前还有大量的工作集中在查找点查 询的最匹配的元组，许多研究工作的前提是存在特定的数据结构和索引 3 7 1 并用它 们来查找与查询结果最匹配的元组，但是当前的传统关系数据库管理系统并不支 持他们所提的索引结构和访问方式【3 。1 。 1 3 研究目标与意义 以上对国内外相关研究现状进行了介绍与分析，从中不难看出，为了实现对 数据库查询结果的排序，大量的研究工作已经致力于精确查询下多查询结果排序 的研究。从所发表的有关数据库查询结果排序的主要文献来看，该领域最近几年 虽然吸引了一批学者投入研究工作，并在各类期刊及会议如v l d b ，p o d s ，i c d e 上己发表了一些有价值的研究文章，但是整体来说研究成果还很少，并且智能化 程度并不高。特别是最近几年出现了数据库柔性查询的新的研究课题，由此而产 生的一些重要的技术难点还有待解决。因此，本文的目标在于研究柔性查询下的 数据库多查询结果自动排序方法，使得数据库系统能够根据用户的柔性查询要求， 按序返回满足用户要求和偏好的查询结果。 当前大多数传统的数据库系统只处理结构化数据，采用结构化查询语言并仅 支持精确的布尔查询【3 引，因此得到的查询结果都完全满足查询要求并且被同等对 待。另外，对于数据库多查询结果的排序问题，目前大多数的数据库系统只能根 据关系表中的一个属性( 例如根据日期或根据价格等) 来对查询结果进行升序或 降序排列，然而对于返回的多个相关查询结果，大多数用户可能会同时考虑多个 属性来作出综合评判。虽然s q l 的一些扩展版本允许用户根据他们的需要来指定 属性权重，但是这些方法并不理想，因为对于大多数普通用户来说，他们并不清 楚如何合理的指定属性权重，而且让用户来指定属性权重的方法在文本型属性上 并不适用。因此，无论从实际应用的需求来看，还是从现有的解决问题的技术方 东北大学硕士学位论文第1 章绪论 法来讲，对基于w e b 数据库的信息检索和排序模型的研究和改进都很有必要。 - ： ； ： 1 4 本文工作 基于交叉熵距离和概率模型理论，本文将在柔性查询框架下，对数据库多查 询结果自动排序问题展开研究，内容包括柔性查询扩展方法、属性权重评估方法、 元组中的属性值对查询要求的满足程度评估方法，元组中的属性值与用户偏好相 关程度评估方法。 1 4 1 研究内容 本文提出了一种w e b 数据库柔性查询下的多查询结果自动排序的方法，该方 法不需要任何的用户反馈就能按顺序返回的查询结果，在排序过程中该方法不仅 考虑了数据库中的数据分布对元组重要性的影响，还考虑了用户对指定属性的不 同重视程度对排序质量的影响。为了区分在指定属性上具有相同分值的元组，本 文还考虑了未指定属性对查询结果排序的影响，未指定属性的影响作用只能通过 它对用户偏好的相关程度来表达，本文利用了历史查询记录和数据库，支持对基 于概率模型排序函数自动的提取来挖掘用户的偏好。 本文的主要工作包括： ( 1 ) 提出了一种柔性查询下指定属性重要性的评估方法，该方法认为属性的 重要程度随着用户查询条件的变化而变化，即属性的重要性不是固定不变的。 ( 2 ) 基于历史查询记录，提出了一种评估用户对指定属性重视程度的方法， 该方法充分考虑了用户对于查询指定属性的偏好和兴趣，并以此评估主观属性权 重。 ( 3 ) 改进了基于历史查询记录的概率模型，进而评估柔性查询中未指定的属 性值对用户偏好的满足程度，最后结合元组在指定属性值上对查询要求的满足程 度和在未指定属性值上与用户偏好的相关程度来衡量元组的最终排序分值，采用 t o p k 方法使得具有最高排序分值的元组排在前面。 1 4 2 组织结构 根据上述研究内容，本论文分为六章，每一章的具体内容安排如下： 第1 章绪论 东北大学硕士学位论文第1 章绪论 本章主要阐述了数据库柔性查询下多查询结果排序的研究背景和研究动机， 分析了国内外相关研究的研究现状，在此基础上，提出了本文的研究目标与研究 意义，最后给出了本文所做的主要工作和论文的结构安排。 第2 章数据库柔性查询及排序相关理论 本章首先介绍数据库查询及相关技术，进而介绍了数据库柔性查询定义及方 法，最后介绍了数据库查询结果排序方法，以及评价标准。 第3 章元组对查询要求的满足程度评估 本章首先考虑用户提出的初始查询条件，根据数据分布和查询历史推测属性 权重，然后评估元组中指定的属性值与查询条件之间的相似度，最后根据属性权 重和属性值间的相似度计算元组对查询要求的满足程度。 第4 章元组对用户偏好的相关程度的评估 本章首先描述了元组对用户偏好的相关程度的评估方法，然后介绍概率模型， 进而提出了基于概率模型的用户偏好评估方法，并且针对多查询结果和柔性查询 结果的不同特点对概率模型进行了改进。 第5 章系统设计和实验分析 本章首先介绍了排序系统的框架结构和实现方法，然后重点描述了实验方法 和实验结果，其中包括排序函数的质量实验和排序函数的执行性能实验。 第6 章结论和展望 总结本文的研究成果，展望未来研究方向。 东北大学硕士学位论文第2 章数据库查询及排序相关理论 第2 章数据库查询及排序相关理论 本章主要介绍数据库查询中的相关概念、技术，数据库的柔性查询，数据库 排序方法及排序的评价标准。 2 1 数据库查询 本节首先介绍数据库以及数据库查询中的相关定义，然后对数据库查询中处 理数值型属性值的技术直方图技术进行简明阐述，最后指出数据库查询中经 常出现的问题。 2 1 1 数据库及查询相关定义 数据库是对客观世界一部分( 可能是一个企业，一个单位等等) 的抽象描述， 各种数据是对客观事物的属性、数量、位置或是它们的相互关系的形式表示，是 各种信息的载体。数据库( d a t a b a s e ) 是指按照一定的结构和规则组织起来的相关数 据的集合，是存放数据的“仓库 ，是按特定的模式建立数据，各个数据之间具有 相关性。数据库是计算机软件的一个重要分支，是在1 9 6 0 年代后期发展起来的数 据管理新技术。从1 9 6 8 年9 月美国i b m 公司发表其研制成功的信息管理系统 ( i n f o r m a t i o nm a n a g e m e n ts y s t e m ) 的第一个版本，1 9 6 9 年1 0 月美国数据库系统语 言协会( c o n f e r e n c eo nd a t as y s t e ml a n g u a g e ) 发表第一个d b t g ( 一种网状数据库 系统方案) ，到今天不过几十年时间，但数据库技术却获得了惊人的发展，几乎成 为各种计算机应用系统的核心部分。如今，数据库已成为重要的信息源，在美国 就有近万个公开的数据库，可以通过多种远程网络为用户提供信息服务。就其本 质来说，数据库是一个计算机化的记录保管系统，是个数字化的信息系统，通过 网络为用户提供快捷、高效的信息服务，以利于实现资源共享。数据库的概念是 在总结数据处理的实践基础上提出来的，它实质上就是一大批计算机化的数据文 件的仓库，除保存和管理数据外，还能根据其服务对象的要求随时提供服务。为 了在信息网络中快速找到我们所需要的信息，必须建立各种类型的数据库并开展 检索服务，信息检索服务是数字化、网络化、智能化和个性化的服务，属于深层 次的知识信息