基于数据树的多类型信息客体统一表示

静态信息客体，一般也称为“数据客体”。数据按照结构类型的不同，可分为结构化数据、半结构化数据、非结构化数据等。不论是结构化数据、半结构化数据，还是非结构化数据，均可以树形结构进行描述。笔者将通过树形结构对客体进行统一化描述，提出了基于数据树的静态信息客体统一表示模型。该方法相对于RDF（Resource Description Framework）来说更具直观性，描述客体不再仅仅限定于Web资源以及对资源说明（元数据、描述数据的数据）的处理，而是信息客体本身，有利于安全标记与信息客体的绑定，以及安全标记绑定方法的统一。

（一）客体数据树定义

1.客体数据树的定义和规则

（1）定义

客体数据树（data tree）是一个七元组，dt=（V，E，R，N，τ，σ，φ），其中：

①V={v1，v2，…，vn}，数据树节点集合。

②E={（u，v）|u，v∈V}，节点间边集合。

③R={≺，→，⇒，||}，数据树节点间的关系。其中，“≺”表示节点之间的蕴含关系，即u≺v；u，v∈V，则表示u在内容结构上蕴含v。“→”表示节点之间的推导关系，如 u→v；u，v∈V，表示已知 u 可推导出 v。 u1，u2，…，uk→v表示已知u1，u2，…，uk可推导出v。“⇒ ”表示数据节点间的序列关系，如u⇒v；u，v∈V，表示u和v前后并列关系。“||”表示数据节点间的并列关系，该并列关系不具有前后关系。

④N表示节点的命名空间，包括各类型数据节点的命名。

⑤τ：τ（v）表示节点v的类型，v∈V。节点类型包括数据单元、元素、属性等。

⑥σ：σ（v）表示节点v的内容或者值，内容和值可为空，v∈V。

⑦φ：φ={φr，φp，φc，φs，φl}。 其中，φr为 dt的根函数，φp为节点祖先关系函数，φc为节点子孙关系函数，φs为节点兄弟关系函数，φl为叶节点函数。

图4-3为具有蕴含关系的数据树dt≺，根节点为φr（dt≺）=R；图4-4表示的是具有推导关系的数据树dt→，根节点为φr（dt→）=R。dt≺为一个正常的树形结构，dt→为一个倒立的树形结构。本书对数据树的定义，相对于《大数据时代信息安全刑法保护的立法完善研究》《大数据时代信息安全保障算法和法律的融合》两部著作来说，更侧重于信息客体内部数据之间的关系，而不仅仅具有树自身的关系，这在上述两部著作中是被忽略的。

图4-3　具有蕴含关系的数据树dt≺

图4-4　具有推导关系的数据树dt→

（2）规则

①若 dti≻dtj，dtj≻dtk，则有 dti≻dtk。 该规则反映了数据树蕴含关系的传递性，如果dtj是dti的子树，dtk是dtj的子树，则dtk是dti的子树。

②在数据树 dt=（V，E，R，N，τ，σ，φ）中，若 v1，v2，v3→v，v4，v3→v，则v4与v1，v2是等价的。该规则表示在一个具有推导关系的数据树中，若v1，v2，v3能够推导出 v，且在数据树中，又∃v4，v4、v3能够推导出 v，则 v1，v2必定与v4是等价的，或者存在依赖关系。依此可以进行类推。

2.数据子树

dt'是 dt的子树，dt'⊂dt，dt=（V，E，R，N，τ，σ，φ），dt'=（V'，E'，R'，N'，τ'，σ'，φ'），则有：

①V'⊆V，数据节点具有包含关系。

②E'⊆E，数据子树dt'的边是dt中的边，或者是dt中具有推导关系的节点之间隐含的边。

③R'⊆R，即数据子树dt'的蕴含、推导、序列及并列关系被包含在数据树dt的关系R中。

④τ'（v）=τ（v），σ'（v）=σ（v），v∈V'∧v∈V，即子树 dt'中的节点类型和内容与数据树dt中节点的内容或值是一致的。

