一对多关系数据模型使用键链接的合理性的数学原理

大一下学期的时候,我们的魏部长让我做一个调查问卷管理系统,用于生成调查问卷并可统计结果。当然,因为能力有限所以这个项目在刚做到一点的时候就流产了。为了储存不同的调查问卷的题目信息,当时我想到的唯一的办法就是——为每个调查问卷建一个表,再用一个表储存全局信息。这种方法现在看来几乎是不可考虑的,但按当时的经验确实没有其他办法。
这个模型最初可以追溯到我做 PHP 的第五个作业的时候。那是复杂的新闻发布系统,有一个功能就是每条新闻都可以添加评论。由于当时没什么经验,在为这个功能设计数据库的时候遇到了困难(事实上最后还是没有做出这个功能)。一条新闻对应多条评论,这是一个一对多的关系。现在我们知道标准的解决办法是建两个表—— news 和 comments ,其中 comments 表用一个字段 news_id 标识评论所对应的新闻。但当时并没有想到这样做,当时的想法有两个:
  1. 为每条新闻建立一个表储存这条新闻的评论。
  2. 将一条新闻的所有评论存放在一个字段中,用特殊符号区分这些评论。
但以上两种方法都有很明显的缺点。第一种方法要改变数据库结构,这是无论如何不被推荐的。这需要对表操作,在当时我已经意识到这将大大降低运行效率,而且还要对表设计合理的命名方式,还需要针对可能出现的意外进行错误处理(例如某个表不存在,或试图创建一个已经存在的表,需要处理的意外情况将出奇地多)。第二种方式甚至不如第一种方式,这种方式储存时修改非常不方便,而且还要处理用户添加的评论中包含这个特殊字符的情况。
这两个方法有一个共同的特点,就是与新闻直接对应的实体都只有一个,即这个新闻所对应的表,和这个新闻所对应的评论的联合。但我忽略了一个重要且基本但不那么显然的事实:两个可列集的笛卡儿积仍然是可列集。为了解释这句话,需要解释很多概念。
首先是集合,这在高中数学第一章就讲了。对于高中已经阐述过的概念这里不再重复。有些集合的元素是有限个,这叫做有限集。而元素有无限个的集合当然就叫做无限集。这里要介绍的是集合的基数概念。基数就是反映一个集合中元素的多少的一个量。对于有限集来说,基数就是元素个数。而无限集的情况复杂一些,因为无限集的元素个数是无穷大,无穷大和无穷大并不等同。为了讨论无限集基数的情况,要引入另一个概念——对等。两个集合对等,意思就是在这两个集合之间能够建立一个一一对应的关系。比如整数集和偶数集,从整数集中任取一个元素,将其乘以二,有唯一的一个偶数集中的元素与之对应,反之亦然。所以整数集和偶数集对等。这种一一对应的关系未必是唯一的,只要能找到一个——甚至不需要找到,而只要能证明能够找到——就是对等。对等关系满足以下三条性质:
  1. 反身性:一个集合与其自身对等。
  2. 对称性:如果 A 与 B 对等,则 B 与 A 对等。
  3. 传递性:如果 A 与 B 对等, B 与 C 对等,则 A 与 C 对等。
所以对等关系是一个等价关系——这个结论在本文并没什么用处。
我们可以得出一些显然的结论:
  1. 两个有限集对等的充分必要条件是它们的基数相等。
  2. 有限集与无限集必不对等。
  3. 任意有限集不与其真子集对等。但无限集则不一定,比如在上面的例子中,偶数集是整数集的一个真子集,但二者对等。
