层次数据论文

层次数据论文（共8篇）

层次数据论文 篇1

1 绪论

在数据库应用系统开发中,经常要对层次结构的数据对象进行管理。例如,产品的类别和分类、组织机构、行政辖区和人事管理等等。现阶段,主流的数据库管理系统都是基于关系模型的关系数据库管理系统。如何对这些具有层次结构的数据进行建表和管理,是一个必须要解决的实际问题。通过比较,分析了两种建表方式的优缺点;结合组织机构管理的实例,利用CTE进行递归查询,给出一种通用的解决方案。

2 层次模型和关系模型的比较

数据库管理系统总是基于一定的数据模型的,目前,数据库领域常用的逻辑数据模型有:层次模型、网状模型、关系模型、面向对象模型和对象关系模型。层次模型和网状模型统称为格式化模型,该模型的数据库管理系统在20世纪70年代至80年代初非常流行,在数据库管理系统中占据主导地位,现在已经逐渐被关系模型的数据库管理系统所取代[1]。20世纪80年代以来,面向对象的方法和技术在计算机领域的应用和发展,也促使了面向对象数据模型的研究和发展,但是,现阶段主流的数据库管理系统都是基于关系模型。

2.1 层次模型

层次模型是数据库管理系统中最早出现的数据模型,层次数据库管理系统采用层次模型作为数据的组织方式。层次模型用树形结构来表示各类实体以及实体之间的联系,现实世界中许多实体之间的联系本身就是一种自然的层次关系,如行政机构、家族关系等。图1为层次模型的示例图,可以看出层次模型像一棵倒立的树,结点的双亲是唯一的。

层次模型的特点是,任何一个给定的记录值只有按其路径查看时,才能显示出它的全部意义,没有一个子女记录值能够脱离双亲记录值而独立存在。

层次模型的优点是:1)数据结构比较简单;2)层次数据库的查询效率高;3)层次数据模型提供了良好的数据完整性支持;

缺点主要是:1)查询子女结点必须通过双亲结点;2)由于结构严密,数据的存取操作是在真正的物理层次上进行操作,随着应用环境的扩大,程序开发的代码非常复杂,不容易掌握[2]。

但是它对于具有一对多的层次联系的组织机构的描述非常自然、直观、容易理解。

2.2 关系模型

关系模型是当今最为重要的一种数据模型,关系数据库系统采用关系模型作为数据的组织方式。从用户角度看,关系模型由一组关系组成,每个关系的数据结构就是一张二维表,图2为关系模型的数据结构。与层次模型不同,关系模型是建立在严格的数学概念的基础上的,它的理论基础就是关系代数。在关系模型中,实体和实体之间的联系都用二维表来表示。

关系模型的优点:1)关系模型与格式化模型不同,它有严格的数学理论基础;2)关系模型概念单一,无论是实体还是实体之间的联系都用关系来表示;对数据的检索和更新结果也是关系,所以数据结构简单、清晰,用户易懂易用。3)数据的存取路径对用户透明,简化了程序员的工作和数据库开发工作。所以,关系数据模型自诞生以来,发展迅速,现在主流的数据库系统都是基于关系模型的。

3 关系模型中对于层次结构数据的处理

关系数据库管理系统因为其自身的优点,成了现在主流的数据库系统,但是,如何用关系数据库来管理具有层次结构的数据是一个现实的问题。例如企业的组织机构,就是一个典型的层次结构数据。图3为XX集团的组织机构图。关系数据库系统中,对于这种组织机构数据如何建立二维表进行数据管理,有两种不同的解决方法,一种是分级建表,另一种是集中建立。

对于上图中的组织机构,使用分级建表的方式,就是每一级部门建立一个表。如果把集团总公司作为第一级部分,那么服装公司、贸易公司、食品公司就是二级部分,下面的生产部、采购部等就是三级部门,依次类推,最下面的广州办事处等就是5级部门,分别建立下面5个表,表结构分别如表1—表5所示。

在上面这5个表中,除了第一个表没有外键,其他四个表都是上一个表的子表,建立了主外键引用关系。而且后面四个表的结构相似。这种分级建表的方式,优点是表结构清晰,直接显示了部门所属的级别,对于数据的增、删、改、查都比较方便,如果要修改某个级别的部门,直接修改该级别的部门表,如果要查询部门信息以及上级或者下级部门的信息,只需要根据外键做相应的连接查询。但是这种分级建表的方式,最大的缺点是可扩展性差,在建表之前,必须确定该组织机构一共有多少个级别,以此来确定应该建几个表,所以,如果将来部门的分级增加了,系统将不能适应这个变化,因而系统的可扩展性很差。在实际应用中,往往对组织机构的分级会越来越细,为了能够适应这种变化,应该考虑使用另外一种方式建表,即集中式建表,对于组织机构只建立一个表,在这个表里反映出部门之间的上下级隶属关系。表结构如表6所示。

部门信息表,通过定义自参照外键,实现部门之间的隶属关系。对于上面的一级部门,由于不存在上级部门了,所以它的上级部门编号就是空值(NULL)。这种建表方式的最大优点是可扩展性好,将来不论组织机构的级别是增加还是减少,都不需要增加新的表,也不需要修改表的结构。缺点是要想查询某个部门的上级或者下级部门信息以及确定部门所属的级别,往往要通过递归查询,在Micros SQL Server 2005以前版本的数据库管理系统中,一般要通过创建临时表、游标或者视图来实现这种递归查询,而且查询的语句比较复杂,编程相对比较困难[3];在SQL Server 2005版中由于采用了公用表表达式(common table expression,CTE)技术,使得实现递归查询的查询语句变得非常简单。

4 公用表表达式(CTE)

微软公司在SQL Server 2005中引入了公用表表达式技术。CTE可以认为是在单个SELECT、INSERT、UPDATE、DELETE或CREATE VIEW语句的执行范围内定义的临时结果集。CTE与派生表类似,具体表现在不存储为对象,并且只在查询期间有效。与派生表的不同之处在于,CTE可以自引用,也可以在同一查询中引用多次[4]。

在CTE中可以包括对自身的引用,从而创建递归CTE。递归CTE是一个重复执行初始CTE以返回数据子集直到获取完整结果集的公用表表达式。当某个查询引用递归CTE时,它即被称为递归查询,递归查询通常用于返回分层数据。递归CTE可以极大地简化在SELECT、INSERT、UPDATE、DELETE或CREATE VIEW语句中运行递归查询所需的代码[5]。

4.1 CTE的结构

CTE由表示CTE的表达式名称、可选列列表和定义CTE的查询组成。定义CTE后,可以在SELECT、INSERT、UPDATE或DELETE语句中对其进行引用,就像引用表或视图一样。CTE也可用于CREATE VIEW语句,作为定义SELECT语句的一部分。

CTE的基本语法结构如下:

只有在查询定义CTE_query_definition中为所有结果列都提供了不同的名称时,列名称列表[(column_name[,...n])]才是可选的。

调用CTE的语句为:SELECTFROM expression_name;

4.2 CTE的递归查询

