（计算机软件与理论专业论文）xml递归模式的访问控制.pdf

摘要 摘要 x m l 正逐渐成为i n t e r n e t 上数据表示和数据交换的新标准，网络上存 在大量的x m l 格式的可操作数据和其他商业信息。鉴于这些商业信息的 敏感特性，增加了保护x m l 文档的重要性，迫切需要一种对x m l 文档普 通灵活的访问控制机制，支持有效安全的查询访问，不向非授权用户泄漏 敏感信息。在这种情况下，本文对国内外关于x m l 访问控制的研究现状 进行了综合分析比较，从一个全新的角度对基于递归模式的x m l 的访问 控制问题进行了研究。 首先，本文研究了基于安全视图的访问控制中的查询重写技术。虽然 它能处理很多普通的基于安全视图的查询，但是也存在不足之处，即它不 能对基于递归安全视图的查询进行有效重写。因此，本文提出了x m l 递 归安全视图的查询重写算法，并进行了实例分析和实验验证，结果显示它 能对基于递归安全视图的查询进行有效且正确的重写。 其次，本文研究了安全视图获取算法，通过对已有算法的分析，发现 它不能对遇到的递归部分进行处理。因此，本文提出了展开递归节点算法， 并进行了实例分析和实验验证。结果显示在视图获取的过程中遇到递归节 点调用此算法能避免递归安全视图的产生。 最后，通过实验结果验证了本文所提出的两种处理递归模式的方法的 可行性和有效性，并比较了两种方法的效率。 关键词访问控制；递归安全视图；视图获取；查询重写；递归模式 燕山大学工学硕士学位论文 a b s t r a c t x m li sr a p i d l ye m e r g i n ga st h en e ws t a n d a r df o rd a t ar e p r e s e n t a t i o na n d e x c h a n g eo nt h ei n t e r n e t i ti si n c r e a s i n g l yc o m m o nt of i n do p e r a t i o n a ld a t a a n do t h e rb u s i n e s si n f o r m a t i o ni nx m lf o r m a t i nl i g h to ft h es e n s i t i v en a t u r e o fs u c hb u s i n e s si n f o r m a t i o n , t h i sa l s o r a i s e st h ei m p o r t a n ti s s u eo fs e c u r i n g x m lc o n t e n t ，a n dh i g h l i g h t st h en e e df o rag e n e r i c ，f l e x i b l ea c c e s sc o n t r o l m e c h a n i s mf o rx m ld o c u m e n t st h a ts u p p o r t se f f i c i e n ta n ds e c u r eq u e r ya c c e s s ， w i t h o u tr e v e a l i n gs e n s i t i v ei n f o r m a t i o nt ou n a u t h o r i z e du s e r s o nt h e s e c o n d i t i o n s ，t h i sp a p e ra n a l y z e sa n dc o m p a r e st h e i n t e r n a la n de x t e r n a l r e s e a r c h e so fx m l sa c c e s sc o n t r o lm e c h a n i s m ，a n dr e s e a r c h e st h ep r o b l e mo f a c c e s sc o n t r o lo nx m lr e c u r s i v es c h e m af r o man e wp o i n to f v i e w f i r s t l y , t h i sp a p e rr e s e a r c h e st h eq u e r yr e w r i t i n ga p p r o a c ho fa c c e s s c o n t r o lo ns e c u r i t yv i e w s a l t h o u g hi tc a nd e a lw i t hm a n yc o m m o nq u e r i e so n s e c u r i t yv i e w s ，t h e r ea r em a n yl i m i t a t i o n s ，f o re x a m p l e s ，i tc a n n o tr e w r i t et h e q u e r yo ns e c u r i t yv i e w s s o ，t h i sp a p e ri n t r o d u c e sq u e r yr e w r t i n ga l g o r i t h mo n x m lr e c u r s i v es e c u r i t yv i e w s ，a n a l y z e sa ne x a m p l eo fr e w r t i n ga n dt a k e sa n e x p e r i m e n t o u re x p e r i m e n t a lr e s u l t ss h o wt h a tt h ea l g o r i t h mc a ne f f e c t i v e l y r e w r i t e st h eq u e r yo nr e c u r s i v ev i e w s s e c o n d l y , t h i sp a p e rr e s e a r c h e st h es e c u r i t y v i e wd e r i v a t i o na l g o r i t h m w h e nw ea n a l y z e dt h ed e r i v a t i o na l g o r i t h m ，w ef i n dt h a tt h ea l g o r i t h mc a n n o t d e a lw i t ht h er e c u r s i v ep a r t s o ，t h i sp a p e ri n t r o d u c e su n f o l d i n gr e c u r s i v en o d e s a l g o r i t h m ，a n a l ) 7 z e s a ne x a m p l ea n dt a k e sa ne x p e r i m e n tt oc h e c kt h e c o r r e c t i o na n df e a s i b i l i t yo ft h ea l g o r i t h m o u re x p e r i m e n t a lr e s u l t ss h o wt h a t s u c ha nu n f o l d i n gy i e l d san o n - r e c u r s i v e ( d a g ) v i e wd t dt h a tt h ed o c u m e n ti s g u a r a n t e e dt oc o n f o r mt ow h e nw eu s et h eu n f o l d i n ga l g o r i t h mw i t ht h e r e c u r s i v en o d e si nt h ev i e wd e r i v a t i o np r o c e s s a b s t r a c t f i n a l l y , t h ee m p i r i c a ls t u d yv e r i f y i n gt h ef e a s i b i l i t ya n de f f e c t i v e n e s so f t w oa p p r o a c h e sw h i c hc a nd e a lw i t hr e c u r s i v es c h e m ai nt h i sp a p e r k e y w o r d sa c c e s sc o n t r o l ；r e c u r s i v es e c u r i t yv i e w ；v i e wd e r i v a t i o n ；q u e r y r e w r i t i n g ；r e c t t r s i v es c h e m a 1 i i 燕山大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文l 递归模式的访问控 制，是本人在导师指导下，在燕山大学攻读硕士学位期间独立进行研究工 作所取得的成果。据本人所知，论文中除已注明部分外不包含他人已发表 或撰写过的研究成果。对本文的研究工作做出重要贡献的个人和集体，均 已在文中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签字 套莆 日期：w 彩年尹月巧日 燕山大学硕士学位论文使用授权书 ”表示安全标识之间的密级程度关系，则有t s s c u 。强制访问控 制又称为基于格的访问控制。用l 表示安全标识，主体s 的安全标识可表 燕山大学工学硕士学位论文 示为l ( s ) ，客体o 的安全标识可表示为l ( o ) 。 在强制访问控制模型中有3 个基本性质。 ( 1 ) 简单读规贝q ( r e a d d o w n )当满足l ( s ) l ( o ) ，主体s 可读客体o 。 ( 2 ) 自由写规贝l j ( w r i t e u p ) 当满足l ( o ) l ( s ) ，主体s 可写客体o 。 若把读客体看成是信息从客体流向用户，把写客体看成是信息从用户 流向客体，那么简单读规则和自由写规则反映了信息流动的方向是从安全 性要求低处向安全性高处的方向流动。由于安全性要求低的主体可以写安 全性要求比他高的客体，这可能会导致重写己存在的客体，破坏信息的完 整性，所以为了完整性要求规定了限制写规则。 ( 3 ) 限制写规则当满足l ( s ) = l ( o ) ，主体s 可以写对象o 。 在强制访问控制中，主体和客体的安全标识是由系统安全管理员配置 的。除了系统安全管理员外，用户无权改动。因此，强制访问控制模式的 安全性管理是集中管理的。这样防止了用户滥用权限。 强制访问控制确保了在即使有特洛伊木马的情况下，信息也仅将按照 由安全标识组成的格的方向流动( 即保证信息从低层次的安全标识处流向 高层次的安全标识处) ，从而可抵制特洛伊木马的攻击。 m a c 的不足主要表现在两个方面：应用的领域比较窄，使用不灵活， 一般只用于军方等具有明显的等级观念的行业或领域，在经济领域中， m a c 的应用并不是很多；整性方面控制不够，它重点强调信息的向高安 全级的方向流动，对高安全级信息的完整性保护强调不够。 2 3 3基于角色的访问控制 随着计算机信息系统在非军用领域得到更为广泛的应用和网络的普及 化发展，原有的d a c 和m a c 技术己经不能满足现代信息系统安全的需求。 在这种情况下出现了基于角色的访问控制技术。 基于角色的访问控制【2 6 l 的基本思想是通过将权限授予角色而不是直 接授予主体，主体通过角色分派来得到客体操作权限从而实现授权。由于 角色在系统中具有相对于主体的稳定性，并具有更为直观的理解，从而大 大减少系统安全管理员的工作复杂性和工作量。 1 4 第2 章基础知识概述 如图2 1 所示，s a n d h u 于1 9 9 6 年提出了一个通用r b a c 模型【2 7 1 。 角色层次r i d l 一? 图2 - 1 基于角色的访问控制模型r b a c 9 6 f i g 2 - 1r o l e - b a s e da c c e s sc o n t r o lm o d e lr b a c 9 6 这个模型基于三个实体集，用户集( u ) ，角色集( r ) ，权限集( p ) 。直观 地说，一个用户是一个人或一个软件代理：一个角色是组织中一项工作或 者一个职位，通过角色与授权语义相关，并通过授予用户以角色实现权限 的授予；一项权限是对系统中一个或多个敏感对象进行某种方式访问的一 个许可。 在图2 一l 中，用户指派( u a ：u s e ra s s i g n m e n t ) 和权限分派( p a ：p e r m i s s i o n a s s i g n m e n t ) 关系都是多对多的关系。一个用户可以指派多个角色而一个角 色也可以被分派多个用户。同样，一个角色可以有多项权限，而同样的权 限可以被分派给多个角色。图中还存在一个偏序关系角色层次( r h ： r o l eh i e r a r c h y ) ，也记作，这里表示角色x 继承了分派给角色y 的所有权 限。角色层次中的继承是可传递的并且可以多继承。 图2 1 中展现了会话( s ：s e s s i o n ) 集合。每个会话将一个用户和多个可 能的角色联系起来。直观地说，一个用户建立一个会话，期间可以激活多 个角色，当然这些角色是已经分派给用户的。图中双箭头表示一个会话可 以同时激活多个角色。用户的有效权限取决于会话中激活的角色所有权限 燕山大学工学硕士学位论文 的并集。每个会话与单个用户关联，图中以单箭头显示。这个联系在会话 的整个生命周期一般是恒定的。一个用户可能同时有多个会话。 最后，图2 l 中展示了约束集。约束可以应用在先前定义的许多集合 上。一个常见的例子是角色互斥，某个用户拥有一个角色，那么他就不能 再拥有另外一个角色了。 综上所述，形式化定义访问控制模型r b a c 9 6 ，基于角色的访问控制 模型由如下子集组成。 ( 1 ) u ，r ，p 和s ，分别来代表用户集合，角色集合，权限集合和会话 集合： ( 2 ) p a c p x r ，代表一个多对多的权限分配给角色的关系； ( 3 ) u a c u x r ，代表一个多对多的用户分配给角色的关系； ( 4 ) r h c r x r ，代表一个角色层次的偏序关系； ( 5 ) u s e r ：s - - - u ，代表一个函数映射，表示每个会话s i 都与一个用户关 联，这个关联一般在会话生命周期中都不会更改； ( 6 ) r o l e s ：s 一2 2 ，代表一个函数映射，表示每个会话都与一个角色子 集关联：r o l e s ( s i ) r l ( 3 r 全r ) ( u s e r ( s i ) ，r 9 u a 】) ； ( 7 ) c o n s t r a i n t s ，代表约束集合。 由于登录到系统中的用户可以根据需要动态激活自己拥有的角色，避 免用户无意中危害系统安全。由于实现了用户与访问权限的逻辑分离， r b a c 极大地方便了权限管理。例如，如果一个用户的职位发生变化，只 要将用户当前的角色去掉，加入代表新职务或新任务的角色即可。另外， 基于角色的访问控制还可以很好的描述角色层次关系，实现最小特权原则 和职责分离原则，因此r b a c 使访问控制变得相对简单，而且应用方便。 另外，r b a c 还能保证信息的完整性。 2 4 基于安全视图的访问控制模型 本文的研究基础是基于安全视图的访问控制模型，我们首先给出访问 控制模型，如图2 2 所示。 1 6 第2 章基础知识概述 查询p l 查询仇 查询“ 图2 - 2 基于安全视图的访问控制模型 f i g 2 - 2a c c sc o n 打o l lm o d e lo ns e c u r i t yv i e w 下面简要介绍模型中的安全规范、安全视图、查询重写和查询优化。 2 4 1安全规范 安全规范s 是文档d t dd 结合安全注释的扩展。具体地，s 被定义 为( d ，a c c ) ，a c e 是一个部分映射，对每个产生式a - a 和每个a 中的元素 b ，a c c ( a ，b ) 定义如下： a c c ( a ，b ) ：= yl 【q 】ln( 2 1 ) 式中，【q 】是x p a t h 查询集c 中的限定符。y 、【q 】、n 的值表示d 中a 元 素的孩子节点b 是可访问的、有条件访问和不可访问的。如果a c c ( a ，b ) 没 有明确的定义，那么b 继承a 的访问性。如果a c c ( a ，b ) 被明确定义，则可 以覆盖a 的访问性。d 的根节点被默认注释为y 。 给定如图2 3 所示h o s p i t a l 文档，d 中每个元素类型a 为一个节点， 称为a 节点，每条边描述父子关系。具体地，对每个产生式a 斗口，有 一条边从节点a 到口中b 节点。如果a = b + ，那么边用一个一”标记， 表示一个a 元素中可以直接嵌套零个或多个b 元素。如果a 是d i s j u n c t i o n ， 边用虚线表示，与c o n c a t e n a t i o n 相区别。在上下文中，可以将d t d 称为d ， 燕山大学工学硕士学位论文 将a 元素类型称为a 节点。 一个d t d 图可以是一个有向无环图( d a g ) ，也可以是有环图。当d t d 是递归的，即a 直接或间接依据自己定义，则d t d 图为有环图。 山+ a = p t 壬1 e l i n i e a l t r l a l 专p a t i e n t l n f o s t a t n n f o 之上 驴 t e s tb i l l m e d i c a t i o n p h o n e 图2 - 3 文档d t d 示例 f i g 2 - 3e x a m p l ed o c u m e n td t d 例2 1 ：对于图2 3 所示h o s p i t a l 文档，对用户组n u r s e 施加的访问控 制策略描述如下。 h o s p i t a l 专d e p t + 产产生式+ a c c ( h o s p i t a l , d e p t ) = r p a t i e n t w a r d n o = $ w a r d n o 】严q l + d e p t _ e l i n i c a l t r i a l ，p a t i e n t l n f o ，s t a m n f o a c c ( d e p t ，c l i n i c a l t r i a l ) = n c l i n i c a l t r i a l p m i e m l n f o a c c ( c l i n i c a l t r i a l p a t i e n t l n f o ) = y t r e a t m e n tot r i a l + r e g u l a r a g e ( t r e a t m e n t , t r i a l ) = n a c e ( t r e a t m e m ，r e g u l a r ) = n 第2 章基础知识概述 t r i a l - - - hb i l l a c c ( 仃i a l ，b i l l ) = y r e g u l a r 斗b i l l ，m e d i c a t i o n a c cr r e g u l a r , b i l l ) = y a c e ( r e g u l a r , m e d i c a t i o n ) = y 这个规范描述如图2 - 4 所示。 h o s p i t a l q ，i 。 小q l = 【p a t i e n f f w a t d n o = $ w a r d n o d e p t 老：，_，：ii叠 c l i n i c a l t r i a l - 一p a t i e m l n f o s t a f l l n f o i 一t e s t ! b i l lm e d i c a t i o n 图2 - 4 为n u r s e 制定的安全规范 f i g 2 - 4s e c u r i t ys p e c i f i c a t i o nf o rn u r s e 被虚线框住的节点代表“n ”注释，即对用户组n u r s e 不可访问。因 此，n u r s e 仅能访问一个由限定符q l 限制的指定w a r d 下的d e p t 的信息。此 外，n u r s e 没有被授权知道哪个p a t i e n t 参加了c l i n i c a l t r i a l 以及c l i n i c a l t r i a l 的t y p e 和d u r a t i o n ，也不知道p a t i e n t 的t r e a t m e n t 是t r i a l 还是r e g u l a r ，但 是可以知道r e g u l a r 的b i l l 和m e d i c a t i o n 以及t r i a l 的b i l l 。$ w a r d n o 为常量 参数，也就是当一个具体的值如6 替代$ w a r d n o ，则n u r s e 的访问限制 在w a r d 6 。 1 9 燕山大学工学硕士学位论文 a c c ( d e p t ，p a t i e n t i n f 0 ) 没有详细定义，意味着d e p t 的孩子p a t i e n t l n f o 节 点继承d e p t 的访问性y 。类似地，s t a f f i n f o 节点和他的子孙继承d e p t 节点 的访问性。而a c e ( d e p t ，c l i n i c a l t r i a l ) 被定义为n ，覆盖了父节点d e p t 的访问 性y ，表示d e p t 的孩子节点c l i n i c a l t r i a l 不可访问。类似地，a c c ( c l i n i c a l t r i a l p a t i e n t l n f o ) 使p a t i e n t l n f o 节点覆盖了c l i n i c a l t r i a l 节点的访问性； a c c ( t r e a t m e n t ，t r i a l ) 和a c c ( t r e a t m e n t ，r e g u l a r ) 使t r i a l 节点和r e g u l a r 节点覆盖了 t r e a t m e n t 节点的访问性；a c e ( t r i a l ，b i l l ) 使b i l l 节点覆盖了t r i a l 节点的访问性： a c c ( r e g u l a r , b i l l ) 和a c c ( r e g u l a r , m e d i c a t i o n ) 使b i l l 节点和m e d i c a t i o n 节点覆盖 了r e g u l a r 节点的访问性。 如果父节点和它所有孩子有相同的访问性，则产生式的注释可以省略。 例如s t a f f 节点和它的子孙节点将继承s t a f f i n f o 节点的访问性。 对一个d 的x m l 实例t ，访问规范s = ( d ，a c c ) 可以很容易地使用一 个简单的g u i 工具在d 的d t d 图上定义。而且，s 明确地定义了t 中文 档节点的访问性。注意d t d 必须是明确地x m l 标准。既然t 是d 的实 例，这意味着t 的每个b 元素类型v 有唯一一个父亲a 元素和唯一一个产 生式“解析”a 子树。因此，可以用a c c ( a ，b ) 结合a 的产生式定义v 的访问 性a c c ( v ) 。如果v 基于s 是可访问的，则它满足以下两个条件中的一个。 ( 1 ) a c c ( v ) 是y 或a c c ( v ) 是【q 】并在v 点为t r u e ，并且，对所有v 的祖 先v ，a c e ( v ) ： q 】，限定符 q 。】在v 为u q 1 e ； ( 2 ) a c e ( v ) 没有明确定义，但是v 的父亲基于s 是可访问的。 这里要求v 是可访问的，那么v 关联的所有的祖先的限定符都必须为 t r u e 。参考图2 4 ，n u r s e 访问一个d e p a r t m e n td 的信息，d e p t 关联的限定符 q 1 在d 必须为t r u e ，防止n u r s e 非授权访问不同的d e p a r t m e n t 的信息。 定理2 1 ：对任何规范s = ( d ，a c e ) 和任何d 的x m l 实例t ，每个t 中 节点基于s 的访问性是被唯一定义的，也就是要么可访问，要么不可访问。 可以得出如下结论。首先，本文的访问规范支持继承和覆盖。如果一 个节点没有注释但是他的双亲是可访问的或不可访问的，那么这个节点是 可访问的或不可访问的，也就是，节点从双亲那里继承访问性；另一方面， 一个明确的注释可以覆盖它双亲的访问性。第二，基于内容的访问权限通 第2 章基础知识概述 过x p a t h 限定符实现。第三，一个文档中元素的访问性是上下文敏感的， 由根节点到文档中这些元素的路径决定。例如一个p a t i e n t 的b i l l 信息是可 访问的仅当一个d e p t 的p a t i e n t 满足限定符 q d 。因此一个文档中相同类型 的元素可能有不同的访问性。与文献 5 】的访问控制模型比较，本文的安全 规范模型也允许细粒度访问控制，但是更加灵活并且容易制定和修改，因 为安全限制是在d t d 上定义，而不是x l v i l 文档。 2 4 2 安全视图 安全视图隐藏或删除了用户不可访问信息，只包含可访问信息。它定 义了从文档d t d 到视图d t dd v 的映射，视图d t d 是从给定的访问规范 中获取的。安全视图的定义如下。 定义2 1 ：安全视图。假设s = ( d ，a n n ) 是访问规范，安全视图表示为：v ： s d v ，定义安全视图v = ( d v o ) 。 其中，d v 是视图d t d ，对用户可见。o 是从d v 到文档d t d 的映射， 定义了用于从文档t 中提取可访问数据的x p a t h 查询注释。 安全视图定义了从文档d t dd 到视图d t dd v 的一个映射，并通过 给定的访问规范自动导出。令s = ( d ，a c c ) 为一个访问规范，则从s 到视图 d t dd v 的安全视图定义( 或简称为安全视图) 可以标记为v ：s d v ，定义 为v = ( d v ，砷。其中，o 定义) ( p a t h 查询注释，用来从d 的实例t 中提取 可访问数据。 具体地，对于每一个d v 中的产生式a - - - a 和每一个。中的元素b ， 耐a b ) 为一个x p a t h 查询，定义了在d 的文档实例上给定一个a 元素， o ( a b ) 通过从文档中提取数据产生安全视图中a 的子元素b 。 一个特例是使用一元参数a ( r 0 - - r ，其中r v 是d v 的根元素，r 是d 的 根元素，也就是说。映射了t 的根元素到它安全视图的根元素。如果d v 是递归的则安全视图也是递归的。 例2 2 ：根据例2 1 中访问规范导出的一个安全视图v 如图2 5 所示。 视图删除了关于c l i n i c a l t r i a l 的信息，引入了标记d u m m y i 和d u m m y 2 ，用 来隐藏r e g u l a r 和t r i a l ，同时保持了可访问节点t r e a t m e n t 的语义。 2 1 燕山大学工学硕士学位论文 p ， l ：= d u m m y l h o s p i t a l p l i d e p t 皿卜中、奎 p a n e n t l n f o s t a f f l n f o 上f p 吐i e n t 触 d u m m y 2 w ”d n on a n l c p h o n e 八 b i l l m e d i c a t i o n 图2 - 5n u r s e 查询的安全视图 f i g 2 - 5s e c u r i t yv i e wf o rn u l e 对于v = ( d v ，o ) ，o ( 通过视图导出算法计算得出) 表示如下。 产生式：h o s p i t a l _ d e p t o ( h o s p i t a l ，d e p t ) = d e p t + p a t i e n t w a r d n o = $ w a r d n o 】p l + 产生式：d e p t p a t i e n t l n f o 畎d e p t ，p a t i e n t l n f o ) 2p 2 p 2 = ( c l i n i e a l t r i a l u e ) p a t i e n t l n f o 产生式：t r e a t m e n t 斗d u m m y l - 4 - d u m m y 2 o ( t r e a t m e n t ，d u m m y l ) = t r i a l严p 3 + ， o ( t r e a t m e n t ，d u m m y 2 ) 2r e g u l a r严p d + 产生式：a a对所有其他产生式 仃( a ，b ) = b严对所有b a + 严例如，仃( d u m m y l ，b i l l ) = b i l l + 代表空路径。视图d t d 提供给n u r s e ，而仃是不可见的。因此，n u l - s e 不能看见文档d t d ，也不知道d u m m y 代表什么。仃用于在查询重写时提 第2 章基础知识概述 取可访问节点。 2 4 3 查询重写 在基于安全视图的访问控制中，只有安全视图对用户是可见的，所以 用户只能建立基于安全视图的查询，这样就可以防止用户访问敏感信息。 但是，安全视图是虚拟的，不是实际存在的，它的节点上不含有数据信息。 我们可以把视图进行物化，使虚拟的安全视图同数据库中的数据联系起来。 但是，由于不同的用户可能具有不同的访问权限，所以访问策略也就不同。 在多种访问策略存在的情况下，因为x m l 文档中的数据经常变化，这就 使得物化每一个安全视图要付出很大代价。当这种物化视图用来处理安全 问题时，安全模型必须保证在物化视图的同时生成的查询返回给用户的结 果必须准确无误。这时，安全问题的实现交得很困难。所以，有必要提出 查询重写来把基于安全视图的查询转化为基于原始文档的等价查询，这样 就避免了视图物化和保存。只要x m l 文档的结构不发生变化，安全视图 就不会改变，节点数据信息的变化不会影响查询结果，也不会带来额外的 代价。 给定一个基于视图d t d 的查询p ，查询重写算法在d v 上执行查询p 。 对于从d v 中根节点出发通过p 到达的每一个节点a ，通过使用安全视图 的x p a t h 注释o ，重写每一个从i - 到达a 的路径。因为。是从视图节点到 文档节点的映射，所以能产生基于原始文档的与p 等价的查询p t 。 对于一个给定的基于安全视图的查询p ，查询重写算法自动将其转化 为一个基于原文档的查询p 。，对任何t ，p 与p t 产生同样的查询结果，即 p t ( t ) = p ( t v ) ，这样就消除了视图物化及其所带来的问题。 2 4 4 查询优化 重写算法将一个安全视图上的查询转化为等价的原始文档上的查询， 但重写后的查询不一定是有效的。因此考虑到利用d t d 的结构特性f 2 8 】对 x p a t h 查询进行优化伫9 3 们。对于给定的x p a t h 查询p ，希望找到一个实例t 上的查询p 。与p 等价，即p ( t ) = p o ( t ) ，并r p 。比p 更有效，即p o ( t ) 比p ( t ) 燕山大学工学硕士学位论文 花费更少的时间、空间代价。这不仅适应于本文访问控制模型中，利用d ) 优化重写后的查询，同样对于其他的x p a t h 查询赋值【3 l i 也意义重大。 事实上，人们希望在所有与p 等价的查询中找到一个代价最小的查询 p 。，但找不到这样的查询。x p a t h 优化涉及到包含( c o n t a i n m e n t ) t 3 2 州1 测试， 也就是对两个查询p ，和p ：，检查p 。是否包含在p ：中。最近的研究表明，即 使对一个简单的非递归d t d ，一小部分) o a t h 如“u ”而不包括广、“”和 限定符，包含测试也将是n p 完全问题。对于一些复杂的情况更不能确定 是否包含。 2 5 本章小结 本章主要对x m l 安全所涉及的基本知识进行了简要的介绍。 首先，简要介绍了x m l 安全现状及现有的5 种x m l 安全标准。 其次，介绍了访问控制的含义及自主访问控制、强制访问控制和基于 角色的访问控制三种典型的访问控制模型。 最后，介绍了基于安全视图的访问控制模型中的相关知识。 通过对访问控制和x m l 安全知识的了解，为后续研究奠定了基础。 第3 章e x t e n d r e w r i t e 查询重写算法 第3 章e x t e n d r e w r i t e 查询重写算法 3 1引言 上一章主要介绍了与所研究课题相关的基础知识，本章分析了查询重 写的国内外研究现状，阐述了查询重写中的基本概念和问题定义，详细介 绍了基于x m l 安全递归视图的查询重写算法，并通过一个具体的实例对 所提出的算法的执行过程进行分析和说明。 3 2 查询重写的研究现状 随着x m l 应用领域的不断扩展，如何实现x m l 查询重写也相应成为 查询重写领域的一个新的研究热点。由于x m l 数据多为半结构化数据， 其数据模型与传统数据库的数据模型不同，因此传统数据库的有关查询重 写技术不能直接应用到x m l 查询中。在文献 3 5 ，3 6 中提出的两种不同的 查询重写算法，他们都能比较有效的处理非递归安全视图。 在关系模型中，利用视图进行查询应答已经被广泛的研究 3 7 3 9 。文献 【3 7 ，3 8 】中提出了两个基于关系数据的基础算法b u k e t 和i n v e s e 规则算 法。根据两个模型之间的语义不匹配关系和两种查询语言的不同表达能力， 把关系模型上的结果扩展到嵌套数据模型上是非常重要的。 对于半结构化数据模型和图形数据模型的研究也有一些尝试。文献 4 0 1 中提出的方法支持嵌套的查询表达式和结果重建( r e c o n s t r u c t i o n ) ，但是，在 x p a t h 中它不支持类似于“，广或“ 的定位符。文献 4 1 d o 讨论了正则表达式 的查询重写问题。但是，它不能处理结果重建。 在关系数据库中对于查询重写问题的研究已经很广泛。由于x m l 的复 杂特性，它的查询重写问题比关系数据库面临更多的挑战。在文献 4 2 ，4 3 1 中的研究表明x m l 查询包含问题是x m l 查询重写中一个很重要的步骤，但 燕山大学工学硕士学位论文 它是一个c o - n p 问题，特别是当x p a t h 查询只支持有限的几个定位符，包括 ，+ ，【】 的时候。 至今，提出了许多用于处理基于x m l 视图的查询重写的方法。在文献 3 5 中研究了服务器端的x p a t h 查询重写。如果可以把索引认为是x m l 物化 视图的特殊情况，它能处理基于x p a t h 视图的x p a t h 查询重写。它将在多项 式时间内产生可靠的但是不完全的基于x p a t h , ，+ ， 】) 的计划( p l a n ) 。它扩 展了文献 4 1 】中提出的查询包含测试，提出了一个不完全的但是有效的 x p a t h 查询重写算法。但是，它没有考虑多种视图存在的情况。在文献 3 6 】 中研究了客户端的查询重写问题，它提出了一种在多项式时间内处理x p a t h 查询重写的方法，前提条件是查询重写计划可靠而且正确，并且，a t h 的定 位符是有限的。 文献【4 4 】中研究了数据集成中基于视图的查询重写。提出了m p t r e e 和 p p l a t t i c e 来管理多种x m l 视图，并提出了相关算法来有效地产生查询重写 计划。 由于不同的频繁的查询模式，可能会在客户端贮存多个) 蹦l 视图。 在文献 4 5 1 中研究了基于上百个视图的x p a t h 视图的选择问题。虽然可以 通过使用u n i o n 操作符合并基于每个视图的查询重写结果来扩展文献 3 6 1 中提出的方法来支持多种视图，但是整个处理过程的性能将会受很大影响。 每一个视图必须分别独立用来产生候选计划。另外，每一个视图必须花费 时间来对重写计划进行确认。 文献 1 1 】中研究了基于x m l 安全视图的查询。提出了将基于安全视图 的x p a t h 查询重写为基于原始文档的等价查询的r e w r i t e s 算法，此算法避 免了视图的物化和保存，提高了运行的效率。但是，r e w r i t e s 算法不能处理 递归视图。 文献【1 2 】中研究了x m l 访问控制一种动态的查询重写算法。提出 了将用户的基于安全视图的x p a t h 查询重写为一个等价的x q u e r y 查询表 达式的动态查询重写算法。这个表达式可以在原始数据上运行。而且保证 用户只看到视图中的信息并且不能推断出非授权访问的数据。但是，它不 能处理含有递归的模式，而且只能是模式存在的情况下才能应用。 第3 章e x t e n d r e w r i t e 查询重写算法 3 3 基本概念和问题定义 3 3 1d t d 简介 d t d 【4 6 4 7 l 是指一类和x m l 文档联系起来的、专门定义符合本d t d 的 x m l 文档应有的数据结构的文档。它为一个x m l 文档或者文档集合创建 一套规则。它本身不是独立的技术规范，而是属于规范的一部分，帆 文档中的文档类型声明既可以是标记约束，也可以是带有标记约束的外部 文档。这两种约束的总和就是d t d 。它规定了x m l 文档的构建方式。x m l 文档里一定要有什么，一定没有什么，或是什么可出现可不出现，甚至什 么元素该出现多少次，这一切都可以在d t d 里体现出来。因此，可以把 一个d t d 看成是x m l 文档的结构模板，d t d 是一种保证x m l 文档格式 正确的有效方法，可以比较x m l 文档和d t d 文件来看文档是否符合规范， 元素和标签使用是否正确。一个d t d 文档包含：元素的定义规则，元素 问关系的定义规则，元素可使用的属性，可使用的实体或符号规则。 d t d 可以是一个完全独立的文件，也可以在x v i l 文件中直接设定。 也就是说x m l 文档有两种和d t d 产生关联的方法：一是直接在文档里列 出d t d 的内容，二是在文档里指出所引用d t d 的路径，具体d t d 的内 容在该文档里。显然，第二种方法更具有一般性和通用性，而且维护起来 更加容易，也不会显著地加大x m l 文档的长度。 在x m l 文档里面有一条用于与d t d 建立关联的声明d o c t y p e 。当 v i l 解析器读到这条声明的时候，如果这个解析器要验证文档合法性的话 ( 有些解析器默认情况下不会检查文档是否符合d t d 定义的结构) ，它就会 获得并读取d ) ，根据它里面的定义来检验文档。 为了不失一般性，本文用( e l e ，r g ，r ) 表示一个d t d 。其中e l e 是元素类 型( e l e m e mt y p e s ) 的有限集合：r 是i s l e 中与其他元素不同的类型，称为根 元素；r g 定义元素类型，对任何e l e 中的a ，r g ( a ) 正则表达式为： 口：= s t r i el 蜀，或l 且+ + 风i 置( 3 - 1 ) 其中，s 廿表示p c d a t a ，e 表示空集，b 。是e l e 中的一种类型( 称作a 燕山大学工学硕士学位论文 的子元素类型) ，“+ ”、：”和“ 各自表示d i s j u n c t i o n 、c o n c a t e n a t i o n 和k l e e n e s t a r 。称a r g ( a ) 为a 的产生式( p r o d u c t i o n ) 。所有的d t d 都能用这个形 式表示。 定义3 1 ：一个x m l 文档树t ，如果满足以下四个条件，则它符合一 个d t dd 。四个条件为： ( 1 ) 有唯一独一无二的节点，根节点，在t 中用r 标记； ( 2 ) t 中每个节点要么标记为一个e l e 类型a ( 称为a 元素) ，要么标记 为s 仃( 称为文本节点) ； ( 3 ) 每个a 元素有一个孩子序列，孩子序列是有序的元素或文本节点， 用r g ( a ) 定义的正则表达式表示； ( 4 ) 每个文本节点为字符串值( p c d a t a ) ，是树的叶子节点。 如果t 符合d ，