离散数学在关系数据库中的应用.doc

(完整word版)离散数学在关系数据库中的应用
离散数学在关系数据库中的应用

学生姓名： 指导教师：

黑龙江八一农垦大学信息学院计算机科学与技术系2009级

摘要：离散数学是现代数学的一个重要分支，是计算机科学中基础理论的核心课程，它是以研究离散性的结构和相互间的关系为主要目标，其研究对象一般地是有限个或可数个元素。数据库技术被广泛应用于社会各个领域，关系数据库已经成为数据库的主流，离散数学中的笛卡儿积是一个纯数学理论，是研究关系数据库的一种重要方法，显示出不可替代的作用，不仅为其提供理论和方法上的支持，更为重要的是推动了数据库技术的研究和发展。关系数据模型建立在严格的集合代数的基础上，其数据的逻辑结构是一个由行和列组成的二维表来描述关系数据模型，在研究实体集中的域和域之间的可能关系、表结构的确定与设计、关系操作的数据查询和维护功能的实现、关系分解的无损连接性分析、连接依赖等问题都用到二元关系理论。在关系数据库中，对数据的操作几乎全部建立在一个或多个关系表格上，通过对这些关系表格的分类、合并、连接或选取等运算来实现对数据的处理。
关键词：离散数学 笛卡儿乘积 关系数据库 二元关系

1.引言：
离散数学是现代数学的一个重要分支，对计算机科学的研究和发张起着重要的作用。本文仅介绍它在关系数据库中的应用，这部分内容很有用，对开拓我们的思路将起到很好的作用。

2.关系数据结构

在一个给定的应用领域中，所有实体及实体之间联系的关系的集合构成一个关系数据库，关系数据库的值是这些关系模式在某一时刻对应的关系的集合，通常简称为关系数据库。
现实世界的实体以及实体间的各种联系均用关系来表示，数据的逻辑结构——二维表（关系模型中数据的逻辑结构是一张二维表）。
关系模型建立在集合代数的基础上，关系数据库要解决一个具体问题，必须运用数据结构知识。对于问题中所处理的数据，必须首先从具体问题中抽象出一个适当的数学模型，然后设计一个解此数学模型的算法，最后编出程序，进行测试、调整直至得到问题的最终解答。而寻求数学模型就是数据结构研究的内容，寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。数据结构中将操作对象间的关系分为四类：集合、线性结构、树形结构、图状结构或网状结构。数据结构研究的主要内容是数据的逻辑结构，物理存储结构以及基本运算操作，其中逻辑结构和基本运算操作来源于离散数学中的离散结构和算法思考。离散数学中的集合论、关系、图论、树四个章节就反映了数据结构中四大结构的知识，如集合由元素组成，元素可理解为世上的客观事物。关系是集合的元素之间都存在某种关系，例如雇员与其工资之间的关系。图论是有许多现代应用的古老题目，伟大的瑞士数学家列昂哈德·欧拉在18世纪引进了图论的基本思想，他利用图解决了有名的哥尼斯堡七桥问题，还可以用边上带权值的图来解决诸如寻找交通网络里两城市之间最短通路的问题，而树反映对象之间的关系，如组织机构图、家族图、二进制编码都是以树作为模型来讨论。

3.关系数据结构的基本概念

3.１关系
１）域：域是一组具有相同数据类型的值的集合。
例:整数，实数，介于某个取值范围的整数，长度指定长度的字符串集合，{‘男’，‘女’}，介于某个取值范围的日期等。
２）笛卡儿积
给定一组域D1，D2，…，Dn，这些域中可以有相同的。D1，D2，…，Dn的笛卡儿积为：
｛Di，i＝1，2，…，n｝ÎD1×D2×…×Dn＝｛（d1，d2，…，dn）｜di｝　（所有域的所有取值的一个组合，不能重复）
ａ、元组：笛卡儿积中每一个元素（d1，d2，…，dn）叫作一个n元组或简称元组，通常用t表示。
ｂ、分量：笛卡儿积元素（d1，d2，…，dn）中的每一个值di叫作一个分量。
ｃ、笛卡儿积的表示方法：笛卡儿积可表示为一个二维表，表中的每行对应一个元组，表中的每列对应一个域。
３）关系
关系：D1×D2×…×Dn的子集叫作在域D1，D2，…Dn上的关系，表示为： R（D1，D2，…，Dn）
注意：关系是笛卡儿积的有限子集，无限关系在数据库系统中是无意义的。由于笛卡儿积不满足交换律，即
（d1，d2，…，dn）≠（d2，d1，…，dn）
但关系满足交换律，即（d1，d2 ，…，di ，dj ，…，dn）=（d1，d2 ，…，dj，di ，…，dn）（i，j = 1，2，…，n）
解决方法：为关系的每个列附加一个属性名以取消关系元组的有序性。
４）属性：关系中不同列可以对应相同的域，为了加以区分，必须对每列起一个名字，称为属性，n目关系必有n个属性。
５）码
候选码：若关系中的某一属性组的值能唯一地标识一个元组，则称该属性组为候选码。在最简单的情况下，候选码只包含一个属性，称为全码。在最极端的情况下，关系模式的所有属性组是这个关系模式的候选码，称为全码。
主码：若一个关系有多个候选码，则选定其中一个为主码。
６）三类关系
基本关系（基本表或基表）：实际存在的表，是实际存储数据的逻辑表示。
查询表：查询结果对应的表。
视图表：由基本表或其他视图表导出的表，不对应实际存储的数据。