Transact-SQL中的递归CTE的结构与其他编程语言中的递归程序相似。其他语言中的递归程序可能返回标量值,但递归CTE可以返回多行结果集。

递归CTE由下列三个元素组成:

1)程序的调用

递归CTE的第一个调用包括一个或多个由UNION ALL、UNION、EXCEPT或INTERSECT运算符联接的CTE_query_definitions。由于这些查询定义形成了CTE结构的基准结果集,所以它们被称为“定位点成员”。

CTE_query_definitions被视为定位点成员,除非它们引用了CTE本身,所有定位点成员查询定义必须放置在第一个递归成员定义之前,而且必须使用UNION ALL运算符联接最后一个定位点成员和第一个递归成员。

2)程序的递归调用

递归调用包括一个或多个由引用CTE本身的UNION ALL运算符联接的CTE_query_definitions,这些查询定义被称为“递归成员”。

3)终止检查

终止检查是隐式的;当上一个调用中未返回行时,递归将停止。

递归CTE的基本语法结构如下:

下面使用CTE,演示对上面组织机构管理的具体实现。

5 具体案例

对于上图3.所示的组织机构,使用集中建表的方式,根据表6.所示的数据字典,使用如下的代码创建部门信息表(tbl_Depart-ment Info)。

其中上级部门编号(Pra DID)是外键,参照了本表的部门编号(Dept ID)列,部门名称(Dept Name)和上级部门编号(Par DID)满足唯一键约束,即假设不同部门的下级部门名称可以相同,但是同一个部门的下级部门名称是不能相同的。对于部门编号(Dept ID),在实际的应用系统开发中,可以使用自定义函数产生部门编号,也可以使用uniqueidentifier数据类型定义该列,使用NEWID函数产生相应的编号;因此,这些编号一般只作为主键的一个唯一标识,不需要实际的意义,一般也不会显示在应用程序的界面上,记录可以通过应用系统进行录入,录入时可以在应用程序的界面上选择相应的上一级部门。为了能够按一定的顺序显示部门信息,因而设置了显示顺序(Disp Order)列来控制部门信息显示的先后,例如,可以通过设置字母A-Z来标识同一上级部门的下级部门的显示顺序。

向表里插入图3.中的所有部门的信息,为了便于演示,直接指定了部门编号。插入数据的部分Insert语句如下所示。

插入数据后,表里的记录如图4所示。

对于上表中的记录,很难直观的观察到部门之间的隶属关系,也不能确定部门所处的级别。所以,在应用系统开发时,希望能分级显示部门信息,而且直观显示每个部门所处的级别,这样才能根据用户的要求显示相关部门的信息。为了能直观显示部门之间的隶属关系,以及每个部门所处的级别,要对部门信息表(tbl_Department Info)进行递归查询,使用CTE,创建一个可以直观显示组织机构层次关系的视图(vi_Dept)。定义视图的代码如下。

在上面创建视图的代码里,首先,创建了一个公用表表达式d_CTE,它有Department ID、Parent Department ID、部门名称、上级部门名称、部门级别、显示顺序、备注这七列构成,第一个Select语句定义了定位点成员,把tbl_Department Info表中上级部门编号为空值(NULL)作为递归执行的结束,同时指定该部门的级别为0。第二个Select语句定义了递归成员,它把tbl_Department Info表和公用表表达式d_CTE进行内连接,连接的条件是tbl_Department Info表里的上级部门编号等于d_CTE的部门编号,每执行一次连接就把部门级别在上个部门级别的基础上加1,并且把每个部门的上级部门编号和名称跟上上一级部门编号和名称分别用“/”联接起来,显示顺序也进行了联接。连接后的结果集又和tbl_Department Info表进行连接,如此循环下去,直到没有满足连接条件的结果集了,递归将停止,通过UNION ALL运算,把满足连接条件的结果集和定位点的结果集联接起来,由于UNION ALL运算要求列的数据结构要完全一样,包括数据类型、长度与精确,因此在代码中使用convert(varchar(max),Par DID)将上级部门编号等列转换成varchar(max)数据类型。最后,根据d_CTE创建了视图vi_Dept。

执行查询“select*from vi_Dept order by显示顺序”,结果集内容如图5所示。

对于上面通过视图vi_Dept查询到的结果,可以直观看出各部门之间的层次关系,也能确定部门所在的级别,上面图5的记录内容在应用程序界面中可以用Tree View等控件显示出来。通过查询视图vi_Dept,可以直接把某一级别的所有部门列出,也可以查询某一个部门以及它的所有下级部门的信息。例如“select*from vi_Dept where部门编号='3J003'or上级部门编号like'%3J003%'order by显示顺序”,查询的结果集如图6所示。所以,根据视图vi_Dept,可以很容易得到用户应用程序界面中需要显示的各种信息。

6 总结

虽然现在主流的数据库管理系统都是基于关系模型的,但是经常要处理有层次结构的数据对象。通过建立一张具有自参照完整性的表,利用Microsoft SQL Server 2005中的公用表表达式的递归查询功能,生成一个能够呈现对象之间的层次关系的视图,可以满足应用系统开发中的各种查询需要;不但简化了编程工作,提高项目开发效率;而且提高了系统的可扩展性,改善程序的性能。案例中具体实现的SQL脚本,对于层次结构数据的管理具有通用性,可以为同类型的应用提供参考。

摘要：在数据库应用系统开发中,经常要对层次结构数据进行管理,实现的方法有多种,比较分析了每种方法的优缺点。利用Mi-crosoft SQL Server 2005中的新功能公用表表达式(CTE,Common Table Expression)进行递归查询,结合组织机构管理的具体实例,给出了使用CTE进行递归查询的组织机构管理的通用实现方法。

关键词：关系数据库,层次数据,递归查询,公用表表达式,组织机构管理

参考文献

[1]王珊,萨师煊.数据库系统概论[M].4版.北京:高等教育出版社,2006:18-30.

[2]Jeffrey D Ullman,Jennifer Widom.A First Course in Database System(Third Edition)[M].北京:机械工业出版社,2008:17-24.

[3]刘进.浅谈T-SQL语言之递归查询[J].沈阳师范大学学报:自然科学版,2007,25(2):217-219.

[4]MSDN使用公用表表达式[EB/OL].http://msdn.microsoft.com/zh-cn/library/ms190766.aspx.

[5]MSDN使用公用表表达式的递归查询[EB/OL].http://msdn.microsoft.com/zh-cn/library/ms186243.aspx.

层次数据论文 篇2

1 数据溯源相关理论

1. 1 数据溯源的概念与定义

最初，数据溯源的“溯源”通常是与某件艺术品或文学相联系，在艺术品的鉴赏中，数据溯源能够帮助确定某件艺术作品的真实性，可以确定一个作品的历史重要性，也可以确定艺术作品持有者的合法性。数据溯源是一个重载的学术术语，最近一项研究总结了数据溯源在学术上的不同定义，其中部分学者将数据溯源理解为数据的起源; 与此同时，另外一些学者的观点是将“数据溯源”视为记录实验过程的工作流，注释和笔记的元数据; 在国外的研究中，工作流中数据的产生过程是研究数据溯源需要的主要实体; 明华，张勇等学者认为，数据溯源强调的是一种追本溯源的技术，根据追踪路径重现数据的历史状态和演变过程，实现数据历史档案的追溯。

