计算机科学2 0 0 2 V 0 1 2 9 N o - 8 ( 增刊)一种压缩X M L 数据仓库的存储策略AS t o r a g eS t r a t e g yf o rC o m p r e s s i n gX M LW a r e h o u s e王宏志李建中何震瀛 ( 哈尔滨工业大学计算机科学与工程系哈尔滨1 5 0 0 0 1 )A b s t r a c tT h i sp a p e rd e s i g n sas t o r a g es t r a t e g yf o rv e r yl a r g ec o m p r e s s i n gX M Lw a r e h o u s ew i t hl o t so fi d e n t i c a lX M Ld o c u m e n t ss u c ha sh i s t o r yd a t a ，d a t ac r a w l e df r o mW e b W ec l u s t e rt h e X M La tf i r s ta n dt h e ng e tt h ec e n t e ro fe a c hc l u s t e r ，a si st h ed o c u m e n tw i t ht h em i n i m a ls u md i s t a n tt Oo t h e rd o c u m e n t si nt h es a m ec l u s t e r T h u st h ec e n t e r ，t h eo t h e rd o c u m e n ti nt h es a m ec l u s t e r ，t h ee d i td i s t a n c eb e t w e e nc e n t e ra n do t h e rd o c u m e n tf o r m st h eP C G ，a si st h el o g i c a lm o d e lo fo u rs t o r a g e B a s e do nt h el o g i c a lm o d e l ，w ed e s i g nt h ep h y s i c a ls t o r a g es t r a t e g ya n dt h em e t h o d so fm a n a g e m e n tt h ed a t ai nt h em o d e l K e y w o r d sX M Lw a r e h o u s e ，S t o r a g e ，C o m p r e s s i n g ，C l u s t e r1 引言随着I n t e r n e t 的迅速发展，X M L 在计算机领域得到了广泛的应用，海量的X M L 文档存储中，一个导致数据冗余的原因是存在着大量的重复数据，而这种重复常常是不能简单地作为一般的冗余数据去掉的，因为相似经常是部分的，而数据来源的位置 信息和连接信息也是需要存在的内容。事实上在X M L 数据仓库中这种数据冗余往往更大。 本文的核心思想是根据编辑距离( e d i td i s t a n c e ) 1 的代价将X M L 文档进行聚类，对于每一个聚类中的文档寻找中心，也就是和其他文档的编辑距离的代价之和最小的文档，将这个中心文档 存储为一般X M L 文档的形式，把编辑距离的信息单独存储，由于编辑距离的信息是可以编码的而且可以使得同种的数据的存储更加接近，从而获得更加有效的压缩方法。为了描述的方便，在下文中用来表示编辑距离。2 数据模型和存储结构基于变化的存储模型需要将比较相近、也就是编辑距离比较小的X M L 文档放到一起存储，相近 的X M L 构成具有中心结点的文档聚类，每一个聚 类可以用有三种结点的图的形式来表示，定义为文档聚类图( P a g e sC l u s t e rG r a p h ，简称P C G ) 。文档聚 类图中包含三种结点：普通结点( C n o d e ) ：保存X M L 文档的基本信息，包括其版本信息，时间戳以及来源等；原始结点( O n o d e ) ：包含所有信息的中心 X M L 文档；变化结点( D n o d e ) ：包含信息的结点。 在每个P C G 中只有一个O n o d e ，在O n o d e 和 C n o d e 或者C n o d e 和C n o d e 之间有一个或多个D n o d e ，来表示它们之间的编辑距离。在每一个C n o d e 中包含一个X M L 文档的基本信息，这个序列表示的是具有相同结构和信息但是不同基本信息的文档。2 1 编辑距离的定义 我们存储中心结点和结点之间的，在处理用 户的查询时还需要根据这些信息重构X M L 文档，因而我们定义的编辑距离中的操作都是对子树的操 作，因为由子树的增删和移动操作来构造文档比使 用结点的操作执行起来更加容易。我们定义操作如下： a ) I n s e r t ( n ，k ，T ) ：将X M L 子树T 作为结点n 的第k 个儿子插入b ) D e l e t e ( n ，k ，T ) ：删除结点n 的第k 个儿子， X M L 树T c ) U p d a t e ( n ，v ，O V ) ：将结点n 的标签由o v 变化为vd ) M o v e ( n ，k ，m ，P ) ：m 的第P 个儿子树移动到 n 的第k 个儿子的位置上e ) S w a p ( n ，k ，m ，p ) ：交换m 的第P 个儿子树和 n 的第k 个儿子树f ) C o p y ( n ，k ，m ，p ) ：m 的第P 个儿子树复制到 n 的第k 个儿子的位置上* ) 本课题得到国家自然科学基金、国家9 7 3 计划基金( 编号：G 1 9 9 9 0 3 2 7 0 4 ) 、国家8 6 3 计划( 2 0 0 l A A 4 1 5 4 1 0 ) 和黑龙江省九五重大科技攻关资助。王志宏博士生。李建中博士导师。何曩瀛博士生。1 6 g ) N o p ( ) ：空操作我们将只含有其中一个操作的称为原子。对上面每一个操作都可以找到其逆操作，其中的所 有操作都可以用I n s e r t 和D e l e t e 操作以及它们的组合表示( 逆操作和组合的详细表示在文 2 中) ，我 们定义其他的操作是因为I n s e r t 操作和D e l e t e 操作中需要存储子树，这样存储的代价比较大，如果把 中有重复子树T 的I n s e r t 和D e l e t e 操作转化成 为其他操作则可以大大节省存储空间。操作执行代价存储代价总代价I n s e r t ( n ，k ，O ，+ 2 * i n t +口+ O 。十2 *】T )s i r ( T )i n t - - k s t r ( T ) p D e l e t e ( n ，k 0 。+ 2 * i n t +a + 0 。+ 2 *lT )s t r ( T )i n t + s t r ( T ) 1 3U p d a t e ( n 。v 。0 。+ i n t +口+ E o p + i n t1s t r l e n ( v ) + s t r l e n ( V ) + O V ) s t r l e n ( o v )s t r l e n ( o v ) p M o v e ( n ，k a ( 0 p + 4 * 1O p + 4 * i n t m P )i n t ) BS w a p ( n ，k ，C t + ( o 。+ 4 *】0 。+ 4 * i n t m ，p )i n t ) BC o p y ( n ，k ，m ，a + ( 0 p + 4 * lO p + 4 * i n t P )i n t ) p图1 操作的代价模型为了获得最优的存储和查询速度的综合性能， 对于每一个P C G ，我们要选择使得总的编辑距离短 的0 n o d e 并且寻找从O n o d e 构成C n o d e 的最优路径。而操作数最少的路径未必有存储量最小的，比 如对于两个X M L 文档根节点的所有不同儿子树进行插入和删除比较容易构成最短的路径，但是这样需要存储大量的树的信息，显然是不够经济的。因而我们需要定义衡量编辑距离“最优”的代价模型。对于一个操作，两个需要考虑的因素是其执行需要的时间和存储空间，我们定义执行时间参数为a ，存储空间参数为p ，它们的选择和系统的需求与环境有 关。我们定义的关于编辑距离基本操作的代价模型见图1 。我们用操作的代价定义编辑距离的测度I ，如果这个测度满足1 ) 非负2 ) 为零当且仅当两个比较的元素相同3 ) 三角不等式，则其可以按照通常研 究距离的方法进行研究，我们称为他是良定的。P C G 中O n o d e 到每个C n o d e 的代价的和称作P C G 的代 价。文 2 中描述了在这种操作定义和代价模型下计 算两个X M L 文档最优编辑距离的近似算法，得到的是近似最优的编辑距离。 2 2 存储方案的设计 对于每一个P C G ，O n o d e ，C n o d e 和D n o d e 是分 开存储的，O n o d e 作为P C G 的内核，作为独立的 X M L 文档进行存储。C n o d e 包含的是X M L 文档的基本信息，这些信息有固定的模式，可以作为普通的 关系进行存储，所有P C G 中文档的基本信息可以存 储在同一个关系中。如果有很大的O n o d e ，为了便于 查询，可以将其进行拆分，形成较小的O n o d e 和其 以些D n o d e 相连的C n o d e 。如果存在大规模C n o d e 的信息，可以用对于普通关系数据库的压缩方法对其进行压缩 1 0 。存储C n o d e 的关系称为i n o r b a s e 。D n o d e 中包含了绝大多数的信息，对于查询处理也是主要对象，所以需要对它进行有效的存储和 压缩。原始的D n o d e 可以写成X M L 的格式。 对于D n o d e 文档，我们采取将操作标示和操作 中的子树分离存储的方法，并且将操作进行编码以 减小存储量，对于操作的存储定义为o p r a b a s e 。子树中的标签和内容也分开存储，其中对予标签的存储定义为t a g b a s e ，内容根据其不同类型进行不同 的存储，对于不同类型的存储记做c o n t e x t b a s e 【统 一的存储也是可以的，这样不利于进一步的压缩，但是可以使得t a g b a s e 中不需要保存这个t a g 中的数据类型) 。 lo p e r a t i o nlp r e v i o u sln e x t s Jo p e r a t i o n p r e v i o u sIn e x t sjo p e r a t i o n | O p e r a t o rc o d elP a r a m e t e r IlP a r a m e t e r 2IlP a r a m e t e r 。图2o p r a , b a s e 的存储格式O p r a b a s e 其格式如图2 所示，其中o p e r a t i o n 表示一个操作，o p e r a t o rc o d e 是这个操作操作符的编码( 1 7 ) ，p a r a m e t e r l p a r a m e t e r 。是这个操作符 的参数，不同操作符参数的定义方式如下：I n s e r