层次模型和网状模型等非关系模型中，结点用来存储记录，记录间的联系用指针来表达；而..

免费智能真题库 > 历年试卷 > 数据库系统工程师 > 2015年上半年数据库系统工程师上午试卷综合知识

第47题

知识点：基本的数据模型层次模型查找关系模型网状模型指针

关键词：遍历层次模型关系模型指针章/节：数据库技术基础

层次模型和网状模型等非关系模型中，结点用来存储记录，记录间的联系用指针来表达；而关系模型中记录间的联系用（47）来描述，查找相关联记录需要进行记录遍历，为提高查找效率，可以建立（48）。

A. 主码

B. 关系

C. 数据模型

D. 概念模型

相关试题：数据模型

更多>

第62题 2018年上半年

34%

下图所示的扩展E-R图中，属性“电话”属于（62），在逻辑结构设计中，该图中的（63）属性将不会被转换到关系模式中。<..

第59题 2016年上半年

79%

以下关于扩展E-R图设计的描述中，正确的是（59）。

第34题 2018年上半年

33%

假设某企业信息管理系统中的5个实体：部门（部门号，部门名，主管，电话），员工（员工号，姓名，岗位号，电话），项目（项目号，..


知识点讲解
· 基本的数据模型 · 层次模型 · 查找 · 关系模型 · 网状模型 · 指针

基本的数据模型

层次模型（Hierarchical Model）

层次模型采用树型结构表示数据与数据间的联系。在层次模型中，每个结点表示一个记录类型（实体），记录之间的联系用结点之间的连线表示，并且根结点以外的其他结点有且仅有一个双亲结点。上层和下一层类型的联系是1：n联系（包括1:1联系）。

网状模型（Network Model）

采用网络结构表示数据与数据间联系的数据模型称为网状模型（Network Model）。在网状模型中，允许一个以上的节点无双亲，一个节点可以有多于一个的双亲。

网状模型（也称DBTG模型）是一个比层次模型更具有普遍性的数据结构，是层次模型的一个特例。网状模型可以直接地描述现实世界，因为去掉了层次模型的两个限制，允许两个节点之间有多种联系（称之为复合联系）。需要说明的是，网状模型不能表示记录之间的多对多联系，需要引入联结记录来表示多对多联系。

网状模型中的每个节点表示一个记录类型（实体），每个记录类型可以包含若干个字段（实体的属性），节点间的连线表示记录类型之间一对多的联系。层次模型和网状模型的主要区别如下：

（1）网状模型中子女节点与双亲节点的联系不唯一，因此需要为每个联系命名。

（2）网状模型允许复合链，即两个节点之间有两种以上的联系。

通常，网状数据模型没有层次模型那样严格的完整性约束条件，但DBTG在模式DDL中提供了定义DBTG数据库完整性的若干概念和语句，主要有：

（1）支持记录码的概念。码能唯一标识记录的数据项的集合。

（2）保证一个联系中双亲记录和子女记录之间是一对多联系。

（3）以支持双亲记录和子女记录之间的某些约束条件。例如，当插入一条选课记录“1014，C2，98”时，只有学生实体中存在学号为“1014”的学生记录，课程实体存在课程号为“C2”的课程，系统才认为是合法的操作。

网状模型的主要优点是能更为直接地描述现实世界，具有良好的性能，存取效率高。其主要缺点是结构复杂。例如，当应用环境不断扩大时，数据库结构就变得很复杂，不利于最终用户掌握。编制应用程序难度比较大。DBTG模型的DDL、DML语言复杂，记录之间的联系是通过存取路径来实现的，因此程序员必须了解系统结构的细节，增加了编写应用程序的负担。

关系模型（Relational Model）

关系模型（Relation Model）是目前最常用的数据模型之一。关系数据库系统采用关系模型作为数据的组织方式，在关系模型中用表格结构表达实体集以及实体集之间的联系，其最大特色是描述的一致性。关系模型是由若干个关系模式组成的集合。一个关系模式相当于一个记录型，对应于程序设计语言中类型定义的概念。关系是一个实例，也是一张表，对应于程序设计语言中变量的概念。给定变量的值随时间可能发生变化，类似地，当关系被更新时，关系实例的内容也随时间发生了变化。