1. 2 数据溯源的分类方法

通过调研发现，主流的数据溯源分类方法中，消极型溯源法与积极型数据溯源法相对应，增量法与时间标志法相对应。消极型数据溯源法在对溯源信息有需求时去追踪数据溯源信息。通过对查询或转换过程进行分析，反向推导得到数据溯源信息。积极型数据溯源法在事先得到并携带数据溯源信息，即用标记来记录数据的出处，并让标注传播到结果数据中，通过查看数据的标注即可得到数据的数据溯源信息。增量法通过增量定义数据溯源信息; 时间序列法以时间标志定义两个版本之间的增量信息。在增量法中，需事先确定一个参照版本( 通常会是第一个版本或者最后一个版本) ，随后在一系列版本中将版本与版本前后的一系列增量记录下来，从而形成记录在案的数据溯源信息。理想状态下，需保证每一个变化都记录在案，因此每一个增量都要让它的单位与粒度尽可能小。在时间序列法中，一个强大的储存器将所有的版本记录在案，并且在这个过程中，在任意不同的时间点，时间标志会用来标志数据因素的存在。

1. 3 数据溯源的应用意义

对于数据溯源的应用意义，不同学者理解各异。Simmhan 和Plale 等认为，数据溯源的应用意义分为4 点:

( 1) 根据数据溯源信息确定数据质量; ( 2) 认清错误来源; ( 3) 允许派生的自动重新更新; ( 4) 在商业领域，深入到数据仓储中探寻数据的来源，跟踪知识的创建过程，为达到监管的目的，提供一个审计跟踪。在此基础上，数据溯源的应用意义进一步明晰化，主要体现在以下方面: ( 1) 数据质量。数据溯源可以根据数据来源和转换过程来评估数据质量和数据可靠性，它可以为数据的来源提供有力证据。( 2) 审计跟踪。数据溯源可以用来跟踪审计的数据，监测是否有错误数据生成。( 3) 复制副本。详细的数据溯源信息允许数据来源重复，帮助维持数据的时效性是数据复制的秘诀。( 4) 属性。建立数据的版权和所有权，使其能够被引用，在数据错误的情况下能够确定责任。( 5) 情报性。用于数据发现的元数据查询，可以根据数据溯源信息来解释数据。

2 数据溯源典型模型分析

当前，对于数据溯源的相关研究处于初级阶段，通过全面梳理和对比3 种典型的数据溯源模型，以此为分层次的.数据溯源安全模型的构建提供一定的理论基础。

2. 1 数据溯源本体模型

数据溯源本体模型是比较基础的数据溯源模型，该模型虽然只是一个简单的构架，但是它几乎涵盖了数据溯源信息的所有语义内容，其重要性不可忽视。在数据溯源本体模型中，数据溯源语义信息被概念化，包含了7 个相互关联的元素，这7 个元素分别是溯源记录、操作者、操作时间、操作位置、操作内容、操作原因、操作工具。在数据溯源本体模型中，每一个数据溯源信息被定义为一个七元组，这个七元组的函数形式为: 数据溯源信息= { ( 溯源记录、操作者、操作时间、操作位置、操作内容、操作原因、操作工具) } 。“溯源记录”表示在数据衍生过程中，影响数据的某个事件; “操作时间”表示这个事件发生的时间; “操作位置”是指事件发生的具体位置; “操作内容”是指导致这个事件的动作; “操作者”是这个事件发生过程中涉及到的代理; “操作工具”是指在事件发生过程中涉及的程序和技术; “操作原因”是指事件发生的原因。

2. 2 开放型数据溯源模型

开放型数据溯源模型的提出最初是针对科学工作流，且其设计目标是为不同的系统提供可交换的溯源信息，并允许开发人员创建并共享操作该模型的工具。开放型数据溯源模型同时从技术角度定义了溯源，支持对任何事物( 不仅仅是针对计算机系统) 的溯源，并允许多级描述同时共存。开放型数据溯源模型旨在描述构件中的因果依赖关系，在开放型数据溯源模型中，有4 个主要概念如下: ( 1)状态: 指代某个状态，可以是物理的一个对象，也可以是计算机系统的一个数字化表达。( 2) 过程。状态与状态之间转换引起的一个或者一系列的动作。( 3) 参与者。用以促进、控制和影响过程的执行。( 4) 角色。一个过程可能会产生多个状态，不同的状态拥有不同的角色。在开放型数据溯源模型中，主要的几个逻辑步骤如下: ( 1) 过程触发过程。某些过程是不可分割的，一个过程执行完成才能触发下一个过程的执行。( 2) 参与者控制过程。某些过程需要有参与者控制，参与者控制这个过程的开始与结束。( 3) 状态推断状态。状态与状态之间也是无法分割的，一个状态的产生才能推断出下一个状态的产生。( 4) 过程促进状态。状态与过程不可分割，需要启动某个过程才能产生特定的状态。开放型数据溯源模型是状态与过程的相互作用，参与者促动过程的执行，其简要融入了数据溯源本体模型的相关元素。

2. 3 基于DNA 双螺旋结构的数据溯源模型

陈颖提出的基于DNA 双螺旋结构的数据溯源模型将生物学与数据溯源模型相结合，提出了一种较为新颖的数据溯源模型，将数据溯源信息分为数据和操作两部分并对应起来，为数据溯源的研究与发展提供了一种较新的思路。基于DNA 双螺旋结构的数据溯源模型分为二级结构，一级结构对应DNA 的立体结构图，二级机构对应DNA的平面结构图。在一级结构中，双螺旋结构中的两条链分别代表数据序列和作用在数据之上的操作序列。连接两条链间的碱基代表能唯一确定数据及其操作之间关联的属性，用来在数据及其操作之间建立直接的对应关系，其结构具有一定的稳定性。在二级结构中，引入4 个维度: ( 1) 层次维。对数据所做操作所在层次。( 2) 空间维。相应组件所在位置。( 3) 时间维。操作活动发生的时间。( 4) 数据流维。操作活动过程中数据产品消费和生产的数据。基于DNA 双螺旋结构的数据溯源模型二级结构图。基于DNA 双螺旋结构的数据溯源模型在数据溯源研究领域有许多争议，尽管如此，将DNA 中碱基的配对结构与数据序列和数据操作序列联系起来的思想非常有逻辑性。在开放型数据溯源模型与基于DNA 双螺旋结构的数据溯源模型中，对应关系是二者的共同特点。

2. 4 对3 种典型模型的评估

