关系数据结构及形式化定义

关系数据结构及形式化定义在关系模型中，无论是实体还是实体之间的联系均由单一的结构类型即关系（表）来表示。前面己经非形式化地介绍了关系模型及有关的基本概念。关系模型是建立在集合代数的基础上的，这里从集合论角度给出关系数据结构的形式化定义。一关系l．域（Domain）定义1域是一组具有相同数据类型的值的集合。例如，自然数、整数、实数、长度小于25字节的字符串集合、{0，l}、大于等于0且小于等于100的正整数等，都可以是域。2.笛卡尔积（CartesianProduct）定义2给定一组域D1，D2，…，Dn，这些域中可以有相同的。D1，D2，…，Dn的笛卡尔积为：D1×D2×…×Dn={（d1，d2，…，dn）|di∈Di，i=l，2，…，n}其中每一个元素（d1，d2，…，dn）叫作一个n元组（n-tuple）或简称元组（Tuple）。元素中的每一个值di叫作一个分量（Component）。若Di（i=l，2，…，n）为有限集，其基数（Cardinalnumber）为mi（i=l，2，…，n），则D1×D2×…×Dn的基数M为：笛卡尔积可表示为一个二维表。表中的每行对应一个元组，表中的每列对应一个域。例如给出三个城：D1=导师集合SUPERVISOR=张清玫，刘逸D2=专业集合SPECIALITY=计算机专业，信息专业D3=研究生集合POSTGRADUATE=勇，刘晨，王敏则D1，D2，D3的笛卡尔积为：D1×D2×D3={（张清玫，计算机专业，李勇），（张清玫，计算机专业，刘晨），（张清玫，计算机专业，王敏），（张清玫，信息专业，李勇），（张清玫，信息专业，刘晨），（张清玫，信息专业，王敏），（刘逸，计算机专业，李勇），（刘逸，计算机专业，刘晨），（刘逸，计算机专业，王敏），（刘逸，信息专业，李勇），（刘逸，信息专业，刘晨），（刘逸，信息专业，王敏）}其中（张清玫，计算机专业，李勇）、（张清玫，计算机专业，刘晨）等都是元组。张清玫、计算机专业、李勇、刘晨等都是分量。该笛卡尔积的基数为2×2×3=12，也就是说，D1×D2×D3一共有2×2×3=12个元组。这12个元组可列成一张二维表（如表l）。表1D1，D2，D3的笛卡尔积3.关系（Relation）定义3D1×D2×…×Dn的子集叫作在域D1，D2，…，Dn上的关系，表示为R（D1，D2，…，Dn）这里R表示关系的名字，n是关系的目或度（Degree）。关系中的每个元素是关系中的元组，通常用t表示。当n=l时，称该关系为单元关系（Unaryrelation）。当n=2时，称该关系为二元关系（Binaryrelation）。关系是笛卡尔积的有限子集，所以关系也是一个二维表，表的每行对应一个元组，表的每列对应一个域。由于域可以相同，为了加以区分，必须对每列起一个名字，称为属性（Attribute）。n目关系必有n个属性。若关系中的某一属性组的值能唯一地标识一个元组，则称该属性组为候选码（Candidatekey）。若一个关系有多个候选码，则选定其中一个为主码（Primaryhers）。主码的诸属性称为主属性（Primeattribute）。不包含在任何候选码中的属性称为非码属性（Non-keyattribute）。在最简单的情况下，候选码只包含一个属性。在最极端的情况下，关系模式的所有属性组是这个关系模式的候选码，称为全码（All-key）。例如，可以在表2.l的笛卡尔积中取出一个子集来构造一个关系。由于一个研究生只师从于一个导师，学习某一个专业，所以笛卡尔积中的许多元组是无实际意义的，从中取出有实际意义的元组来构造关系。该关系的名字为SAP，属性名就取域名，即SUPERVISOR，SPECIALITY和POSTGRADUATE。则这个关系可以表示为：SAP（SUPERVISOR，SPECIALITY，POSTGRADUATE）假设导师与专业是一对一的，即一个导师只有一个专业；导师与研究生是一对多的，即一个导师可以带多名研究生，而一名研究生只有一个导师。这样SAP关系可以包含三个元组，如表2所示。表2SAP关系假设研究生不会重名（这在实际当中是不合适的，这里只是为了举例方便），则POSTGRADUATE属性的每一个值都唯一地标识了一个元组，因此可以作为SAP关系的主码。关系可以有三种类型：基本关系（通常又称为基本表或基表）、查询表和视图表。基本表是实际存在的表，它是实际存储数据的逻辑表示。查询表是查询结果对应的表。视图表是由基本表或其他视图表导出的表，是虚表，不对应实际存储的数据。按照定义2，关系可以是一个无限集合。由于笛卡尔积不满足交换律，所以按照数学定义，（d1，d2，…，dn）≠（d2，d1，…，dn）。当关系作为关系数据模型的数据结构时，需要给予如下的限定和扩充：（1）无限关系在数据库系统中是无意义的。因此，限定关系数据模型中的关系必须是有限集合。（2）通过为关系的每个列附加一个属性名的方法取消关系元组的有序性，即（d1，d2，…，di，dj，…，dn）=（d2，d1，…，dj，di，…，dn）（i，j=1，2，…，n）。因此，基本关系具有以下六条性质：①列是同质的（Homogeneous），即每一列中的分量是同一类型的数据，来自同一个域。②不同的列可出自同一个域，称其中的每一列为一个属性，不同的属性要给予不同的属性名。例如在上面的例子中，也可以只给出两个城：人（PERSON）=张清玫，刘逸，李勇，刘晨，王敏专业（SPECIALITY）=计算机专业，信息专业SAP关系的导师属性和研究生属性都从PERSON域中取值。为了避免混淆，必须给这两个属性取不同的属性名，而不能直接使用城名。例如定义导师属性名为SUPERVISOR-PERSON（或SUPERVISOR），研究生属性名为POSTGMDUATE-PERSON（或POSTGRADUATE）。③列的顺序无所谓，即列的次序可以任意交换。由于列顺序是无关紧要的，因此在许多实际关系数据库产品中（例如Oracle），增加新属性时，永远是插至最后一列。④任意两个元组不能完全相同。⑤行的顺序无所谓，即行的次序可以任意交换。③分量必须取原子值，即每一个分量都必须是不可分的数据项。注意：在许多实际关系数据库产品中，基本表并不完全具有这六条性质，例如，有的数据库产品（如FoxPro）仍然区分了属性顺序和元组的顺序；许多关系数据库产品中，例如Oracle，FoxPro等，它们都允许关系表中存在两个完全相同的元组，除非用户特别定义了相应的约束条件。关系模型要求关系必须是规范化的，即要求关系模式必须满足一定的规范条件。这些规范条件中最基本的一条就是，关系的每一个分量必须是一个不可分的数据项。规范化的关系简称为范式（NormalForm）。例如，表3虽然很好地表达了导师与研究生之间的一对多关系，但由于POSTGRADUATE分量取了两个值，不符合规范化的要求，因此这样的关系在数据库中是不允许的。表3非规范化关系二关系模式在数据库中要区分型和值。关系数据库中，关系模式是型，关系是值。关系模式是对关系的描述，那么一个关系需要描述哪些方面呢？首先，应该知道，关系实质上是一张二维表，表的每一行为一个元组，每一列为一个属性。一个元组就是该关系所涉及的属性集的笛卡尔积的一个元素。关系是无组的集合，因此关系模式必须指出这个元组集合的结构，即它由哪些属性构成，这些属性来自哪些城，以及属性与城之间的映象关系。其次，一个关系通常是由赋予它的元组语义来确定的。元组语义实质上是一个n目谓词（n是属性集中属性的个数）。凡使该n目谓词为真的笛卡尔积中的元素（或者说凡符合元组语义的那部分元素）的全体就构成了该关系模式的关系。现实世界随着时间在不断地变化，因而在不同的时刻，关系模式的关系也会有所变化。但是，现实世界的许多己有事实限定了关系模式所有可能的关系必须满足一定的完整性约束条件。这些约柬或者通过对属性取值范围的限定，例如职工年龄小于65岁（65岁以后必须退休），或者通过属性值间的相互关连（主要体现于值的相等与否）反映出来。关系模式应当刻划出这些完整性约束条件。因此一个关系模式应当是一个5元组。定义4关系的描述称为关系模式（RelationSchema）。它可以形式化地表示为：R（U，D，dom，F）其中R为关系名，U为组成该关系的属性名集合，D为属性组U中属性所来自的域，dom为属性向域的映象集合，F为属性间数据的依赖关系集合。例如，在上面例子中，由于导师和研究生出自同一个域-人，所以要取不同的属性名，并在模式中定义属性向域的映象，即说明它们分别出自哪个域，如：dom（SUPERVISOR-PERSON）=dom（POSTGRADUATE-PERSON）=PERSON关系模式通常可以简记为R（U）或R（A1，A2，…，An）其中，R为关系名，A1，A2，…，An为属性名。而域名及属性向域的映象常常直接说明为属性的类型、长度。关系是关系模式在某一时刻的状态或内容。关系模式是静态的、稳定的，而关系是动态的、随时间不断变化的，因为关系操作在不断地更新着数据库中的数据。但在实际当中，人们常常把关系模式和关系都称为关系，这不难从上下文中加以区别。三关系数据