面向对象数据模型（Object Oriented Model）

面向对象数据模型（Object Oriented Model）的核心概念如下：

（1）对象和对象标识（OID）。对象是现实世界中实体的模型化，与记录、元组的概念相似，但远比它们复杂。每一个对象都有一个唯一的标识，称为对象标识。对象标识不等于关系模式中的记录标识，OID是独立于值的，全系统唯一的。

（2）封装（encapsulate）。每一个对象是状态（state）和行为（behavior）的封装。对象的状态是该对象属性的集合，对象的行为是在该对象状态上操作的方法（程序代码）的集合。被封装的状态和行为在对象外部是看不见的，只能通过显式定义的消息传递来访问。

（3）对象的属性（object attribute）。对象的属性描述对象的状态、组成和特性，对象的某个属性可以是单值或值的集合。对象的一个属性值本身在该属性看来也是一个对象。

（4）类和类层次（class and class hierarchy）。

①类。所有具有相同属性和方法集的对象构成了一个对象类。任何一个对象都是某个对象类的一个实例（instance）。对象类中属性的定义域可以是任何类，包括基本类，如整型、实型和字串等；一般类，包含自身属性和方法类本身。

②类层次。所有的类组成了一个有根有向无环图，称为类层次（结构）。一个类可以从直接／间接祖先（超类）中继承（inherit）所有的属性和方法，该类称为子类。

（5）继承（inherit）。子类可以从其超类中继承所有属性和方法。类继承可分为单继承（即一个类只能有一个超类）和多重继承（即一个类可以有多个超类）。

面向对象数据模型比网络、层次、关系数据模型具有更加丰富的表达能力。由于面向对象模型的丰富表达能力，模型相对复杂。有关面向对象分析及设计方面的内容可参考第10章。

层次模型

层次模型（Hierarchical Model）采用树型结构表示数据与数据间的联系。在层次模型中，每一个节点表示一个记录类型（实体），记录之间的联系用节点之间的连线表示，并且根节点以外的其他节点有且仅有一个双亲节点。

层次模型不能直接表示多对多的联系。若要表示多对多的联系，可采用如下两种方法。

（1）冗余节点法。两个实体的多对多联系转换为两个一对多联系。该方法的优点是节点清晰，允许节点改变存储位置。缺点是需要额外的存储空间，有潜在的数据不一致性。

（2）虚拟节点分解法。将冗余节点转换为虚拟节点。虚拟节点是一个指引元，指向所代替的节点。该方法的优点是减少对存储空间的浪费，避免数据不一致性。缺点是改变存储位置可能引起虚拟节点中指针的修改。

层次模型的特点是记录之间的联系通过指针实现，比较简单，查询效率高。

层次模型的缺点是只能表示1:n的联系，尽管有许多辅助手段实现m:n的联系，但较复杂不易掌握；由于层次顺序严格和复杂，插入删除操作是限制比较多，导致应用程序编制比较复杂。1968年，美国IBM公司推出的IMS系统（信息管理系统）是典型的层次模型系统，20世纪70年代在商业上得到了广泛的应用。

查找

1）顺序查找

顺序查找又称线性查找，顺序查找的过程是从线性表的一端开始，依次逐个与表中元素的关键字值进行比较，如果找到其关键字与给定值相等的元素，则查找成功；若表中所有元素的关键字与给定值比较都不成功，则查找失败。

2）折半查找

折半查找的过程是先将给定值与有序线性表中间位置上元素的关键字进行比较，若两者相等，则查找成功；若给定值小于该元素的关键字，那么选取中间位置元素关键字值小的那部分元素作为新的查找范围，然后继续进行折半查找；如果给定值大于该元素的关键字，那么选取比中间位置元素关键字值大的那部分元素作为新的查找范围，然后继续进行折半查找，直到找到关键字与给定值相等的元素或查找范围中的元素数量为零时结束。

3）分块查找

在分块查找过程中，首先将表分成若干块，每一块中关键字不一定有序，但块之间是有序的。此外，还建立了一个索引表，索引表按关键字有序。分块查找过程需分两步进行：先确定待查记录所在的块；然后在块中顺序查找。