数据溯源本体模型从语义上涵盖数据溯源信息7 个层次的内容，详尽周全，其概念结构清晰简单，易于理解，存储方便，适用于关系数据库。数据溯源本体模型的不足之处在于其着眼点只在于语义层，没有实现与溯源信息其他层次的衔接。开放型数据溯源模型定义溯源的方式精准且与技术无关，不论其是否由计算机系统产生，都支持对任何事物溯源的数字化描述。在开放型数据溯源模型中，状态与过程相互作用，参与者起操控作用，结构清晰简单易于理解，然而开放型数据溯源模型只涉及逻辑层次上的框架模型，语义层次的信息不够详尽。基于DNA螺旋结构的数据溯源模型的优点在于数据及操作之间的可相互推导，有效解决了数据与操作之间的对应关系，直观地揭示了数据序列及操作序列变化，同样，基于DNA 双螺旋结构的数据溯源模型着眼于逻辑层次上的框架模型，而语义层次的信息不够详尽。

多层次的数据仓库系统框架 篇3

数据仓库系统是以数据仓库技术为基础, 以联机分析处理和数据挖掘工具为手段, 是一项基于数据管理和利用的综合性技术和解决方案[1,2]。通过研究, 本文将提出多层次的数据仓库系统总体框架, 以及基于该框架的数据仓库的体系结构、及数据仓库平台的评测指标。

1、多层次的数据仓库系统的总体参考框架

为了实现数据仓库系统, 可以将系统的总体参考框架分解为九层, 层次结构见图1。上述九层的相互关系是:下一层是上一层的基础, 上一层是下一层的实现目标。由上而下是系统的分析过程, 而由下而上则是系统的实现过程。

用户层:用户通过可视化的应用系统界面, 利用业务层所提供的业务模块对数据仓库或数据集市进行决策查询分析或知识挖掘。

业务层:是基于数据仓库的业务模型。它除了利用现有的OLAP分析工具进行随机查询和分析之外, 还可以根据系统业务, 利用开发工具开发常用的、较固定的应用程序, 实现对数据仓库中数据的查询。

功能层:其功能主要包括从数据源抽取数据, 对抽取的数据进行筛选、清理, 然后将清洁的数据加载到数据仓库中, 同时根据用户的需求建立数据集市, 并完成对数据仓库数据的查询、决策分析和知识的挖掘等功能。

管理层:是对数据仓库中的数据与元数据进行管理。数据管理与元数据管理主要对数据仓库中的数据进行抽取、清理、加载、更新与刷新等管理。

数据层:由数据仓库的数据模型组成, 它是数据仓库系统的核心层。为了使用户能够尽可能地直接访问到数据, 数据仓库中的数据是按照决策分析的主题来组织的, 每个主题对应一个宏观的分析领域。数据的概念模型是多维数据模型, 常见的数据模型有:星形模型、雪花模型、星座模型、雪瀑模型等。

环境支持层:主要包括数据传输和数据仓库基础两大部分。数据传输层实现数据仓库中不同结构之间的数据传输, 其中包括数据传输和传输网络、客户/服务器代理和中间件、复制系统以及数据传输的安全保障系统。数据仓库的基础层则包含系统管理、工作流程管理、存储系统和处理系统。

工具层:由数据仓库构建工具、各种查询工具和各种应用程序开发工具组成, 它支持数据仓库的数据模型, 并使数据模型能更好地为应用程序服务。

操作系统层:一般由Windows NT、Windows 2000、Unix、Linux等网络操作系统组成。对于数据仓库系统, 网络操作系统的性能应该支持内核线程、高容量内存、特大型文件系统、应用程序所用页面大小可变以及并行处理。

物理层:由网络硬件及通信设备组成, 它是网络操作系统的基础。

2、数据仓库的体系结构

数据仓库是数据仓库系统的重要组成部分和数据基础。根据数据仓库的方法学, 数据仓库体系架构可以分为五个层次[3]。这五个层次反映了数据仓库的基本逻辑结构和数据在数据仓库的流动过程。五个应用层次是:

(1) 数据建模层:通过对现有业务系统数据源的分析, 按照数据仓库建模理论构造新的数据模型, 该层是整个分析应用系统的起点。

(2) 数据获取层:确定项目实施所需的数据清洗工具, 定义出数据从原业务系统到数据仓库系统的ETL技术方案, 最终完成数据的收集、清洗、转换、加载的工作。

(3) 数据存储层:是系统保存数据的区域, 数据来自于不同的源数据库, 数据仓库的物理设计要尽可能符合数据模型。

(4) 数据访问层:是数据仓库结构中支持一套共用的表示工具和分析工具的组成部分, 是最终用户与数据仓库交流的层次。

(5) 数据与元数据管理层:主要完成对整个数据仓库实施中的数据与元数据进行管理的功能, 包括逻辑模型到物理模型的映射、数据访问的授权以及用户安全控制等等。

3、数据仓库平台的测试指标

在测试过程中, 可以使用两个专门针对数据仓库平台的测试指标进行辅助测试:

3.1 TPC-D测试

对于数据仓库系统, 衡量其数据仓库性能的主要指标是TPC-D, 它主要从3方面对数据仓库进行测试:

QppD:描述系统的查询处理能力;

QthD:即流量测试结果, 主要描述系统在多个用户同时进行查询时的处理能力, 实际上它代表了系统的并行处理能力;

QphD:即价格性能比。

显然, 前面两个指标的数据越大越好, 而最后一个则越小越好。当然, 首先要考虑的应该是能否满足业务上的需求。TPC-D给了两种测试方式的选择: (1) 直接进行多用户状态下的流量测试; (2) 或者先在单用户状态下进行测试, 然后利用测得的处理能力指标Qpp D, 并用流量指标的计算公式计算出Qth D。那么在实际的测试过程中如何区分这两种测试结果呢?只要把TPC-D的测试概要下载并打印出来, 就可以了解在做流量测试时的Stream数目。Stream数实际上代表了同时递交查询请求的用户个数。如果是单用户状态下的测试, 则只能发现一个Stream, 即Stream0。

由于TPC-D对测试的数据仓库模型、数据的加载以及所有查询都做了非常严格的规定, 因此, TPC-D的测试结果可以对数据仓库系统的加载测试提供一个初步的参考。

3.2 Data Challenge测试

除TPC-D以外, 还有一个Data Challenge的测试标准。与TPC-D不同的是, 它非常注重考察系统的动态查询能力。在测试数据仓库系统时, 应该考虑以下问题:

目前业务部门有些什么急需解决的问题, 这些问题借助传统的生产系统能解决吗?

目前有多大的数据量, 今后的扩展要求如何, 能不能做在线的升级?

系统的并行处理能力怎样?因为它将直接影响系统处理复杂查询和动态查询的能力;

充分考虑了以上各方面的问题后, 所投资建立的实际系统一般都能达到预期的效果。

4、结束语

数据仓库的体系结构属于基础设施的建设, 只有稳固的数据仓库基础设施才能支撑灵活多样的数据仓库应用。而对企业来说, 数据仓库的建设是一个系统工程, 是一个不断建立、发展、完善的过程, 这就要求企业以数据仓库系统的总体参考框架为基础, 逐步构建完整的、健壮的数据仓库系统。

摘要：本文提出了多层次的数据仓库系统总体框架, 以及基于该框架的数据仓库的体系结构和数据仓库平台的测试指标。以此为基础, 并结合已有的业务系统, 企业可以逐步构建完整的、健壮的数据仓库系统。

