计算机及应用毕业设计-1.4万字基于XML的异构数据库.docx

北京市高等教育自学考试毕业设计基于XML的异构数据库查询中间件的实现专业计算机及应用学生李闪闪指导老师陈向群日期2006年10月论文摘要外交部各部门在实施信息化的过程中，采用了不同的数据管理系统，这些系统从简单的文件数据库到复杂的网络数据库，构成了异构数据源。这些异构数据库系统资源共享性差，有的甚至无法共享，形成了各自的信息孤岛，存在大量重复建设、资源浪费的情况，为解决这个问题，本文给出了基于XML的异构数据库查询中间件的方案及其主要框架。该框架以中间件集成方式为基础，将XML引入到了中间件系统中来。本文采用VCxSQLSERVER.DoTNET等软件，在ADO、XML等技术的支持下，本文完成了一个较为实用的异构数据库查询中间件程序。该中间件由词法分析器、语法分析器、重写器、计划生成、计划执行等模块组成，实现了对异构数据库(ACCESS.SQL)的联合查询。本文实现的中间件是针对本人所在处里的两套异构数据库系统进行设计，这两套异构数据库分别采用了ACCESS、SQLSERVER数据库，现在该中间件正处在运行测试阶段。关键词：异构数据库；中间件；XML论文摘要2目录3第一章概述51.l论文选题背景51.2国内外发展现状51.2.1当前数据集成方案51.2.2国内外研究现状71.3论文目标8131论文要实现的目标81.3.2XML技术的引入91.4 论文的组织结构91.5 本章小结10第二章中间件设计方案112主要架构112.2 系统目标122.2.1 软件架构132.2.2 视图层次14223功能模块142.3 中间件工作流程162.3.1 用户输入查询请求16232语法树的生成16233查询计划树的生成17234查询计划树的重写182.3.5 查询计划树的优化182.3.6 查询分解202.4 冲突的解决202.4.1 冲突的类型212.4.2 异构数据库冲突的解决方法21第三章中间件的实现233.1.1 语法树的生成233.1.2 1.EX和YACC的使用233.1.3 语法树的生成243.2 计划树的生成2633查询分解的实现283.4 数据类型的统一3235用户界面32第四章总结344.1论文总结3442心得体会344.3进一步工作35第一章概述1.1 论文选题背景外交部各部门在发展过程中积累了大量数据，并为存储和管理这些数据不断投资，然而，由于实施数据管理系统的阶段性，以及计算机存储技术的不断发展,和人为因素的影响，以至于大到部门间的系统、小到一个处内的各个系统都可能采用不同的数据管理系统，从简单的文件数据库到复杂的网络数据库，它们构成了外交部内部的异构数据源。尽管这些数据管理系统能够满足数据存储和管理要求，但在信息共享的今天，这些异构数据库系统资源共享性差，有的甚至无法共享，形成了各自的信息孤岛，存在大量重复建设、资源浪费的情况。例如，本人所在处就需要用到几套系统：一套外交部固定资产管理系统，这套系统采用了SQLSERVER作为数据库；一套是办公网系统，这套系统采用了Oracle作为数据库；一套是处内办公软件，这套软件采用ACCESS作为数据库。有时需要同时获得这三套系统的信息，就必须分别对这三套系统进行访问，然后将信息汇总后再进行处理。这样的处理显示是低效的，复杂的，易于出错的。所以，无论是从本部门发展角度还是从外交部整体的角度来看，对异构数据库访问的需求将越来越多，建立异构数据库的集成查询等势在必行。1.2 国内外发展现状1.2.1 当前数据集成方案一、联邦数据库系统集成几个数据库的最简单的结构可能是实现需要交互的所有数据库对之间的一对一连接。这些连接允许一个数据库系统DBl以另一个数据库系统DB2能理解的术语来查询D2。这种结构的问题是，如果n个数据库中的每一个都需要与其他n-1个数据库进行交互，则我们必须写n(n-l)条代码以支持系统之间的查询。图LI联邦数据库模型二、数据仓库在数据仓库集成结构中，来自几个数据源的数据被抽取出来，合成一个全局模式。然后，数据存储在数据仓库中，这在用户看来与普通数据库无异。组织方式如图L2所示。L2数据仓底一旦数据存储在数据仓库中，用户就可以提出查询，正如他们向任何数据库提出查询一样。另一方面，通常不允许用户对数据仓库进行更新，因为这些更新不能反映在基本数据源中，并且可以导致数据仓库与数据源不一致。此外，数据仓库中的内容需要周期性的更新，以保持和数据源里的数据一致。三、MediationoMediator是一种软件组件，它支持虚拟数据库，用户可以查询这个虚拟数据库，就像它已物化一样。Mediator不存储任何自己的数据，而是将用户的查询翻译成一个或多个对数据源的查询。然后，Mediator将那些数据些对用户查询的回答进行综合处理，将结果返回给用户。其基本结构如图L3所×Fo图1.3Mediator模型Mediator负责把查询分发到各个包装器，包装器然后把查询转换成本地数据源可以理解的模式。MediatOr本身不对查询进行任何解释。MediatOr对包装器返回的结果进行合成。按照这个理论来讲的话，对于需要集成的数据源，为每个数据源都要设计一个包装器，或者说为一类数据源（关系数据库、XML.web数据）设计一个可动态配置的包装器C这种方式存在的问题：既然Mediator不对查询进行解释，那么这种对数据源的集成就无法考虑到数据源之间数据的特殊的联系。因为每个包装器只了解自己数据源的内容，Mediator只负责把各个包装器返回来的数据进行的组合。1.2.2 国内外研究现状异构数据库集成并不是一个新的研究领域，随着XML技术的采用，该领域又重新成为了研究的热点。从采用基于XML技术的中间件来集成异构数据库或异构信息的角度来看，目前，相关研究主要集中在国外。美国政府在1998年通过OPAL计划开始支持YAT（基于中间件的信息集成系统）的研究，该系统Mediator/Wrapper中间件框架实现了关系模式和SGML到ODMG的转化，在2000年，该系统的研究再次受到OPAL计划和AQUARELLE资助，并以研究基于xml中间件信息集成系统（YAT系统）为主，其中ChristophidesV,CLUETS,SIMEONJ等人主要研究了以XML集成视图对异构数据的包装和查询，并提出了相应的代数体系结构。Wisconsin大学和IBMAlmadenResearchCenter共同研究和实现了XPERANTO中间件系统是一个比较成功的系统。就关系模式到XML模式转化（模式转换是基于XML的异构数据库集成中间件的核心）面来看，已存在转化工具和大量相关算法的研究：相关工具：一些商业产品实现了关系模式到XML文档的转化，例如0DBC2XML、Oracle'sSQLsXMLSpyxSiIkRoute工具。目前，除ODBC2XML,XMLSpysIkRoute外，大部分的工具都是为相关的数据库产品服务，不支持多种异构数据库系统更不支持其到XML的集成,而OraCHSSQL、XMLSpysSiIkRoUte虽然支持多种数据库系统，但仍不支持异构数据库的集成。同时，这些工具大部分（除XMLSPy外）都是输出XMLDTD模式，不支持XMLSChema模式。相关算法的研究也主要集中在国外。如DongwonLee（UCLA1美国，加利福尼亚大学洛杉矶分校）在美国国防部高级研究项目（DARPA）和国家科学基金（NSF）的双重支持项目XPRESSXML中，提出基于XML的关系数据库发布和基于关系数据库的XML存贮和检索，提出并初步建立基于约束的模式映射。JayavelShanmugasundaram（Cornell,美国，康奈尔大学），提出基于内嵌的关系数据发布技术。WenfeiFan（贝尔实验室）则在建立XML约束方面作了大量研究。1.3 论文目标1.3.1 论文要实现的目标本文要实现一个数据库集成中间件，该中间件采用SQL语言作为输入，通过ADC）接口，实现对异构数据库ACCESS和SQLSERVER联合查询，并将查询结果以XML作为结果输出给用户。其主要特点是：一、以SQL语言为输入，会使用用户感到十分方便。同时也可以利用SQL语言在操作关系数据库时的强大功能。二、以XML为结果，则可以有效的将结果与其它应用程序进行数据交换。在本文要实现的中间件中，要解决的主要问题是：一、异构性异构性是企业异构数据集成必须面临的首要问题，其主要表现在两方面：强调数据的存储方式是不同的。关系数据库、文本文件就可以认为是异构的。Sqlserver和Orade也可以认为异构的，同样是Sqlserver数据源，表示了相同的数据，如果表的结构有所不同，也是异构数据源。强调存储地点的异构。不同主机之间，不同的操作系统之间，不同网络之间，它们的数据之间的差别，而这种异构数据源的集成重在通信。在本文中，主要解决的问题是第一方面的问题，也就是数据存储方式不同的异构。二、语义冲突信息资源之间存在着语义上的区别。这些语义上的不同可能引起各种矛盾，从简单的名字语义冲突（不同的名字代表相同的概念），到复杂的结构语义冲突（不同的模型表达同样的信息）。语义冲突会带来数据集成结果的冗余，干扰数据处理、发布和交换。所以如何尽量减少语义冲突也是数据集成的一个研究热点。1.3.2 XML技术的引入随着XML及其相关技术和应用的发展，XML不仅成为了应用间交换数据的一种标准，也是万维网重要的信息交换标准和表示的技术之一。事实上，现在业界已存在几个工业标准（XMLDTD）的草案。XML的产生给不同的信息格式的统一带来了深刻的影响。XML第一次提供了一种信息交换模式，这种格式是可编辑,易解析，并且可以表示为任何类型的结构或半结构化信息。目前，XML已有多方支持，并且XML的强适应性，使其可以实现对资源的快速包装和集成发布，所以，通过引入了XML技术，将XML技术与全局数据模式相结合可以使异构数据源集成中间件系统能更好地适应于开放、发展环境中的数据集成。1.4论文的组织结构本文探讨了实现异构数据源查询中间件的设计方法和实现技术路线，给出了原型系统的设计方案。文章的整体结构如下：第一章主要是讨论异构数据源集成的必要性，及其研究的主要内容，同时也列举了国内国外的研究进展和相应的成果。第二章介绍了本文所实现的异构数据源中间件原型系统的整个架构和中间件系统的整个工作流程O第三章加述）在原型系统实现的过程，原型系统每部分功能实现中所采用的算法、流程，以及在解决具体问题时所采用的方案和核心代码。最后谈到了系统所达到的目标。第四章是全文的总结，概括了本文中所实现系统的特点，同时也指出了其不足和未来能进一步完善之处。1.5本章小结异构数据源集成查询并不是一个新的课题，但在企业生存环境不断改变的前提下，这个课题也是不断发展的。如何面向未来，采用合理的技术实现网络时代企业数据集成将是一个持久的讨论。作为企业应用和企业服务集成实现的一个基础，企业异构数据源集成将对企业信息化进程带来深远的影响。第二章中间件设计方案本章将从逻辑架构、视图层次、内部实现、数据存储等多个角度来阐述中间件系统的具体实现方案。2.1 主要架构目前已有的基于XML的异构数据源集成中间件方案，其一般架构都是基于图2.1设计的。数据源层表示现有的异构的数据源以及在这些数据源上的应用。XML中间件层是最重要也是承担主要工作的一层。中间件先在每个数据源上加上一个WraPPer,使各个异构数据源中的数据经过WraPPer封装后具有统一的数据格式。这种经过Wrapper封装后的数据称之为输出模式。产生输出模式的数据后，中间件系统会分解、处理用户的查询请求，把不同数据源的输出模式进行合并，形成一个统一的数据视图，最后以全局模式展示给用户。全局概念模式是在一个或几个输出模式的基础上形成的新的“视图”。全局概念模式本身并不存储数据，而是利用数据字典记录了是由哪几个输出模式的所组成。用户可以直接访问全局概念模式而不需要关心概念模式的具体构成方式。全局概念模式有点类似于数据库概念当中的“视图”。全局视图的建立就是针对所有数据源数据模式的抽取过程，它将各异构数据源中的不同的数据表示形式统一成一致的数据视图。其中，关键要解决的问题是对各个数据源的集成存取，或者说将用户对集成视图的操纵转换成对底层数据源的操纵，包括两方面工作：一个是将用户对集成模式的访问转换成数据源可以执行的请求；另一方面是将各数据源返回的数据转换成集成模式的表示形式，反之亦然。XMLHTML MSS 耳它应用程序接口层全局模式分散，异构，异质数据源WrtpperXml 中 间 件 层数 据 源 层应用2应用n图2.1集成中间件基本架构2.2 系统目标针对上述体系结构，本文中间件原型系统所实现的主要功能目标包括：一、实现对特定SQL语言(系统定义的一种类SQL语言)的支持SQL语言(StrUCtUredQueryLanguage)是一种介于关系代数与关系演算之间的语言，是一种用来与关系数据库管理系统通信的标准计算机语言。其功能包括数据查询、数据操纵、数据定义和数据控制4个方面，是一个通用的、功能极强的关系数据库语言。目前已成为关系数据库的标准语言。中间件系统支持SQL语言，可以使用户不需要学习过多的新知识，易于掌握，提高了中间件的易用性。二、将最终结果转化为XML的形式随着XML及其相关技术和应用的发展，XML不仅成为了应用间交换数据的一种标准，也是万维网重要的信息交换标准和表示的技术之一。事实上，现在业界已存在几个工业标准(XMLDTD)的草案。XML的产生给不同的信息格式的统一带来了深刻的影响。XML第一次提供了一种信息交换模式，这种格式是可编辑，易解析，并且可以表示为任何类型的结构或半结构化信息。2.2.1 软件架构根据以上给出的系统功能目标，本文实现的中间件的主要架构如图2.2所示。图2.2中描述了整个中间件系统的工作流程，其主要由以下几个部分组成。 用户输入请求。用户以系统规定的SQL语句，作为输入请求；接收查询语句，进行词法语法分析，生成查询树；根据查询树，生成相应的任务树；将任务树根据数据源所在的位置进行分解，从数据源中取出数据；(5)将各数据源返回的结果进行组合，最终以XML的形式输出。IS 2.2中间件系统架构2.2.2 视图层次设计的原型中间件系统中，一共有四种模式：全局外模式、全局概念模式、输出模式和局部模式。局部模式是指各异构数据源存储数据的原始格式。局部模式中，各类数据源的数据格式是不同的，异构的C输出模式在本系统中以ADo接口的形式表现出来。通过ADo访问可以将ADO可以访问的数据源中的数据变成统一的Recordset类型的。本中间件使用了ADO编程接口，是为了让ADO起到一个Wrapper的作用，使各个数据源中的数据通过Wrapper（ADO）变成同构的数据。当然，ADo缺少对半结构化和非结构化数据的支持。本文只考虑到了ADO所支持的数据源。全局概念模式是将各个异构数据源中的数据组合在一起的一种模式。这种模式已经是同构的，并且是将各个数据源的数据组合在一起的，但是输出模式对于全局概念模式来讲不是透明的，换句话说，对于用户来说，全局概念模式是很多同构数据源的组合。全局外模式是建立在全局概念模式之上的一种模式，输出模式对于全局外模式来说，是透明的。对于用户来讲，全局外模式是一个独立的数据源，而感觉不到任何数据的异构性和多数据源性。图2.3视图层次2.2.3 功能模块系统的功能模块图如图2.4所示。功能模块的主要部分包括ParSer（查询分解器），PIanner（计划生成器）和executer（执行器）。Parser的主要任务是将用户的查询语句进行分解，生成查询树。Planner功能模块的作用是根据上一步所生成的各子查询树，产生相应的执行计划，并对计划进行一定程度的优化。Executer功能模块的作用是执行上一步所生成的计划。此外，在PIanner和executer运行时过程中，将参考数据源配置文件，以找到数据源的物理位置。图2.4功能模块2.3 中间件工作流程下面详细介绍一下异构数据库查询中间件系统从接收用户查询命令到最后返回XML的整个过程。2.3.1 用户输入查询请求用户的查询请求是以系统规定的类SQL语句为输入形式的。之所以采用类SQL语句的形式，主要是由于SQL语言易学易用，功能强大，且已经普及。2.3.2 语法树的生成将类SQL语句演变为相应语法树的过程中，使用了Lex和Yacc工具。1.ex是一个词法分析生成器，可以识别出满足原型系统给出的定义文件中的规则的“单词”。YaCC是一个语法分析生成器，负责对LeX生成的“单词”进行语法分析。通过事先定义好的语法规则，最终可以生成一棵语法树C在IeX和yacc帮助下，通过定义文件，可以生成一颗语法树。在语法树中，用户输入的SQL语句根据语法定义文件以树形结构的形式显示出来。图2.5语法树例如，如果用户输入的SQL语句如下：SELECTS.sno,S.sname,SC.ScoreFROMstudentS,StudentCourseSCWHERES.sno=SC.snoands.dept='CS'根据上述语法定义文件，系统将最终生成如图2.5所示的语法树。2.3.3 查询计划树的生成定义1查询计划树(PlanTree)是一棵树B=(V,E),其中，V是节点集，每个非叶节点是类操作符，叶节点为类。在定义1中，类是符合输出模式的数据，如果是关系数据库的话，可以称之为“关系”，但一般被集成的数据不一定都是关系数据库，这里将输出模式中的数据称之为类。一棵查询计划树的结构应该类似于图2.6(b)所示。其中op是指类操作符，c是指类。类操作符主要包括：选择操作SL、投影操作PJ、并UN、差DF、笛卡尔积CP、联接川、分组操作GB。其中分组操作主要是支持聚合函数。下面将介绍如何将yacc生成的语法树变为查询计划树。对于像Select的类SQL语句，主要变换规则如下：(1)将语法树中的FromJist的儿子结点，也就是所有要操作的类，进行笛卡尔积的操作，把结果做为第(2)步的参数；(2)如果有聚合操作，那么把第一步的传来的结果进行聚合操作，然后把运算完的结果当做参数传给第(3)步；(3)把上面传来的参数进行选择(SL)操作，选择操作的参数为语法树中Condition部分。在选择操作之前，先进行优化，把Condition尽量下推，以减少取出的数据，从而减少网络传输量。选择操作完成后，把结果传给第四步；(4)进行投影操作，其参数为SeILiSt部分。下面以图2.6生成的语法树为例来说明对应这棵语法树的查询计划树是如何生成的。将图2.5对应的语法树转换成相应措施的查询计划树，为如图2.6(a)所示。ProjectGuo,snatnc>serwe)ISELECT(3.sw>三SaSnoand8.dept-*CS?)(a)(b)图2.6查询计划树2.3.4 查询计划树的重写当把用户的查询请求转变成一棵查询计划树后，接下来的第二步任务就是要进行查询计划树的整理和重写工作。根据用户请求而直接生成的查询计划树，其叶结点有可能是全局概念模式，而不符合数据库的输出模式要求，也就是说查询计划树的叶结点还不能被单个数据库的包装器所能解释，因此需要整理初始查询计划树并重新生成新的查询计划树。因此，需要将凡是叶结点是全局概念模式的都转变为输出模式。为进行该步工作，采取的主要方法是通过数据字典的记录，把拥有全局概念模式的叶结点都各自转变成一棵子查询计划树。具体的变化形式以图2.7所示为例。图2.7查询重写2.3.5 查询计划树的优化整理和重写查询树的工作完成以后，接下来进行的工作就是优化查询计划树。在一个单数据库系统中，查询优化的目的是为了提高数据库的存取速度，而提高存取速度的关键是考虑数据在存储系统中的排列，取出数据时数据量的大小等因素。在异构数据源集成实现中，数据存储的功能是由各个异构的数据库管理系统自己分别来完成的。那么优化查询计划树的主要目标在于充分利用各个数据库自己的优化功能,把能在数据库管理系统完成的查询不转嫁到集成系统中来完成。虽然查询优化的目的与传统单个数据库系统中的优化目的不相同，但是利用各数据源自带的优化方式，可以很容易实现异构数据库查询任务树的优化目的。本文对实现查询计划树的优化的主要方法总结包括：(1)把对查询任务树中的一元操作尽量下移到叶节点；(2)若查询任务树中有二元操作，应该尽量把操作下推，使这个操作与其操作的类最为接近。这种查询优化对本文后面要完成的查询分解是非常有意义的。只有通过这种优化方式，很多操作就可以直接成块的交给各个异构的数据库系统，而不需要中间件负责完成这部分工作。这样，一方面可以提高数据的存取速度，还可以减少所设计的集成中间件的负担。针对上面所举例子来说，经过查询优化模块的处理可以将查询任务树变形为图2.8(a)的形式。转化成这种形式以后，SELECT(s.dept='CS')这个任务在查询分解时就可以交给包装器和数据源来进行处理了，而不需要中间件再进行处理CProjeet(三0r雌Uuc,ProjectCsiio,SnaUIe,IISRLECr(S,三=SC.S.no)SRUICT<S,三=SC刖。)图2,8杳询分解案例2.3.6 查询分解当查询计划树进行优化完之后，就可以进行分解，把一棵查询计划树分解成几棵小的查询计划树。然后把小的查询计划树交给包装器，包装器把查询计划树变换成其对应的数据库系统能解释的语言，传给异构的数据源，然后返回数据。在查询分解的过程中，目标是希望传输给包装器的是“最大化”的子树，也就是说尽量把查询任务交给包装器和数据源来处理。这样做的优点是：一方面增加查询的并行性，充分利用数据源本身的查询能力；另一方面也可以减少中间件的负担。因此，将查询任务进行再次分解的主要方法总结为下面的过程：后序遍历计划树，如果在遍历的过程中，所有的叶结点都是位于同一个数据源上，则继续遍历，否则遍历停止；取出已成功遍历的最大子树作为“最大化”了的一个子查询计划树，对剩余的查询计划子树继续遍历，直至所有的叶结点被成功地遍历为止。以上面的查询计划树为例，该树分解后形成如图2.8(b)所示的几棵查询子树。当查询树被分解完几棵查询子树之后，就把这些子查询计划树发送到对应包装器当中去。包装器的任务就是将各自接收的查询计划子树变成数据源可以理解的查询语句。对于关系数据库来讲，包装器会把子查询计划树变成SQL语句，其过程是一个由SQL变为查询计划树一个相反的过程。其主要变换过程如下：（1）将查询计划子树中的叶结点作为SQL语句中的FROM语句的一部分；（2）如果查询计划子树中有选择操作，则把其条件部分作为Where语句的一部分；（3）如果查询计划子树中有投影操作，则把投影操作的参数做为Select语句的一部分。生成各关系数据库的SQL语句之后，就可以有相应的关系数据库系统将该语句直接发给数据源，从数据源中查询得到数据。当然，如果数据源不支持SQL语句，而支持其它的语句，那么相应的包装器就会把查询计划树变为相应支持的语句。2.4冲突的解决解决语义冲突是异构数据源集成的一个关键技术难点。异构数据源之间存在着语义上的差别。这些语义上的不同可能在集成中会引起各种矛盾，从简单的名字语义冲突（不同的名字代表相同的概念），到复杂的结构语义冲突（不同的模型表达同样的信息）。语义冲突会带来数据集成结果的冗余，干扰数据处理、发布和交换。所以如何尽量减少语义冲突也是数据集成的一个研究热点。在很多数据集成模型中，冲突的解决是要通过配置文件来解决的，在集成的过程中，要先读取配置文件。本文实现的集成原型系统中吸取了T-SQL（SqISerVer中的SQL语句）的特性，使用扩展SQL语言实现了对冲突在一定程度上的解决。2.4.1 冲突的类型冲突的类型大致可以分为以下几种：（1）命名冲突。由于各用户数据库遵循不同的实体命名习惯，因而存在命名冲突。命名冲突包括同物异名和同名异物；（2）结构冲突。由于对实体对象的使用方式不同，各用户数据库对同一数据对象的描述结构可能存在差异；（3）语义冲突。是指对同一数据对象的表达方式不同，语义冲突包括标量冲突、域冲突和数据冲突等。2.4.2 异构数据库冲突的解决方法一、处理命名冲突标准数据库与用户数据库的字段名是可能发生命名冲突的。命名冲突有两个来源：同物异名和同名异物。分析字段名之间的相似和失配有助于发现命名冲突。当不同名的字段在关系模式中有几个共同的性质与约束时，谓之相似，它们可能是同物异名；反之，当同名的字段在关系模式中有几个不同的性质与约束时，谓之失配，它们可能是异物同名。当检查到同义词或同名异义时，要建立对应的映射规划，去掉二义性。例如：某一用户数据库的关系表有字段：Name标准数据库的关系表有对应字段：姓名某一用户数据库和标准数据库就发生命名冲突，需要建立映射规则：NanIeT姓名。在原型中间件系统中，数据库集成的视图是使用SQL语句来完成的，在SQL语句中，使用AS关键字可以实现语义冲突。其表达如下：Nameas冲突二、处理结构冲突在分析并解决了命名冲突后，命名达到了一致性。分析结构冲突则要对输入模式中的同名概念进行比较，看能否归并它们。例如：某一用户数据库的电话表有字段：firstName和IastName标准数据库的电话表有对应字段：fullName某一用户数据库和标准数据库就发生结构冲突，建立映射规则：IastName+''+firstName->fulIName在SQL语句中要实现该结构的冲突，就要实现对表达式的支持，对于上面的冲突，可以用如下的表达式：IastName+,+firstNameASfullName三、处理语义冲突。语义冲突是指在不同的数据源中用不同的形式来表示同一个内容。比如说，在某一数据库中表示性别的时候，用“男”和“女”，而在标准的数据库中用1和Oo解决这样的问题是需要通过函数以及表达的一个映射来实现这个问题。举例来说：在原有时候时间系统中，都是用15位来表示身份证号，一般在标准的数据库中,将用18位来表示。要实现这种变换，可使中间件系统支持字符串SUbString函数其原型为：substring(string,int1int)substring表示取子串，三个参数是第一个表示原串，第二个参数表示从第几个字符开始，第三个参数表示一共取几个字符。我们就可以用类似SUbString(date,L6)+'19'+substring(code,7,9)+'6'的形式(当然，转换函数可能要比这个复杂，这里只是来说明函数与表达式在解决冲突中的应用)来将一个原来15位的身份证号表示为18位的进行表示。从而解决冲突。总之，通过定义映射规则的方式可以解决大部分数据冲突，而且对于一些系统更新不一致或人为错误引起的语义冲突，数据库维护人员可根据具体情况定义相应的映射规则。第三章中间件的实现异构数据源中间件的程序架构中，主要包括语法树的生成，计划树的生成及优化，执行计划等几个部分，下面分别介绍程序架构以及实现的难点。语法树的生成1.EX和YACC的使用1.eX和YaCC是UNIX两个非常重要的、功能强大的工具。LeX是一种生成扫描器的工具。扫描器是一种识别文本中的词汇模式的程序。这些词汇模式(或者常规表达式)在一种特殊的句子结构中定义。一种匹配的常规表达式可能会包含相关的动作。这一动作可能还包括返回一个标记。当Lex接收到文件或文本形式的输入时，它试图将文本与常规表达式进行匹配.它一次读入一个输入字符，直到找到一个匹配的模式。如果能够找到一个匹配的模式，Lex就执行相关的动作(可能包括返回一个标记)。另一方面，如果没有可以匹配的常规表达式，将会停止进一步的处理，Lex将显示一个错误消息C1.eX和C是强耦合的。一个Jex文件(LeX文件具有JeX的扩展名)通过IeX公用程序来传递，并生成C的输出文件。这些文件被编译为词法分析器的可执行版本。YaeC代表YetAnotherCompiIerCompiler<>YaCC的GNU版叫做BiSOno它是一种工具，将任何一种编程语言的所有语法翻译成针对此种语言的YaCC语法解析器。它用巴科斯范式(BNF,BackusNaUrForm)来书写。按照惯例，Yacc文件有.y后缀。用YaCC来创建一个编译器包括四个步骤：通过在语法文件上运行Yacc生成一个解析器。说明语法：编写一个.y的语法文件(同时说明C在这里要进行的动作)。编写一个词法分析器来处理输入并将标记传递给解析器。这可以使用IeX来完成。编写一个函数，通过调用yyparse()来开始解析，编写错误处理例程(如yyerror()。编译Yacc生成的代码以及其他相关的源文件。将目标文件链接到适当的可执行解析器库。通过对Iex和yacc的使用，系统最后将用户输入的类SQL语句变成一棵语法树。3.1.1 语法树的生成生成的语法树主要保存在下面的结构体中typedefstructQuryLinkitem*qual；/*条件。也就是包括Where子句里的全部内容，以一棵树的形式*/1.inkltem*targetList；显示给用户的字段。也就是SEIEcT语句后面的内容TargetFieId*baseRei；连接的基本表。也就是FROM子句后面的内容Query；条件的存储是以树的结构方式存储的。树的结点的类型是LinkItem类（图3.1）。TargetFieId类是Linkltem的子类（图3.1）0当该结点表示数据库表中某个字段的时候，用TargetFieId类表示。在TargetFieId类中的三个字段分别表示：ClatabaseName:数据库名称tableName:表名fieldname：字段名在LinkItem类中，type字段有以下几种类型。MefineNOTUSE0保留#defineOPERATE1关系谓词ANDORNOT#defineCOMPARE2比较><>=<=I=#defineFIELD3表示数据库的字段#defineVALUE4常量#defineCOMPUTE5计算+-*/#defineFUNCTION6函数substring等下面举例来说明从SQL语句到生成相应语法树的过程C图3.1Linkltem类继承关系图4.2语法树内部结构图3.2语法树实例Parser实现的关键是把各个子句分开，得到每个子句的具体内容，以一个树形结构来存其内容。这一部分在Iex语法分析器和yacc词法分析器的实现。例如，当用户输入以下SQL语句时SELECT*FROMtabi,tab2WHEREtabl.a=tab2.f对应生成的语法树如图3.2所示。3.2 计划树的生成计划树是由查询树所变化而来的。在PlanTree中，其结点的主要结构如图3.3所示。其中Plan结点是父结点，在实际的存储中，使用的是Join类型的结点，SeqSCan类型的结点和SQLSCan类型的结点。Join类型的结点，在计划树中非叶结点，SeqSCan和SQLScan结点都是叶结点。SeqScan与SQLScan类型不同的是SeqScan是开始生成的计划树的结点，而SQLScan是在查询分解以后，将分解后的子树变为一个结点时，所代表的结点类型。«结构P加n+Plan()“ type : NodeTag +qual : l.inkltcm -Icfttrcc : Plan * +ighttree : Plan -rs : RecordsetPtr结构>>Join：-phn : Plan«结构 A>ScqScanscan : ScanJ ba*Rel: THrgField *VV钻aSQLSen+scan:Scan:*-sql:WbqStringJditmbase&me:WbqSrring图3.3Plan结点类图Plan结构中的type表示这个结点是的类型typedefenumNdTagPJOlN,表示连结P_SCAN,表示SeqScan结点P_UNIQUE,去掉重复P-SORT1排序P_SQL表示SQLScan结点JNodeTag；对于如下SQL语句：SeIeCtdbI.tl.fl,db2.t2.f2fromdbl.tl,db2.t2wheredbl.tl.fl=5anddbl.tl.fl=db2.t2.f2对应生成的计划树如图34所示。图3.4计划树内部结构由查询树变为计划树的任务主要由Planner类（图3.5）来完成，其算法流程图如图3.6所示。图3.5Planner类Planner-fromStr:WbqString34PlanneroPlanned)AgCnerHtCPlan(inparser:QUey)：Plan*'IprintP)an(tnplan:Plan*,inutfut:treatn)*-changcToSq1(inplanRoot:Plan*):intAInSanicDaLibHsTinplan:Plan*,inoutdutabascNdinc:WbqString):blprintPlan(inplan:Plan*,inoutfbut:ofstrcam,in_count:int)-nergcToSQLSc<n(inutplan:Plan*):Plan*,*-changeToSQLScan(inoulplan:Plan:)Plan,Planner：generatePlan(Query*parser)图3.6查询树转计划树获取ParSe指针，艮厝旨向语法树的指针.3.3 查询分解的实现查询分解的主要目标是一个计划树的内容变为多个计划树。所以对于属于同一数据源的数据，系统将尽量将其变为一个查询结点，并将查询请求，发送到相应的数据源。把计划树按照数据源进行分解，变为对各个数据源的访问，其基本流程如图3.7所示。voidplanner：ChangeToSQLScan(Plan*&plan)'t图3.7查询分解流程图获得PIan类型的指针检查叶结点是否属于同一数据源的算法流程图如图3.8所示。boolPlanner：:IsInSameDatabase(Plan*plan,WbqString&databaseName)图3.8检查叶结点是否是同一数据源如果以计划树中的某一个结点A为根结点的子计划树中所有的叶结点所关系到的数据源是同一个数据源，那么就可以将以A为根结点的树转化为一个结点。同时，将以A为