受以上启发,我们规定:如果两个无限集对等,那么令它们有相等的基数。
于是,为了确定一些表述起来比较复杂的无限集的基数,可以让它们与一些简单的无限集建立对等关系,然后就能确定它的基数就是简单的无限集的基数。这里的简单和复杂是人给与集合的概念,而并不是集合本身固有的性质,仅仅是如果我们能比较简单地描述出一个集合,那么就称之为简单。最简单的无限集当然就是自然数集({0,1,2,3,…},大家数数就数的这些吧)。对于无限集的基数,由于都是无穷大,所以我们没有现成的数字来表示它们,但全用∞又无法表现出无限集基数之间的区别,所以我们引入一个符号——阿列夫零(打不出来)。我们规定:自然数集(非负整数集)的基数是阿列夫零。与自然数集对等的集合称为可列集。顾名思义,可列集的元素尽管无穷,但我们可以按一个特定的规则列出来(这个规则未必唯一),这个集合中的任何一个给定的元素,只要我们足够耐心,都能在有限的时间内将它列出来。
顺便说一下,以下结论为真,但跟我们的主题关系不大,所以不展开讲:
  1. 有理数集与自然数集对等,即有理数集的基数为阿列夫零,亦即有理数集为可列集。
  2. 区间 [0,1] 的基数是阿列夫一,或者记为 c 。 [0,1] 与自然数集不对等,所以 c 不等于阿列夫零。
  3. 实数集 R 与 [0,1] 可以建立对等的关系,所以其基数也是 c 。
  4. 在阿列夫零和 c 之间是否还有其他的基数,是一个仁者见仁智者见智的问题,允许有和不允许有都能得出合理的结论,发展成为不同的数学分支。
  5. 基数没有上限。这是因为,我们称一个集合的所有子集构成的集合为这个集合的幂集,如 {1,2,3} 的幂集为 {Φ,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}} ,当然无限集也是这样,那么一个集合与其幂集必不对等。设一个集合的基数为 n ,那么其幂集的基数就为 2^n ,并且 n≠2^n (强调这一点是因为对无穷大的运算有时会看起来有点反常,比如阿列夫零加一还是阿列夫零),且 2^n>n 。所以,如果某个人声称找到了一个集合,这个集合的基数是所有集合的基数的上限,那么这个集合的幂集的基数就立刻比它大了,这就推翻了这个人的结论。
根据自然数集与偶数集对等的结论的启示,我们可以得出一些比较显而易见的结论:自然数集与 {0,0.5,1,1.5,2,2.5,…} 对等,即后面那个集合是可列集。也就是说,阿列夫零×2=阿列夫零。同理, {0,1/3,2/3,3/3,4/3,5/3,6/3,…} 也是可列集,即阿列夫零×3=阿列夫零。也就是说,对于任何的正整数 n 都有阿列夫零×n=阿列夫零。那么我们自然会想到阿列夫零×阿列夫零会不会还等于阿列夫零呢?答案是肯定的,我们可以用三角形法则((0,0),(1,0),(0,1),(2,0),(1,1),(0,2),(3,0),(2,1),(1,2),(0,3),…)或者矩形法则((0,0),(1,0),(1,1),(0,1),(2,0),(2,1),(2,2),(1,2),(0,2),…)遍历迪卡尔积中的全部元素。前面说过,只要我们能够按照一定规则把集合中的全部元素一个不多一个不漏地全部列出来,那这个集合就是可列集。事实上,两个自然数集的笛卡尔积的基数就是阿列夫零×阿列夫零。那么阿列夫零^2=阿列夫零。这就是我们需要的结论了。
当然,我们可以继续下去,但接下来的结论本文并不需要。同理,阿列夫零^3=阿列夫零^2×阿列夫零=阿列夫零。继续下去,对于任何的正整数 n ,都有阿列夫零^n=阿列夫零。
人的求知欲望是无穷的。到这一步人们自然会问:阿列夫零^阿列夫零是否还是阿列夫零呢?这句话等价于:可列个可列集的笛卡尔积是否还是可列集呢?答案是肯定的,在这里就不再严格证明了,但是到现在大家凭直觉也应该能感觉到其正确性了。
好,说了这么多,回到数据库上来。其实新闻的评论就是可列个可列集的笛卡尔积。首先我们假定一种理想的情况:数据库服务器的储存空间无穷大。那么每条新闻所对应的评论的数量在自然数内取值。也就是说,一条新闻所对应的评论至多有阿列夫零个。而数据库中至多能储存的新闻条数也是阿列夫零个。所以我们需要为评论预备阿列夫零×阿列夫零个位置,在文章开始提到的两种方法中,第一种建立了阿列夫零个表,每个表中有阿列夫零条数据;而第二种方法将一个阿列夫零退化为1。但事实上,根据以上的分析,阿列夫零×阿列夫零还是等于阿列夫零,也就是说我们完全可以使用阿列夫零个位置存放阿列夫零×阿列夫零条数据。这就是我们的用一个表储存所有新闻的评论的模型。
Advertisements

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s