关键词：数据仓库,总体框架,体系结构,评测指标

参考文献

[1]李波.数据仓库与联机分析处理 (OLAP) 技术.北京广播学院学报 (自然科学版) .2005 (04) .

[2]李亚丽等.基于多维数据模型的数据仓库的构建.北京印刷学院学报.2006 (03)

层次数据论文 篇4

一、数据库加密层次分析

根据数据库的结构可知, 实现数据库的加密可以从三个层次考虑:OS (Operating System, 操作系统) 操作系统层、DBMS (Database Management System, 数据库管理系统) 内核层和DBMS外层。

1. 在OS层加密。

从操作系统的角度来看, OS层位于DBMS层之下, 所以无法辨认数据库文件中的数据关系, 也就无法合理地产生、管理和使用密钥。因此, 在OS层对数据库文件进行加密, 对于大型数据库来说, 目前还难以实现。

2. 在DBMS内核层加密。

在DBMS内核层实现加密, 是指数据在物理存取之前完成加 (解) 密工作。这种方式的优点是加密功能强, 并且加密功能几乎不会影响其他功能;缺点是在服务器端进行加 (解) 密运算, 加重了数据库服务器的负载, 并且因为加 (解) 密是在内核中完成, 就势必需要数据库供应商对其进行技术支持, 这一点不容易实现。DBMS内核层加密关系如图1所示。

3. 在DBMS外层加密。

DBMS外层实现加密在安全层实现加密就是将数据库加密系统做成一个安全层工具。采用这种加密方法的优点是可扩充性强, 数据库的加解密系统可以做成一个独立平台, 不需要数据库供应商进行技术支持, 并且可以将加密密文直接在网上传输;缺点是数据库的功能和查询效率会受一些限制。DBMS外层加密关系如图2所示。

二、数据库加密层次方案选择

数据库数据的存储加密、解密处理可以在数据库系统的不同层次实现, 分别形成以下方案。

1. 添加加密定义接口和处理模块, 以及对数据加解密软件或硬件的调用接口。

由于该方案的实现需要修改DBMS源代码, 而我国目前使用的数据库管理系统大多数是国外开发的, 无法获得源代码, 该方案受条件限制难以实现。另外, 由于内核级加密势必增加服务器的负载 (尤其是使用硬件加密) , 在多用户环境中将影响系统整体效率。因此, 可以先由应用程序调用执行加密运算的软件或硬件实现数据明密转换, 然后将加密文传递给数据管理系统存储。该方案的优点是实现简单, 不需要在系统软件层 (如DBMS层和OS层) 进行任何修改工作。但该缺点是应用不透明, 每个需要数据加 (解) 密的应用都要处理数据加 (解) 密运算调用、数据类型转换等工作, 增加了应用开发的复杂度和难度。另外, 由于数据类型转换模块难以插入应用开发工具中, 将会造成开发工具中的一些功能失效, 这对于图形界面的应用开发来说也是极大的损失。

2. 利用应用接口层, 在数据库应用和内核之间增加加 (解) 密功能模块。

该方案避免了修改内核时的应用开发, 具有较高的透明度, 同时可以实现客户端加密、解密, 对数据库系统整体影响较小。客户 (服务器) 模式最大的优越性就是合理分担计算, 因此一些应由服务器端DBMS内核完成的处理 (如视图处理) , 不应该放置在客户端完成。

3. 对磁盘块进行加密, 实现数据存储加密。

例如软件移动存储加密王, 它的特点是能够对存储在里面的数据进行加密, 从而保证数据不被非法盗用。但是, 这种加密必须由软件辅助完成, 在安装完移动硬盘的驱动之后, 再安装一个加密管理软件就可以实现。加密是通过在特定的硬盘分区里生成加密防卫区实现的, 只有提供了正确的密码, 才可以读取存储在其中的数据。因此, 该方案适于保证移动硬盘的携带安全, 保证备份数据的安全, 但是对于大数据量、频繁访问的应用来说是不合适的。

层次数据论文 篇5

数据中心基础设施建设需要有全面的理论基础、严格的行业标准、系统的设备配置要求、科学的管理措施和安全的运行机制。对于数据中心基础设施的建设者来说实施方案的选择是非常关键的, 我们认为马斯洛需求层次理论在数据中心基础设施建设中的应用具有重要的指导意义, 本文从需求层次理论的角度出发, 探讨数据中心基础设施的需求层次。

一、马斯洛需求层次理论

需求层次理论是由美国著名心理学家马斯洛 (Maslow) 在1943年所著的《人的动机理论》一书中首先提出的。他将人的多种需求由低到高归纳为五个层次, 即生理需求、安全需求、情感需求、尊重需求和自我实现的需求, 并阐明了它们的内在联系。低一层次的需要获得满足后, 就会向高一层次的需要发展。一般来说, 只有在较低层次的需求得到满足之后, 较高层次的需求才会有足够的活力驱动行为。

二、基础设施建设的需求层次理论

如图1所示, 可知道数据中心基础设施所包含的主要内容, 如何根据需要进行数据中心的基础设施建设呢?结合马斯洛需求层次理论对数据中心基础设施的需求进行了如图2所示的划分, 希望能够对数据中心基础设施的建设提供参考, 下面结合马斯洛需求层次理论分析数据中心基础设施建设的层次需求:

2.1运行需求。

对任何一个企业而言, 数据中心的存在与否就像马斯洛需求层次理论的第一个需求层次一样, 是企业各项业务的运行根本。如果只要求一个数据中心满足一些简单的数据交换、信息处理, 那么这样的数据中心就能够容忍一些中断和停机;建设这样的数据中心, 对基础设施而言就非常简单了, 在对其进行评估时就只需要看能否提供电源系统、能否提供局部热点的简单制冷设备就可以了, 对其它方的要求就相对较低。因为正如生理需求一样, 电源和制冷是最基本的需求和最低级的需求, 只要有满足这两个方面的需求的基础设施, 数据中心就有运行的保证。从国内数据中心使用需求来看, 建设这种需求层次的企业有:小型企业、SOHO、部门级数据中心 (评估标准如图3) 。

2.2冗余需求。

正如马斯洛需求理论所分析的一样, 某一层次的需要相对满足了, 就会向高一层次发展, 追求更高一层次的需要就成为驱使行为的动力。对已经拥有最低层次数据中心的企业而言, 随着企业的不断发展, 对数据中心的要求也在不断提高, 在这个阶段对数据中心的建设和改造, 其基础设施又需有更高层次的要求:冗余, 特别是电力和制冷的基本冗余, 因为随着需求的不断增加, 数据中心的服务器和存储设备增长较多, 数据的额外保护和安全需求也在不断增加。对这个层次的数据中心做需求评估, 其基础设施的需求改变体现在以下几个方面:1) 数据中心需配备架空地板, 解决综合布线及制冷通道问题;2) 用UPS或备用发动机来处理电力负荷, 设计容量满足单回路的N+1;3) 制冷系统在满足制冷需求的同时有一定冗余, 设计容量满足N+1;4) 有可靠的信息系统接入;5) 消防报警系统及简单的手持式灭火装置;6) 对关键电路和其他基础设施进行维护需要程序式的关闭设备。总结其对基础设施的要求, 此种层次需求的数据中心有单点的中断可能, 该类型数据中心包括:中等规模的企业级数据中心、与外界业务交往少的数据中心或机房 (评估标准如图4) 。