4）哈希表及其查找

根据设定的哈希函数H（key）和处理冲突的方法，将一组关键字映射到一个有限的连续地址集上，并以关键字在地址集中的像作为记录在表中的存储位置，这种表称为哈希表，也称散列表。这一过程所得到的存储位置称为散列地址，由此形成的查找方法称为散列查找。

关系模型

我们先学习几个相关的基本概念。

（1）域：一组具有相同数据类型的值的集合。

（2）笛卡儿积：给定一组域D₁，D₂，…，D_n，这些域中可以有相同的。它们的笛卡儿积为：D₁×D₂×…×D_n={（d₁，d₂，…，d_n）|d_j∈D_j，j=1，2，…，n}。其中每一个元素（d₁，d₂，…，d_n）叫作一个n元组（简称为元组）。元组中的每一个值d_j叫作一个分量。

（3）关系：D₁×D₂×…×D_n的子集叫作在域D₁，D₂，…，D_n上的关系，用R（D₁，D₂，…，D_n）表示。这里R表示关系的名字，n是关系的目或度。

关系中的每个元素是关系中的元组，通常用t表示。关系是笛卡儿积的子集，所以关系也是一个二维表，表的每行对应一个元组，表的每列对应一个域。由于域可以相同，为了加以区分，必须对每列起一个名字，称为属性。

若关系中的某一属性组（一个或多个属性）的值能唯一地标识一个元组，则称该属性组为候选码（候选键）。若一个关系有多个候选码，则选定其中一个作为主码（主键）。主码的所有属性称为主属性。不包含在任何候选码中的属性称为非码属性（非主属性）。在最简单的情况下，候选码只包含一个属性。在最极端的情况下，关系模式所有属性的组合构成关系模式的候选码，称为全码。

关系可以有三种类型：基本关系（基本表、基表）、查询表和视图表。基本表是实际存在的表，它是实际存储数据的逻辑表示；查询表是查询结果对应的表；视图表是由基本表或其他视图表导出的表，是虚表，不对应实际存储的数据。

基本关系具有以下6条性质：

（1）列是同质的，即每一列中的分量是同一类型的数据，来自同一个域。

（2）不同的列可出自同一个域，称其中的每一列为一个属性，不同的属性要给予不同的属性名。

（3）列的顺序无所谓，即列的次序可以任意交换。

（4）任意两个元组不能完全相同。但在大多数实际关系数据库产品中，例如Oracle等，如果用户没有定义有关的约束条件，它们都允许关系表中存在两个完全相同的元组。

（5）行的顺序无所谓，即行的次序可以任意交换。

（6）分量必须取原子值，即每一个分量都必须是不可分的数据项。

关系的描述称为关系模式，一个关系模式应当是一个五元组，它可以形式化地表示为：R（U，D，DOM，F）。其中R为关系名，U为组成该关系的属性名集合，D为属性组U中属性所来自的域，DOM为属性向域的映像集合，F为属性间数据的依赖关系集合。关系模式通常可以简记为R（A₁，A₂，…，A_n）。其中R为关系名，A₁，A₂，…，A_n为属性名。

关系实际上就是关系模式在某一时刻的状态或内容。也就是说，关系模式是型，关系是它的值。关系模式是静态的、稳定的，而关系是动态的、随时间不断变化的，因为关系操作在不断地更新着数据库中的数据。但在实际当中，常常把关系模式和关系统称为关系，读者可以从上下文中加以区别。

在关系模型中，实体以及实体间的联系都是用关系来表示。在一个给定的现实世界领域中，相应于所有实体及实体之间的联系的关系的集合构成一个关系数据库。

关系数据库也有型和值之分。关系数据库的型也称为关系数据库模式，是对关系数据库的描述，是关系模式的集合。关系数据库的值也称为关系数据库，是关系的集合。关系数据库模式与关系数据库通常统称为关系数据库。

网状模型

采用网状结构表示数据与数据间联系的数据模型称为网状模型。在网状模型中，允许一个以上的节点无双亲，一个节点可以有多于一个的双亲。