数据子树的目的是用于更细粒度地刻画客体内数据间的关系，便于对客体进行裂解，以实施多级别用户对同一客体的不同访问。

3.数据树图（Data Tree Graph）

（1）定义

数据树图DTG={{dt}，λ}，表示数据树与数据树间关系的集合。其中：

①{dt}是数据树集合，它要么是同一客体数据子树的集合；要么是具有某一类特征数据树的集合。

②λ为数据树间关系。λ（dt1，dt2）表示dt1和dt2的关系，关系包括等价关系、蕴含关系、并列关系、序列关系。其中，等价关系指的是相似数据树。

数据树图DTG用于代表某一客体的数据森林，或某一类数据树形成的森林，如数据库某一个表中所有数据。森林中的数据树通过关系λ进行关联。

（2）规则

规则：dti和 dtj具有推导关系，若 dti||dtj，vi∈V（dti）∧vi≠φc（dti），vj∈V（dtj）∧vj≠φr（dtj），vi=vj，且 vj，φp（vj）构成的数据子树是一个线性数据树，则必有φc（vi）→φp（vj）。

该规则说明：在具有推导关系的dti和dtj中，若dti中的节点vi不是其叶子节点，dtj中的节点vj不是其根节点，vi=vj，且vj与其父节点构成的子树为线性数据树，则可衍生出已知vi的“孩子”节点，就能推导出vj的父节点。最简单的实例是具有两个节点的线性数据树间的推导。

4.数据树的删除与合并操作

针对数据树的操作，笔者重点讨论下其删除与合并，以用于多级网络信息客体视图的生成。

（1）数据树节点的删除操作

①节点v为dt叶子节点。若dt为具有推导关系的数据树，则在删除v的同时，也要删除其兄弟节点φs（v），以保证推导关系的合理性、正确性；若dt为其他关系的数据树，则直接删除v。

②节点v为dt的根节点。若dt为具有序列关系的数据树，则删除节点v，v的孩子节点φc（v）成为dt新的根节点；若dt为其他关系的数据树，则删除数据树dt。

③节点v为dt的中间节点。若dt为具有蕴含关系的数据树，则将以v为根节点的数据子树删除，以保证数据的完整性；若dt为具有推导关系的数据树，则将以v为根的数据子树，以及以v兄弟节点φ（sv）为根节点的子树删除；若dt为具有序列或并列关系的数据树，则将节点v的父节点φ（pv）指向其孩子节点φ（cv）。

（2）数据树的合并操作

①若合并的dti，dtj属于同一客体，则依据数据树图中各个子树间的关系进行合并，若dti的一个叶子节点为dtj的根节点，则合并两个节点。

（二）数据树的性质

为了使得数据树更加规范化、合理化，下面，笔者将对数据树的性质进行讨论：

（1）若 dti≻dtj，dtj≻dtk，则有 dti≻dtk。 该性质反映了数据树蕴含关系的传递性，数据树dtj是dti的子树，dtk是dtj的子树，则dtk是dti的子树。

（2）若 dti≈dtj，dtj≈dtk，则有 dti≈dtk。 该性质表示，如果数据树 dti和dt j是等价的，dtj和dtk是等价的，则dti和dtk一定是等价的。该规则反映了等价关系的传递性。如图4-5所示。

图4-5　规则的实例

（3）在一个数据树 dt=（V，E，R，N，τ，σ，φ）中，若 v1，v2，v3→v，v4，v3→v，则v4与v1，v2是等价的。该规则表示，在一个具有推导关系的数据树中，若v1，v2，v3能够推导出 v，且在数据树中，由 v4，v3能够推导出 v，则 v1，v2必定与v4是等价的，或者存在依赖关系。依此可以进行类推。