2.3恢复需求。

满足冗余需求的数据中心有单点中断的可能, 为了进一步提高数据中心的可靠性及可用性, 满足数据中心恢复需求, 在满足冗余需求的前提下, 还需要加强以下几个方面的要求:1) 数据中心选址需要考虑:可用电源的接入、建筑物抵御风险的能力、通讯设施的接入等因素;2) 以主动-被动或是双主动模式提供冗余电源和制冷设备;3) 能够为需要的计算机设备提供双电源;4) 冗余的信息系统接入;5) 消防系统方面需配置有效的检测和灭火装置以满足一个小时的防火等级;6) 有较好的环境保障;7) 系统运行要求为:满足365*24小时不间断运行。此类数据中心的基础设施要求已经达到了较高的标准, 拥有以上基础设施的数据中心主要有:有影响力的信息工厂、不能够承受不定期停机的数据中心、国有集团公司的数据中心、省部级的数据中心等 (评估标准如图5) 。

2.4灾备需求。

一般来说, 数据中心的基础设施建设达到恢复需求已可以满足需求了, 但对于一些要求特别高、有灾备需求的数据中心而言, 其基础设施需求除了满足上面各项需求等级外, 还需要在基础设施方面考虑如下需求保障:1) 基础设施能保证任何计划性活动不会引起关键性负载中断;2) 需要有来自不同电力公司的电力供应及需要两个独立的 (N+1) UPS系统;3) 制冷系统来讲需要满足N+X (X>1) 的系统冗余;4) 信息系统的提供需要具备相互独立的公司提供的网络线路;5) 消防系统能满足最低两个小时的防火等级;6) 在不同的区域之间设隔离区和分配区;7) 物理结构能够抵御绝大多数自然灾害的威胁;8) 拥有24小时现场电子监控和安全监控系统。此类数据中心主要包括:证券、电力、商业银行、保险公司、大型跨国公司的销售公司、国家级数据库等数据业务非常重要的数据中心 (评估标准如图6) 。

2.5生存需求。

按照马斯洛需求层次理论, 对个人而言最高需求是个人价值的作为实现, 对数据中心的建设来说, 其基础设施建设的最高需求有哪些特殊要求呢?关系国家军事安全, 金融安全、科研保密等相关的数据中心, 因为其关系到一个国家的政治、经济、军事安全, 关系一个国家的生存和发展, 就需要考虑关系国泰民安的生存需求, 因此数据中心基础设施建设的最高需求从某种意义来讲就是生存需求。能够参与设计和施工这类数据中心基础设施的人很少, 但不影响我们对于其基础设施需求的研究, 其对基础设施的研究除了前面几种需求, 还需要提高的包含以下几个方面:1) 数据中心选址的安全性、可靠性及保密性;2) 电力供应拥有自己独立使用的发电系统;3) 数据中心的信息交换和获取必须通过专用通道进行;4) 除了电子监控系统和安全监控系统外, 须有专业的安保人员24小时进行安全保卫工作。

此类数据中心主要包括:国家银行、国家军事、国家安全及国家级科研等数据中心。

三、马斯洛的需求层次理论对数据中心基础设施建设的意义

数据中心的建设与一个企业的经济实力、科研力量等因素息息相关, 虽然数据中心的基础设施建设根据年代的早晚大致可以分为四个等级, 但根据自己数据中心的使用要求和需要, 数据的集中程度以及对数据依赖度将决定构建或者采用哪一个级别的数据中心, 就像马斯洛需求层次理论阐述的一样, 满足自己的需求层次就可以了;根据实际的需求灵活运用层次理论、不用按部就班和墨守成规才是运用层次理论去指导数据中心基础设施建设的最终目的和意义。

参考文献

[1]王其英.机房与UPS选型技术手册[M].中国电力出版社, 2008.

[2]Greg Schulz (美) .绿色虚拟数据中心[M].人民邮电出版社, 2010.

[3]马斯洛 (美) .马斯洛人本哲学[M].九州图书出版社, 2003.

层次数据论文 篇6

关键词：战术数据链,模糊层次分析法,评估

0引言

数据链系统结构复杂, 影响其作战支撑能力的因素很多, 属于多因素综合评估问题, 部分因素带有显著的不确定性, 考虑到多因素综合评估的本质特点, 本文构建了数据链系统的支撑能力评估指标体系, 通过层次分析法和模糊综合评价分析法对数据链支撑能力进行了实例评估, 得出了评估结果。

1评估指标体系

选择合适的指标建立评估指标体系, 是做好系统效能评估的关键。建立数据链应用的评估指标体系, 主要包含网络覆盖能力、信息传输能力、目标识别与跟踪能力、可靠性及抗毁能力等, 具体指标体系如图1所示。

2评估方法

模糊综合评价法[5,6,7]给定两个有限论域:

评判因素的评判决策矩阵为:

就是U到V上的一个模糊关系。

3案例分析

利用层次分析法和模糊综合评价法对数据链应用支撑能力进行分析。

第一步, 针对数据链性能指标建立性能指标的专家模糊评估值。

第二步, 针对评估指标, 通过五位专家打分, 利用模糊分布法对二级指标给出评判决策矩阵Rui;

第三步, 利用层次分析法, 确定能力层对效能层的权重, 性能层指标对应能力的权重, 如表1、表2、表3、表4和表5所示。

第四步, 根据性能层的模糊评判矩阵和权重矩阵, 计算能力层的模糊评判矩阵。

第五步, 根据能力层的模糊评判矩阵和权重矩阵, 计算效能层数据链作战应用支撑能力的模糊评判矩阵。

根据最大隶属原则, 数据链应用支撑能力属于“较好”, 最终评价对应的分值为75分。由此可以得出, 降低数据链设备的故障率, 提高安全保障能力可有效提高数据链的应用支撑能力, 与对数据链应用支撑性能的判断一致。

4结束语

本文利用模糊层次分析法以及专家评价法对数据链作战应用支撑能力进行了示例评估, 可为数据链作战效能评估以及对数据链装备的改进完善提供依据。

参考文献

[1]孙义民, 杨丽萍.信息化战争中的战术数据链[M].北京:北京邮电大学出版社, 2005.

层次数据论文 篇7

1相关工作

