关系型数据库中不确定性数据的Topk查询研究.pdfVIP

第２９卷第４期　　　 计算机应用与软件 Ｖｏｌ２９Ｎｏ．４ ２０１２年４月　　 ＣｏｍｐｕｔｅｒＡｐｐｌｉｃａｔｉｏｎｓａｎｄＳｏｆｔｗａｒｅ Ａｐｒ．２０１２ 关系型数据库中不确定性数据的Ｔｏｐｋ查询研究 李雪娇　余建桥　冯　静 （西南大学计算机与信息科学学院　重庆４００７１５） 摘　要　　Ｔｏｐｋ查询在传统的存储确定性数据的关系型数据库中得到了广泛的应用，但是对于存储不确定性数据的数据库，Ｔｏｐｋ 查询必须结合元组的分值和不确定性来处理。已有的Ｔｏｐｋ查询没有很好地结合元组的分值和不确定性，因此，定义一种新的针对 不确定性数据的Ｔｏｐｋ查询语义，并且实现了查询算法，在新语义下，计算第ｉ位排名时考虑了第ｉ－１位元组，能够更好地权衡分值 和不确定性。不同数据集上的实验显示，该算法是有效的。 关键词　　不确定性　关系型数据库　Ｔｏｐｋ 中图分类号　ＴＰ３１１．１３２ 文献标识码　Ａ ＳＴＵＤＹＯＮＴｏｐｋＱＵＥＲＹＯＦＵＮＣＥＲＴＡＩＮＴＹＤＡＴＡＩＮＲＥＬＡＴＩＯＮＡＬＤＡＴＡＢＡＳＥ ＬｉＸｕｅｊｉａｏ　ＹｕＪｉａｎｑｉａｏ　ＦｅｎｇＪｉｎｇ （ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒａｎｄＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅ，ＳｏｕｔｈｗｅｓｔＵｎｉｖｅｒｓｉｔｙ，Ｃｈｏｎｇｑｉｎｇ４００７１５，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ　　Ｔｏｐｋｑｕｅｒｙｈａｓｂｅｅｎｗｉｄｅｌｙａｐｐｌｉｅｄｉｎｔｒａｄｉｔｉｏｎａｌｒｅｌａｔｉｏｎａｌｄａｔａｂａｓｅｓｓｔｏｒｉｎｇｔｈｅｄｅｔｅｒｍｉｎｉｓｔｉｃｄａｔａ，ｂｕｔｆｏｒｔｈｅｄａｔａｂａｓｅｓ ｓｔｏｒｉｎｇｕｎｃｅｒｔａｉｎｔｙｄａｔａ．Ｔｏｐｋｑｕｅｒｙｈａｖｅｔｏｐｒｏｃｅｓｓｉｎｃｏｎｊｕｎｃｔｉｏｎｗｉｔｈｔｈｅｓｃｏｒｅａｎｄｕｎｃｅｒｔａｉｎｔｙｏｆｔｕｐｌｅｓ．ＥｘｉｓｔｉｎｇＴｏｐｋｑｕｅｒｙｄｏｅｓｎｏｔ ｃｏｍｂｉｎｅｔｈｅｍｗｅｌｌ，ｔｈｅｒｅｆｏｒｅａｎｅｗｓｅｍａｎｔｉｃｓｏｆＴｏｐｋｑｕｅｒｙｆｏｒｕｎｃｅｒｔａｉｎｔｙｄａｔａｉｓｄｅｆｉｎｅｄ，ａｎｄｔｈｅｑｕｅｒｙａｌｇｏｒｉｔｈｍｉｓｉｍｐｌｅｍｅｎｔｅｄ．Ｉｎｔｈｉｓ ｎｅｗｓｅｍａｎｔｉｃｓ，ｔｈｅｔｕｐｌｅａｔｒａｎｋｉ－１ｉｓｃｏｎｓｉｄｅｒｅｄｗｈｅｎｃｏｍｐｕｔｉｎｇｔｈｅｔｕｐｌｅａｔｒａｎｋｉ，ｓｏｉｔｂｅｔｔｅｒｂａｌａｎｃｅｓｔｈｅｓｃｏｒｅａｎｄｕｎｃｅｒｔａｉｎｔｙｏｆ ｔｕｐｌｅｓ．Ｅｘｐｅｒｉｍｅｎｔｓｏｎｄｉｆｆｅｒｅｎｔｄａｔａｓｅｔｓｄｅｍｏｎｓｔｒａｔｅｔｈｅｅｆｆｉｃｉｅｎｃｙｏｆｔｈｅａｌｇｏｒｉｔｈｍ． Ｋｅｙｗｏｒｄｓ　　Ｕｎｃｅｒｔａｉｎｔｙ　Ｒｅｌａｔｉｏｎａｌｄａｔａｂａｓｅ　Ｔｏｐｋ 存在级不确定性是指元组有一个概率值，表示该元组存在的可 ０　引　言 能性大小；属性级不确定性是指元组的属性具有一个概率值，以 概率密度函数或者统计参数来描述特定属性的不确定性。 传感器网络、数据集成、隐私保护等各种现实应用中会产生 关系型数据库中存储存在级不确定性数据时，给每个元组 大量不确定性数据，不确定性数据广泛存在于军事、金融和电信 加上一个概率维，表示该元组的可信度大小，在进行Ｔｏｐｋ查询 等领域中。不确定性数据的排名要综合考虑分值大小和概率值 时，该概率维和数据的分值共同影响查询结果。 大小，其Ｔｏｐｋ查询在语义上具有歧义，不同的分值和概率值的 结合方式会产生不同的查询结果，所以关系型数据库中传统的 １．２　可能世界模型 针对确定性数据的 Ｔｏｐｋ查询不能直接应用在不确定性数 研究者们针对不确定性数据