网状模型是一个比层次模型更具普遍性的数据结构，是层次模型的一个特例。它去掉了层次模型的两个限制，并允许两个节点之间有多种联系（称之为复合联系）。

网状模型中的每个节点表示一个记录类型（实体），每个记录类型可以包含若干个字段（实体的属性），节点间的连线表示记录类型之间一对多的联系。

网状模型在模式DDL中提供了定义DBTG数据库完整性的若干概念和语句，主要有：支持记录码的概念，保证一个联系中双亲记录和子女记录之间是一对多的联系，支持双亲记录和子女记录之间的某些约束条件。

网状模型的优点是：能够更为直接地描述现实世界，具有良好的性能，存取效率高。

网状模型的缺点是：结构比较复杂。随着应用环境的扩大，数据库的结构变得越来越复杂，不利于最终用户掌握，编制应用程序难度比较大。

指针

简单来说，指针是内存单元的地址，它可能是变量的地址、数组空间的地址，或者是函数的入口地址。存储地址的变量称为指针变量，简称为指针。指针是C语言中最有力的武器，能够为程序员提供极大的编程灵活性。

指针的定义

指针类型的变量是用来存放内存地址的，下面是两个指针变量的定义：

变量ptr1和ptr2都是指针类型的变量，ptr1用于保存一个整型变量的地址（称ptr1指向一个整型变量），ptr2用于保存一个字符型变量的地址（称ptr2指向一个字符变量）。

使用指针时需明确两个概念：指针对象和指针指向的对象。指针对象是明确命名的指针变量，如上例中的ptr1、ptr2；指针指向的对象是另一个变量，用“*”和指针变量联合表示，如上例中的整型变量*ptr1和字符变量*ptr2，由于上面的定义中未对ptr1和ptr2进行初始化，它们的初始值是随机的，也就是*ptr1和*ptr2可视为并不存在。

借助指针变量可以针对指定的地址进行操作，例如，设置地址为0x1234开始的存储空间存放一个整型变量的值0x5678，代码如下。

定义指针变量时需要在每个变量名前加“*”，如下：

指针的加减运算

对指针变量进行加减运算时，是以指针所指向的数据类型存储宽度为单位计算的。

例如，下面的指针p和s在进行加1运算时有不同的结果。

p+1实际上是按照公式p+1*sizeof（int）来计算的，s+1则是按照s+1*sizeof（char）进行计算。

空指针

标准预处理宏NULL（它的值为0，称为空指针常量）常用来表示指针不指向任何内存单元，可以把NULL赋给任意类型的指针变量，以初始化指针变量。例如：

需要注意：全局指针变量会被自动初始化为NULL，局部指针变量的初始值是随机的。编程时常见的一个错误是没有给指针变量赋初值。未初始化的指针变量可能表示了一个非法的地址，导致程序运行时出现内存访问错误，从而使程序异常终止。

“&”和“*”

“&”称为地址运算符，其作用是获取变量的地址。“*”称为间接运算符，其作用是获取指针所指向的变量。

例如，下面的语句“pa=&b；”执行后，变量pa就得到了b的地址（称为指针pa指向b），*pa表示pa指向的变量（也就是变量b）。

例如：

在上面的例子中，通过指针pa修改了变量b的值，本质上是对b的间接访问。在程序中通过指针访问数据对象或函数对象，提供了运算处理上的灵活性。

如果指针变量的值是空指针或者是随机的，通过指针来访问数据就是一种错误（在编译时报错，或者在运行时发生异常），下面的语句会产生一个运行时错误（vp可能表示了一个非法的地址，因此它所指向的对象*vp也是非法的）。

void*类型可以与任意的数据类型匹配。void指针在被使用之前，必须转换为明确的类型。例如：

指针与堆内存

在程序运行过程中，堆内存能够被动态地分配和释放，在C程序中通过malloc（或calloc、realloc）和free函数实现该处理要求。

例如：

在堆中分配的内存块的生存期是由程序员自己控制的，应在程序中显式地释放。例如：

注意：指针为空（指针值为0或NULL）时表示不指向任何内存单元，因此释放空指针没有意义。

