数据结构论文2000字

什么数据结构

人们把客观存在的事物以数据的形式存储到计算机中，经历了对现实生活中事物特性的认识、概念化到计算机数据库里的具体表示的逐级抽象过程，即现实世界－概念世界－机器世界三个领域。有时也将概念世界称为信息世界；将机器世界称为存储或数据世界。 一、三个世界 1、现实世界 人们管理的对象存于现实世界中。现实世界的事物及事物之间存在着联系，这种联系是客观存在的，是由事物本身的性质决定的。例如学校的教学系统中有教师、学生、课程，教师为学生授课，学生选修课程并取得成绩。 2、概念世界 概念世界是现实世界在人们头脑中的反映，是对客观事物及其联系的一种抽象描述，从而产生概念模型。概念模型是现实世界到机器世界必然经过的中间层次。涉及到下面几个术语： 实体：我们把客观存在并且可以相互区别的事物称为实体。实体可以是实际事物，也可以是抽象事件。如一个职工、一场比赛等。 实体集：同一类实体的集合称为实体集。如全体职工。注意区分"型"与"值"的概念。如每个职工是职工实体"型"的一个具体"值"。 属性：描述实体的特性称为属性。如职工的职工号，姓名，性别，出生日期，职称等。 关键字：如果某个属性或属性组合的值能唯一地标识出实体集中的每一个实体，可以选作关键字。用作标识的关键字，也称为码。如"职工号"就可作为关键字。 联系：实体集之间的对应关系称为联系，它反映现实世界事物之间的相互关联。联系分为两种，一种是实体内部各属性之间的联系。另一种是实体之间的联系。 3、机器世界 存入计算机系统里的数据是将概念世界中的事物数据化的结果。为了准确地反映事物本身及事物之间的各种联系，数据库中的数据必须有一定的结构，这种结构用数据模型来表示。数据模型将概念世界中的实体，及实体间的联系进一步抽象成便于计算机处理的方式。 数据模型应满足三方面要求：一是能比较真实地模拟现实世界；二是容易为人所理解；三是便于在计算机上实现。数据结构、数据操作和完整性约束是构成数据模型的三要素。数据模型主要包括网状模型、层次模型、关系模型等，它是按计算机系统的观点对数据建模，用于DBMS的实现。 关系数据库采用关系模型作为数据的组织方式。 关系数据库因其严格的数学理论、使用简单灵活、数据独立性强等特点，而被公认为最有前途的一种数据库管理系统。它的发展十分迅速，目前已成为占据主导地位的数据库管理系统。自20世纪80年代以来，作为商品推出的数据库管理系统几乎都是关系型的，例如，Oracle，Sybase，Informix，Visual FoxPro等。 网络数据库也叫Web数据库。促进Internet发展的因素之一就是Web技术。由静态网页技术的HTML到动态网页技术的CGI、ASP、PHP、JSP等，Web技术经历了一个重要的变革过程。Web已经不再局限于仅仅由静态网页提供信息服务，而改变为动态的网页，可提供交互式的信息查询服务，使信息数据库服务成为了可能。Web数据库就是将数据库技术与Web技术融合在一起，使数据库系统成为Web的重要有机组成部分，从而实现数据库与网络技术的无缝结合。这一结合不仅把Web与数据库的所有优势集合在了一起，而且充分利用了大量已有数据库的信息资源。图1-1是Web数据库的基本结构图，它由数据库服务器（Database Server）、中间件（Middle Ware）、Web服务器（Web Server）、浏览器（Browser）4部分组成。 Web数据库的基本结构 它的工作过程可简单地描述成：用户通过浏览器端的操作界面以交互的方式经由Web服务器来访问数据库。用户向数据库提交的信息以及数据库返回给用户的信息都是以网页的形式显示。 1 Internet技术与相关协议 Internet技术在Web数据库技术中扮演着重要的角色。Internet（因特网）专指全球最大的、开放的、由众多网络相互连接而成的计算机网络，并通过各种协议在计算机网络中传递信息。TCP/IP协议是Internet上使用的两个最基本的协议。因此也可以说Internet是全球范围的基于分组交换原理和TCP/IP协议的计算机网络。它将信息进行分组后，以数据包为单位进行传输。Internet在进行信息传输时，主要完成两项任务。 （1）正确地将源信息文件分割成一个个数据包，并能在目的地将源信息文件的数据包再准确地重组起来。 （2）将数据包准确地送往目的地。 TCP/IP协议的作用就是为了完成上述两项任务，规范了网络上所有计算机之间数据传递的方式与数据格式，提供了数据打包和寻址的标准方法。 1．TCP/IP协议 TCP协议（Transmission Control Protocol，传输控制协议）规定了分割数据和重组数据所要遵循的规则和要进行的操作。TCP协议能保证数据发送的正确性，如果发现数据有损失，TCP将重新发送数据。 2．IP协议 在Internet上传送数据往往都是远距离的，因此在传输过程中要通过路由器一站一站的转接来实现。路由器是一种特殊的计算机，它会检测数据包的目的地主机地址，然后决定将该数据包送往何处。IP协议（Internet Protocol，网际协议）给Internet中的每一台计算机规定了一个地址，称为IP地址。IP地址的标准是由4部分组成（例如11），其中前两部分规定了当前使用网络的管理机构，第3部分规定了当前使用的网络地址，第4部分规定了当前使用的计算机地址。 Internet上提供的主要服务有E-mail、FTP、BBS、Telnet、WWW等。其中WWW（World Wide Web，万维网）由于其丰富的信息资源而成为Internet最为重要的服务。

