分布式不确定数据查询处理关键技术研究

Data are often increasingly generated, stored, and processed distributively with the information technology development.Meanwhile, when large amounts of data are generated, fuzzy, uncertainty,and even errors are inherently introduced, especially in a distributed setup. We use distributed uncertain databases to manage such massive data. In distributed data management, the key problem of query is not to compute the probabilities of answer tuples but the eignvalues of the distributed uncertain data. The eignvalues include top-k, histograms, heavy hitters, sketches and synopses, and etc. This project begins with novel sampling method. We plan to introduce efficient algorithms to compute the eignvalues of the distributed data. The algorithm can be scaled up in a linear way. We next propose the method to accelerate processing big data. The typical method is efficient merge and index. This project will study the aggregation and statistics in distribution data. Because of the open world and massive data, incremental maintenance is the main technique to efficiently compute eignvalues. Finally, a distributed probabilistic data management system (DPDMS) prototype is implemented based on the query processing techniques developed in this project. This DPDMS is used to demonstrate our theories and algorithms. The project is not only useful for distributed uncertain database queries but also for combining MapReduce and databases.

由于现代信息技术的发展，数据分布式地产生、存储和处理成为一种常态。在分布式开放环境下，当数据产生时会不可避免地引入一些模糊、不确定甚至错误，本项目用分布式不确定数据库来管理大数据。在分布式环境下，查询处理的首要任务不是计算结果元组的概率值，而是计算分布式不确定数据的特征值，包括top-k、直方图、高频数据、数据草案和概要等。本项目从新颖的采样策略入手，拟提出高效的算法求出不确定数据的特征值，该算法能够近似线性扩展；接着提出大数据的加速处理策略，典型的方法是高效的归并算法和索引技术。本项目还要研究分布式不确定数据的聚集查询和统计技术；由于针对的是海量数据和开放式环境，增量维护是高效求解特征值的关键技术。最后，研发一个分布式不确定数据库原型系统，对本项目提出的理论和算法进行验证和分析。本项目的工作不仅对分布式不确定数据库查询处理有直接意义，而且对MapReduce和数据库的有机结合有理论指导。

由于现代信息技术的发展，数据分布式地产生、存储和处理成为一种常态。在分布式开放环境下，当数据产生时会不可避免地引入一些模糊、不确定甚至错误，本项目用分布式不确定数据库来管理大数据。如何让用户更高效地获取所需的信息，是一项重要的研究，最简单、有效的方式是信息检索技术，搜索结果的好坏与用户满足非常相关。本项目主要研究在后验特征不足的情况下，如何从有限的数据中，挖掘更好的先验特征及设计有效的排序模型来较快、较好地提升时效性检索的排序效果。.在元组独立的概率数据库中根据不等式的结构特性，我们把不等式查询语句被分为三类：路径类型、树类型和图类型，我们提出了高效的算法来计算不等式查询的概率和输入元组对结果元组的敏感性。.在AI的不确定推理中，对信念有两种有用的并且不同的理解：第一种是绝对信念或者命题中的信念程度，第二种是信念更新或者信念度量的改变。本项目通过为信念函数设计一个信念更新框架建立了Pignistic变换和似然变换的联系，在该信念更新框架中似然变换工作在信念更新，而Pignistic变换工作在绝对信念，进一步我们定义了一个新的信念更新操作来联系这两种变换，并且解释了在信念函数模型中参数统计推断的架构。.本项目接着研究了一个公理验证系统，它的适用对象是带有信用函数的决策支持。我们采用的策略是研究信用函数的对立面Savage理论，它的状态空间是有限的并且结果集是连续系统。一致性公理用于确保所有的行动对同样的最大和最小结果必须是一致的。我们的独立性公理表明存在一个功能函数并且隐含着信用函数状态空间的唯一性。我们进一步证明在没有独立性公理的中性理论中两个事实是相同的，无论什么时候他们都产生相同的信用函数。.近年来因果关系研究成为大数据的研究热点之一，将因果关系研究与数据库查询相结合，以研究表中的元组对查询结果的重要性，resilience是其中一种典型研究。针对带有不等式关系的路径类型查询，实现了基于最大流最小割方法计算resilience的算法Min-Cut，并提出一个线性复杂度的动态规划DPResi算法，通过将不等式的布尔连接查询语句的resilience求解问题转换为溯源图中最短距离计算的问题，并结合溯源图的包含关系及最优子结构性质，运用动态规划的思想实现了线性时间开销的DPResi算法，理论分析及实验验证了DPResi算法计算resilience的高效性并具有较好的扩