因为内存资源是有限的，所以若申请的内存块不再需要就及时释放。如果程序中存在未被释放（由于丢失其地址在程序中也不能再访问）的内存块，则称为内存泄漏。持续的内存泄漏会导致程序性能降低，甚至崩溃。嵌入式系统存储空间非常有限，一般情况下应尽量采用静态存储分配策略。

指针与数组

通过指针访问数组元素

在C程序中，常利用指针访问数组元素，数组名表示数组在内存中的首地址，即数组中第一个元素的地址。可以通过下标访问数组元素，也可以通过指针访问数组元素。

例如：

数组arr的元素可以用*ptr、*（ptr+1）、*（ptr+2）、*（ptr+3）来引用。

数组名是常量指针，数组名的值不能改变，因此arr++是错误的，而ptr++是允许的。例如，下面的代码通过修改指针ptr来访问数组中的每个元素。

一般情况下，一个int型变量占用4个字节的内存空间，一个char型变量占用一个字节的空间，所以str是字符指针的话，str++就使str指向下一个字符；而整型指针ptr++则使ptr指向下一个int型整数，即指向数组的第二个元素。

可以用指针访问二维数组元素。例如，对于一个m行、n列的二维整型数组，其定义为

由于二维数组元素在内存中是以线性序列方式存储的，且按行存放，所以用指针访问二维数组的关键是如何计算出某个二维数组元素在内存中的地址。二维数组a的元素a[i][j]（ii][j]之前的元素所占空间形成的偏移量，概念上表示为a+（i×n+j）*sizeof（int），在程序中需要表示为（&a[0][0]+i×n+j）。

通过指针访问字符串常量

可将指针设置为指向字符串常量（存储在只读存储区域），通过指针读取字符串或其中的字符。例如，

不允许在程序运行过程中修改字符串常量。例如，下面代码试图通过修改字符串的第2个字符将“hello”改为“hallo”，程序运行时该操作会导致异常，原因是str指向的是字符串常量“hello”，该字符串在运行时不能被修改。

如果用const进行修饰，这个错误在编译阶段就能检查出来，修改如下：

指针数组

如果数组的元素类型是指针类型，则称之为指针数组。下面的ptrarr是一维数组，数组元素是指向整型变量的指针。

若需要动态生成二维整型数组，则传统的处理方式是先设置一个指针数组arr2，然后将其每个元素的值（指针）初始化为动态分配的“行”。

指针运算

在C程序中，对指针变量加一个整数或减一个整数的含义与指针指向的对象有关，也就是与指针所指向的变量所占用存储空间的大小有关。例如：

常量指针与指针常量

常量指针是指针变量指向的对象是常量，即指针变量可以修改，但是不能通过指针变量来修改其指向的对象。例如，

指针常量是指针本身是个常量，不能再指向其他对象。

在定义指针时，如果在指针变量前加一个const修饰符，就定义了一个指针常量，即指针值是不能修改的。

指针常量定义时被初始化为指向整型变量d。p本身不能修改（即p不能再指向其他对象），但它所指向变量的内容却可以修改，例如，*p=5（实际上是将d的值改为5）。

区分常量指针和指针常量的关键是“*”的位置，如果const在“*”的左边，则为常量指针，如果const在“*”的右边则为指针常量。如果将“*”读作“指针”，将const读作“常量”，内容正好符合。对于定义“int const *p；”p是常量指针，而定义“int* const p；”p是指针常量。

指针与函数

指针可以作为函数的参数或返回值。

指针作为函数参数

函数调用时，用指针作为函数的参数可以借助指针来改变调用函数中实参变量的值。以下面的swap函数为例进行说明，该函数的功能是交换两个整型变量的值。

若有函数调用swap（&x，&y），则swap函数执行后两个实参x和y的值被交换。函数中参与运算的值不是pa、pb本身，而是它们所指向的变量，也就是实参x、y（*pa与x、*pb与y所表示的对象相同）。在调用函数中，是把实参的地址传送给形参，即传送&x和&y，在swap函数中指针pa和pb并没有被修改。

如果在被调用函数中修改了指针参数的值，则不能实现对实参变量的修改。例如，下面函数get_str中的错误是将指针p指向的目标修改了，从而在main中调用get_str后，ptr的值仍然是NULL。