概率数据库理论介绍综述课件

概率数据库理论概率数据库理论计本一班李东伟The theory of probabilistic databases简介在许多现实的应用中，如过程监控，决策分析，遥感等领域，数据的不确定性普遍存在。传统的数据管理技术却无法有效管理不确定性数据，人们开始探讨数据不确定性的本质。上世纪八十年代末开始出现的概率数据库（probabilistic database）研究，这一研究认为元组在数据库中的存在具有不确定性、属性值具有不确定性、查询应答也具有不确定性。但是，一直以来，人们对不确定性问题认识不足，这也决定了人们对待不确定数据管理的态度，很多研究工作虽然遇到了不确定性问题，但往往采取传统的“去除不确定性”方法避开对不确定数据的管理。课程号课程号 课程名课程名 学生学生 C201201 数据结构 70 C201202 操作系统 60 C201203 计算机原理 60课程关系C属性属性值关系模式元组1元组2元组3关关系系状状态态举个简单的例子来比较一下确定与不确定数据精确集合131X=6举个简单的例子来比较一下确定与不确定数据113模糊集合数据库存储信息。信息的存储形式，历来被认为是简单的事实，如“Supplier X supplies part Y“从数据建模的观点看，许多情景要求更复杂是信息形式可以用来回答下面这样的问题。1.供应商X供应的Y的这部分有多可靠。2.如果一个X类型的人已经买了产品Z，那么他还会买产品Y有多大可能性（或者说他再买Y的可能性会不会更大？3.如果X已知，则关于Y的有多少额外的信息能有Z提供。随着信息管理技术的发展,现代社会已步入信息社会,信息量与日俱增。而与此相矛盾的是,在某一方面,信息量又显得非常匮乏,所掌握的信息也同时存在不确定性和不完全性。1：实体(Entity)与实体集实体是指客观存在并可以相互区分的事物。具有相同属性的实体可构成一个实体集。2：属性属性(Attribute)是指实体集中所有实体所具有的共同特征。3：联系与联系集联系(Relationship)是指实体集间有意义的相互作用。实体间的联系有一对多联系，一对多联系和多对多联系。具有相同属性的联系属于同一联系集(Relationship Set)。班级名学生班级属于班主任姓名性别年龄学号学生性别年龄学号班级姓名学生性别年龄学号MN这里，我们需要先来简介下传统的数据库。在传统数据库的应用中，数据的存在性和精确性均确凿无疑。在关系数据库模型概念中最重要的是信息与信息保存。关系模型的基本原理是信息原理：所有信息都表示为关系中的数据值。通常，一个关系数据库（RDB）被定义为一个有限的关系集合，其中每个关系是一个笛卡尔积的子集，称为域域（domain）。也就是域 是一组具有相同数据类型的值的集合。一个关系通常 是由赋予它的元组语义来确定的。凡符合元组语义的那部分元素的全体就构成了该关系模式的关系。1.关系和概率数据库定义：设有属性集A1和A2分别在值域D1和D2中取值，则两个属性集的笛卡尔积定义为：笛卡尔积是集合论中的基本概念之一，由下面的定义给出。例如，A=a,b,B=0,1,2,则AxB=,BxA=,下面我们先来说一下笛卡尔积下面我们先来说一下笛卡尔积。则则D D1 1，D D2 2，D D3 3的笛卡尔积为：的笛卡尔积为：D D1 1D D2 2D D3 3(张清玫，计算机专业，李勇张清玫，计算机专业，李勇)，(张清玫，计算机专业，刘晨张清玫，计算机专业，刘晨)，(张清玫，计算机专业，王敏张清玫，计算机专业，王敏)，(张清玫，信息专业，李勇张清玫，信息专业，李勇)，(张清玫，信息专业，刘晨张清玫，信息专业，刘晨)，(张清玫，信息专业，王敏张清玫，信息专业，王敏)，(刘逸，计算机专业，李勇刘逸，计算机专业，李勇)，(刘逸，计算机专业，刘晨刘逸，计算机专业，刘晨)，(刘逸，计算机专业，王敏刘逸，计算机专业，王敏)，(刘逸，信息专业，李勇刘逸，信息专业，李勇)，(刘逸，信息专业，刘晨刘逸，信息专业，刘晨)，(刘逸，信息专业，王敏刘逸，信息专业，王敏)例例 给出三个域：给出三个域：D D1 1=SUPERVISOR=SUPERVISOR=张清玫，刘逸张清玫，刘逸 D D2 2=SPECIALITY=SPECIALITY=计算机专业，信息专业计算机专业，信息专业 D D3 3=POSTGRADUATE=POSTGRADUATE=李勇，刘晨，王敏李勇，刘晨，王敏 课本中的笛卡尔积课本中的笛卡尔积对于任何关系，关系中关联着域的属性集被称为一个关系模式，关系模式集被称为一个关系库模式。通常，我们定义一个关系数据库（relational database）是一个集合RD=B1，.，Bn。这里每个RD中的元素B是一个关系系统，B=。是组成该关系的属性名非空集合。是属性集U中属性所来自的域。是属性间的数据依赖关系集合。我们经常会谈到这个关系而不是全部的数据系统。dom 是每个属性向域的映像集合。它常常直接说明属性的类型，长度。(Bi中所有可能的元组,，简称Ti;)B=一个概率系统，就像一个关系系统。是一个四元组 ，但是它的第四个分量 p 是一个类型T-0,1的函数，限制为 。我们指p是V上的一个分布。一个概率数据库（PDB）是概率系统中的概率数据的集合。PDB提供一种表示信息类型的不能被关系数据库捕捉的方法。用这种方法，关系数据库理论中所有的数据模式概念和机制被运用到更复杂的模式情景。2.信息和约束2.1信息内容一个重要的思想关联着关系当用在数据库上就是信息。任何关系，在它的域的范围内不是满的笛卡尔积，它就会有约束。一个具有约束的分布函数使元组T在一定程度上偏离了均匀分布。信息熵：信息的基本作用就是消除人们 对事物的不确定性。变量的不确定性越大，熵也就越大，把它搞清楚所需要的信息量也就越大。一个变量取值的信息量可以看作是它带来的“使人惊讶的程度”，一个必然事件没有任何信息量，而一个极其偶然的事件的发生则会使人非常“惊讶”，因而包括大量信息。自然地，信息量的概率就与变量的概率分布联系在了一起。香农熵（Shannon Entropy）成功表达了一个离散型变量所带来的平均信息量：设H是一个离散概率分布的（香农）熵。规定：0 log 0=0；显然H0；让我们考虑一系列可以生成随机数的程序。如果我们知道这些程序生成的随机数就是1,2,3,.,n个，并且每个数字出现的概率是不一样的，不妨设概率分别是p1,p2,pn。那么不同的程序就会有不同的生成数字的概率。假如一个程序生成3的概率是99%，而另一个程序生成1n个数都是可能的，这件事儿我们如何用数学来刻画呢，这就是Shannon找到的信息熵公式：对于第二个程序，如果所有的数字都是等可能的，那么p1=p2=pn=1/n，那么H=log(n)。显然第二种情况下的H大于第一种情况。所以H可以描述这些随机生成数程序的信息量大小。可以验证一下，对于第一个程序，如果确定生成3，所以p3=1,其他的p=0，那么H(0,0,1,)就是0。对于第二种情况，H的计算过程如下：H(1/n,.,1/n)=log(n)由例子，我们可以得到一个重要的熵的特性：设N是系统S内的事件总数，则熵 。当且仅当p1=p2=.=pn时，也既p=，等号成立，此时系统S的熵最大。我们来看一下关系数据库中的投影定义：关系R上的投影是从R中选择若干属性列组成新的关系。记作：其中，A为R的属性列。这个操作是对一个关系进行垂直分割，投影运算的直观意义如图2-2所示。我们举一个实际的例子。设有一个学生情况表(student).查询学生情况表中的学生的学号和姓名。或设P是一个关系，分布p，模式为V，让 。则p到Z上的投影(Projection)是：且我们引用 作为一个投影操作的结果。这个定义的有道理的，(当处理一个关系系统和特征函数r，对概率系统这个定义是相同的，除了 操作 被max取代。与关系数据库中符号 相对应。这里，在后一个表达上，r是被特征函数取代。)系统 将作为P的一个子系统被引用，且Z是V的一个子模式（dom|z是dom到z的限制。）一个p分布在数据库模式X=（V1,.Vk）上的投影是一个（数据库实例）子分布 。分布在数据库模式的投影是：eg：p1(v1v2=00)=p(v1v2v3=000)+p(v1v2v3=001)例如：数据库中的依赖关系：学号-姓名语文成绩+数学成绩=总成绩 数据依赖的主要类型数据依赖的主要类型函数依赖函数依赖(Functional Dependency(Functional Dependency，简记，简记FD)FD)多值依赖多值依赖(Multivalued Dependency(Multivalued Dependency，简记，简记MVD)MVD)连接依赖连接依赖(Join Dependency)(Join Dependency)在一个标准简单的数据库应用中，数据依赖经常可以由属性的意义推出，由应用所确定。在复杂的科学数据库情景中，经常的情况是依赖不能被事先预知。201201-郭靖通常在数据库上执行的操作（例如连接）可能导致一个分布p被一个分布q取代。为了发展大概的妥善的连接依赖的（数据库分解）的模糊想法，我们用一个信息损耗的方法作为代替。另一方面，我们也想要一种方法。PDB如何准确地确定在一些属性集（例如，）的一个分布，当这种分布是在数据库中一个单一的概率系统没有展示的时候。由于依赖这个关系重点我们在后面用到，这里我先简介一下最基本的函数依赖函数依赖；函数依赖简单点说就是：某个属性集决定另一个属性集时，称另一属性集依赖于该属性集。函数依赖函数依赖：设X,Y是关系R的两个属性集合，当任何时刻R中的任意两个元组中的X属性值相同时，则它们的Y属性值也相同，则称X函数决定Y，或Y函数依赖于X。说明说明:1.1.函数依赖不是指关系模式函数依赖不是指关系模式R R的某个或某些关的某个或某些关系实例满足的约束条件，而是指系实例满足的约束条件，而是指R R的的所有关系实所有关系实例例均要满足的约束条件。均要满足的约束条件。2.2.函数依赖是函数依赖是语义范畴语义范畴的概念。只能根据数的概念。只能根据数 据的语义来确定函数依赖。据的语义来确定函数依赖。例如例如“姓名姓名年龄年龄”这个函数依赖只有在这个函数依赖只有在不允许有同名人的条件下成立不允许有同名人的条件下成立对于一个概率系统 ，其中有X,Y V,以及X和Y在p上适当的投影。当且仅当这里H（Y|X）是X对Y的条件下的熵，也可以被定义为定义：以后，我们用YX表示YUX明显地，H(Y|X)=0意味着一旦属性X上的元组值已知，则属性Y上的元组就没有了不确定性可能。）H(Y|X)的值可以衡量大概的函数依赖。H(Y|X)离0越远，依赖性越弱。H(Y|X)能获得的最大值是H(Y)，当X与Y没有关联性时。因此，一个可信的方法，关联着一个给定的系统P，是定义：定义：关于多值依赖：定义：设R(U)是属性集U上的一个关系模式。X，Y，Z是的U的子集,并且Z=U-X-Y。关系模式R(U)中多值依赖XY成立，当且仅当对R(U)的任一关系r,给定的一对(x，z)值有一组Y的值，这组值仅仅决定于x值而与z值无关。若X-Y，而Z=空集，则称X-Y为平凡的多值依赖。否则，称X-Y为非平凡的多值依赖。举例如下，有这样一个关系 ，假设一个产品只能放到一个仓库中，但是一个仓库可以有若干管理员，那么对应于一个 仓库管理员，库存产品有一个仓库号，而实际上，这个仓库号只与库存产品号有关，与管理员无关，就说这是多值依赖。例：例：在关系在关系SC(Sno,Cno,Grade)SC(Sno,Cno,Grade)中，中，非平凡函数依赖：非平凡函数依赖：(Sno,Cno)Grade(Sno,Cno)Grade 平凡函数依赖：平凡函数依赖：(Sno,Cno)Sno (Sno,Cno)Sno (Sno,Cno)Cno (Sno,Cno)Cno定义:关系模式R的一个分解：=R1，R2，Rn U=U1U2Un，且不存在 Ui Uj，F Fi i 为为 F F在在 U Ui i 上的投影。上的投影。我们再来看数据库分解！1.SL分解为下面三个关系模式：SN(Sno)SD(Sdept)SO(Sloc)分解后的关系为：模式的分解（续）n分解后的数据库丢失了许多信息n例如无法查询95001学生所在系或所在宿舍。n如果分解后的关系可以通过自然连接恢复为原来的关系，那么这种分解就没有丢失信息我们注意到，除个别情况，一般分解后的关系模式包含不了原关系模式下的全部信息。也就是说，一般情况下用分解后的关系是恢复不了（或者说重建不了）原关系的。2.SL分解为下面二个关系模式：NL(Sno,Sloc)DL(Sdept,Sloc)分解后的关系为：nNLDL比原来n的SL关系多了n3个元组无法知道95002、95004、95005究竟是哪个系的学生元组增加了，信息丢失了第三种分解方法3.将SL分解为下面二个关系模式：ND(Sno,Sdept)NL(Sno,Sloc)分解后的关系为：NDNLSnoSdeptSloc95001CSA95002ISB95003MAC95004CSA95005PHB与SL关系一样，因此没有丢失信息。具有无损连接性的模式分解n关系模式R的一个分解=R1，R2，Rn,若R与R1、R2、Rn自然连接的结果相等，则称关系模式R的这个分解具有无损连接性（Losslessjoin）具有无损连接性的分解保证不丢失信息无损连接性不一定能解决插入异常、删除不一定能解决插入异常、删除异常、修改复杂、数据冗余等问题异常、修改复杂、数据冗余等问题概率数据库是怎么产生的？1 1）基本概念：）基本概念：客观世界的现象或过程中，存在以下两种基本情况：客观世界的现象或过程中，存在以下两种基本情况：*确定性：有规律性或无规律性，可预测性强，解释的确定性：有规律性或无规律性，可预测性强，解释的唯一性，只有一种可能；有的测得准唯一性，只有一种可能；有的测得准.*不确定性：规律性不明显，时有时无，可预测性差，不确定性：规律性不明显，时有时无，可预测性差，多种解释，多种可能，有的测不准多种解释，多种可能，有的测不准.概率数据库可以存储那些不能用关系模型所代表的信息类型。概率数据库也可以被看做是一般化的关系数据库。任何关系数据库都可以被一个没有信息丢失的概率数据库代表。数据固有的不确定性数据固有的不确定性数据获取过程中引起的不确定性数据获取过程中引起的不确定性数据处理过程中引起的不确定性数据处理过程中引起的不确定性数据转换过程中引起的不确定性数据转换过程中引起的不确定性数据传输过程中引起的不确定性数据传输过程中引起的不确定性数据提取与分类过程中引起的不确定性数据提取与分类过程中引起的不确定性数据应用不当引起的不确定性数据应用不当引起的不确定性2）产生原因产生原因：现在认为一个数据集成系统需要在三个层次上处理不确定性不确定性数据源、不确定性模式映射、不确定性查询。系统的基本框架结构如图5所示。中介模式数据源D4不确定性查询数据源D1数据源D2数据源D3数据源D5数据的不确定本质和数据集成过程中的不确定因素决定了数据集成系统具有不确定性。基于中介模式的一个例子数据源1:学生表数据源2:课程表姓名学号年龄性别郭靖11110124男黄蓉11110223女郭靖英语历史数学NN黄蓉英语物理化学数学美术基于中介模式，我们现在要查询学生郭靖的信息数据库系统要将郭靖同学所在的两个（也可能会有更多）表调出，利用模式映射技术构造中介模式，形成一个二维表。如图所示。姓名学号年龄性别选课郭靖11110124男英语历史数学NN黄蓉11110223女英语物理化学数学美术不确定数据库建模的研究工作很多，可能世界模型则是应用最广泛的数据模型。在该模型中，各元组的任一合法组合均构成一个可能世界实例（instance），实例的概率值可以通过相关元组的概率计算得到。IDID信息信息概率概率1A0.32B0.73C0.6图2(a)是一个不确定性数据库，包含三个元组，概率字段表示该元组的发生概率。元组之间可能独立也可能存在依赖关系。首先假设各个元组之间独立，则共有23=8个可能世界实例，各实例的概率等于实例内元组的概率乘积与实例外元组的不发生概率的乘积，如图2(b)所示。(a)一个不确定数据库样例元组独立：(b)(b)PW P(PW)0.08411 0 0.036.036220 0.196.19633 0 0.126.1261,21,20 0.084.0841,31,3 0 0.054.0542,32,3 0 0.294.2941,2,31,2,3 0.126假设规则为：，即元组1与元组3不能够同时发生，但可以同时不发生。总共有6个可能世界实例，如图(c)所示。某些场景下，元组之间并非独立，而是存在依赖关系，这种依赖关系可以用规则描述。图图C C 依赖规则：依赖规则：PW 1 2 2 3 3 1,21,2 2,32,3 P(PW)0.030.09 0.180.07 0.21 0.42元组本身存在性的不确定性可用概率p描述：即该元组存在的概率是p，不存在的概率是1-p。元组的属性值的不确定性有多种描述方式，最通用的方式是以概率密度函数描述属性值，也可以用一些统计值进行描述，例如方差等。不确定数据有两方面的内涵，即各元组本身存在性的不确定性和各元组属性值的不确定性。*一个特定的数据库实例（也即可能世界实例）一个特定的数据库实例（也即可能世界实例）的概率等于其所包含的元组的概率等于其所包含的元组发生发生的概率乘积和的概率乘积和其所不包含的元组的不发生概率的乘积其所不包含的元组的不发生概率的乘积*所有可能世界的概率之和所有可能世界的概率之和=1一提到不确定性，人们很自然的能够想到概率，概率是描述不确定性的一种手段，也正是如此，人们在处理日常大量的数据集成中的不确定性问题，由此带动了概率数据库（probabilistic database）的发展。概率数据库中的数据本身是带有概率的，查询结果也是具有概率的。概率关系模式将概率理论应用于经典关系模式中,并且有相当完善的代数结构体系。由于现实数据并不都是关系的,所以概率理论同样适用于其它类型的数据。概率数据库系统的研究概率数据库系统的研究总结一个概率数据库理论的某些方面，也适用于关系数据已经被概述了。这种理论是一种统一的数据建模的方法，集成了关系数据库理论，系统理论和多元统计模型技术的一部分。在两个领域的进一步研究是：用概率关系作为依赖条件，以及它们相互作用的方式，以及在何种程度上从一个给定的数据库实例上可设别哪一种分布或关系。后一个区域的发展根据数据库中容纳的信息对于推理问题和决策制定会特别的有用！谢谢！