空间属性数据库范式分解算法研究

空间属性数据库范式分解算法研究 ISSN1005—2763 CN43—1215/TD 矿业研究与开发第27卷第5期 MININGR&D,Vo1.27,No.5 2007年1O月 0ct.2OO7 空间属性数据库范式分解算法研究 张春明,孙豁然,姜绍飞,李元辉,韩冬梅 (1.东北大学,辽宁沈阳110004;2.沈阳建筑大学,辽宁沈阳110168) 摘要:从空间属性数据库的E—R概念数据模型转换得到 的关系数据模型普遍存在着某种程度的数据冗余,由此会引 起很多无法预料的问题.通常需要借助于关系规范化理论 将其分解成规范化的第三范式.由于手工进行分解费时费 力,因此,提出了一种可以在空间属性数据库设计和优化过 程中自动将关系模式分解为第三范式的通用算法.该算法 同样适用于普通的关系数据库. 关键词:关系数据库;关系规范化;范式分解;算法;函数依赖 中图分类号:TP311.138文献标识码:A 文章编号:1005—2763(2007)05—0061—03 StudyonNormalFormDecompositionAlgorithm forSpatialAttributeDatabase ZhangChunming,SunHuoran,flangShaofei, Yuanhui.HanDongmei (1.NortheasternUniversity,Shenyang,Liaoning110004, Chona;2.ShenyangJianZhuUniversity,Shenyang, Liaoning110168,China) Abstract:Informingrelationdatamodelbyconveningdirectly fromtheE——Rconceptualdatamodelofaspatialattributedata-- base,somedataredundanc1whichmayresultinunexpected problemsgenerallycomesintobeing.Forcontrollingthedatare— dundancy,therelationdatamodelusuallyisdecomposedinto normalizedthirdnormalform(3NF)basedonrelationnormali— zationtheory,butthemanualdecompositiontakesalotoftime andlaborInthepaper,anewgeneralalgorithmwhichcanau— tomaticallydecomposerelationdatamodelintothirdnormalform (3NF)forthedesignandoptimizationofspatialattributedata— baseisproposed.Thenewalgorithmisalsoapplicabletogeneral relationaldatabase. KeyWords:Relationaldatabase,Relationnormalization,Nor- malformdecomposition,Algorithm,Functionaldependencies 1算法的理论依据 空间属性数据库逻辑结构设计是指把E—R概 念数据模型转换成地理信息系统(GIS)支持的数据 模型,最常见的是关系数据模型.从E—R模型直 接转换得到的关系数据模型普遍存在着某种程度的 数据冗余,由此会引起很多问题.因此,必须借助于 E.F.Codd等学者的关系规范化理论将其加工成为 规范化的关系(Normalization). 关系规范化理论定义了关系与关系模式.关系 模式就是对关系的描述,包括关系名,关系中的属性 以及属性之间的依赖关系.在关系模式中,满足特 定要求的关系称之为范式.最基本的规范化关系 (第一范式)指关系的每一个分量必须是原子的,即 不可再分的数据项.然而并非所有这样的规范化的 关系都具有理想的内在性质.根据规范化关系的内 在性质,把规范化的关系划分成一些等级.最低级 别为第一范式(1NF),第二级别为第二范式(2NF), 依此类推.更高级范式存在于它的低级范式中.如 一 个2NF关系也是1NF关系,但1NF关系不一定是 2NF关系.只有3级及以上的关系才具有理想的内 在性质,才能更好地描述现实世界. 关系的规范化级别是数据的语义特性,而不是 值的特性,是由数据之间的依赖关系 决定 郑伟家庭教育讲座全集个人独资股东决定成立安全领导小组关于成立临时党支部关于注销分公司决定 的.数据 依赖是一个关系中属性之间相互联系的抽象,是数 据内在的语义性质.根据一个关系内的各属性之间 依赖情况来判定关系是否具有某些不合适的性质, 然后再将具有不合适性质的关系转换为更为合适的 形式.这种从低级别的关系模式转化为高级别的关 系模式的过程就是规范化过程. 现实生活中最常见的一种数据依赖是函数依赖 (FunctionalDependency).其定义为:设尺()是属 性集上的关系模式.,】,是的子集.若对于 尺()的任意一个可能的关系r,r中不可能存在两个 元组在上的属性值相等,而在】,上的属性值不等, 收稿日期:2006—11—30 基金项目:国家自然科学基金资助项目(50474018,50408033,50474017). 作者简介:张春明(1968一),男,重庆人, 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 师,从事地理信息系统技 术及其应用的研究,Email:mrzhang2001@163com. 62矿业研究与开发 则称函数确定y或y函数依赖于,记作—y. 函数依赖和别的数据依赖一样是语义范畴的概 念,只能根据语义来确定一个函数依赖.例如,矿种 编号一矿种名称.自变量(即矿种编号)确定之 后,相应的函数值)(即矿种名称)也就唯一地确 定了,称”矿种编号”函数决定”矿种名称”,或称 “矿种名称”函数依赖于”矿种编号”.注意:这个函 数依赖只有在”矿种编号”没有重复编号的前提下 成立,否则必须规定编号不允许重复,函数依赖才能 成立.换句话说,函数依赖不是关系模式的某个或 某些关系满足的约束条件,而且是指的一切关系 均要满足的约束条件. 在()中,如果—y,并且对于的任何一 个真子集,都有硝,则称y对完全函数依赖. 若—y,但y不完全函数依赖于,则称y对部 分函数依赖. 在()中,如果—y(,且y不是的子 集),y—z,则称z对X传递函数依赖,记作—z. 将最基本的第一范式转化为更高级别的范式实 质上是一个范式分解,也就是所谓的关系规范化的 过程.它与函数依赖图之间有着传统密不可分的关 系.人们常常借助于函数依赖图进行范式分解和对 关系模式进行优化.对于具有简单函数依赖关系的 数据库应用,完全可以直接画出函数依赖图,并据此 进行范式分解.但对于逻辑关系错综复杂的数据库 应用,直接画出函数依赖图有些困难,而且容易出 错.为此,本文基于上述规范化理论首次提出一种 可以借助于计算机程序辅助实现范式分解的通用算 法.它可以自动消除那些冗余的函数依赖关系,并 且可以自动生成满足第三范式要求的关系模式. 2算法的实现步骤 该算法的基本原理是通过消除第一范式中的局 部函数依赖,使之成为第二范式;再消除第二范式中 的传递函数依赖,使之成为第三范式.当然,该算法 的实现过程并不像原理描述这样简单,而是必须遵 循一定的步骤.以下结合实例说明该算法的实现过 程及具体步骤. 图1为某空间属性数据库中地层及相关实体的 E—R图.将所有属性一一列出,直到这些属性不 能再细分为止,即均为原子屙『生,这样便得到关系模 式(属第一范式).它的形式化定义是一个5元组: (,D,MAP,F).其中与范式分解密切相关的主 要是和F.是的属性集合,即: U={地层编号,地层单位符号,地层单位名称, 岩石代码,岩石名称,岩石颜色代码,岩石颜色名称, 岩石结构代码,岩石结构名称,岩石构造代码,岩石 构造名称,矿种代码,矿种名称,地层厚度} F是属性间数据依赖关系(此处指函数依赖) 的集合,是关系的元组语义的描述,是一种完整性约 束条件.即: F={地层编号一地层单位符号,地层编号一地 层单位名称,(地层编号,地层单位符号)一地层单 位名称,地层单位符号一地层单位名称,地层编号一 地层厚度,……} 矿种代(代码)(名称 l旱竺 i一 地层单位符号表lI岩石代码表 lIlll ,I 一.一图1地层及相关实体的E—R图 (图中双线表示完全参与;属性下面的实线表示主关键字,虚线 表示弱实体的部分关键字属性,波浪线表示外关键字) 2.1输入属性之间的函数依赖关系 首先,根据语义列出函数依赖关系.一定不要 遗漏任何基本的函数依赖关系,但不必考虑这些关 系是否有冗余,本算法会自动消除此类冗余.这里 没有使用函数依赖闭包算法来穷举所有的函数依赖 关系,因为其数量呈指数量级,而且没有必要一一列 出(函数依赖闭包是指对于给定的关系的函数依 赖集合F,应用Armstrong推理规则推导出在中成 立的所有函数依赖,记作F).由于计算属『生集合 的闭包可以判断一个函数依赖是否从F推导出的, 即函数依赖—y是使用Armstrong推理规则得自 张春明,等:空间属性数据库范式分解算法研究63 F,当且仅当y包含于,其中是相对于F计算 出的属性的闭包,因此,该结论可用来验证所输入 的函数依赖关系是否成立. 然后,把所有形如l,形式的属性问依赖关 系分别作为一条记录存储.至于究竟存储到数据库, 还是存储到集合数据结构中,完全取决于用户程序 设计的偏好.每条记录分成两个字段,分别保存属性 和y的名称.为叙述方便,以下将其分别称作左字 段(决定列)和右字段(被决定列).左字段既可以是 单个属性,如”地层编号”,也可以是多个属性的组 合,如”地层编号,地层单位符号”等.但右字段必 须是单个屙j生.对于形如(y,z)的依赖关系应 将其分解为两个独立的记录y和Z.对于 yz形式的函数依赖,也应将其分解为两个独 立的记录y和yZ形式. 2.2搜索并替换互为决定列的属性 对于任意一条函数依赖关系记录y,若在 记录集中还存在另一条函数依赖关系记录y, 则X和y互为决定列.这种情况下和y是一种并列 关系或等价关系.如范例中的”地层单位符号”属性 和”地层单位名称”屙j生.将记录集中所有的和y 全部替换为新的属性名y(如”地层单位符号一地 层单位名称”),并把和y与新属性疋y之间的关 系保存到一个单独创建的记录集中,姑且称它为属 性名替换记录集.属性名替换记录集中的每条记录 保存有新属性和被其替换掉的旧属性之间的对应关 系,留待后面使用. 由于本算法规定右字段必须为单个属性,因此, 该步骤实际上只是替换互为决定列的单个属性.替 换完成后必须删除—y—y这样的冗余记录,且 对于左字段中那些组合属性中可能重复出现的新属 性名—y,仅保留其中一个噩一y. 重复上述步骤,直到所有互为决定列的属性处 理完毕. 在进行下一步之前,对于左字段为组合属性 (即包括多个属性)的记录,必须对左字段中的各属 性名按照名称进行排序,如(z,B,F,D)字符串排序 后变为(B,D,F,Z)字符串.之所以必须事先进行 排序,是因为算法中需要对各记录的左字段进行比 较运算,如果没有事先约定排序规则,那么程序会认 为{A,B}和{B,A}是两个完全不同的集合.为避免 出现这样的错误,该算法规定必须对左字段内各属 性进行预先排序. 2.3消除局部函数依赖 消除局部函数依赖的理论依据如下:若z 且yz成立,则必定有: (1)X与y等价或至少互为决定列; (2)X或y中某个为组合属性,且包括于y或 者y包括于,即存在局部函数依赖., 由于在步骤2中已排除了(1)的情况,因此,可 以断定存在局部函数依赖,其中左字段长度较短者 一 定包含在左字段长度较长者之中.换句话说,可 以删除左字段长度较长者所在的那条函数依赖关系 记录. 具体步骤如下?:对于记录集中右字段值相同的 记录,比较其左字段值,仅保留左字段长度最短的记 录,删除长度较长的记录.如范例中的两条函数依 赖关系记录: 地层编号地层单位名称 地层编号,地层单位符号地层单位名称 „ 删除左字段长度较长的后一条记录,即可消除 局部函数依赖. 重复上述步骤,直到消除所有的局部函数依赖 为止. 2.4消除传递函数依赖 消除传递函数依赖的方法比较简单.对于任意 一 条函数依赖关系记录y,在记录集中查找左 字段值为y的所有记录.若找到一条记录yz,则 再在记录集中搜索z记录.如果找到的话就删 除该记录.如范例中的3条函数依赖关系记录: 地层编号地层单位符号 地层单位符号地层单位名称 地层编号地层单位名称 删除最后一条记录即可消除传递函数依赖. 重复上述步骤,直到消除所有的传递函数依赖 为止. 2.5范式整理 经过前几步的处理,便进入到范式整理阶段. 将处理后的函数依赖关系记录集中所有左字段值相 同的记录合并为一个关系,其中左字段值作为关系 的主关键字,右字段值对应的各属性的集合作为非 关键字属性.若主关键字包括有在屙j生名替换记录 集中记录的新建属性(参见步骤2),则应将其还原 为原来的属性.为增加其通用性,常见的做法是仅 选择原来的属性中的一个替换新建属性,原则上任 (下转第89页) 刘正宇,等:望儿山金矿中深孔预注浆堵水技术研究89 (7)注浆压力.南风井贯通巷道静水压力通过 孔内突水后注浆泵压力表测定为1.8,2MPa,因 此,施工时注浆压力确定为5,6MPa.望儿山金矿 南风井贯通巷道主要是构造裂隙脉状含水带小裂隙 出水,进浆量一般不超过3.0t水泥,注浆压力上升 很快,在每次注浆施工时,终压一般达到l0,l5 MPa_1] .中深孔预注浆堵水结束标准:注浆压力达 到设计终压值,并维持30min;每孔浆液注入量达到 设计总量. (8)堵水效果….望儿山金矿南风井贯通巷 道共施工中深孔预注浆堵水段3段,全长97in.该 区域含水构造密集发育,特别是第一,第二段,钻孔 进尺时最大突水通过容积法测定超过100in/h,平 均钻进3in进行1次注浆.通过中深孔预注浆堵水 处理,南风井贯通巷道仅残留滴水<10in/h,而在 贯通巷道北端约40in范围巷道内,初始出水量为 100in./h,通过”顶水注浆”,”壁后注浆”手段处理 后尚残留滴淋水30in./h,两者比较可知,中深孔预 注浆堵水效果显着. 3结论与建议 (1)望儿山金矿南风井贯通巷道处于富水区, 地质条件复杂,节理裂隙发育且相互穿插,表象多为 “x”和”人”字型,出水构造揭露后再进行注浆封 堵,由于水压偏大,难以解决表层冒浆的问题,堵水 效果欠佳.而中深孔预注浆堵水技术从根本上解决 了掌子面冒浆的技术难题,用常规注浆手段就能取 (上接第63页) 何一个属性均可以,但一般选择表示ID的属性.如 范例中”地层单位符号一地层单位名称”属性对应的 属性组合为”地层单位符号”和”地层单位名称”,此 时可以选择其中的”地层单位符号”属性替代”地层 单位符号一地层单位名称”属性作为主关键字.然 后将原来属性组合单独作为一个新的关系,新关系 仍以前面挑选的属性作为主关键字,剩余属性全部 作为候选关键字.如(地层单位符号,地层单位名 称),其中”地层单位符号”属性仍作为主关键字, “地层单位名称”属性则作为候选关键字. 对于属性名替换记录集中记录的其它新建属 性,若这些属性不是其它任何属性的决定列,则这些 记录本身各自可以形成一个新的关系. 经过上述整理生成的所有关系均为规范化的第 得显着的堵水效果. (2)中深孔预注浆堵水技术既有很好的堵水效 果,在构造破碎带和断层发育区段还能起到注浆加 固巷道周边岩石的作用. (3)中深孔预注浆堵水技术也存在一定的局限 性,在巷道轮廓线外围,当含水构造走向与钻孔走向 平行且与钻孔已揭露构造无水力联系时,注浆堵水 施工结束后巷道掘进当中,由于受爆破冲击波的影 响,巷道内有可能出现较大的滴淋水甚至涌水.因 此,掘进前为保险起见,建议在掌子面加强探水工 作,5个探水孔的水平角为0.,15.,垂直角为5., 15.,孔深不小于4.0In,孔径与炮眼相同,遇探水孔 突水时应进行注浆堵水J. (4)由于在望儿山金矿南风井贯通巷道施工的 3段中深孔预注浆堵水效果显着,没对钻孔的孔斜 做定量分析.在不同地质条件下,终孔位置如果偏 离巷道轮廓线过大,受浆液扩散范围的局限,注浆堵 水效果可能欠佳,因此应根据实际施工情况进行钻 孔开孔角度的调整及采取有效措施防止孔斜过大. 参考文献: [1]黄丙仁.望JC山金矿南风井贯通工程竣工 报告 软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载 [R].长沙:长 沙矿山研究院,2003. [2]刘正宇.望儿山金矿主竖井一侧地下水治理工程竣工报告 [R].长沙:长沙矿山研究院,20{)2. [3].唐业清.简明地基基础设计施工手册[M].北京:中国建筑工 业出版社,20{)3. [4]彭振斌.注浆工程设计计算与施工[M].武汉:中国地质大学 出版社,1997. 三范式.如果还想进一步转换为Boyce—Codd范式 (BCNF),第四范式,甚至第五范式,则可以根据上 述处理结果画出依赖图,然后再根据语义关系进行 规范化,使之成为更高级别的范式. 本文所述的范式分解算法仅是笔者的一种新尝 试,错误和不当之处恳请广大读者指教. 参考文献:一 [1]萨师煊,王珊.数据库系统概论(第三版)[M].北京:高等 教育出版社,2000. [2]张凤琴,张水平.数据库原理及应用[M].北京:清华大学出版 社,2005. [3]海燕,皇甫中民.基于函数依赖的关系模式分解方法分析 [J].水利电力机械,2005,27(3):45,47. [4]仝春灵,左毅,李玉忱.关系模式设计的规范化与非规范化 [J].济南大学(自然科学版),2006,20(3):228,231. 一 [5]王雄,孙水裕,王孝武.城市环境信息系统数据库设计及最 小覆盖算法[J].计算机与数字工程,2004,32(4):34,36.