数据库系统的内部结构体系简介
计算机安全是计算机技术的一个分支,其目标包括保护信息免受未经授权的访问、中断和修改,同时为系统的预期用户保持系统的可访问性和可用性。下面是我收集的数据库系统的内部结构体系,希望大家认真阅读!
数据库系统的内部具有三级模式与二级映射。
1)数据库系统的三级模式
数据模式是数据库系统中数据结构的一种表示形式,它具有不同的层次与结构方式。
(1)概念模式
概念模式是数据库系统中全局数据逻辑结构的描述,是全体用户公共数据视图。概念模式主要描述数据的概念记录类型以及它们之间的关系,还包括一些数据间的语义约束。
(2)外模式
外模式又称子模式或用户模式,是用户的数据视图,即用户见到的数据模式。
概念模式给出系统全局的数据描述而外模式则给出每个用户的局部数据描述。
(3)内模式
内模式又称物理模式,它给出数据库物理存储结构与物理存储方法,如数据存储的文件结构、索引、集簇及hash等存取方式与存取路径,内模式的物理性主要体现在 *** 作系统及文件级上。
内模式对一般的用户是透明的,但它的设计直接影响到数据库系统的性能。
模式的三个级别层次反映了模式的三个不同环境以及它们的不同要求,其中内模式处于最底层,它反映数据在计算机物理结构中的实际存储形式,概念模式牌中层,它反映了设计者的数据全局逻辑要求,而外模式处于最外层,通过两种映射由物理数据库映射而成它反映用户对数据的要求。
2)数据库系统的二级映射
数据库系统的三级模式是对数据的三个级别抽象,它把数据的具体物理实现留给物理模式,使得全局设计者不必关心数据库的具体实现与物理背景;通过两级映射建立了模式间的联系与转换,使得概念模式与外模式虽然并不物理存在,但也能通过映射获得实体。同时,两级映射也保证了数据库系统中数据的独立性。
两级模式的映射:
概念模式到内模式的映射:该映射给出概念模式中数据的全局逻辑结构到数据的物理存储结构间的对应关系
外模式到概念模式的映射:该映射给出了外模式与概念模式之间的对应关系
拓展外部结构
从数据库最终用户角度看,数据库系统的结构分为集中式(单用户结构、主从式结构)、分布式(客户机/服务器结构)和多层结构,这是数据库系统外部的体系结构。
(1)单用户应用结构:是运行在个人计算机上的结构模式,常称为桌面(Desktop)DBMS。属于单用户DBMS的主要产品有:Microsoft Access、Paradox、Fox系列。单用户的DBMS的功能在数据的一致性维护、完整性检查及安全性管理上是不完善的。桌面数据库管理系统中比较好的有Access、Paradox等,它基本实现了DBMS应该具有的功能。
(2)主机/终端结构:是以大型主机为中心(Mainframe.Centric)的结构模式,也称为分时共享(Time—Sharing)模式,它是面向终端的多用户计算机系统(主从式结构)。该结构以一台主机为核心,将 *** 作系统、应用程序、DBMS、数据库等数据和资源均放在该主机上,所有的应用处理均由主机承担,每个与主机相连接的终端都是作为主机的一种I/O设备。由于是集中式管理,主机的任何错误都有可能导致整个系统的瘫痪。因此,这种结构对系统的主机的性能要求比较高,维护费用也较高。
(3)客户机/服务器(Client—Server,C/S)结构:是随着计算机网络的广泛使用而出现的结构模式。该结构是将一个数据库分解为客户机(称为前端,Front—End)、应用程序和服务器(称为后端,Back-End)三部分,通过网络连接应用程序和服务器。由于C/S结构的本质是通过对服务功能的分布实现分工服务,因而又称为分布式服务模式。人们将C/S称为二层结构的数据库应用模式。
(4)多层数据库应用结构:将应用程序放在服务器端执行,客户机端安装统一的前端运行环境——浏览器,在客户机和服务器之间增加一层用于转换的服务器,形成三层结构的数据库应用模式,这就是Intemet/Intranet环境下数据库的应用模式。三层结构是由二层(C/S)结构扩展而来的,这种三层结构也称为浏览器/Web 服务器/数据库服务器(B/W/S)结构。
;(1) 试说明R不是2NF模式的理由。
存在部分依赖,所以R不是2NF
(2) 试把R分解成2NF模式集。
R1(ABC),R2(AD) 说明:消除部分依赖关系
2(1)R存在传递依赖。
(2)R1(CB),R2(BA) 说明:消除传递依赖关系
数据依赖的公理系统
逻辑蕴含
定义511 对于满足一组函数依赖 F 的关系模式R <U,F>,其任何一个关系r,若函数依
赖X→Y都成立, 则称F逻辑蕴含X →Y。
一、Armstrong公理系统:
关系模式R <U,F >来说有以下的推理规则:
Al自反律(Reflexivity):若Y≤X≤U,则X →Y为F所蕴含。
A2增广律(Augmentation):若X→Y为F所蕴含,且Z≤U,则XZ→YZ为F所蕴含。
A3传递律(Transitivity):若X→Y及Y→Z为F所蕴含,则X→Z为F所蕴含。
注意:由自反律所得到的函数依赖均是平凡的函数依赖,自反律的使用并不依赖于F。
定理 5l Armstrong推理规则是正确的
证明:
(1)自反律:若Y∈X∈U,则X →Y为F所蕴含
证: 设Y∈X∈U 对R <U,F> 的任一关系r中的任意两个元组t,s:
若t[X]=s[X],由于Y≤X,有t[y]=s[y],
所以X→Y成立,自反律得证
(2)增广律: 若X→Y为F所蕴含,且Z∈U,则XZ→YZ 为F所蕴含。
证:设X→Y为F所蕴含,且Z∈U。设R<U,F> 的任一关系r中任意的两个元组t,s;
若t[XZ]=s[XZ],则有t[X]=s[X]和t[Z]=s[Z];
由X→Y,于是有t[Y]=s[Y],所以t[YZ]=s[YZ];
所以XZ→YZ为F所蕴含,增广律得证。
(3) 传递律:若X→Y及Y→Z为F所蕴含,则X→Z为 F所蕴含。
证:设X→Y及Y→Z为F所蕴含。对R<U,F> 的任一关系 r中的任意两个元组 t,s。
若t[X]=s[X],由于X→Y,有 t[Y]=s[Y];再由Y→Z,有t[Z]=s[Z];
所以X→Z为F所蕴含,传递律得证。
二、导出规则
1根据A1,A2,A3这三条推理规则可以得到下面三条推理规则:
合并规则:由X→Y,X→Z,有X→YZ。(A2, A3)
伪传递规则:由X→Y,WY→Z,有XW→Z。(A2, A3)
分解规则:由X→Y及 Z≤Y,有X→Z。(A1, A3)
2根据合并规则和分解规则,可得引理51
引理5l X→A1 A2…Ak成立的充分必要条件是X→Ai成立(i=l,2,…,k)。
三、函数依赖闭包
定义5l2 在关系模式R<U,F>中为F所逻辑蕴含的函数依赖的全体叫作F的闭包,记为F+。
定义513 设F为属性集U上的一组函数依赖,X≤U, XF+ ={ A|X→A能由F 根据
Armstrong公理导出},XF+称为属性集X关于函数依赖集F 的闭包。
引理52 设F为属性集U上的一组函数依赖,X,Y≤U,X→Y能由F 根据Armstrong公理导
出的充分必要条件是Y≤XF+。
用途:将判定X→Y是否能由F根据Armstrong公理导出的问题, 就转化为求出XF+ ,判定
Y是否为XF+的子集的问题。
算法5l 求属性集X(X≤U)关于U上的函数依赖集F 的闭包XF+
输入:X,F
输出:XF+
步骤:
(1)令X(0)=X,i=0
(2)求B,这里B = { A |(ヨV)(ヨW)(V→W∈F∧V≤X(i)∧A∈W)};
(3)X(i+1)=B∪X(i)
(4)判断X(i+1)= X (i)吗
(5)若相等或X(i)=U , 则X(i)就是XF+ , 算法终止。
(6)若否,则 i=i+l,返回第(2)步。
对于算法5l, 令ai =|X(i)|,{ai }形成一个步长大于1的严格增的序列,序列的上
界是 | U |,因此该算法最多|U| - |X| 次循环就会终止。
[例1] 已知关系模式R<U,F>,其中U={A,B,C,D,E};F={AB→C,B→D,C→E,
EC→B,AC→B}。求(AB)F+ 。
解 设X(0)=AB;
(1)计算X(1): 逐一的扫描F集合中各个函数依赖,找左部为A,B或AB的函数依赖。
得到两个:AB→C,B→D,于是X(1)=AB∪CD=ABCD。
(2)因为X(0)≠ X(1) ,所以再找出左部为ABCD子集的那些函数依赖,又得到
AB→C,B→D, C→E,AC→B,于是X(2)=X(1)∪BCDE=ABCDE。
(3)因为X(2)=U,算法终止,所以(AB)F+ =ABCDE。
四、Armstrong公理系统的有效性与完备性
有效性:由F出发根据Armstrong公理推导出来的每一个函数依赖一定在F+中
/ Armstrong正确
完备性:F+中的每一个函数依赖,必定可以由F出发根据Armstrong公理推导出来
/ Armstrong公理够用,完全
完备性:所有不能用Armstrong公理推导出来f, 都不为真。
若 f 不能用Armstrong公理推导出来, f∈ F+
有效性与完备性的证明(略)
Armstrong公理的完备性及有效性说明:
“蕴含” == “导出” 等价的概念;
F+ ==由F出发借助Armstrong公理导出的函数依赖的集合五、函数依赖集等价
定义514 如果G+=F+,就说函数依赖集F覆盖G(F是G的覆盖,或G是F的覆盖)或F与G等价。
引理53 F+ = G+ 的充分必要条件是F≤G+ ,和G≤F+
证: 必要性显然,只证充分性。
(1)若F≤G+ ,则XF+≤XG++ 。
(2)任取X→Y∈F+ 则有 Y≤XF+≤XG++ 。
所以X→Y∈(G+)+= G+。即F+≤G+。
(3)同理可证G+≤F+ ,所以F+ = G+。
六、最小依赖集
定义515 如果函数依赖集F满足下列条件,则称F为一个极小函数依赖集。亦称为最小依
赖集或最小覆盖。
(1) F中任一函数依赖的右部仅含有一个属性。
(2) F中不存在这样的函数依赖X→A,使得F与F-{X→A}等价。
(3) F中不存在这样的函数依赖X→A,X有真子集Z使得F-{X→A}∪{Z→A}与F等价。
[例2] 对于5l节中的关系模式S<U,F>,其中:U={ SNO,SDEPT,MN,CNAME,G },
F={ SNO→SDEPT,SDEPT→MN,(SNO,CNAME)→G }
设F’={SNO→SDEPT,SNO→MN,SDEPT→MN,(SNO,CNAME)→G,(SNO,
SDEPT)→SDEPT}F是最小覆盖,而F ’不是。
因为:F ’-{SNO→MN}与F ’等价 F ’-{(SNO,SDEPT)→SDEPT}也与F ’等价
F ’-{(SNO,SDEPT)→SDEPT}∪{SNO→SDEPT}也与F ’等价
七、极小化过程
定理53 每一个函数依赖集F均等价于一个极小函数依赖集Fm。此Fm称为F的最小依赖集
证:构造性证明,依据定义分三步对F进行“极小化处理”,找出F的一个最小依赖集。
(1)逐一检查F中各函数依赖FDi:X→Y,
若Y=A1A2 …Ak,k > 2,则用 { X→Aj |j=1,2,…, k} 来取代X→Y。
引理51保证了F变换前后的等价性。
(2)逐一检查F中各函数依赖FDi:X→A,
令G=F-{X→A},若A≤XG+, 则从F中去掉此函数依赖。
由于F与G =F-{X→A}等价的充要条件是A≤XG+ 。因此F变换前后是等价的。
(3)逐一取出F中各函数依赖FDi:X→A,
设X=B1B2…Bm,逐一考查Bi (i=l,2,…,m),若A∈(X-Bi )F+ ,则以X-Bi 取
代X。由于F与F-{X→A}∪{Z→A}等价的充要条件是A≤ZF+ ,其中Z=X-Bi。因此F变换
前后是等价的。
由定义,最后剩下的F就一定是极小依赖集。因为对F的每一次“改造”都保证了改造
前后的两个函数依赖集等价,因此剩下的F与原来的F等价。 证毕
定理53的证明过程 也是求F极小依赖集的过程
[例3] F = {A→B,B→A,B→C,A→C,C→A}
Fm1、Fm2都是F的最小依赖集:
Fm1= {A→B,B→C,C→A}
Fm2= {A→B,B→A,A→C,C→A}
F的最小依赖集Fm不一定是唯一的。
它与对各函数依赖FDi 及X→A中X各属性的处置顺序有关。
极小化过程( 定理53的证明 )也是检验F是否为极小依赖集的一个算法。若改造后的
F与原来的F相同,说明F本身就是一个最小依赖集。
在R<U,F>中可以用与F等价的依赖集G来取代F
原因:两个关系模式R1 <U,F>,R2<U,G>,如果F与G等价,那么R1的关系一定是R2的
关系。反过来,R2的关系也一定是R1的关系。
关系模式的分解
1.模式分解的等价标准
规范化过程中将一个关系模式分解为若干个关系模式,应该保证分解后产生的模式和原来的模式等价。常用的等价标准有要求:
● 分解是具有无损连接性的;
● 分解是保持函数依赖的;
● 分解既要具有无损连接又要保持函数依赖两种。
将一个关系模式R(U,F)分解为若干个关系模式R1(U1,F1),R2(U2,F2)…Rn(Un,Fn)(其中U=U1 U2 … Un,R1为F在U1上的投影),这意味着相应的将存储在一个二维表r中的数据分散到若干个二维表r1,r2,…,rn中(其中r1是r在属性组U1上的投影)。我们当然希望这样的分解不丢失信息,也就是说,希望能够通过对关系r1,r2…rn的自然连接运算重新得到关系r中的所有信息。
事实上,将关系r投影为r1,r2,…,rn时并不会丢失信息,关键是对r1,r2,…,rn作自然连接可能会产生一些原来r中没有的元组,从而无法区别那些元组是r中原来有的,即数据库中应该存在的数据,在这个意义上丢失了信息。
例如:设关系模式S(SNO,CLASSNO,DEPTNO)在某一时刻的关系r如下表5-14
表5-14
SNO CLASSNO DEPTNO
S1 C1 D1
S2 C2 D2
S3 C2 D2
S4 C3 D1
若按分解方案一将关系模式S分解为:
S11(SNO,DEPTNO)和
S12(CLASSNO,DEPTNO),
则将r投影到S11和S12的属性上,得到关系r11如表5-15,r12如表5-16。
表5-15
SNO DEPTNO
S1 D1
S2 D2
S3 D2
S4 D1
表5-16
CLASSNO DEPTNO
C1 D1
C2 D2
C3 D1
对分解后的两个关系作自然连接r11r12,得到r'如表5-17如下:
表5-17
SNO CLASSNO DEPTNO
S1 C1 D1
S1 C3 D1
S2 C2 D2
S3 C2 D2
S4 C1 D1
S4 C3 D1
r'中的元组S1C3D1和S4C1D1都不是原来r中的元组。就是说,我们无法知道原来r中到底有哪些元组,这是我们不希望的。
定义1:设关系模式R(U,F)分解为关系模式R1(U1,F1),R2(U2,F2),…,Rn(Un,Fn),若对于R的任何一个可能的关系r,都有r=r1r2…rn,即r在R1,R2,…,Rn上的投影的自然连接等于r,则称关系模式R的这个分解是具有无损连接性的。
分解1不具有无损连接性,这是一个不好的分解方案。
在将一个关系模式分解为三个或者更多个关系模式的情况下,要判别分解是否具有无损连接性需要比较复杂的算法。然而若将一个关系模式分解为两个关系模式,则很容易判别分解是否具有无损连接性。
关系模式R(U,F)分解为关系模式R1(U1,F1),R2(U2,F2)是具有无损连接性的分解的充分必要条件是(U1∩U2→U1-U2)∈F+,或者(U2∩U1→U2-U1)∈F+。
让我们再考察第二种分解方案,将关系模式S分解为:
S21(SNO,CLASSNO),
S22(SNO,DEPTNO)
由于U1∩U2=SNO,U1-U2=CLASSNO,显然U1 U2→U1-U2,所以分解2具有无损连接性。然而分解2也不是一个很好的分解方案,将前面例子的关系r投影到S21,S22的属性上,得到关系r21如表5-18和r22如表5-19:
表5-18
SNO CLASSNO
S1 C1
S2 C2
S3 C2
S4 C3
表5-19
SNO DEPTNO
S1 D1
S2 D2
S3 D2
S4 D1
在这种分解中,假设学生S3从C2班转到C3班,于是我们需要在r21中将元组S3C2修改为S3C3,同时在r22中将元组S3D2修改为S3D1。如果这两个修改没有同时完成,数据库中就会存在不一致信息。这是因为分解得到的两个关系模式不是互相独立造成的。F中的函数依赖CLASSNO→DEPTNO既没有投影到关系模式R22中,而是跨在两个关系模式上。函数依赖是数据库中的完整性约束条件。在r中,若两个元组的X值相等,则Y值也必须相等。现在r的一个元组中的X值和Y值跨在两个不同的关系中,为维护数据库的一致性,在一个关系中修改X值时就需要相应的在另外一个关系中修改Y值,这当然是很麻烦而且是容易出错的,于是我们要求模式分解保持函数依赖这条等价标准。
定义2:设关系模式R(U,F)分解为关系模式R1(U1,F1),R2(U2,F2),…,Rn(Un,Fn),若F=(F1F2…Fn) ,即F所逻辑蕴含的函数依赖一定也由分解得到的各个关系式中的函数依赖所逻辑蕴含,则称关系模式R的这个分解是保持函数依赖的。
分解方案二不是保持函数依赖的,因为分解得到的关系模式中只有函数依赖SNO→CLASSNO,丢失了函数依赖CLASSNO→DEPTNO。不是一个好的分解。
分解方案三是保持函数依赖的。
告诉你做的具体方法:
1) R(A,B,C,D,E,F)
F={A→BC,CF→DE,DE→BF}
求出candidate key
candidate key: AC,AD,AF
2) R(A,B,C,D,E,F)
F={A→BCD,D→EF}
Decomposition: {R1=A B C D, R2=D E F}
Is it a loss_less joint decomposition
Since R1 Ç R2= D
R2 – R1 =E F
And D→E F
So it is a lossless-join decomposition
3) Suppose R(A, B, C, D,G),
F = {A→B, B→C, C→D, D→G,G→A },
R1(A,B), R2(B,C), R3(C,D),R4(D,G)
Is {R1, R2, R3,R4} dependency-preserving
Since AB Í R1, A→B is preserved
Since BC Í R2, B→C is preserved
Since CD Í R3, C→D is preserved
Since DG Í R3, D→G is preserved
W=G;
first iteration:
W = G È ((G Ç AB)+ Ç AB) = G;
W = G È ((G Ç BC)+ Ç BC) = G;
W = G È ((G Ç CD)+ Ç CD) =G;
W = G È ((G Ç DG)+ Ç DG)
=G È (G+ Ç DG )
=G È (ABCDG Ç DG)
=DG
second iteration:
W = DG È ((DG Ç AB)+ Ç AB) = DG;
W = DG È ((DG Ç BC)+ Ç BC) = DG;
W = DG È ((DG Ç CD)+ Ç CD)
= DG È (D+ Ç CD)
= DG È (ABCDG Ç CD)
=CDG
W = CDG È ((CDG Ç DG)+ ÇDG)
= CDG È (DG+ ÇDG)
=CDG
third iteration:
W = CDG È ((CDG Ç AB)+ ÇAB) = CDG
W = CDG È ((CDG Ç BC)+ ÇBC)
= CDG È (C+ Ç BC)
= CDG È (ABCDG Ç BC)
= BCDG
W = BCDG È ((BCDG Ç CD)+ ÇCD) = BCDG
third iteration:
W = BCDG È ((BCDG Ç AB)+ Ç AB)
= ABCDG;
以上就是关于数据库系统的内部结构体系简介全部的内容,包括:数据库系统的内部结构体系简介、sql数据库习题,规范化过程中的范式及模式分解问题、“数据库依赖的公理系统”和“模式的分解”这两部分怎么学习啊! 我都蒙了! 救命呀!等相关内容解答,如果想了解更多相关内容,可以关注我们,你们的支持是我们更新的动力!
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)