3.2关系操作集合
1）常用的关系操作
查询、选择、投影、连接、交、并、差。
数据更新：插入、删除、修改。
查询的表达能力是其中最主要的部分。
2）关系操作的特点：集合操作方式，即操作的对象和结果都是集合。
3）关系数据语言的种类
A、关系代数语言：用关系的运算来表达查询要求。
B、关系演算语言：用谓词来表达查询要求元组关系演算语言，谓词变元的基本对象是元组变量。
C、域关系演算语言。
D、具有关系代数和关系演算双重特点的语言。
4）关系数据语言的特点
①关系语言是一种高度非过程化的语言；
②能够嵌入高级语言中使用；
③关系代数、元组关系演算和域关系演算三种语言在表达上完全等价。

3.3关系完整性约束
1）实体完整性：通常由关系系统自动支持。
2）参照完整性：早期系统不支持，目前大型系统能自动支持。
3）用户定义的完整性：反映应用领域需要遵循的约束条件，体现了具体领域中的语义约束。

4.关系结构模型

关系式数据结构把一些复杂的数据结构归结为简单的二元关系(即二维表格形式)，例如某单位的职工关系就是一个二元关系。
由关系数据结构组成的数据库系统被称为关系数据库系统，在关系数据库中，对数据的操作几乎全部建立在一个或多个关系表格上，通过对这些关系表格的分类、合并、连接或选取等运算来实现数据的管理。对于一个实际的应用问题(如人事管理问题)，有时需要多个关系才能实现，可以概括地说，一个关系称为一个数据库，若干个数据库可以构成一个数据库系统，数据库系统可以派生出各种不同类型的辅助文件和建立它的应用系统。
离散数学在关系数据库研究中的作用越来越大，关系数据库科学中普遍采用离散数学中的一些基本概念、基本思想、基本方法，使得关系数据库科学越趋完善与成熟。离散数学在关系数据库中有着广泛应用，除了在上述提到的领域中发挥了重要作用外，在其他领域也有着重要的应用，如离散数学中的数理逻辑部分在关系数据库设计中的应用尤为突出，数字逻辑作为关系数据库的一个重要理论，在很大程度上起源于离散数学的数理逻辑中的命题与逻辑演算，利用命题中各关联词的运算规律把由高低电平表示的各个对象元之间的运算与二进制数之间的运算联系起来，使得我们可以用数学的方法来解决对象元问题，使得整个问题变得更加直观，更加系统化。集合论在关系数据库中也有广泛的应用，它为数据结构和算法分析奠定了数学基础，也为许多问题从算法角度如何加以解决提供了进行抽象和描述的一些重要方法，在软件工程数据库中也会用到。代数结构是关于运算或计算规则的学问，在关系数据库中，代数方法被广泛应用于许多分支学科，如可计算性、形式语言与自动机、密码学、网络与通信理论、程序理论和形式语义学等，格与布尔代数理论成为关系数据库系统设计中的重要工具，图论对开关理论与逻辑设计、数据库制表与构建、操作系统、程序设计语言的编译系统以及信息的组织与检索起重要作用，其平面图、树的研究对集成电路的布线、网络线路的铺设、网络信息流量的分析等的实用价值显而易见。

5.总结
离散数学不仅是关系数据库迅猛发展的支撑学科，更是提高学生逻辑思维能力、创造性思维能力以及形式化表述能力的动力源，离散数学课程所传授的思想和方法，广泛地体现在关系数据库及相关方面的诸多领域，从数据管理到信息处理，从构建数据库到数据库应用技术，无不与离散数学密切相关。在现代计算机关系数据库科学中，如果不了解离散数学的基本内容，则在关系数据库应用中就寸步难行了。

参考文献

[1] 耿素云，屈婉玲，张立昂.离散数学（第四版）.北京：清华大学出版社，2008.
[2] 王珊，萨师煊.数据库系统概论.北京：高等教育出版社，2006.
[3] 李昭原.数据库原理与应用.北京：科学出版社，1999.
[4] 瞿亮，江厚松.关系数据库ORACLE9I原理及应用.北京：北京交通大学出版社，2005.
5