层次数据之间具有关联关系即为关联层次数据。最早的关联层次数据可视化是在层次可视化基础上直接添加关联边, 但大量的边交叉会造成严重的视觉混乱。因此, 引入边绑定算法来减少视觉杂乱度[1]。Tree Net Viz方法采用放射环表示层次关系, 用边绑定后曲线表示关联关系[2]。双关联树[3]主要解决了两类层次数据以及他们之间的关联关系可视化问题。折线也可表示关联关系[4]。而另一类关联层次数据可视化方法是将层次数据可视化方法和邻接矩阵相结合。较为经典的是Matrix browser方法[5], 层次关系用节点- 链接的正交布局, 关联关系用矩阵来展现。该方法不会造成视觉杂乱, 但空间利用率不太高且关联关系表达不太直观。该方法仅通过邻接矩阵表达了两类层次数据之间的直接关系, 而对于两类层次数据之间的间接关系并没有有效呈现出来。

因此, 本文以关联层次数据分析为需求, 提出一种关联层次数据混合布局方法, 利用节点- 链接和两个邻接矩阵来可视化关联层次数据, 帮助用户挖掘层次数据之间的直接和间接关联关系。

2双矩阵热图布局方法简介

针对两类层次数据之间的直接关系和间接关系, 本文采用双矩阵热图来展现。其中, 直接关系表示为一类层次数据与另一类层次数据之间的关系;间接关系表示为一类层次数据内部变量之间的关系, 该关系由另一类层次数据决定。

2.1构造间接关系矩阵

一般采用“距离”来衡量两个样本之间的相似性。由于欧氏距离能够体现个体数值特征的绝对差异, 因此本文采用最简单的欧式距离公式。

本文定义两个k维向量a和b, 公式 (1) 中, ai或bi的取值为数值, 且i=1, 2, …k。

那么, 向量A和B间的欧式距离为:

设一个含有n个k维对象的集合Q, Q={Q1, Q2, …Qi, … , Qn}, i={1, 2, …, n}, 其中Qi={Qi1, Qi2, …Qij, …, Qik}, Qij为数值型。 公式 (3) 为Q的欧式距离矩阵, 用Do表示, 即间接关系矩阵。

其中, dij=Do (Qi, Qj) 是Q中任意两个对象Qi和Qj之间的欧式距离。由于Do矩阵是对称矩阵, 因此只绘制三角矩阵。 定义一个颜色空间, 将该颜色空间的两个极端值分别赋予dij的最大值和最小值, 并将其他dij与颜色对应, 映射到矩阵空间的相应位置上。

2.2构造直接关系矩阵

首先定义两个k维集合G和H。公式 (4) 中, Gi或Hi的取值没有限定, 且i=1, 2, …k。

其次, 计算两个集合的直接关系数值矩阵PC, 定义直接关系矩阵PC为:

其中, gihj表示取值为gi和hj的个数累计。同样定义一个颜色空间, 将该颜色空间的两个极端值分别赋予gihj中的最大值和最小值, 其他gihj值按比例求出相对应的颜色, 并映射到矩阵上。

2.3柱状图的绘制

本文将柱状图用于两个集合之间直接关系矩阵热图横向和纵向上的统计展示。根据公式纵向上求出∑ki=1gih1到∑kj=1g1hj, 横向上求出∑kj=1g1hj到∑kj=1gkhj, 其中gihj表示取值为gi和hi的个数累计, 且分别用柱状图绘制后放置在矩阵热图的上方和右侧, 辅助用户从整体的角度来分析数据。

3关联层次数据混合布局方法

3.1节点- 链接法的呈现

节点- 链接法的核心问题是如何在屏幕上放置节点, 以及如何绘制节点及节点间的链接关系。横纵轴布局算法是最简单的节点链接法, 它沿着横轴或纵轴扩充或缩进子节点。

横纵轴布局算法步骤如下:

第一步:根据树的深度, 将空间沿纵轴平均分成等高的区域, 每个区域对应树的一层。树中相同深度的节点属于同一层。

第二步:根据每一层节点的数量, 将对应的区域沿横纵轴平均分成等宽区域。

第三步:将节点布置在每个区域的中心。

第四步:在节点和它的父节点之间连线。

3.2关联层次数据混合布局方法

关联层次数据混合布局方法是将节点- 链接与矩阵热图相结合。具体步骤:首先, 以方形矩阵为中心, 将两个三角矩阵分别放置在方形矩阵的左侧和下方, 将两个柱形图分别放置在方形矩阵的上方和右侧, 并与方形矩阵的每一维相对应。其次, 将方形矩阵每一维对应的值放置在方形矩阵与三角距离矩阵中间, 便于用户查询每一维的属性。最后, 将两类层次数据以节点-链接的形式呈现在两个三角矩阵的上方。

3.3可视化结果展示

本文的数据集是农药残留模拟数据集。农产品主要分为蔬菜、水果、调味料等等, 而每类下面还可继续分类, 如蔬菜可分为根茎类和叶菜类等。同样, 农药按照基质可分为氨基酸类、磷类等, 而如果按照毒性可分为剧毒、高度、中毒和低毒。因此, 农产品和农药本身就是个层次结构的数据。

图1是基于矩阵热图的关联层次数据可视化方法结果图展示。图中A矩阵表示农产品中检出农药的情况, 即小矩形代表某个农产品中检出某个农药的频次。颜色越深, 代表检出频次越高。A上方的柱形图表示每个被检出的农药的频次统计;A右侧的柱形图表示每个检出农药的农产品的频次统计。图中左侧的B矩阵是农产品关联矩阵, 横轴和纵轴均代表农产品, 小矩形颜色越浅表示两个农产品距离越近越相似, 即检出的农药相似。同样, 图中下方的C矩阵是农药关联矩阵, 展示不同农药之间的相关性。而农产品和农药两个三角矩阵的上方是对农产品和农药的一个层次结构的展示, 即类别展示。它们的右侧则是相对应的农产品和农药的名称。由图可知, 芹菜中检出农药比较严重, 且芹菜与其他蔬菜水果存在明显差异性。同样, 农药carbofuran被检出的比例也较大, 而农药phorate、农药omethoate与其他农药的差异性也比较大。

4结语

本文针对如何将关联层次数据集进行可视化的问题, 提出了一种关联层次数据混合布局方法。将节点- 链接和矩阵热图相结合, 并将其应用于食品安全领域, 帮助相关人员发现潜在的问题。未来, 在矩阵热图的排序上需要进行优化, 可采用聚类排序或其他排序算法让矩阵热图在关系呈现上有更好的表现。此外, 本文提出的方法还可用于电商、金融等多个领域, 从而对具有直接或间接关联的层次数据进行可视化和可视分析。

参考文献

[1]Zhou H, Xu P, Yuan X, et al.Edge Bundling in Information Visualization[J].Tsinghua Science and Technology, 2013 (2) :145-156.

[2]Gou L, Zhang X.Treenetviz:Revealing Patterns of Networks Over Tree Structures[J].IEEE Transactions on Visualization and Computer Graphics, 2011 (12) :2449-2458.

[3]陈谊, 张鑫跃, 陈红倩, 冯玉超.一种双关联树的混合布局算法[J].系统仿真学报, 2014 (9) :2160-2165.

[4]Sugiyama K, Misue K.Visualization of Structural Information:Automatic Drawing of Compound Digraphs[J].IEEE Transactions on Systems, Man, and Cybernetics, 1991 (4) :876-892.

层次数据论文 篇8

