【概述】

数据库设计，广义来讲，是数据库及其应用系统的设计，即设计整个数据库应用系统；狭义来讲，是设计数据库本身，即设计数据库的各级模式并建立数据库，属于数据库应用系统设计的一部分

数据库设计的一般定义为：对于一个给定的应用环境，构造优化的数据库逻辑模式和物理结构，并据此建立数据库及其应用系统，使之能够有效地存储和管理数据，满足各种用户的应用需求，包括信息管理要求和数据操作要求

【概述】

顺序查找（Sequential search），又称线性查找，其可分为无序表的查找和有序表的查找

对无序表的查找即暴力搜索，其核心思想是：将所有情况都列举到线性表或数组中，根据要求找一个合适的维度，枚举每一个元素，并对每一个元素判断其是否符合条件

【概述】

对于范式来说，数据依赖和函数依赖下定义的码是必不可缺的前置内容，其详细介绍见下：

• 数据依赖：点击这里
• 函数依赖下定义的码：点击这里

【候选码与主码】

设 $K$ 是 $R < U,F >$ 中的属性或属性组合，若 $K\xrightarrow{F} U$，则称 $K$ 为 $R$ 的候选码（Candidate Key），若候选码多于一个，则选定其中一个为主码（Primary Key）

例如，在关系模式 student(Sno, Sname, Sage) 中，Sno 是可以唯一标识一个元组的，同样的 (Sno, Sage) 也可以唯一标识一个元组，但这个组合不能称为候选码，因为即使去掉 Sname 属性，剩下的 Sno 也完全可以唯一标识一个元组

【树的遍历】

树中最基本的操作是遍历，从根结点出发，按照某种次序访问树中的所有结点，使得每个结点仅被访问一次

根据树的定义可知：一棵树由根结点和 $m$ 棵子树构成，因此只要递归的遍历根结点和 $m$ 棵子树即可遍历整棵树

【函数依赖】

函数依赖

设 $R(U)$ 是属性集 $U$ 上的关系模式，$X$、$Y$ 是 $U$ 的子集，若对于 $R(U)$ 的任意一个可能的关系 $r$，$r$ 中不可能存在两个元组在 $X$ 上的属性值相等，而 $Y$ 上的属性值不等，则称 $X$ 函数确定 $Y$，或 $Y$ 函数依赖于 $X$，记作：$X\rightarrow Y$

【问题的提出】

之前已经介绍过关系数据库的基本概念、关系模型的三部分、关系数据库的标准语言 SQL，但有一个很基本的问题没有涉及：针对一个具体问题，应该如何构造一个适合它的数据库模式，即应该构造几个关系模式，每个关系由哪些属性组成等

这个问题确切来讲是关系数据库逻辑设计问题，由于关系模型有严格的数学理论基础，且可以向别的数据模型转换，因此，以关系模型为背景讨论这个问题，形成了数据库逻辑设计的一个有力工具，即关系数据库规范化理论

【概述】

树中最基本的操作是遍历，即从根结点出发，按照某种次序访问树中的所有结点，使得每个结点仅被访问一次

在二叉树中，有两种遍历方式，一种是基于树的递归特性的前/中/后序遍历，一种是基于树的层次特性的层次遍历

为方便测试与树相关的算法而编写的树的随机数据生成器

树的结点为 1~10 个，边权为 1~100，各点编号随机化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include <algorithm>
#include<ctime>
using namespace std;
#define N 50

struct Edge {
    int x, y;
    int dis;
} edge[N];
int n,edgeTot;
int tot, x[N], y[N], dis[N];
int id[N], father[N];
int Find(int x) { return father[x] == x ? x : Find(father[x]); }
int main() {
    srand(time(0));
    n = rand() % 10 + 1;
    
    printf("%d\n", n);
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            x[++tot] = i;
            y[tot] = j;
            dis[tot] = rand() % 100 + 1;
        }
    }
    for (int i = 1; i <= tot; ++i){
        id[i] = i;
        father[i] = i;
    }
 
    random_shuffle(id + 1, id + tot + 1);
 
    for (int i = 1; i <= tot; ++i) {
        int pos = id[i];
        int fx = Find(x[pos]);
        int fy = Find(y[pos]);
        if (fx == fy)
            continue;
        father[fy] = fx;
 
        edge[++edgeTot].x = x[pos];
        edge[edgeTot].y = y[pos];
        edge[edgeTot].dis = dis[pos];
        if (edgeTot == n - 1)
            break;
    }
 
    for ( int i = 1; i <= edgeTot; i++)
        printf("%d %d %d\n", edge[i].x, edge[i].y, edge[i].dis);
        
    system("pause");
    return 0;
}

【空值的产生】

在向基本表中插入一个元组时，若还不知道具体的值，可以显式的指定空值

例如，向 sc 表中插入一个元组（学生号：3，课程号：1，成绩：空）