（4）数据树 dti和 dtj具有推导关系，若 dti||dt j，vi∈V（dti）∧vi≠φc（dti），vj∈V（dtj）∧vj≠φr（dtj），vi=vj，且 vj，φp（vj）构成的数据子树是一个线性数据树，则必有φc（vi）→φp（vi）。该规则说明的是，dti和dtj是具有推导关系的数据树，且两个数据树为并列关系，若dti中的节点vi不是其叶子节点，dtj中的节点vj不是其根节点，vi=vj，且vj与其父节点构成的子树为线性数据树，则可衍生出已知vi的孩子节点，就能推导出vj的父节点。

当然，在第（4）个性质中，最简单的事例为两个节点的线性数据树间的推导，如 vi→vj，vj→vk⇒vi→vk。 因此，dti和 dtj为含有两个节点的具有推导关系的线性数据树，分别包含节点 vi，vj，vk和 vl，vj=φp（vi），vl=φp（vk），若vj=vk，则 vi→vl。

（三）多类型信息客体数据树转换方法

下面，笔者将针对不同类型的信息客体，对其数据树的构建方法与原则分别进行讨论。

1.结构化数据

由于结构化数据具有一定的结构，可采用二维表结构来逻辑表达，通常存储在关系数据库中。而在数据库中，数据都是采用表的方式进行组织的，每个表都是一个典型的深度为2的数据树。如图4-8所示。

数据库表到数据树的转换原则：

（1）的名称转换为数据树的根节点，其类型为元素，值为空。

（2）表的各个项或者属性按照顺序成为根节点的孩子节点，其类型为属性。

（3）若表中存在两个条件：①函数依赖关系F（α）=β，α和β为表中的项，即 α 和 β 存在映射关系；②多值依赖关系 α1，…，αj→α，β1，…，βk→β，…，→γ，即联合推导关系。则将其相应的子树转换为具有推导关系的数据子树，并保留其祖先树。(www.xing528.com)

通过上述转换原则，将各个表转换为不同的数据树或者数据森林，从而形成由表自身数据树、数据子树以及与该表相关的其他表的数据树组成的数据树图。

为了能够更加准确地表述数据库，下面，笔者引入两个概念：一是数据束（data cluster）。数据束DC={DTG}，即数据树图的集合，表示的是同一数据库表、关系表、不同属性值的数据树的集合。二是数据库（database）。数据库DB={DC}，即数据库是数据束的集合，表示的是由所有表组成的数据库。

2.半结构化数据

半结构化数据是结构化的数据，但是结构变化较大，由于结构变化大，所以不能用简单的表与其对应。针对半结构数据，通常的存储方式为XML，将不同类别的信息保存在XML的不同节点中，其优点是比较灵活、扩展性好，信息扩展只需更改对应的DTD或者XSD即可。而XML本身就是一个逻辑的树形结构，它由元素、属性等组成。

XML文档到数据树的转换原则如下：

第一，将XML文档中的标签映射到数据树中的节点上，节点名称与XML文档标签保持一致，但如果存在相同的名称，则按照XML文档中元素的序列关系，在其名称后添加“-1”。

第二，XML文档根元素转换为数据树的根节点，其类型为元素。

第三，XML文档中其他的元素、属性按照XML文档中层次关系转换为数据树根节点的后代节点。

第四，XML文档中存在独立的或者同类的数据单元，可将数据树分割为不同的数据子树，也称为XML片段。

第五，若XML文档数据树存在节点依赖关系，则将相应的元素或属性集转换为具有推导关系的子树。

3.非结构化数据

非结构化数据是相对于结构化数据而言的，是不便用数据库表逻辑表达的数据，如文本、图片、视频等。针对非结构化数据，笔者将从几个典型的数据载体进行阐述。

（1）文本

文本数据典型的代表为office系列，如Word。由于这些文本本身可用XML的方式进行存储，因此文本文件可遵循半结构化数据转换原则进行数据树的转换。但是，文本中可能存在图片、表格等非结构化数据，因此为了方便表示，笔者将把文本中的图像、表格作为整体进行处理，可作为某一元素的子元素或者属性。

对于一个doc文档而言，其目录结构中的节点转换为数据树中的元素节点，每一个元素节点包含属性、子元素和内容节点；文档中的图片和表格可以作为节点来表示。不同的是，form节点下还包括了属性节点。