上层模块管理下层模块的一个重要工作就是传送新配置的数据。以交换机以例,当某个手机用户的信息变更时,也就产生了新的配置数据。新的配置数据需要迅速正确地传递到交换机系统的各个模块中,而这往往会成为影响系统性能稳定的瓶颈问题,如何使新配置的数据快速传送到系统的各个模块,成为层次型多模块结构嵌入式实时系统数据管理的一个重要课题。

1 树形结构模型的建立

为了更好地研究模块之间数据传送的问题,我们将这种层次型多模块结构抽象成一个树形结构。一个模块就是树中一个结点,两个可以传送数据的模块所代表的结点之间以边相连。上层模块是父结点,被管理的下层模块是子结点。

以某种类型的交换机系统为例:第一层是系统主模块,它管理两台交换机;第二层是交换机主模块,它管理交换机的若干层框架;第三层是框架主模块,它管理框架上的各个插板;第四层是插板主模块,它管理插板上的各个子板;第五层是子板模块。每个模块是树上一个结点,有一个唯一编号。这个交换机系统的模块树结构可以用图1表示。

图1中根结点是整个系统的主模块,交换机的后台管理系统所产生的配置数据,都传送向这个模块[3]。每个模块都有一个唯一整数编号,可以作为对应结点的结点号。当根结点接收到新的数据后,应尽可能快地传送到树中各个结点,以便各个模块及时拥有新的数据,保证整个系统的可靠性和实时性[2]。

由于是多模块系统,单个模块便是一个嵌入式系统,它们之间是相对独立工作的。因此多个模块可以同时向相邻模块传送数据。但是,一个模块不可能同时将数据传送给若干个相邻模块。也就是在这个树形结构中,各个结点可同时向自身的子结点传送数据,但不能一个结点同时向自身多个子结点传送数据。综上所述,我们将要解决的问题归纳为:从一棵树的根结点开始将数据传送给树上的所有结点,结点之间的边的权值表示了结点和子结点之间数据传送所花费的时间。每次数据传送只能从父结点传向一个子结点,多个结点可以同时向其子结点传送数据。如何安排每个非叶结点向其所有子结点传送数据的顺序,使得数据传送到所有结点所花费时间最少,并求这个时间值。

2 求解传送顺序算法的提出和证明

如果在多模块系统中,任意两个相邻模块传送数据的时间相等,那么这个模块树的边就没有权值或所有边的权值相等,这个问题就是算法分析中的鸡毛信问题了[4]。但是在实际系统中,模块之间的数据传送时间不仅不相等,而且还会根据系统运行的状态而改变。因此,这个模块树边的权值也是不相等的,且动态可变。

2.1 算法的描述

首先定义一个函数F(x)。x是模块树中的一个结点号,函数的值表示数据从结点x,传遍整个以x为根的子树所有结点的最短时间。很显然,如果x为叶结点,则F(x)为0;如果x为根结点,则F(x)为就是我们所求取的最少花费时间值。

设一个非叶结点A有n个子结点,分别为A1、A2…An,A结点将数据传送给各个子结点的时间为t1、t2…tn。如果A向子结点传送数据的顺序安排为A1、A2…An,对于任一子结点Ai(1≤i≤n),定义一个函数D(Ai),其值是:以结点A获得数据时刻为起始,以Ai为根的子树的所有结点都获得数据时刻为终止,这两个时刻之间的时间间隔。

根据D函数的定义,更改两个相邻结点Ai和Ai+1的传送顺序,也就是先传送给Ai+1结点,后传送给Ai结点,将不影响其它n-2个结点的D函数值。

定理:对于模块树中任意一个非叶结点,其向子结点的数据传送顺序按子结点的F函数值从大到小排列,即可保证树中所有结点都获取数据所花费的时间最短。

2.2 算法的证明

根据上节中D函数的定义,如果交换两个传送顺序连续的子结点Ai和Ai+1的传送顺序,也就是先传送给Ai+1结点,后传送给A结点,将不影响其它n-2个结点的D函数值。

假设F(Ai)≤F(Ai+1),在Ai和Ai+1的传送顺序交换前:

在Ai和Ai+1的传送顺序交换后:

由于,所以交换后的MAX(D(Ai),D(Ai+1))值要小于等于交换前的值。又由于其它n-2个结点的D函数值不受影响,故此交换后的MAX(D(A1)、D(A2)…D(An))的值要小于等于交换前的值。

综上所述,两个传送顺序连续的子结点Ai和Ai+1,如果F(Ai)≤F(Ai+1),则交换它们的传送顺序后,可以取得一个更优的F(A)值。以此类推,可以证明只要向子结点的数据传送顺序按子结点的F函数值从大到小排列,就可以得到一个最优的F(A)值。

3 算法的实现

3.1 模块树和传送顺序的数据结构

表示树的数据结构种类较多,由于模块树的边有权值,所以使用矩陈来表示这个树结构[3]。定义二维数组tree[N+1][N+1],其中N表示树中结点数,结点号分别为1、2…N。其中任一元素tree[i][j],若i>j,表示结点i到结点j的权值。如果i≤j,或i结点到j结点没有边,tree[i][j]值设置为-1。

算法的输出结果有两类:一类是所有节点的F函数值,另一类是所有非叶接点的数据传送顺序。用另外一个整型二维数组order[N+1][N+1]表示输出结果。假设结点i(1≤i≤N)有k个子结点,则order[i][0]表示结点i的F函数值,初值设置为0;order[i][j](j=1~k)表示i结点向所有子结点的传送顺序。如order[i][1]表示第1个传送的子结点,order[i][j]表示第j个传送的子结点。order数组的其它元素值无意义,其值设置为-1。

3.2 算法流程设计

计算所有结点的F函数值和传送顺序的最直观的算法当然是递归算法,但是递归算法效率差,所消耗资源多,不适合于嵌入式实时系统。可以使用动态规划法计算所有节点的F值和传送顺序,其算法原理是:首先将所有叶结点的F函数值设置为0,并将下述过程循环m次,m是树的非叶结点数。

找到一个结点,其子结点的F函数值都已经获得。按照子结点的F函数值从大到小的顺序,将这些子结点的结点号排列在order数组中相应的位置,并计算出这个结点的F函数值,放入order数组相应位置。流程图如图2。

4 结束语

每个复杂的多模块结构的实时嵌入式系统都有不同的特点,如果能设计出一个适用于本系统的快速数据配置方法,将极大地提高系统的稳定性、可靠性和实时处理能力。嵌入式实时系统的数据配置方法牵涉到数据库技术,计算机通信,嵌入式操作系统和嵌入式编程等多方面的知识,是一项复杂的工作,需要在实践中不断地创新和发展。

参考文献

[1]连一峰.分布式侵入检测模型研究[J].计算机研究与发展,2003,40(8):23-24.

[2]李忠民.ARM嵌入式VXWORKS实践教程[M].北京:北京航空航天大学出版社,2006.

[3]耿国华.数据结构-C语言描述[M].西安:西安电子科技大学出版社,2002.

[4]王哓东.算法设计与分析[M].北京:清华大学出版社,2003.