非一致性数据库概率查询策略及算法分析.pdfVIP

非一致性数据库概率查询策略与算法分析1 1 2 1 3 刘波 ，雷刚跃 ，杨路明 ，邓云龙 1 中南大学信息学院，湖南长沙（410083 ） 2 湖南信息职业技术学院，湖南长沙（410200 ） 3 中南大学湘雅三医院，湖南长沙（410013 ） E-mail ：ltbo99@ 摘 要：完整性约束是保证关系型数据库中数据确定性的重要条件，而现实世界中大量存在 着不确定性的信息，但这些信息依然具有很好的使用价值，需要被检索和利用。本文在总结 前人工作的基础上，结合概率数据库理论，提出了一种新的针对非一致性数据库的查询策略， 利用并、交、差、选择、投影、连接等约束方法，能有效地对非一致性数据进行修复，其四 元组概率计算方法和概率查询重写技术能克服非一致性数据库查询的许多不足，实验显示这 些方法可以减少数据冲突的发生。 关键词：非一致性数据库；概率数据模型；数据清洗；查询重写；约束查询 中图分类号：TP311.5 文献识别码:A 0 引言 众所周知,关系数据库统治数据库领域长盛不衰的法宝就是描述性查询语言SQL及其运 行基础关系代数。关系代数的特征之一是给出明确的查询语义,之二是用于支持查询优化， 而它的优势来自于简单、明确的数据模型——关系,具有完善的数学基础和系统的转换规则, 并以确定性信息为研究对象,有完整性约束条件,如实体完整性、域完整性、引用完整性和用 户定义完整性，这些约束有效地保证了关系型数据库中数据的完整性和有效性，使数据符合 现实世界的实体规则,有利数据的生成与查询。但随着互联网的飞速发展,网络迅速成为一种 重要的信息传播和交换的手段,尤其是在Web 上,有着极其丰富的数据来源， 这些数据大多数 是变化的，有些是有规律的变化，有些是无规律的变化，或者变化的规律是不确定的，对于 有规律的变化,可以利用关系数据库表示,而对于大量无规律的数据则无法用SQL准确查询, 因为这些大量产生的无规律的数据并不总能维持关系型数据库的一致性，往往会产生数据冲 突，但这些信息仍然具有使用价值，不能简单丢弃, 如表 1、表2 所示,如果要查找姓名刘波 的网络课程成绩,或查找网络课程分数 97 是谁的分数,是无法给出确切的信息,因为刘波的网 络课程可能是97,也有可能是62,或网络课程分数97 可能是刘波的,也可能是沐文的,这些信息 都是不确切的,它违背了关系数据库一致性原则，那么能否找出一种有效的方法把这些非一 致性信息转化为一致性信息，并能准确查询这些信息呢? 表1 学生选课表 表2 科目成绩表 学号 姓名 科目 概率 代号 科目 成绩 概率 s1 刘波 网络 0.8 t1 10028 网络 97 0.9 s2 木阳 英语 0.6 t2 10016 英语 85 0.7 s3 刘波 操作系统 0.2 t3 10028 网络 62 0.1 s4 沐文 网络 0.4 t4 10014 英语 58 0.2 … … … … … … 1本课题得到中南大学大学生创新创业启航行动重点资助创新项目－非一致性数据库的一致性查询技术研 究（编号ZB018）和湖南省教育厅科研基金遗传算法参数设计（编号 05c67