有图片的，这里发不了图片，满意我的论文加分后联系我，我发给你。　　基于关系数据库的模式匹配技术研究　　摘 要 随着 网络 技术的 发展 ，信息处理需要对大量的、异构的数据源的数据进行统一存取，多源异构数据的集成 问题 就显得十分重要。而模式匹配是数据集成领域的一个基本技术。文章提出一种解决关系数据库语义冲突问题的模式匹配技术，以实现异构数据的共享与互操作。　　关键词 数据集成；模式匹配；语义冲突　　1 引言　　随着 计算 机及网络技术的快速发展，网络上的各种信息以指数级爆炸性增长，成为了一个巨大的信息库，同时各 企业 单位开发了大量的软硬件平台各异的 应用 系统，在各种应用系统下又积累了丰富的数据资源。这样就形成了成千上万个异构的数据源，多为传统的关系数据库数据。这些数据资源由于软硬件平台各异、数据模型各异而形成了异构数据，使各数据源间的互操作变得复杂。为了更好地利用这些异构信息，以及不造成企业应用系统的重复建设和数据资源的浪费，模式匹配技术吸引了众多关注。本文针对模式匹配过程中存在的语义冲突进行分类，并提出了相应的解决策略，以达到异构数据源的共享和互操作。　　2 模式匹配中的冲突问题　　在数据集成领域中，由于数据源系统多是独立开发，数据源是相对自治的，因此描述数据的数据模型或存储结构经常会出现模式的不一致，数据源的自治性和数据源模式的异构性使数据源在共享和互操作上存在了语义冲突。这些正是模式匹配的焦点问题，它们形式上的性质使得人们很容易想到要用模式匹配去解决逻辑、语义和知识的描述问题。　　对于描述模式匹配中的语义冲突有两种较有代表性的分类[4]。第一种分类将冲突分为异类冲突、命名冲突、语义冲突和结构冲突。第二种分类主要是对第一类异类冲突概念的一个细致的改进，但和其它分类仍有细微的不同，它把异类冲突看作是语义不一致的一类(如语义冲突)，把冲突分为命名冲突、域冲突、元数据冲突、结构冲突、属性丢失和硬件/软件不同。　　模式匹配是一项复杂而繁重的任务，所能集成的数据源越来越多，上述冲突情况也会越来越普遍，想解决所有的模式冲突是不现实的。本文主要解决关系数据模式之间的语义冲突。　　3 模式匹配中的语义冲突　　本文所提出的模式匹配 方法 是根据关系数据库的特点设计的。关系数据库中关系的基本单位是属性，属性本身就包含着语义信息，因此异构数据源语义相似性就围绕着数据源模式中的属性来进行，并在匹配的过程中解决异构数据源模式之间的一系列语义冲突。　　1 语义匹配体系结构　　本文提出的语义匹配体系结构采用数据集成中的虚拟法数据集成系统的典型体系结构，采用将局部模式匹配到全局模式的语义匹配体系结构，自下而上地建立全局模式。首先进行模式转化，消除因各种局部数据模式之间的差异所带来的 影响 ，解决各种局部模式之间的语义冲突等，然后在转化后的模式的基础上进行模式匹配，其主要手段是提供各数据源的虚拟的集成视图。　　数据仍保存在各数据源上，集成系统仅提供一个虚拟的集成视图和对该集成视图的查询的处理机制。系统能自动地将用户对集成模式的查询请求转换成对各异构数据源的查询。在这种体系结构中，中间层根本不实际存储数据，当客户端发出查询请求时，仅是简单地将查询发送到适当的数据源上。由于该方法不需要重复存储大量数据，并能保证查询到最新的数据，因此比较适合于高度自治、集成数量多且更新变化快的异构数据源集成。　　本文中的语义匹配的体系结构如图1所示。　　2 关系数据库模式中语义冲突问题分类及其解决策略　　大多数数据库系统提供了一套概念结构来对现实世界的数据进行建模。每一个概念结构被认为是一个类型，它可以是一种复杂类型或一种基本类型。类型和它所表示的数据间的联系就称为语义[3]。　　在关系数据库中，一个关系模式是一个有序对(R，c)，其中R为模式所指向的关系(表)的名称，而c则为具有不同名称的属性的有限集。同时，属性也是一个有序对(N，D)，其中N为属性的名称，而D则为一个域。可以看出关系模式的基本单位是属性。属性本身就包含着语义信息，因此模式语义相似性就围绕模式中的属性来进行，并在模式匹配的过程中解决异构数据库模式之间的一系列语义冲突。　　根据语义的定义，在关系数据库系统中，语义系统是由模式、模式的属性、模式中属性之间的联系和模式间的属性之间的联系构成。这里将语义分为3级：模式级、属性级和实例级。下面将异构模式中存在的语义冲突问题进行了分类，并阐述了各种语义冲突的解决策略：　　1)模式级冲突　　(1)关系命名冲突。包括关系名同义词和关系名同形异义词。前者进行换名或建立关系名同义词表以记载该类冲突；后者进行换名或建立关系名同形异义词表以记载该类冲突。　　(2)关系结构冲突。分为包含冲突和相交冲突。包含冲突是指在含义相同的两个关系 R1 和 R2 中一个关系的属性集是另一个的属性子集。相交冲突是指两关系属性集的交不为空，我们用 attrset 代表关系的属性集。对包含冲突：①如果两个关系的属性集相同即attrset(R1)=attrset(R2)，则合并这两个对象，Merge(R1， R2)into R3；②如果 attrset(R1) attrset(R2)，则 attrset(R2')=attrset(R2)－attrset(R1)，attrset(R1') = attrset(R1)；③对相交冲突：通常概括语义进行如下解决：generalize(R1，R2)其中 attrset(R3)=attrset(R1)∩attrset(R2)， attrset(R1')= attrset(R1)－attrset(R3)；attrset(R2')=attrset(R2)－attrset(R3)。　　(3)关系关键字冲突：两个含义相同的关系具有不同的关键字约束。包括候选关键字冲突和主关键字冲突。解决候选关键字冲突的 方法 是，将两关系的候选关键字的交集作为两关系的候选关键字；解决主关键字冲突的方法是，从两关系的公共候选关键字中选一个分别作为两关系的主关键字。　　(4)多对多的关系冲突：两个数据库中用不同数量的关系来表达现实世界的相同语义信息，就产生了多对多的关系冲突，这种冲突分3种：一对多，多对一和多对多。解决方法是在表示相同语义信息的数据库中关系之间建立映射来表示多对多的关系。　　2)属性级冲突　　(1)属性命名冲突：分属性名同义词冲突和属性名同形异义词。前者的解决方法是，换名或建立属性名同义词字典；后者的解决方法是，换名或建立属性名同形异义词字典。　　(2)属性约束冲突：分属性类型冲突和属性长度冲突两种。当在两个相关的关系R1和R2的属性N1和N2具有不同的属性类型时，就发生属性类型冲突。解决方法是在全局模式中将发生属性类型冲突的属性统一到某种属性类型。对属性长度的解决方法是，在全局模式中将发生属性长度类型冲突的属性对统一定义为最大者就可。　　(3)多对多的属性冲突：两个数据库中的关系分别用不同数量的属性来表达现实世界中相同的语义信息时，就发生了多对多的属性冲突，这种冲突分3种：一对多，多对一和多对多。解决方法是在表示相同语义信息的数据库中关系的属性之间建立映射来表示这种多对多的关系。　　3)实例级冲突　　(1)不兼容关系实例冲突：当含义相同的数据项在不同的数据库中存在不一致的数据值时就发生了不兼容关系实例冲突。其解决方法是：将关系实例的最近修改作为关系实例冲突部分的值，但不能保证数据的正确性。　　(2)关系实例表示冲突：关系实例表示冲突是指用不兼容的符号、量纲和精度来表示相关关系实例中等价的数据元素，主要包括表达冲突、量纲冲突和精度冲突。表达冲突是指在两个相关的关系R1和R2中含义相同的属性N1和N2具有不同的数据表达时，这种冲突使用语义值的概念来解决，即将表示同一概念的多种表达在全局数据中进行统一即可。量纲冲突是指在两个相关的关系R1和R2和中含义相同的属性N1和N2具有不同的量纲表示。量纲冲突也可以语义值加以解决，解决过程如下：分别定义发生量纲冲突的局部数据源的语义值模式和语义值说明，然后再定义全局数据模式中相应的语义值模式和语义值说明，将发生量纲冲突的属性值在全局模式中进行统一。精度冲突是指在两个相关的关系 R1 和 R2 中含义相同的属性具有不同的精度。其解决方法是在全局模式中将发生精度冲突的数据项定义为最高精度即可。　　4 总结　　本文针对异构数据源管理自治和模式异构的特点，提出了数据源集成模式匹配的体系结构，制定了匹配策略， 研究 了基于语义的模式匹配过程。以关系模式为 参考 模式，对异构数据源关系模式间可能存在的语义冲突 问题 进行了分类，并阐述了解决这些语义冲突的策略。　　参考 文献　　[1] Bergamaschi S， Castano S， Vincini M Semantic Integration of Semistructured and Structured Data Sources [J] SIGMOD Record， 1999， 28(1)： 54-　　[2] Li W， Clifton C， Liu S Database Integration Using Neural Network： Implementation and Experiences [J] Knowledge and Information Systems， 2000， 2(1)　　[3] Reddy M P， Prasad B E， GReddy P A Methodology for Integration of Heterogeneous Databases [J] Information System， 1999，24(5)　　[4] Rahm E，Bernstein PA Survey of Approaches to Automatic Schema Matching[J] The International Journal on Very Large Data Bases (VLDB)，2001，10(4)：334-　　[5] 孟小峰，周龙骧，王珊数据库技术 发展 趋势[J]软件学报，2004，15(12)：1822-1835　　[6] 邓志鸿，唐世渭，张铭，等Ontology研究综述[J]北京大学学报( 自然 科学 版)，2002，38(5)：730-738　　[7] 郭志鑫基于本体的文档引文元数据信息抽取[J]微 计算 机信息，2006，22(6-3)　　相关文献：　　基于XML的多数据库系统集成数据模型 - 华中科技大学学报：自然科学版 - 卢晓蓉 陈传波 等　　基于CORBA和XML的多数据库系统研究 - 郑州轻工业学院学报：自然科学版 - 张素智,钱慎一,卢正鼎,　　集成数据库和文件系统的多数据库事务模型 - 华中理工大学学报 - 卢正鼎 肖卫军　　基于主动规则对象的分布式多数据库系统集成 - 小型微型计算机系统 - 胡华,高济,　　基于CORBA的多数据库系统 - 计算机科学 - 石祥滨 张斌　　基于XML的文件系统与多数据库系统的集成 - 小型微型计算机系统 - 卢正鼎 李兵 等　　基于CORBA／XML的多数据库系统的研究与实现 - 计算机研究与发展 - 卢正鼎 李兵 等　　多数据库系统集成平台CMDatabase体系结构 - 计算机工程 - 魏振钢 郭山清 贾忠伟　　多数据库系统的数据模式集成与查询处理 - 电脑开发与应用 - 陶世群　　数据库网格：基于网格的多数据库系统 - 计算机工程与应用 - 任浩 李志刚 肖侬　　高校学生收费系统基于多数据库系统集成的一种实践 - 昆明冶金高等专科学校学报 - 杨滨生,蒋涛勇,张中祥,谢静静,　　基于RDBMS的地理信息集成数据库系统 - 计算机工程 - 江崇礼 王丽佳 等　　基于CORBA的异构数据库系统集成模型的研究 - 现代计算机：下半月版 - 陈刚　　基于分布式对象技术的多数据库系统 - 计算机工程与科学 - 韩伟红 隋品波　　基于CORBA的多数据库系统互操作技术 - 计算机科学 - 肖明,肖毅,