（2）视频

视频是由一帧一帧组成的，某段连续的帧构成了一个视频画面。

视频到数据树的转换原则如下：

第一，视频中的帧映射到数据树的节点上，帧名为节点名，节点类型为元素。

第二，连续的帧构成数据树的子树，连续帧之间是一种序列关系。

第三，如果存在若干画面可以推导出下一个画面，则可以画面作为节点，形成具有推导关系的数据子树。此时，节点名为画面连续帧的名，类型为数据单元。

（3）图像

图像包括像素图像和矢量图像，像素图像是由众多像素组成的，而矢量图像则是带有方位位置的像素图像。

图像数据节点（Picture Data Node）：将可组成一个可识别图像单元的像素集合，称之为图像节点。一个图像是由若干节点组成的。

由于一个图像是由若干图像节点组成的，所以可根据节点之间在图像中的相对位置，构建成一个数据树。图像到数据树的转换原则如下：

第一，图像节点映射为数据树节点，图像节点名为数据树节点名，节点类型为元素。

第二，将图像进行分割以后，依据图像的特点，选取合理的图像节点作为数据树的根节点，其他节点则按照节点间的相对位置，映射为数据树的其他节点。

第三，图像节点间关系映射为数据树节点之间的关系。图像节点之间的关系通常为并列对等关系，因此尽管数据树呈现的是层次化的节点关系，但是数据树节点关系仍应与图像节点间关系保持一致。

（四）数据树操作

针对客体关系，下面，笔者对数据树的操作进行讨论。数据树的操作主要包括节点删除、合并、拆分等。

1.数据树节点删除（v-delete）

数据树dt节点的删除原则包括以下三方面：

（1）节点v为dt叶子节点

①若dt为具有蕴含关系或具有序列关系的数据树，则直接将节点v删除；

②若dt为具有推导关系的数据树，则在删除节点v的同时，也将其兄弟节点φs（v）删除，以保证数据树推导关系的合理性、正确性。

（2）节点v为dt根节点

①若dt为具有蕴含关系或具有推导关系的数据树，则删除数据树dt。

②若dt为具有序列关系的数据树，则删除节点v，v的孩子节点φc（v）成为dt新的根节点。

（3）节点v为dt的中间节点

①若dt为具有蕴含关系的数据树，则将以v为根节点的数据子树删除，以保证数据的完整性。

②若dt为具有序列关系的数据树，则将节点v的父节点φp（v）指向其孩子节点φ（cv）。

③若dt为具有推导关系的数据树，则将以v为根的数据子树，以及以v兄弟节点φ（sv）为根节点的子树删除。

2.数据树的合并（dt-combination）

数据树的合并分为两种情况：一是在数据图中，同一客体所有数据子树的合并；二是不同客体之间数据树的合并。

数据树合并遵循的原则包括以下两方面：

（1）若合并的数据树dti和dtj均属于同一客体

第一，遵循数据图中各个子树之间的关系进行合并。

第二，若数据树dti的一个叶子节点为数据树dtj的根节点，则合并两个节点。

（2）若合并的数据树dti和dtj分属于两个客体

首先，将数据树进行二叉树转换，有两个转换方法：一是数据树根节点v的第一个孩子v1，作为根节点v的左子树，其他孩子节点v2…vk作为v1的右子树；二是分别以v1，v2…，vk为根节点进行递归操作。

3.数据树的拆分（dt-splitting）

数据树的拆分是相对于合并而言的，其遵循原则主要包括以下两方面：

第一，若是一个客体的数据树拆分，则有：根节点可单独划分开，但其孩子节点被拆分开时，必须保留根节点；数据树子树的拆分也要遵循上述原则。

第二，若是多融合客体数据树的拆分，则有：多融合客体数据树的拆分要遵循右子树分割原则，即多客体合并时右子树插入原则；在数据树中，若某一数据子树的根节点与该根节点的父节点相同，则从数据树中分离此数据子树。