Taogen's Blog

本篇将介绍设计模式中的5种创建型模式，其中设计模式的实现代码使用 Java 语言描述。

Creational Design Patterns

创建型设计模式是抽象实例化过程。它们帮助使系统独立于对象是如何创建、如何组合和如何表示的。

创建型模式封装了系统使用的具体的 classes 的细节，隐藏了 classes 的 objects 是如何创建的和如何一起协作的，系统最多知道对象的接口或抽象类是什么。创建型模式给你很大的灵活性在“创建什么”，“谁创建的”，“怎样创建的”和“什么时候创建的”等方面。

Abstract Factory

What

Abstract Factory 模式提供了一个接口来创建相关的对象家族，而不用指定它们具体的 classes。

Why

Motivation

我们想要整体的改变多个 objects，从一种类型的对象家族改变为另一种类型。

例子：一个应用可以切换不同的外观，主要是切换 widgets 的样式，widgets 包括：scroll bars，windows，和 buttons。不同的风格需要创建不同的 objects，我们希望风格切换时，可以轻易地创建不同风格的 widgets 对象。

Applicability

• 一个系统它的产品是如何 created，composed，和 represented 应该是独立的。
• 一个系统应该是配置多个产品家族中的一个。
• 相关的家族产品对象是设计成一起使用。
• 你想要提供一个产品的类库，只暴露它们的接口，不暴露它们的实现。

Solution

Structure

Participants

• AbstactFactory：提供创建抽象产品对象的接口。
• ConcreteFactory：实现创建具体产品对象的操作。
• AbstractProduct：定义一类产品对象的接口。
• ConcreteProduct：具体的产品对象。
• Client：仅仅使用 AbstractFactory 和 AbstractProduct classes 去创建家族产品对象。

Collaborations

在运行时，正常只有单个 ConcreteFactory class 实例是创建的。这个 concrete factory 创建产品对象有特定的实现。创建不同的产品对象，client 应该使用不同的 concrete factory。

AbstractFactory 将产品对象的创建推迟到它的 subclass ConcreteFactory.

Implementations

interface AbstractFactory{
    abstract ProductA createProductA();
    abstract ProductB createProductB();
}                                                                              
	
class ConcreteFactory1 implements AbstractFactory{
    public ProductA createProductA(){
        return new ProductA1();
    }
    public ProductB createProductB(){
        return new ProductB1();
    }
}

class ConocreteFactory2 implements AbstractFactory{
    public ProductA createProductA(){
        return new ProductA2();
    }
    public ProductB createProductB(){
        return new ProductB2();
    }
}
	
interface ProductA{}
class ProductA1 implements AbstractProductA{}
class ProductA2 implements AbstractProductA{}
	
interface ProductB{}
class ProductB1 implements AbstractProductB{}
class ProductB2 implements AbstractProductB{}

public class FactoryProvider{
	public static AbstractFactory getFactory(String choice){
        return "1".equals(choice) ? new ConcreteFactory1() : new ConcreteFactory2();
    }
}

public class Client{
    public static void main(String[] args){
        AbstrsctFactory factory = FactoryProvider.getFactory("1");
        ProductA productA = factory.createProductA();
        ProductB productB = factory.createProductB();
    }
}

Consequences

Benefits

• 它隔离具体的 classes。
• 它使得改变产品家族对象变得容易。
• 它提升了产品对象的一致性。

Drawbacks

• 支持新种类的产品是困难的。他需要修改 AbstractFactory 接口和它的子类。

Builder

What

将复杂对象的构造与其表现分开，因此相同的构造过程可以创建不同的表现。

Why

Motivation

不改变过程，构造不同的对象。

例子：阅读器软件可以将 RTF（Rich Text Format）文档转换为很多其他的文本格式。每一种格式转换处理器对应一个 Converter 对象，它们都是 TextConverter 的子类。我们想要不改变阅读器转换的处理逻辑，轻易的增加新的格式转换处理器。

Applicability

• 创建一个复杂的对象的算法应该是独立于组成对象的部分及其组装方式。
• 对象构造过程必须允许不同的表现。

Solution

Structure

Participants

• Bulider：指定一个创建产品对象的抽象接口。
• ConcreteBuilder：实现 Builder 接口，构造和装配产品对象。
• Director：使用 Builder 接口构造对象。
• Product：要被创建的产品对象。

Collaborations

• Client 创建 Director 对象和配置一个想要的 Builder 对象。
• Director 通知 builder 产品对象什么时候应该构建。
• Builder 处理来自 director 的请求。
• Client 从 builder 中取出产品对象。

Implementations

interface Builder{
    void buildComponet1();
    void buildComponet2();
}
public class ConcreteBuilder1 implements Builder{
    Product product;
    public ConcreteBuilder1(){
        this.product = new Product();
    }
    void buildComponet1(){
        this.product.setComponet1(xxx);
    }
    void buildComponet2(){
        this.product.setComponet2(xxx);
    }
    public Product getProduct(){
        return this.product.
    }
}
public class ConcreteBuilder2 implements Builder{
    Product product;
    public ConcreteBuilder2(){
        this.product = new Product();
    }
    void buildComponet1(){
        this.product.setComponet1(xxx);
    }
    void buildComponet2(){
        this.product.setComponet2(xxx);
    }
    public Product getProduct(){
        return this.product.
    }
}

public class Director{
    private Builder builder;
    public Director(Builder builder){
        this.builder = builder;
    }
    public void construct(){
        this.builder.buildComponet1();
        this.builder.buildComponet2();
    }
    pubilc Product getProduct(){
        return this.builder.getProduct();
    }
}

public class Client{
    public static void main(String[] args){
        Builder builder = new ConcreteBuilder1();
        Director director = new Director(builder);
        director.construct();
        Product product = director.getProduct();
    }
}

Consequences

Benefits

• 它让你轻易改变一个产品内部的表现。
• 它隔离了构建和表现得代码。构建过程不变，可以有不同的表现。
• 它让你更好的控制构建过程。

Drawbacks

• 改变产品的内部表现，需要定义不同的 Builder 子类。

Factory Method

What

定义一个创建对象的接口，但是让子类决定那个类应该被实例化。Factory Method 让一个类的实例化延迟到子类。

Why

Motivation

使用抽象对象维持关系，一个抽象类型的具体子类决定另一个抽象类型的具体子类。把对象的实例化延迟到子类。

例子：文本编辑器可以创建多种格式的文档，不同的子应用决定了不同的文档类型，如 WPS 软件可以创建 word，excel，ppt 等文档。系统只知道创建一个应用就要创建一个对应的文档，但是不能预测文档 Document 的哪个子类被实例化。可以通过 Factory Method 解决这个问题，封装 Document 具体子类的创建过程，将它从客户端处理过程分离。

Applicability

• 一个必须被实例化的 class 不能被实例化。
• 一个 class 想要它的子类去指定哪个对象要被创建。

Solution

Structure

Participants

• Product：定义要被创建的对象的接口。
• ConcreteProduct：实现 Product 的具体的类。
• Creator：声明 factory method，返回 Product 类型的对象。
• ConcreteCretor：override factory method 返回一个 ConcreteProduct 的实例。

Collaborations

• Creator 依靠它的子类去返回一个合适的 ConcreteProduct 实例。

Implementations

public interface Product{}

public class ProductA implements Product{}

public class ProductB implements Product{}

public interface Creator{
    Product createProduct();
}

public class CreatorA implements Creator{
    Product createProduct(){
        return new ProductA();
    }
}

public class CreatorB implements Creator{
    Product createProduct(){
        return new ProductB();
    }
}

public class Client{
    Creator creator = new CreatorA();
    Product productA = creator.createProudct();
}

Consequences

Benefits

• 消除绑定具体的子类的代码。代码仅仅处理 Product 接口。
• 更灵活的创建对象。
• 连接平行的类的层次结构。

Drawbacks

• Client 必须通过实例化 Creator 子类去创建一个特定的 ConcreteProduct 对象。当 ConcreteProduct 类增加时，ConcreteCreator 类也需要增加 。

Prototype

What

指定使用 prototype 实例创建的对象的类型，并且通过拷贝这个 prototype 去创建新的对象。

Why

Motivation

想要重复创建类似的对象，且这个对象的创建过程比较复杂。

例子：一个可以编辑音乐谱的编辑器。他需要重复的添加多个音符。

Applicability

• 一个系统它的产品对象的创建，组合，和表现应该是独立的。
• 一个 class 的实例化在运行时指定的。
• 很方便的去克隆大量的对象，而不是手动实例化。

Solution

Structure

Participants

• Prototype：定义一个克隆自己的接口。
• ConcretePrototype：实现克隆自己的操作。
• Client：通过请求 prototype 克隆方法来创建对象。

Collaborations

• Client 请求 prototype 去克隆自己。

Implementations

public interface Prototype extends Cloneable{
    Prototype clone();
}
public class ConcretePrototype1 implements Prototype{
    private String name;

    public ConcretePrototype1(){
        this.name= "ConcretePrototype1-aha";
        // simulating complex construction process
        try {
            Thread.sleep(1);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

    public ConcretePrototype1 clone() {
        Object prototype = null;
        try {
            prototype = super.clone();
        } catch (CloneNotSupportedException e) {
            e.printStackTrace();
        }
        return (ConcretePrototype1) prototype;
    }
}
public class ConcretePrototype2 implements Prototype{
	//... same with ConcretePrototype1
}
public class Client{
    public static void main(String[] args){
        ConcretePrototype1 concretePrototype1 = new ConcretePrototype1;
        ConcretePrototype1 copy1 = concretePrototype1.clone();
        System.out.println(copy1.equals(concretePrototype1));
    }
}

Consequences

Benefits

• Prototype 有一些和 Abstract Factory 和 Builder 模式类似的优点，即对 client 隐藏具体的产品类，这些模式让 client 使用不同的具体的子类，却不用修改 Client 实现逻辑。
• 在运行时动态地增加或去除产品对象。

Drawbacks

• 每一个 Prototype 必须实现 clone 操作，这个 clone 操作的实现有可能是复杂的。如，不支持拷贝或存在循环参考。

Singleton

What

确保一个 class 仅有一个实例，并且提供一个全局的访问它的方法。

Why

Motivation

有些 class 必须只有一个实例。如，一个系统应该仅有一个文件系统和一个窗口管理器。

Applicability

• 一个 class 必须有且仅有一个实例，并且有一个全局访问的接入点。

Solution

Structure

Participants

• Singleton：它负责去创建一个唯一的实例。它提供一个获取实例的操作，让 client 得到唯一的实例。

Collaborations

• Client 通过 Sigleton 的获取实例操作，获取到唯一的 Singleton 实例。

Implementations

• Private constructor method.
• Public getInstance() method.

// Hungry
public class Singleton{
    private final static Singleton instance =  new Singleton();
    private Singleton(){}
    public static Singleton getInstance(){
        return instance;
    }
}

// Lazy 1 by lazily create instance.
public class Singleton
{
	private static Singleton instance;
	private Singleton() {}
	public synchronized static Singleton getInstance() 
	{
		if (instance == null)
		{
			synchronized (Singleton.class)
			{
				if (instance == null)
				{
					instance = new Singleton();
				}
			}
		}
		return instance;
	}
}

// Lazy 2 by Inner Class
public class Singleton 
{
	private Singleton() {}
	
	private static class Inner
	{
		private static final Singleton INSTANCE = new Singleton();
	}
	
	public static Singleton getInstance() 
	{
		return Inner.INSTANCE;
	}
}

Consequences

Benefits

• 控制访问唯一的实例。

References

[1] Design Patterns: Elements of Reusable Object-Oriented Software by Erich Gamma, Richard Helm, Ralph Johnson and John Vlissides

欢迎来到设计模式系列文章，这是设计模式系列文章的第一篇，本篇将介绍设计模式的基本概念，主要介绍“什么是设计模式”，“为什么要使用设计模式”，以及“如何使用设计模式”等内容。

设计面向对象软件是困难的，设计可重用的面向对象软件则更加困难。你必须找到相关的 objects，以适当的 granularity 将他们分解为 classes，定义 class interfaces 和 inheritance hierarchies，以及在他们之间建立关系。你的设计应当解决当前的问题，也要足以解决未来的问题和需求。你还要避免重复设计，或者最小化重复设计。做好这些事情不是一件简单的事情，设计模式可以快速的帮助我们有效的解决复杂问题。

What is Design Patterns?

设计模式是描述特定环境下重复出现的问题和问题解决方案的核心内容，且这个方案可以重复的使用。具体来说，它描述了 objects 和 classes 之间的交流，它是定制化地去解决一个在特定场景下的设计问题。

一般来说，一个设计模式包含以下四个基本元素：

• Pattern Name。模式名称可以用于描述问题和它的解决方案。它是对设计的高度的抽象。模式的专业词汇，能够方便我们去讨论交流和写文档等。
• Problem。问题描述了我们什么时候要使用这个模式。它解释了问题和模式的应用场景。它可能描述一个不灵活的 class 和 object 结构设计的特征，通过这些特征可以知道应该通过哪些设计模式去解决这些问题。
• Solution。抽象地描述问题和一般的解决方案。它描述了设计方案，以及 classes 或 objects 之间的 relationships，responsibilities，和 collaborations 等。
• Consequences。应用一个模式的结果和 trade-offs。它描述了应用一个模式的 costs 和 benefits。

Why design patterns are needed?

设计模式是帮助我们快速解决特定场景的设计问题，帮助我们设计一个可重用、可扩展性的应用。它主要有以下几个优点：

• 设计模式使得重用成功的设计和架构变得更加容易。
• 设计模式通过提供 class 和 object 相互作用和它们的潜在意图的明确规范，来提升对存在系统的文档编写和维护。
• 设计模式可以帮助设计者更快的得到一个正确的设计。

How Design Patterns Solve Design Problems

面向对象程序是由 objects 组成的。一个 object 包含 data 和 procedures。当 object 接收到来自 client 的请求时，执行相关的操作。请求只能让 object 执行一个操作。操作是唯一改变 object 内部数据的方式。object 内部状态是 encapsulated，对外部是不可见的。

面向对象最难的部分就是把一个系统 decomposing 为 objects。这个任务是很复杂的，因为它涉及到很多因素。如：encapsulated，granularity，dependency，flexibility，performance，evolution，reusability 等等。这些影响因素往往是相互冲突的，需要有所权衡，然而，兼顾这么多因素不是一件很容易的事。设计模式通过考虑这些因素，针对特定的应用场景的问题，提供了一个有效的解决方案。

How to Select a Design Pattern

常见的设计模式有20多种，我们应该怎么去选择呢？下面列出了一些找到合适的设计模式的方法：

• 考虑设计模式是如何解决问题的。
• 查看每个设计模式的意图和目的。
• 思考设计模式是如何相互关联的。设计模式之间的关系。
• 检查导致重复设计的原因。看你的设计是否有类似的问题，看哪些模式可以帮助避免重复设计。
• 考虑你的设计中什么是变化的。

How to Use a Design Pattern

当你选择好了设计模式之后，你可以通过以下步骤将设计模式应用在你的程序中。

1. 查看该模式的 Applicability 和 Consequence 部分的描述内容，确定你选择的模式能够正确地解决你的问题。
2. 学习该模式的 Structure，Participants 和 Collaborations 部分内容，确保你理解了 classes 和 objects 在模式中是如何关联的。
3. 查看具体的代码实现例子。学习如何实现该模式。
4. 选择对于你的应用环境有意义的 Participants 的名称。如使用 Strategy 模式设计文本组合算法，你可以命名为 SimpleLayoutStrategy，TeXLayoutStrategy。
5. 定义 Classes。具体为：声明 interfaces，建立继承关系，定义对象的变量。
6. 定义该模式在具体应用中的classes 的操作名称。即定义有意义的方法名称。如在 factory method 模式中，可能使用 create- 为前缀的方法名称。
7. 实现定义好的方法，实现模式中的 responsibilities 和 collaborations。

References

[1] Design Patterns: Elements of Reusable Object-Oriented Software by Erich Gamma, Richard Helm, Ralph Johnson and John Vlissides

前几个月我从0到1完成了 hot-crawler 这个网站项目，它也是我个人的第一个网站，至今（2019年12月）已稳定运行了四个多月。功能虽然很简单，但是整个过程却十分的艰难。当时完全没想到开发一个网站需要做这么多事情，很多事情都是第一次做，只能遇到问题解决问题，硬着头皮上。当时对完整的开发流程不是很清楚，做的时候基本上是想到什么做什么，流程可能不完善或者不正确，但从0到1实现一个网站要做的事情基本上都做了。根据之前的经验和整理，下面按照我自己的理解，介绍一下从0到1创建一个网站的大致过程。

I. 设计阶段

这个阶段主要是构思想法、收集需求、设计功能和时间计划。

主要的工作：

• 需求分析。
• 原型和UI设计。
• 系统设计。
• 时间规划和任务划分。

产出的结果：

• 用户需求和设计
  • 软件需求规格说明书（User/Software Requirements Specification, SRS）
  • 确定网站域名，网站名称，LOGO，Slogan。
  • 系统交互原型图。
  • UI 设计图。
• 软件设计
  • 软件架构文档（Software Architecture Document）
  • 数据库设计文档（Database Design Document）
  • API 文档（API Documentation）
  • 软件详细设计文档（Software detailed design）
  • 开发流程规范文档
• 过程文档（Process Documentation）
  • 项目计划，估计和时间表。（Plans, estimates, and schedules.）

What is plans, estimates, and schedules in project management?

II. 代码实现阶段

这个阶段主要是根据软件需求文档、软件设计文档和开发流程规范文档进行项目代码开发。

主要的工作：

• 配置服务器。具体包括：购买服务器，搭建项目运行环境，部署项目。
• 配置域名。具体包括：购买域名，DNS 解析，Nginx 反向代理，HTTPS。
• 搭建持续集成（CI/CD）。具体包括：创建 Git 仓库，添加 gitignore，搭建或购买 CI 服务，配置 Docker，配置 Jenkins。
• 后端代码实现。具体包括：创建项目，创建数据库，配置数据源，集成第三方类库，编写单元测试，编写模块代码。
• 前端代码实现。具体包括：构建项目，实现UI布局，实现交互动作，兼容多个终端（PC，Mobile，Tablet 等）
• 前后端对接。

产出的结果：

• 功能完整和可运行的前后端的代码。
• 项目说明文档（Source Code Document）。

III. 功能测试阶段

这个阶段主要是为预发布做准备。全面的系统功能测试、bug修复、功能优化等。

主要的工作：

• 功能测试。
• Bug 修复。
• 前端功能优化。如，优化样式，兼容PC端和移动端。
• 后端功能优化。如，可配置，可扩展，和用户体验优化等。

产出的结果：

• 软件能够达到需求文档的所有要求。

IV. 性能测试和性能优化

这个阶段主要是为发布前做准备，保证服务的高性能、高可用和安全性等。

主要的工作：

• 性能测试（Performance Testing）
  • 负载测试（Load Testing）。测试软件系统是否达到需求文档设计的目标，譬如软件在一定时期内，最大支持多少并发用户数，软件请求出错率等，测试的主要是软件系统的性能。
  • 压力测试（Stress Testing）。测试硬件系统是否达到需求文档设计的性能目标，譬如在一定时期内，系统的 CPU 利用率，内存使用率，磁盘I/O吞吐率，网络吞吐量等，压力测试和负载测试最大的差别在于测试目的不同。
  • 容量测试（Volume Testing）。确定系统最大承受量，譬如系统最大用户数,最大存储量，最多处理的数据流量等。
• 高性能
  • 算法实现优化。
  • JVM 优化。
  • 数据库优化。如，数据库表结构、索引和SQL优化。读写分离，分库分表。
  • 添加缓存和搜索引擎等。
  • 静态资源 CDN。
• 高可用
  • 应用服务高可用。如，1. 详细的日志记录。2. 软件程序作为 Linux 服务，设置崩溃后可自动重启。3. DNS 负载均衡。4. Nginx 负载均衡。
  • 数据库高可用。如，数据库集群，数据备份。
  • 热部署、热更新。
  • 云监控（阿里云监控）。
• 安全性
  • 设置系统防火墙。
  • 设置软件防火墙。
  • SSH 公钥登录。
  • 防止 SQL 注入和 XSS 攻击。
  • 防止 DDoS 攻击。

产出的结果：

• 应用服务具备高性能、高可用和安全性等特点。

IV. 预发布和内测

这个阶段主要是小范围的推广试用，收集反馈意见，持续打磨和优化。

主要的工作：

• 推广。
• 收集意见。
• 持续改进和优化。

产出的结果：

• 软件功能完善、体验良好。

VI. 正式发布和推广

网站正式发布，全面推广。

VII. 日常维护

这个阶段的主要是潜在问题修复，用户体验优化，和功能调整等。

主要的工作：

• 潜在问题缺陷发现和修复。
• 优化用户体验。

产出的结果：

• 保证应用服务的正常运行。
• 功能持续调整和优化。

VIII. 其他

其他一些优化网站的事情。如下：

• 埋点，数据采集和分析。统计用户行为，分析数据优化功能。

• SEO。

References

[1] Technical Documentation in Software Development: Types, Best Practices, and Tools

本篇将介绍数据库设计相关的概念。主要分为两个部分：数据库概念模型设计和关系型数据库设计。它们分别对应的设计方法是 E-R 模型（Entity-Relationship Model）和标准化（Normalization）。

数据库设计和 E-R 模型

数据库设计过程

设计过程

• 需求分析阶段。与用户和领域专家交流，收集需求，充分地描述出预期的数据库用户需要的数据。这个阶段产出的是用户需求的规范。
• 概念设计阶段。选择一个数据模型，将用户需求转换为数据库概念模式。这个阶段主要是专注于描述数据和数据之间的关系。用专业的、概念的数据模型去描述数据结构，主要使用 entity-relationship model 和 normalization 方式去设计。这个阶段一般产出的是实体关系图（E-R图）。完整的概念设计 schema 还包含功能需求规范。描述用户对数据的操作类型，如修改，查询和取出具体的数据，删除数据。
• 逻辑设计阶段。将抽象的数据模型转换为数据库的实现。将概念模型转换为数据库系统使用的模型，如将 entity-relationship model 转换为 relational model。
• 物理设计阶段。设计物理存储的细节。包括文件组织的形式和选择索引结构。

物理的 schema 相对来说是比较容易改变的，而改变逻辑的 schema 是很难的，可能会影响到大量分散在应用程序中的查询和更新代码。因此，在构建应用程序之前，必须谨慎地和考虑周全地进行数据库设计。

设计中常见的问题

• 冗余（Redundancy）。冗余的信息表示可能导致重复的信息出现不一致。如一些过时的或错误的信息依然存在数据库中。信息应该准确的出现在一个地方。
• 不完全（Incompleteness）。一个坏的设计可能会使企业的某些方面难以建模或无法建模。不合理的分解关系的属性，导致难以插入一个新增的数据，或者必须其它属性设为 null。如，没有单独的课程表，只有课程设置表，当新增课程时，无法插入课程属性到课程设置表。

E-R 模型

E-R 模型可以将现实世界中企业的含义和相互作用映射到一个概念的模式。E-R 数据模型采用三个基本的概念：实体集，关系集，和属性。

Entity Sets

实体（Entity）是现实中的一个事情或一个对象，每个对象是与其它对象有区别的。如大学中的一个人就是一个实体。一个实体有一组属性，它的属性值可以唯一标识一个实体。如，一个人可能有一个身份证号码属性，这个属性值可以唯一的标识一个人。一个实体可以是具体的，如一个人或一本书等，也可以是抽象的，如一个课程或一个机票预订等。

实体集（Entity Set）是一组有相同类型的实体，它们共享相同的属性。

Relationship Sets

关系（Relationship）是几个实体之间的关联。如一个老师实体和一个学生实体之间有一个指导的关系。

关系集（Relationship Sets）是一组相同类型的关系。多个实体集之间的关系总和构成了关系集。实体集之间的关联称为参与，如 实体集 E1，E2… 参与关系集 R。实体在关系中扮演的功能称为该实体的角色。

相同的实体集之间的可能超过一个关系集。两个实体集之间的称为二元关系集（Binary Relationship Set）。然而，关系集可能涉及超过两个实体集。参与一个关系集的实体集的数量称为Degree of the relationship set。二元关系集的 degree 是 2，三元关系集的 degree 是 3。

Attributes

每一个属性有一组允许的值，称为 domain 或者 value set。每一个实体可以用一组属性和属性值对来描述。

E-R 模型中的属性类型有：

• 简单（Simple）和组合（Composite）属性。组合属性可以分为多个子部分，如 name 属性可以由 first_name, middle_name, 和 last_name 组合而成。
• 单值（Single-valued）和 多值（Multivalued）属性。单值属性表示只能出现一个值，如 ID 属性只能一个，多值属性表示可以有多个值，如 phone_number 可以有多个电话号码。
• 派生属性（Derived）。这类属性的值可以从其它相关属性的值得出。如 age 可以从 date_of_birth 属性值得出。

一个属性为 null 值表示不存在或者未知。

Constraints

E-R 模型中主要有两种约束：映射基数和参与约束。

映射基数（Mapping Cardinality）主要用于描述二元关系集。映射基数的类型有：

• One-to-one。一个实体 A 最多关联一个实体 B。
• One-to-many。一个实体 A 可以关联多个实体 B。
• Many-to-one。多个实体 A 可以关联一个实体 B。
• Many-to-many。一个实体 A 可以关联多个实体 B。一个实体 B 也可以关联多个实体 A。

参与约束（Participation Constraints）表示一个实体集参与一个关系的数量。主要有两种参与约束：

• Total。它表示一个实体集所有实体都参与了一个关系集。
• Partial。它表示一个实体集部分实体参与了一个关系集。

Keys

一个 key （键）是能够区分不同的实体的一组属性。Superkey 表示可以区分实体的一组属性。Candidate key 表示最小的 Superkey 即用来区分实体的最小的属性集。Primary key 与 candidate key 是相同的，只是在不同的地方的表述，Primary key 用在数据库的表述中，而另一个用在 E-R 模型中。

去除冗余的属性

设计一个数据库的 E-R 模型，通常是先确定有哪些实体集，为实体集选择合适的属性，为实体集建立合适的关系。一些属性同时出现在多个实体集中，为它们建立关系集，并取出重复的属性。

E-R 图

E-R 图可以图形化地表示数据库地总体的逻辑结构。E-R 图简单而清晰，被广泛使用在 E-R 模型中。

基本结构

E-R 图主要的组件有：

• 分为两部分的长方形（Rectangle Divided）：用来表示实体集。

• 菱形（Diamond）：表示关系集。

• 没有划分的长方形（Undivided Rectangle）：表示一个关系集的属性。

• 线（Line）：用来连接实体集和关系集。

• 虚线（Dashed Line）：用来连接一个关系集的属性到另一个关系集。

• 双线（Double Line）：用来指出一个实体集完全参与一个关系集。即表示参与约束。

• 双线菱形（Double Diamond）：表示关系集是被弱实体连接的。

• 实体集的主键属性用下划线标识。

一个简单的 E-R 图，如下所示：

E-R 图映射基数的表示

E-R 图使用关系集到实体集之间的有向线（Directed Line）和无向线（Undirected Line）来表示 one-to-one，one-to-many 等映射基数。有向线表示 one，无向线表示 many。如下 E-R 图表示 student 与 instructor 的 many-to-one 关系。

更复杂的映射基数使用 l..h 表示，l 表示最小的基数，h 表示最大的基数。基数的值可以是 0 到无穷， * 表示无穷。常见的表示，如 1..1，0..* 。左边线上的基数表示右边实体集的参与数量，反之亦然。

弱实体集

一个实体集没有足够的属性去组成一个主键，即没有主键的实体集称为弱实体集（Week Entity Sets）。一个实体必须依赖另一个实体的属性才能完整，即实体需要添加其它实体的属性才能被唯一标识或者说能实现主键。

为了使弱实体集有意义，它必须关联另一个实体集，称为标识实体集（Identifying Entity Set）或所有者实体集（owner entity set）。每个弱实体必须与一个标识实体相关联； 就是说，弱实体集依赖于标识实体集而存在。 标识实体集拥有它标识的弱实体集。 将弱实体集与标识实体集相关联的关系称为标识关系（Identifying Relationship）。如 section（课时） 必须依赖 course （课程）的 cource_id。

更多的 E-R 图的表示，如：

• 组合属性（Composite Attributes）

• 角色（Role）

• 非二元关系集（Nonbinary Relationship Sets）

这些 E-R 表示的内容，不详细解释了，如有兴趣可查阅文章最后给出的参考书籍。

一个大学的 E-R 图例子如下图所示：

E-R 模型转换为关系模型

E-R 模型和关系模型都是抽象的逻辑的表示真实世界。要实现数据库必须把 E-R 模型转换为数据库系统对应的数据模型。当前小节，我们描述如何将 E-R 模型转换为关系型数据库的关系模型。主要涉及两个问题：E-R schema 如何转换为 relation schema，E-R schema 中的约束如何转换为 relation schema 的约束。

强实体集的简单属性的表示

E-R 模型中的一个 Entity Set 的每个属性对应一个 Relation 的每个元组。

强实体集的复杂属性的表示

组合属性（Composite Attributes）。组合属性中的每一个属性作为一个单独的属性。

多值属性（Multivalued Attributes）。为多值属性单独创建一个表。如一个教师有多个手机号码，可以单独创建一个表 instructor_phone (ID, phone number)。

派生属性（Derived Attributes）。派生是属性可以简单的作为表的属性。

弱实体集的表示

把依赖的实体集的属性与当前表属性组合成主键，同时为依赖的属性创建一个外键约束。

关系集的表示

• many-to-many。组合所有参与实体集的主键作为关系集的主键。

• one-to-one。任意选一个实体集的主键作为关系集的主键。

• many-to-one or one-to-many。选择 many 那一边的实体集的主键作为关系集的主键。

• n-ary without any arrows edges。组合所有参与实体集的主键作为关系集的主键。

• n-ary with an arrow edge。组合所有不在箭头那边的实体集的主键作为关系集的主键。

Schema 的冗余

连接弱实体集和强实体集的关系集的 schema 是多余的。E-R 图中的这一类关系集不需要出现在数据库关系型模型中。

Schema 的结合

Schema 的结合表示：去除关系集，使它结合到实体集中。常见的结合如下：

• one-to-one 中的关系集，可以结合在任一实体集的 schema 中。

• many-to-one or one-to-many 的关系集，可以结合在 many 那边的实体集的 schema 中。

• many-to-many 的关系集一般无法与实体集结合。

去除了关系集，一个实体集使用外键关联另一个实体集。

不完全参与关系结合后的实体集，可以使用 null 表示不存在的关联。

E-R 模型设计中的问题

有时实体集和关系集是不明确的，可能有大量不同的方式定义实体集和关系集。我们讨论一些基本的 E-R 模型设计的问题。

Entity Sets versus Attributes

一个实体有多值属性，这个多值属性是设计为一个属性还是一个实体集？

这需要看具体情况，如 instructor 实体集有一个多值属性 phone_number。如果这个多值属性的每个属性值需要维护额外的信息，如一个手机号码需要指定一个地点属性。这种情况下，多值属性需要设计成一个实体集 inst_phone(phone_number, location)， inst_phone 实体集与 instructor 实体集建立一个关系集。

Entity Sets versus Relationship Sets

一个对象应该表示为实体集还是关系集，有时候它是不明确的。

如学生（student）实体集和课时（section）实体集之间的对象应该如何表示？可以表示为一个关系 take。也可以表示为 一个实体登记（registration） 和两个关系 section_reg 和 student_reg。

一个对象是使用关系集还是实体集一个重要的参考准则：关系集是实体集之间的动作。

Binary versus n-ary Relationship Sets

当存在多元关系集时，多元关系集应该使用二元关系集代替。

Placement of Relationship Attributes

关系集的属性在结合的实体集中。如 instructor 和 student 之间是 one-to-many 的关系，其中关系集 advisor 有一个属性 date 表示成为一个学生的指导者的日期。在结合的时候这个属性可以放在 student 实体集中。

扩展的 E-R 特性

Specialization

实体集包含实体子集，这些子集在某种程度上不同于集合中的其它实体。

设计子集实体集的过程称为 Specialization。一个例子如下图所示：

Generalization

Generalization 是 specialization 的逆过程。不同的实体集通过共同的属性提取为父集实体集。

Attribute Inheritance

Specialization 和 Generalization 中的高层的实体集被底层实体集继承。

Aggregation

E-R 模型中无法表示关系之间的关系。Aggregation 是一个把关系集作为更高层级的实体集的抽象。一个例子如下图所示：

Extended E-R Features Reduction to Relation Schemas

E-R 模型扩展特性 Generalization 如何在关系型 Schema 中表示

第一种方式是，为更高层的实体集创建一个 schema，为每一个低层的实体集创建一个 schema，低层的 schema 属性由它特有的属性和高层的主键组成，添加一个外键约束，底层的 schema 主键参考高层 schema 的主键。如一个高层实体集下的两个低层实体集的关系型 schema 的例子：

person(ID, name, street, city)
employee(ID, salary)
student(ID, tot_cred)

第二种方式是，当实体集只有两层，而且分化是完全的。可以不创建高层的 schema，只是创建第二层的 schema，底层的 schema 的属性由高层的属性和自己特有的属性组成。如下：

employee(ID, name, street, city, salary)
student(ID, name, street, city, tot_cred)

上面两种方式都是用高层的实体集的主键作为它们自己的主键。第二种方式的缺点是：1）没有创建高层的实体集的 schema，当一个关系集与高层实体集关联时，无法参考这个实体集。避免这个问题可以创建一个 person 表，只包含它的主键。2）如果是 overlapping generalization 即一个实体可以同时作为多个子对象，那么一些值会重复的存储在多个表中。3）如果 disjoint 是不完整的，如有的对象不属于任何一个子对象，那么第二种方式无法表示这个对象。

E-R 模型扩展特性 Aggregation 如何在关系型 Schema 中表示

把 aggregation 当作一个实体集。aggregation 的主键就是关系集的主键。

其它的数据建模方式

E-R 图没有统一的标准，不同的地方可能使用不同的标识或图形。E-R 图可以帮助我们对系统组件的数据表现进行建模，但是数据表现只有系统设计的一部分，系统设计还需要设计，如用户和系统的交互，系统的功能模块的规范等等。我们可以使用 UML （Unified Modeling Language）来表示系统的更多的设计。

数据库设计的其它方面

Schema 的设计只是数据库设计中的一部分。其它方面的设计也不可忽略。

• 数据约束和关系型数据库设计。除了属性和关系，还是大量的数据约束需要设计，如主键约束，外键约束，检查约束，断言，和触发器等等。
• 使用需求。性能要求，如吞吐量（Throughput），响应时间（Response Time）。
• 数据库授权。
• 数据流工作流。
• 考虑未来可能的变化。

关系型数据库设计和标准化

关系型数据库设计的目标是生成一组关系 schema 使得存储信息没有不必要的冗余，以及高效地取出信息。实现这个目标可以通过设计一个满足范式（Normal Form）的 schema。

我们将介绍一种基于函数依赖（Functional Dependencies）的正式的关系数据库设计方法。 然后，我们根据函数依赖和其他类型的数据依赖定义范式。

好的关系型设计的特点

一个好的关系型数据库设计。

• 不能出现太多的数据冗余，需要将冗余的信息属性进行适当的分解。
• 不能过度的分解，使得丢失信息完整性。

关系型数据库设计的核心在于：在保证数据完整性的情况下，如何减少数据的冗余。以及如何在性能和冗余之间权衡。

Functional Dependencies

在介绍范式之前，我们需要先了解什么是函数依赖（functional dependencies）。

Notations

• 使用 Greek Letters 表示 Functional Dependency 中的一组属性。如 α, β。
• 使用小写 Roman Letter 加上在小括号中的大写 Roman Ltter 表示一个 relation schema，如 r(R)，其中大写字母 R 表示一组属性。Greek Letter 表示的一组属性可能是部分属性或者全部属性，Roman Letter 一般表示全部属性。
• 一组属性组成的 superkey 使用 K 表示。我们可以说 K 是 r(R) 的一个 superkey。
• 我们使用小写表示关系。如 instructor。在定义或者算法中，使用单个字符表示关系，如 r 。

Functional Dependencies

表示一个 functional dependency 存在一个 schema 中的定义如下：

设 schema 为 r(R), α ⊆ R 且 β ⊆ R.

• 给定的一个 r(R) 的实例中，如果实例中的所有的元组对 t1 和 t2 满足：若 t1[α] = t2[α], 那么 t1[β] = t2[β]，则可以说这个实例满足 functional dependency α ⟶ β。
• 如果在schema r(R) 的每一个合法的实例中，都满足一个 functional dependency α ⟶ β，则可以说这个 functional dependency α ⟶ β holds on schema r(R)。

使用 functional-dependency notation 表示一个 schema 的 superkey：如果 functional dependency K ⟶ R holds on r(R)，则 K 是 r(R) 的一个 superkey。

具体的例子：使用 functional dependency 表示 inst_dept(ID, name, salary, dept_name, building, budge) 的 superkey：

ID, dept_name ⟶ name, salary, building, budget

Functional Dependencies 有两种用途：

1. 测试给定的 relation 的一个实例是否满足一组给定的 functional dependencies F。
2. 指定对合法的 relation 的约束。

Trivial

一些 functional dependencies 是 trivial，因为它们满足所有的 relations。例如 A ⟶ A，AB ⟶ A。

Trivial functional dependencies 的定义：如果 β ⊆ α，则 functional dependencies α ⟶ β 是 trivial。

Closure

所有可以从给定的 functional dependencies F 推导出来的 functional dependencies 集合称为 closure of F，表示为 F+。F+ 包含了所有 F 中的 functional dependencies。

Logically Implied

我们可以证明有其他的 functional dependencies 也 hold on the schema，我们可以说这些 functional dependencies 是 logically Implied by F。更正式地说，给定一个 schema r(R)，如果满足 F 每一个 r(R) 的实例也满足 ⨍，则一个 functional dependency ⨍ 是通过一组 functional dependencies F 逻辑暗示的（logically implied）。

如给定一个 relation schema r (A, B, C, G, H, I) 和一组 functional dependencies：A ⟶ B, A ⟶ C, CG ⟶ H, CG ⟶ I, B ⟶ H。那么 A ⟶ H 是 logically Implied。

closure of F 即 F+ 是一组所有被 F logically implied 的 functional dependencies。

Axioms

通过一些公理（Axioms）可以找到一个relation schema 的 logically implied functional dependencies。Armstrong‘s Axioms 表示如下：

• Relexivity rule。If α is a set of attributes and β ⊆ α, then α → β holds.
• Augmentation rule。 If α → β holds and γ is a set of attributes, then γα → γβ holds.
• Transitivity rule。 If α → β holds and β → γ holds, then α → γ holds.

Armstrong’s Axioms ，它是 sound，因为它们不生成任何不正确的 functional dependencies。它是 complete，因为对于给定的一组 functional dependencies F 它可以生成所有的 F+。

其它的公理：

• Union rule。 If α → β holds and α → γ holds, then α → βγ holds.
• Decomposition rule。If α → βγ holds, then α → β holds and α → γ holds.
• Pseudotransitivity rule。 If α → β holds and γβ → δ holds, then αγ → δ holds.

Formal Forms

常见的范式（Formal Forms）有：第一范式，第二范式，第三范式，BC 范式，和第四范式。

Atomic Domains and First Normal Form

为了减少单个属性的数据冗余，我们常用的方法是：对于组合属性，如 address 由 street，city，state 和 zip 等组成，我们创建一个单独的表来表示这些属性。对于多值属性，我们让每一个多值属性中的每一项作为一个单独的属性。

在关系模型中，我们通过形式化（Formalize）来实现一个属性没有任何子结构。如果一个 domain 是不可再分的单元称这个 domain is atomic。我们定义：如果一个 relation schema R 中的所有属性的 domain 是 atomic，则称这个 schema R 是在 First Normal Form (1NF，第一范式) 中的。

Boyce-Codd Normal Form

Boyce-Codd Normal Form (BCNF) 它消除了可以基于 functional dependencies 发现的所有数据冗余。但是可能存在一些其它类型的的冗余，需要用其它的方法来解决，如 multivalue dependencies。

如果对于来自 α → β, a ⊆ R, β ⊆ R 的 F+ 中的所有 functional dependencies 满足以下至少一项条件，则 relation schema R 的 functional dependencies F 在BCNF中：

• α → β 是一个 trivial functional dependency。
• α 是 schema R 的一个 superkey。

以上条件可以理解为：schema 中的任何 nontrivial functional dependency 的左侧必须是一个 superkey。

一个 schema 不在 BCNF 中的例子：

inst_dept (ID, name, salary, dept_name, building, budget)

其中存在 dept_name → budget hold on inst_dept，由于它不是一个 trivial functional dependency，且 dept_name 不是一个 superkey。BCNF 的两个可选项一个也不满足，所以 inst_dept 不在 BCNF 中。

一个不在 BCNF 中的 schema 可以进行分解。分解为两个 schema 如下：

• (α ∩ β)
• (R - (β - α))

注意其中 “-” 表示属性集之间的差集。

如 inst_dept (ID, name, salary, dept_name, building, budget) 中 α = dept_name, β = {building, budget}, α → β 不满足 BCNF，inst_dept 分解为：

• (α ∩ β) = (dept_name, building, budget)
• (R - (β - α)) = (ID, name, dept_name, salary)

Third Normal Form

Third Normal Form（3NF，第三范式）通过允许某些 nontrivial functional dependencies （其左侧不是 superkey）来稍微放松约束。

如果对于来自 α → β, 其中 a ⊆ R, β ⊆ R 的 F+ 中的所有 functional dependencies 满足以下至少一项条件，则 relation schema R 的 functional dependencies F 在 3NF 中：

• α → β 是一个 trivial functional dependency。
• α 是 schema R 的一个 superkey。
• β - α 中的每一个属性 A 是包含于 R 的 candidate key 中的。

3NF 的定义前两个可选项是和 BCNF 一样的，它多给出了一个可选项。任何满足 BCNF 的 schema 也满足 3NF，BCNF 是更严格的 3NF。

如，schema dept_advisor(s_ID, i_ID, dept_name)，存在下面的 functional dependencies：

i_ID → dept_name
s_ID, dept_name → i_ID

可以看出 i_ID → dept_name 不在 BCNF 中。α = i_ID, β = dept_name, β - α = dept_name，因为 s_ID, dept_name → i_ID hold on dept_advisor，dpet_name 包含于 candidate key中，所以 dept_advisor 是在 3NF 中的。

Multivalue Dependencies and Fourth Normal Form

从某种意义上说，一些 relation schema 即使它们在 BCNF 中，似乎仍未得到足够的规范化（normalized），因为它们仍然遭受信息重复的问题。Multivalue dependencies 就是这一类的数据冗余问题，而 Fourth Normal Form （4NF，第四范式）就是为了消除 multivalue dependencies 问题。

Multivalue Dependencies（多值依赖）使用双箭头 “↠” 符号表示，如 A ↠ B。如果一个关系同时满足下面三个条件，则这个relation schema 存在 multivalue dependencies：

• 一个属性 A 的值，对应多个属性 B 的值。
• 关系表至少由 3 个属性。
• 设关系表有三个属性分别为 A，B，C，属性 B 和 C 是独立的。

如下列 enrolment 表存在多值依赖 s_id ↠ hobby。其中，s_id 表示学生ID，course 表示课程，hobby 表示爱好。

消除多值依赖，将它分解为两个表。

stu_course

stu_hobby

Second Normal Form

一个 schema 在 Second Normal Form （2NF，第二范式）它需要满足以下条件：

• 它是在 1NF 中的。
• 所有非键属性是完全 functional dependent on the primary key。

如下 purchase_detail schema：

purchase_detail(customerID, storeID, purchase_location)

它的主键是 customerID 和 storeID。但存在 functional dependency storeID → purchase_location，storeID 不是完整的 primary key 所以 purchase_detail 不在 2NF 中。我们将 purchase_detail 进行分解使他满足 2NF：

purchase(customerID, storeID)
store(storeID, purchase_location)

范式总结

小结

E-R 模型专注于实体和它们之间的关系，而标准化专注于去除冗余数据，防止数据修改不完整，标准化有利于保证数据的一致性。完整性约束防止数据错误修改，与标准化类似，它也是为了保证数据的一致性。

References

[1] Database System Concept (6th) by Avi Silberschatz, Henry F. Korth, and S. Sudarshan

[2] Second Normal Form

[3] Normal Forms in DBMS - geeksforgeeks

[4] Unicode Math Symbols

本篇将介绍关系型数据库，数据库查询语言（SQL 语言）和形式关系查询语言。你将了解关系型数据库的详细内容，SQL 语句的使用，以及形式关系查询语言的用法。

介绍关系型模型

关系型模型是如今商业的数据处理应用程序的主要数据模型。关系型模型因其简单易用的特点被广泛使用。

关系型数据库的结构

关系型数据库是一组表（Table）组成，每一个表分配一个唯一的名称。

关系型模型中，术语关系（Relation）用于参考数据库的表（Table），术语元组（Tuple）用于参考数据库的行（Row），术语属性（Attribute）参考数据库的列（Column）。术语关系实例（Relation Instance）参考数据的实例。一个关系由多个元组构成。一个元组由多个属性值构成。每一个属性的取值范围称为域（Domain）。所有的属性的域是原子的、不可分的。null 值是一个特殊的值，它表示未知或者不存在。

数据库模式

数据库的表现形式可以分为逻辑的和物理的。数据库模式（Database Schema）是数据库的逻辑设计。数据库实例（Database Instance）表示数据库某个时刻的数据的快照。数据库模式由一组属性和对应的域组成。

键

我们必须有一种方法去区分一个关系中的不同的元组。Superkey 是一个或多个属性组合，它可以唯一的标识关系中的一个元组。如，在关系型数据库中我们常用 ID 来标识一个行记录。没有子集 Superkey 的 Superkey ，这种最小的 Superkey 称为 候选键（Candidate Key）。在数据库中我们使用术语主键（Primary Key）来表示数据库设计人员选择的候选键。在一个关系中的任何两个元组不允许出现相同的 key 属性值。

一个关系 r1 的属性是另一个关系 r2 的主键，这个属性称为外键（Foreign Key）。参考完整性约束（Referential Integrity Constraint）表示一个外键属性值出现在参考关系中，它也必须出现在被参考的关系中。

模式图

数据库的主键和外键依赖可以通过模式图（Schema Diagram）来表示。每个关系用一个矩形表示，主键属性添加下划线表示，外键依赖表示为从外键属性出发的带箭头的线指向被参考的关系的主键属性。一个数据库模式图的例子，如下图所示。

数据库查询语言

数据库查询语言包括过程和非过程的。

非过程查询语言（Nonprocedural Language）是指用户描述希望得到的信息，但没有给出一个获得信息的具体的过程。常见的非过程查询语言，如 SQL （Structured Query Language），关系演算（relational calculus）。

过程查询语言（Procedural Language）是指用户指定了执行一系列的操作计算得到希望的结果。常见的过程查询语言，如关系代数（relational algebra）。

本篇接下来会详细的介绍以上数据库查询语言的用法。

关系型操作

过程的关系型查询语言提供了一组操作应用在一个关系或者多个关系中。关系查询的结果本身是一个关系，因此关系运算可以应用于查询结果以及给定的一组关系。具体的关系型操作的表达取决于具体的查询语言。

常见的操作有，选择（select），投影（project），连接（join），笛卡尔积（Cartesian Product），组合（Union），相交（Intersect）等等。这些操作会在下面的关系代数查询语言中详细介绍。

介绍 SQL

有大量的数据库查询语言可以使用。SQL 是目前最广泛使用的一种查询语言。SQL 不仅能查询数据库，它也可以定义和修改数据库。

SQL 语言概述

IBM 开发了初始版本的 SQL，原名为 Sequel。Sequel 语言经过发展，它的名称变成了 SQL （Structured Query Language）。1986年 国际标准组织（ISO）发布了一个 SQL 标准，称为 SQL-86。后续陆续发布了很多个 SQL 标准版本，最近的一个版本为 SQL:2008。

SQL 语言由多个部分组成：

• 数据定义语言（Data-Definition Language, DDL）,它可以定义、删除和修改关系模式（relation schema）。
• 数据操纵语言（Data-Manipulation Language, DML）它可以查询，插入，删除和修改数据库的元组。
• 完整性（Integrity）。DDL 包含语句可以指定数据的完整性约束。
• 视图定义。DDL 包含语句可以定义视图。
• 事务控制。SQL 包含命令可以指定事务的开始和结束。
• 嵌入的 SQL 或动态的 SQL。它可以嵌入在编程语言中如 C, C++, Java 进行操作数据库。
• 授权（Authorization）。DDL 包含语句可以指定关系和视图的访问权限。

每个数据库系统实现的 SQL 与标准的 SQL 有一些小差异，但大部分是标准的，SQL 的功能组成也大致一样。特定的数据库系统中的不标准的 SQL 可以查阅数据库系统的用户手册。

SQL 数据定义

数据库中的一组关系必须通过数据定义语言（DDL）来指定给数据库系统。SQL DDL 可以定义：

• 每个关系的模式（Schema）
• 每个属性的类型。
• 完整性约束。
• 每个关系的一组索引。
• 每个关系的安全和授权信息。
• 每个关系的物理存储结构。

基本类型

SQL 标准支持大量的内置类型，包括：

• char(n)：固定长度 n 的字符串。
• varchar(n)：可变长度的字符串，最大长度为n。
• int：一个整数。与硬件相关的整数的有限子集。
• smallint：一个小的整数。
• numeric(p, d)：指定精度和固定的小数部分的数。该数据有p位数字（加一个符号）组成，p 位数字中的 d 位在小数据的右边。如，numeric(3, 1) 可以表示 44.5，不可以表示 444.5，4.45 等。
• real, double precision：浮点数和双精度浮点数。具体精度与硬件相关。
• float(n)：一个浮点数，精度至少为 n 位。

每一种类型可以包含一个特殊的值称为 null。null 表示未知或者不存在。

char 数据类型存储固定长度的字符串，当字符串长度不够时，自动在字符串后面加空格。

char 和 varchar 等类型的字符串之间比较时，先转换为相同的长度，再进行比较。

SQL 也支持 nvarchar 类型，它是字符串类型，它存储的是 Unicode 编码或者多语言数据。而 varchar存储的是 ASCII 数据。nvarchar 一个字符使用 2 个字节，varchar 一个字符使用 1 个字节。然而，很多数据库允许 Unicode （UTF-8）的数据存储在 varchar 类型中。

基本的模式定义

SQL 使用 create table 语句创建一个数据库的关系。如

create table department
	(dept_name varchar(20),
	building varchar(15) not null,
	budget numeric(12,2),
	primary key (dept_name));

SQL 可以指定完整性约束：

• primary key(Aj1, Aj2…)
• foreign key(Ak1, Ak2…)
• not null

插入元组语句：

insert into instructor
	values (10211, ’Smith’, ’Biology’, 66000);

删除元组语句：

delete from student;

删除表语句：

drop table r;

修改表语句。如，添加属性和删除属性。

alter table r add A D;
alter table r drop A;

基本的 SQL 查询操作

基本的 SQL 查询语句有三个子句（Clause）：select，from 和 where。

一个关系中的查询

使用 select from where 三个基本的子句进行单表查询

select name
from instructor
where salary > 70000;

使用关键字 distinct 去除重复的记录，关键字 all 允许重复的结果。

select distinct dept_name
from instructor;

select 子句支持算术表达式

select ID, name, dept_name, salary * 1.1
from instructor;

where 子句支持逻辑连词，and, or, not

select name
from instructor
where dept_name = ’Comp. Sci.’ and salary > 70000;

多个关系的查询

典型的多个关系的 SQL 查询语句

select A1, A2,..., An
from r1, r2,...,rm
where P;

多个关系的查询使用 from 子句指定查询哪些关系。

from 子句多表查询的过程：

1. 生成一个 from 子句中的所有关系的笛卡尔乘积（Cartesian Product）。

2. 基于步骤1产生的结果，使用 where 子句的断言进行筛选元组。

3. 基于步骤2产生的结果，输出 select 子句指定的属性。

多个关系的连接查询

natural join：创建一个连接基于两个关系中相同名称的属性具有相同的属性值。连接后的关系中相同的属性只显示一次。natural join 一般默认是 inner join。

join 和 from 多表查询可以得到相同的结果，但 join 写法更简洁。natural join 语句如下

select A1, A2,..., An
from r1 natural join r2 natural join ... natural join rm
where P;

join 的实现是通过将两个关系按特定属性排序后进行连接的,不会生成笛卡尔积，但是需要对关系表进行排序。Cartesian product 一个是空间消耗，join 一个是时间消耗。

其它基本的 SQL 查询操作

重命名

as 关键字可以重命名结果关系中的属性名称，以及重命名 SQL 语句中的关系名称，如 old-name as new-name。新的名称可以称为别名 （alias）。

select T.name as instructor_name, S.course_id
from instructor as T, teaches as S
where T.ID= S.ID;

字符串操作

比较操作：SQL 标准中字符串比较是区分大小写的，但是常见的数据库系统，如 MySQL 和 SQL Server 中不区分大小写。

字符串函数：SQL 支持大量的字符串函数，如：转换大小写 upper(s), lower(s)，去除开始和结尾的空格 trim(s)。每个数据库系统中的字符串函数不一样，具体参照特定的数据库系统手册。

模式匹配：可以使用 like 操作符进行字符串的模式匹配。字符串中的 % 匹配一个或多个任意字符，_ 匹配任何一个字符。

select dept_name
from department
where building like ’%Watson%’;

转义符：SQL 使用反斜杠 \ 进行转义字符（Escape Character）。

正则表达式：SQL 标准支持比 like 操作更强大的模式匹配，在 SQL 中可以使用正则表达式。

select 子句中的属性规范

符号 * 再 select 子句中表示一个关系的所有属性。

select instructor.*
from instructor, teaches
where instructor.ID= teaches.ID;

排序

SQL 支持对一个关系中的元组进行排序，使用 order by 子句可以对查询结果的元组进行排序。

select name
from instructor
where dept name = ’Physics’
order by name;

where 子句的断言

SQL 中的 where 子句支持 between 操作符进行比较断言。between 可以代替 算术操作符 >=, <=

select name
from instructor
where salary between 90000 and 100000;

比较运算符可以支持元组，即多个属性按顺序比较。如， (a1, a2) < (b1, b2)， (a1, a2) = (b1, b2)

集合操作

常见的集合操作（Set Operations）如：组合 union，相交intersect 和排除 except。集合操作默认会去除重复的记录，添加 all 关键字，可以允许重复的记录。如 union all，intersect all， except all 等。一个集合操作的 SQL 语句例子如下：

(select course_id
from section
where semester = ’Fall’ and year= 2009)
union
(select course_id
from section
where semester = ’Spring’ and year= 2010);

Null 值

Null 值在关系型操作中是一个特殊问题，Null 值表示的是未知或不存在。Null 值在算术操作，比较操作，和逻辑操作视为特殊情况。可以把 Null 值理解为一个未知的值。

算术操作

算术操作中包含 null 的表达式，返回结果为 null。如 null + 5 // result is null. 表示的是： 未知 + 5，结果是未知。

比较操作

比较操作包含 null 时，结果既不是 true 也不是 false，而是未知。返回结果为 null。如 1 < null //result is null。表示的是：1 是否小于未知，结果是未知。

逻辑操作

where 子句中的逻辑连接是出现 null。

• and. true and null is null, false and null is false, null and null is null
• or. true or null is true, false or null is null, null or null is null
• not. not null is null

可以使用 select 子句去测试结果，如

select true and null; // return null
select true or null; //return true

测试属性值是否为空

使用 is null 和 is not null 来测试值是否为空。不能用等号来测试属性属性是否为空，因为 null = null // result is null。一个 SQL 例子如下：

select name
from instructor
where salary is null;

聚合函数

聚合函数（Aggregate Function）是一个函数把一组值作为输入，返回一个值。SQL 提供5个内置聚合函数：

• 平均值：avg
• 最小值：min
• 最大值：max
• 总和：sum
• 数量：count

sum 和 avg 函数的输入必须是数字。其它的函数输入的可以是数字和非数字，如字符串。

基本的聚合

select avg (salary)
from instructor;

select count (distinct ID)
from teaches

count(*) 表示查询一个关系的元组的数量。

select count (*)
from course;

分组聚合

聚合函数不仅可以使用在单个元组集合中，也可以使用在多个元组集合中。SQL 使用 group by 子句进行分组。它根据 group by 子句指定的所有属性的相同属性值进行分组。一个分组聚合的 SQL 例子：

select dept_name, avg (salary) as avg_salary
from instructor
group by dept_name;

注意事项：使用分组查询时，select 子句中出现的属性必须是 group by 中出现的属性。其它属性不能直接出现在 select 子句中，可以出现在聚合函数里。如，上面的 SQL，group by dept_name，所以 select 子句只能出现 dept_name 属性和聚合函数 select dept_name, avg (salary)。

原因：对某些属性进行分组，目的只能是计算这些分组的聚合函数结果。在分组查询的结果中，分组的属性和未分组的属性是一对多的关系，无法在一行中表示，所以 select 子句中不允许出现不是 group by 的属性。

Having 子句

having 子句使用聚合函数对分组进行过滤。SQL 语句例子如下：

select dept_name, avg (salary) as avg_salary
from instructor
group by dept_name
having avg(salary) > 42000;

一个分组查询包含 having 子句的查询处理过程：

• 根据 from 子句得到关系的所有元组。
• 如果 where 子句存在，则根据 where 子句的断言，过滤 from 子句中的元组。
• 根据 group by 子句对元组进行分组。
• 根据 having 子句过滤分组。
• 根据 select 子句中的聚合函数，得出每个分组的查询结果。

聚合函数中的 Null 和 Boolean 值

Null 值

除了 count() 函数之外的所有聚合函数，都忽略 null 值的输入。

select sum(salary)
from instructor;

上面 SQL 语句中的 sum(salary) ，如果分组中某个元组的 salary 属性值为 null，这个元组将被忽略。即 null 值不参与聚合函数的计算。

嵌套子查询

嵌套的子查询可以嵌套在 select 子句，from 子句，where 子句和 having 子句。

集合成员（Set Membership）

in 关键字可以测试一个值是否是一个集合的成员。这个集合是由 select 子句产生的。测试不是一个集合成员使用 not in关键字。

select distinct course_id
from section
where course_id in (select course id
		from section
		where semester = ’Spring’ and year= 2010);

集合对比（Set Comparison）

测试一个值至少大于一个集合中的一个值使用 > some 关键字，测试大于一个集合中的所有值使用 > all 关键字。这个集合同样是 select 子句产生的。

select name
from instructor
where salary > some (select salary
		from instructor
		where dept_name = ’Biology’);

测试空关系

使用 exists 关键字测试一个子查询的结果是否由存在元组。如果子查询结果为空，则返回 false，不为空则返回 true。

select course_id
from section as S
where semester = ’Fall’ and year= 2009 and
	exists (select *
		from section as T
		where semester = ’Spring’ and year= 2010 and
		S.course_id= T.course_id);

测试是否存在重复元组

使用 unique 关键字可以测试子查询是否存在重复的元组。存在重复返回 true，不存在则返回 false。not unique 测试是否不存在重复。

select T.course_id
from course as T
where not unique (select R.course_id
	from section as R
	where T.course_id= R.course_id and
		R.year = 2009);

子查询在 from 子句

select dept_name, avg_salary
from (select dept_name, avg (salary) as avg_salary
	from instructor
	group by dept_name)
where avg_salary > 42000;

with 子句

with 子句可以定义一个临时的关系。

with max_budget (value) as
	(select max(budget)
	from department)
select budget
from department, max_budget
where department.budget = max_budget.value;

标量子查询

SQL 允许子查询嵌入 select 子句中，子查询必须返回一个元组中的一个属性，这个子查询称为标量子查询（ Scalar Subqueries）

select dept_name,
	(select count(*)
	from instructor
	where department.dept_name = instructor.dept_name)
	as num_instructors
from department;

修改数据库操作

删除操作

delete from r
where P;

插入操作

insert into course
	values (’CS-437’, ’Database Systems’, ’Comp. Sci.’, 4);

插入元组基于一个查询的结果

insert into instructor (name, dept_name)
	select name, dept_name
	from student
	where dept_name = ’Music’;

更新操作

update instructor
set salary= salary * 1.05;

中级的 SQL

这部分主要介绍更复杂的 SQL 包括：SQL 查询，视图定义，事务，完整性约束，数据定义和授权。

join 表达式

上面介绍的 natural join 是根据相同的属性名称自动 inner join。SQL 支持明确指定 join 的断言，即指定 join 的属性。除了 inner join 还有 outer join。如果没有指定是 inner 还是 outer，一般 join 是指 inner join。

join 条件

使用 on 关键字可以指定 join 要关联的属性。

select *
from student join takes on student.ID= takes.ID;

outer join

inner join 取的是两个关系表属性的交集，outer join 可以取某一个关系表的全部元组，或者两个关系表的全部元组，没有关联的元组其它属性用 null 表示。

outer join 分为：

• left outer join：保留 join 语句前面的那个关系表的所有元组。
• right outer join：保留 join 语句后面的关系表的所有元组。
• full outer join：保留两个关系的所有元组。

outer join SQL 语句：

select *
from student natural left outer join takes;

join 用在子查询中：

select *
from (select *
	from student
	where dept_name= ’Comp. Sci’)
	natural full outer join
	(select *
	from takes
	where semester = ’Spring’ and year = 2009);

使用 where 子句代替 on 的断言

select *
from student left outer join takes on true
where student.ID= takes.ID;

视图

有时我们不希望用户看到全部的逻辑模型。出于安全考虑我们需要对用户隐藏一些数据。我们可以创建一个个性化的关系集合给用户查询，而不用整个逻辑模型。SQL 允许一个通过一个查询定义一个虚拟关系表。这个关系包含查询的结果。虚拟关系不是预先计算和存储的，而是每当使用虚拟关系时通过执行查询计算的。视图（View）不是逻辑模型的一部分，而是一个虚拟关系使用户可见的。

视图的定义

使用 create view 命令定义视图。表达式语法格式如下：

create view v as <query expression>

视图定义的例子：

create view faculty as
select ID, name, dept_name
from instructor;

使用视图

一旦我们定义了一个视图，我们可以使用视图名称作为一个虚拟关系。查询视图和查询正常的关系表是一样的。

select dept_name
from faculty
where name= ’Watson’;

物化视图

一些数据库系统允许视图关系被存储，当实际的关系改变时，视图是更新的，这样的视图称为物化的视图（Materialized View）。保持物化的视图更新的过程称为物化视图维护（Materialized View Maintenance），简称视图维护。

视图维护可以是及时的，关系改变时视图立刻更新；也可以是懒惰的，当视图访问的时候更新视图；另外也可以周期的更新视图。

如果用户频繁的使用视图，物化视图是有益的。视图可以快速的响应查询，避免读取大量的关系。物化视图可以带来好处，但也需要考虑它的不利因素，如存储空间的花费和视图更新操作需要的性能消耗。

更新视图

直接修改视图关系一般是不允许的。有些数据库允许更新视图。

事务

事务是由一系列 SQL 语句组成的一个逻辑单元。事务具有原子性。一个事务通过一个语句表示开始，通过一个语句表示结束。结束一个事务有两种操作，一个是提交，一个是回滚，其中某个操作必须发生且仅有一个操作发生。事务执行中没有任何错误发生，最终会执行提交。事务执行中出现错误，会执行回滚操作，数据库会回滚到事务开始时最初的状态。

当事务由多个 SQL 语句组成，单个 SQL 语句的自动提交需要关闭，使用应用程序接口，如 JDBC 或 ODBC 可以定义事务和关闭事务自动提交。

完整性约束

完整性约束（Integrity Constraint）确保数据库的改变不会丢失数据的一致性。常见的完整性约束，如名称不能为空。不能存在相同的 ID。预算金额必须大于0等等。

完整性约束通常是数据库模式（Schema）设计过程的一部分。完整性约束的声明是 create table 创建关系的一部分。完整性约束可以使用 alter table <table-name> add constraint 语句添加到已存在的关系中，当 alter 命令执行时，系统第一次会验证当前关系是否满足这个约束，不满足则拒绝这个添加约束命令。

单表的完整性约束

单表的完整性约束有：

• not null
• unique
• check

name varchar(20) not null
phone varchar(15) not null unique
age int check (age > 18)

参考完整性约束

参考完整性（Referential Integrity）它确保出现在一个关系中指定的属性值，也出现在另一个关系中。

foreign key 子句可以定义在 create table 语句中，定义个参考完整性约束。如：

foreign key (dept_name) references department

在 SQL 中，外键一般时参考另一个关系的主键。然而，只要参考候选键（Candidate Key）就行，如主键属性，或者唯一约束属性。

当一个参考完整性约束违反时，这个语句时被拒绝执行的。然而，foreign key 子句可以定义在参考的关系违反约束时指定一个删除或者更新操作，系统可以改变参考关系恢复约束，而不是拒绝执行。on delete cascade 子句在外键中声明，可以删除对应的参考关系元组，来满足约束。

foreign key (dept_name) references department 
	on delete cascade 
	on update cascade

SQL 也允许 foreign key 子句指定其它非 cascade 的动作。如使用 set null, set default 代替 cascade。

如果存在跨多个关系的一串外键依赖关系，则该链一端的删除或更新会在整个链中传播。

外键属性允许 Null 值，null 值自动满足参考完整性约束。

复杂的检查条件和断言

SQL 支持子查询在 check 子句中，如

check (time slot id in (select time slot id from time slot))

复杂的检查条件是有用的，但是也是有性能消耗的。每次插入或更新都要进行检查。

断言（Assertion） 是一个断言条件，数据库总是满足的。域约束和参考完整性约束是一个特殊形式的断言。断言的 SQL 形式如下：

create assertion <assertion-name> check <predicate>;

复杂的断言是耗费巨大的，使用时要谨慎。

当前，没有一种广泛使用的数据库系统支持 check 子句中的子查询或断言。然而，相同的功能可以通过触发器实现。

SQL 数据类型和 Schema

除了整数，浮点数和字符类型，SQL 还支持其它的内置数据类型。

SQL 中的日期和时间类型

• date：包含年月日等信息。
• time：包含时分秒。
• timestamp：date 和 time 的结合。

日期和时间的值具体格式如下：

date ’2001-04-25’
time ’09:30:00’
timestamp ’2001-04-25 10:29:01.45’

SQL 支持提取时间或日期中的单独的字段。如，提取日期中的年或月。

SQL 定义了一些函数取获取当前日期和时间。如，current_date()，current_time()。具体参考相关的数据库系统的实现。

SQL 允许时间日期数据使用算术和比较操作。如 select x - y , wher x < y

默认值

SQL 允许指定一个属性的默认值，通过 default 关键字进行指定。当插入语句没有给一个属性赋值时，则使用指定的默认值。

age int default 18

创建索引

索引（Index）是一个数据结构允许高效地查找属性值，而不用扫描一个关系中的所有元组。一个广泛使用的索引类型为 B+树索引。SQL 语言没有正式的定义索引的语法，大多数数据库系统支持索引创建语言如下：

create index studentID_index on student(ID);

大对象类型

很多当前的数据库应用需要存储特别大的属性，如一张图片，视频剪辑等等。SQL 提供大对象数据类型： clob (character data)和 blob (binary data)，其中字母 lob 表示 Large Object。

book review clob(10KB)
image blob(10MB)
movie blob(2GB)

取出一个完整的大对象到内存中是不高效的或不实际的。SQL query 将取出大对象的 locator（定位器），通过 locator 处理对象。

用户自定义的类型

SQL 支持创建用户自定义类型。有两种格式的类型：distinct types 和 structured data types。使用 create type 子句定义一个类型：

create type Dollars as numeric(12,2) final;

创建表扩展

SQL 支持创建一个与某个表有相同的 schema 的表，使用 create table ... like 语句。

create table temp_instructor like instructor;

创建一个表包含一个查询的结果，使用 create table ... as 语句。如：

create table t1 as
    (select *
    from instructor
    where dept name= ’Music’)
with data;

with data 表示包含数据，然而很多数据库实现默认包含数据，with data 子句可以忽略。

Schema, Catalogs, and Environments

数据库系统提供了一个三层等级的命名关系。顶层是 catalog，它包含下一层的 schema，每个 schema 包含多个 SQL 对象如关系表，视图等。

每个用户有一个默认的 catalog 和 schema。默认的 catalog 和 schema 为每个连接设置 SQL 环境的一部分，该环境还包括用户标识符（也称授权标识符）。所有常见的 SQL 语句都是在一个 schema 上下文中运行的。

授权

SQL 标准包含的权限（Privilege）有：select，insert，update和delete。所有权限使用 all privileges 表示。当一个用户执行一个 查询或更新时，系统授权检查该用户是否有这个权限。如果没有则拒绝执行。最终的权限是通过数据库管理员给定的。

权限的授与和撤销

grant 语句可以用来授予权限，权限可以授予给用户和角色。grant 语句格式如下：

grant <privilege list>
on <relation name or view name>
to <user/role list>;

授权的例子：

grant select on department to Amit, Satoshi;
grant update (budget) on department to Amit, Satoshi;

revoke 语句可以用来撤销权限，revoke 语句的语法格式和 grant 类似，撤销权限的例子：

revoke select on department from Amit, Satoshi;
revoke update (budget) on department from Amit, Satoshi;

角色

在现实生活中，一些用户有相同的权限。管理源需要重复的为某些用户授予权限。为了解决这个问题可以使用角色来给用户授权。先把权限授予给角色，然后把角色授予给用户。这样可以方便的管理用户权限。

创建一个角色语句的例子：

create role instructor;

给角色授予权限的例子：

grant select on takes
to instructor;

把角色授权给用户的例子：

grant instructor to dean;

权限的传递

一个用户的权限授予给另一个用户。使用 with grant option 子句，如

grant select on department to Amit with grant option;

高级的 SQL

编程语言执行 SQL

SQL 是一个强大的声明式查询语言。SQL 不是图灵完备的，所以数据库应用不能使用 SQL 开发。应用程序一般用 C, C++ 或 Java 实现，通过嵌入 SQL 来访问数据库。

应用程序访问数据库的两种方式：

• 动态的 SQL（Dynamic SQL）。程序在运行时构造一个 SQL 语句。通过应用程序接口提交 SQL 语句给数据库服务器，得到返回结果。常见的应用程序接口，如 JDBC 是 Java 语言连接数据库的应用程序接口。ODBC 是 C 语言的应用程序接口。
• 嵌入的 SQL（Embedded SQL）。在程序编译之前，使用预处理器将 SQL 语句给数据库系统预编译和优化，将程序中的 SQL 语句代替合适的代码。

JDBC

JDBC （Java Database Connectivity）标准定义了一个应用程序接口（API），让 Java 程序能够连接数据库服务器。不同的数据库系统有不同的 JDBC 实现。

JDBC 主要的操作：

• 与数据库建立连接。
• 传送 SQL 语句给数据库系统。
• 取出 SQL 执行的结果。
• 调用方法和存储过程。
• 获取数据库元数据。
• 执行事务。自动提交。

方法和存储过程

存储过程（Procedure）和方法（Function）允许一系列 SQL 操作存储在数据库，通过 SQL 语句调用执行。

它的优点：

• 允许多个应用程序访问。

• 一处修改多处使用，存储过程的逻辑改变，不需要修改其它应用程序。

• 应用程序调用存储过程，而不是直接的修改数据库关系。

SQL 标准定义了存储过程的语法标准，但是大部分数据库的实现是不标准的版本。

声明和调用方法和存储过程

SQL 标准的方法和存储过程例子：

create function instructors_of (dept_name varchar(20))
	returns table (
		ID varchar (5),
		name varchar (20),
		dept_name varchar (20),
		salary numeric (8,2))
return table
	(select ID, name, dept_name, salary
	from instructor
	where instructor.dept_name = instructor of.dept_name);

create procedure dept_count_proc(in dept name varchar(20), out d_count integer)
	begin
		select count(*) into d_count
		from instructor
		where instructor.dept_name= dept_count_proc.dept_name
	end

调用存储过程的 SQL 语句。

declare d_count integer;
call dept_count_proc(’Physics’, d_count);

存储过程和方法的不同：

• 存储过程是预编译的对象，而方法每次调用都要编译。
• 存储过程有输入参数和输出参数，而方法只有输入参数。
• 存储过程不包含 return 语句，可以返回 0 个或多个值。而方法有 return 语句，必须且仅有一个返回值，返回值可以是基本类或者组合类型。
• 方法可以调用存储过程，反之不能。

触发器

触发器（Trigger）是一个语句在触发事件时自动执行的。

触发器的用途：

• 实现一些完整性约束，当 SQL 的约束机制不能实现的。
• 启动一些自动任务。

定义触发器的 SQL 例子：

create trigger timeslot_check1 after insert on section
referencing new row as nrow
for each row
when (nrow.time_slot_id not in (
	select time_slot_id
	from time_slot)) 
begin
	rollback
end;

大部分数据库触发器实现的语法是不标准的。具体的情况，需要参考具体数据库的用法。

触发器可以设置启用或关闭。

触发器应该小心使用，因为运行时检测到触发器错误会导致出发该触发器的操作语句执行失败。触发器是有用的，但是当存在替代方案时最好避免使用触发器。

形式关系查询语言

关系型查询语言（如 SQL 语言）是基于形式模型的。常见的形式关系查询语言（Formal Relational Query Language）如下：

• 关系代数（Relational Algebra）
• 元组关系演算（Tuple Relational Calculus）
• 域关系演算（Domain Relational Calculus）

关系代数

关系代数（Relational Algebra）是一个过程的查询语言。它由一组操作组成，把一个和多个关系作为输入，产生一个新的关系作为结果。

基本的操作有：select，project，union，set difference，Cartesian product，rename。

其它操作：set intersection，natural join，assignment。

关系代数表达式的例子：

select

project

set union

set intersection

set difference

Cartesian product

rename

natural join

assignment

left/right/full outer join

arithmetic operations

aggregate functions

元组关系演算

元组关系演算（Tuple Relational Calculus）是一个非过程查询语言。一个元组关系演算的查询表示形式如下：

{t | P(t)}

t：表示所有的元组

P：表示断言。

t[A]：表示元组t中的属性A。

t ∈ A：表示元组 t 在关系 r 中。

元组关系演算查询表达式的使用例子：

{t | t ∈ instructor ∧ t[salary] > 80000}

{t | ∃ s ∈ instructor (t[ID] = s[ID] ∧ s[salary] > 80000)}

{t | ∃ r ∈ student (r[ID] = t[ID]) ∧
	( ∀ u ∈ cour se (u[dept name] = “ Biology” ⇒
		∃ s ∈ takes (t[ID] = s[ID]
		∧ s[course id] = u[course id]))}

域关系演算

域关系演算（Domain Relational Calculus）是另一种关系演算的查询语言。它的表达形式如下：

{< x1, x2,..., xn > | P(x1, x2,..., xn)}

x1, x2,…, xn 表示域变量，P 表示操作公式。

使用例子：

{< i, n, d,s > | < i, n, d,s > ∈ instructor ∧ s > 80000}

{< n > | ∃ i, d,s (< i, n, d,s > ∈ instructor ∧ s > 80000)}

无论是关系型代数，元组关系演算，还是域关系演算，每一个表达式都是由若干个基本操作组成的，所以，这三种形式关系查询表达式，可以互相转换。

在数据库系统中，一个查询的 SQL 语句，必须先转换为关系代数查询表达式，然后执行相关查询操作，因为关系代数查询表达式是过程的，它明确了执行哪些基本的操作，而 SQL 没有指定执行哪些基本操作。

小结

SQL 的细节实在是太多了，我们来小结一下。

SQL 内置的数据类型

SQL DDL

• 定义表：定义表的属性和数据类型，定义完整性约束，定义参考完整性约束。
• 定义索引。
• 修改表：添加/删除表字段、添加/删除表的约束。
• 删除表。
• 授权。
• 定义/删除：视图、存储过程、方法和触发器。

常见的完整性约束

• not null
• unique
• check
• referential Integrity

SQL DML

• 插入，修改，删除和查询元组。

SQL DML 的查询操作

• 基本的单表查询。select … from … where，去重（distinct, all），算术表达式，逻辑连词（and, or, not）。
• 基本的多表查询。from Cartesian product，natural join，outer join
• 其它基本的 SQL 查询操作。as（rename），like（string），order by，limit
• 集合操作。union，intersection，except
• 聚合函数和 having 子句。
• 嵌套子查询。

SQL DML 的查询总结

References

[1] Database System Concept (6th) by Avi Silberschatz, Henry F. Korth, and S. Sudarshan

本文将带你进入数据库系统的世界，带你了解数据库系统的核心概念，一览数据库系统的全貌。通过本文你将了解数据库系统是什么，它有哪些功能，它的组成结构，它是如何实现的，以及其它和数据库相关的知识。

介绍数据库系统

数据库系统是什么

数据库管理系统（Database-Management System，DBMS）是一组相互关联的数据的集合和一组用于访问这些数据的程序。数据库管理系统也可以简称为数据库系统。这些被管理的数据的集合称为数据库。数据库系统的主要目的是为了提供一种既方便又高效地存储和检索数据库信息的方法。

数据库系统是为了管理大量信息而设计的。管理数据的工作主要涉及：定义信息的结构；提供一个操作信息的机制；以及保证信息的安全，如防止未授权访问。

数据库系统的应用

数据库的使用是十分广泛的。常见的应用场景如：企业日常信息，银行和金融，大学，航空公司，和通信等。这些企业和机构需要利用数据库来存储和检索大量的数据信息。数据库已成为当今每个企业必不可少的组成部分。

20世纪90年代，网络的快速发展，大量的在线服务和应用被人们广泛的使用，这些应用的数据几乎都是存在数据库系统中。虽然应用接口隐藏了访问数据库的细节，大部分人在使用网络应用时没有意识到自己在操作数据库，实际上，访问数据库已成为每个人生活中不可缺少的一部分。

为什么需要数据库系统

在数据库系统出现之前，人们使用文件处理系统（File-Processing System）来存储和检索信息。文件处理系统简单地用一个文件和一个程序来管理一个实体的数据，它不适应数据结构的灵活改变和处理数据之间的关联关系。文件处理系统主要的缺点如下：

• 数据冗余（Data Redundancy）和不一致性（Inconsistency）。一个数据项出现在多个文件中，因为不同的文件由不同的程序处理的，所以出现数据冗余和不同文件的数据不一致。
• 访问数据很困难。程序不能实现复杂的信息检索功能。
• 数据隔离（Data Isolation）问题。数据分散在不同的文件，可能不同的格式。
• 完整性（Integrity）问题。很难实现数据的完整性约束条件。如账户余额不能少于零。
• 原子性（Atomicity）问题。很难实现原子操作，很难恢复和保证数据一致性。
• 并发访问异常。没有并发控制，导致并发访问数据异常。
• 安全问题。不能实现安全访问约束。

文件处理系统存在以上大量的问题，它不能满足企业对大量数据高效快速处理的需求，人们迫切需要一个更高效、便捷、安全的数据管理系统。所以需要开发一个数据库管理系统来解决这些问题。

数据的表现形式

数据库系统给用户提供了数据的抽象视图，它隐藏了数据是如何存储和如何维护的细节。

数据抽象

数据库系统需要高效的检索数据，这往往需要设计一个复杂的数据结构去表示数据。为了简化用户与数据库系统的交互，通常将数据抽象成不同的层级，如下所示：

• 物理层（Physical Level）。物理层是最低的抽象层描述了数据的实际存储方式，以及详细地描述了复杂的底层数据结构。
• 逻辑层（Logical Level）。逻辑层描述了哪些数据存储在数据库中，数据之间存在什么关系。
• 视图层（View Level）。简化用户与系统的数据交互，仅提供一部分重要的信息给用户，隐藏一些次要的信息。

物理层，它通过编译器向数据库程序员隐藏了底层存储的细节。逻辑层，它通过编程语言向程序员隐藏了数据存储的细节。视图层，它通过应用程序向用户隐藏了数据类型的细节。

不同的用户在不同的抽象层与数据库进行交互，使得每一个用户都可以方便和高效的管理数据。

实例和模式

实例（Instances）是某一个时刻存储在数据库中的信息的集合。

模式（Schema）是全部的数据库的设计。

数据模型

数据模型（Data Models）是数据库结构和基础。它是一个用于描述数据、数据关系、数据语义和一致性约束的概念性工具的集合。数据模型提供了一种方式去描述数据库在物理层、逻辑层、视图层的设计。

常见的数据模型：

• 关系型模型（Relational Model）。使用一组表（Table）来表示数据和数据之间的关系。每个表有多个列（Columns）每个列有唯一的名称。表也称为关系（Relation）。
• 实体关系模型（Entity-Relationship Model）
• 基于对象的数据模型（Object-Based Data Model）
• 半结构化的数据模型（Semistructured Data Model）

以上数据模型中，关系型模型应用最为广泛，大部分数据库系统是采用关系型模型实现的。

数据库语言

数据库系统提供了数据定义语言去指定数据库的模式（Schema），以及数据操纵语言去表示数据库查询和更新操作。数据定义语言和数据操纵语言不是两种单独的语言，它们都是数据库语言的组成部分。被广泛使用的数据库语言，如 SQL（Structured Query Language）语言。

数据操纵语言

数据操纵语言（Data-Manipulation Language, DML）能够访问和操作数据。基本的操作类型为：查询，插入，删除和修改。

数据操纵语言可以分为两种类型：程序式的（Procedural），声明式的（Declarative）。声明式的更简单，不需要指定如何获取数据。

数据定义语言

数据定义语言（Data-Definition Language, DDL）指定了数据库的模式，也指定了数据的属性。

数据存储在数据库中必须要满足某些一致性约束（Consistency Constraints）。如，账户余额不能少于0。数据定义语言（DDL）可以指定数据的完整性约束（Integrity Constraints），完整性约束是一致性约束的一部分，它防止不符合规范的数据进入数据库。常见的完整性约束如下：

• 域约束（Domain Constraints）。约束数据的取值范围和精度等。
• 参考约束（Referential Constraints）。关系 A 的一个属性参考关系 B 的属性，参考的属性必须出现在被参考的关系中。
• 断言（Assertions）。数据需要满足断言的约束条件。

数据定义语言的输出结果保存在数据库系统的数据字典（Data Dictionary）中，它包含了数据库的元数据（Metadata）即描述数据的数据。

关系型数据库

关系型数据库（Relational Database）是基于关系模型（Relational Model）的和使用一系列的表（Table）来表示数据和数据之间的关系。

表

一张表（Table）包含多个列，每个列有唯一的名称。一个表的结构示例，如下图所示。

数据库的表是由一些类型固定的记录（Record）构成的，一行数据称为一个记录。每个记录有固定数量的字段（Field）或属性（Attribute）。表的每一列与记录的每一个字段是相对应的。

表的操作

我们可以使用 SQL 语言来对数据库进行操作。如创建一张表：

create table department
	(dept_name char(20),
	building char(15),
	budget numeric(12,2));

查询数据

select department.dept_name
from department
where department.budget > 95000;

应用程序访问数据库

SQL 语言不是图灵完备的，一些计算不能通过 SQL 语言完成，但是操作数据库必须使用数据库语言如 SQL 语言。由于应用程序不能通过 SQL 语言来实现，一般使用如 C, C++ 或者 Java 来实现，应用程序访问数据库一般是通过嵌入 SQL 语句来与数据库进行交互的。

应用程序访问数据库的两种方式：

• 应用程序接口。通过它发送 DML 和 DDL SQL 语句给数据库，和取回执行结果。
• 嵌入 DML 调用。

数据库设计

数据库设计主要任务是数据库模式（Schema）的设计。

设计过程

• 需求分析。与用户和领域专家进行交流，设计如何让数据库的结构满足用户的数据需求。收集需求，用文字的形式描述数据结构，最后得出一个用户需求规格说明书。

• 概念设计（Conceptual Design）。选择一个数据模型，将用户需求转换为数据库概念模式。这个阶段主要是专注于描述数据和数据之间的关系。用专业的概念的数据模型去描述数据结构，主要使用 entity-relationship model 和 normalization 方式去设计。

• 逻辑设计（Logical Design）。将抽象的数据模型转换为数据库的实现。将概念模型转换为数据库系统使用的模型，如将 entity-relationship model 转换为 relational model。

• 物理设计（Physical Design）。设计物理存储的细节。包括文件组织的形式和内部的存储结构等。

实体关系模型

Entity-Relationship (E-R) 数据模型使用一组对象称为实体（Entity）和对象之间的关系（Relationship）来表示数据和它们之间的关系。每个实体由一组属性组成。E-R 模型可以表示数据约束。一个实体类型的所有实例称为实体集（Entity Set），两个实体类型的所有的实例之间的关系称为关系集（Relationship Set）。

E-R 模型中一个重要的约束是映射基数（Mapping Cardinality）它表示一个实体关联另一个实体的数量。

标准化

标准化（Normalization）可以让我的数据减少不必要的冗余。它使用范式（Normal Form）来设计数据库的模式（Schema）。常见的范式有：First normal form (1NF), Second normal form (2NF), Third normal form (3NF), Boyce-Codd normal form (BCNF).

数据的存储和查询

数据库系统分为多个模块，它们分别处理不同的任务。数据库系统的功能可以大致分为存储管理器（Storage Manager）和查询处理器（Query Processor）。存储管理器负责管理数据的物理存储空间，查询处理器负责简化和优化数据的访问。

存储管理器

存储管理器是数据库的一个组件，它提供了底层存储和应用程序之间的接口。它与操作系统的文件系统进行交互。它将 SQL 语句转换为底层的文件系统的命令。存储管理器的主要职责是：存储、取出和更新数据库中的数据。

存储管理器的组件包括：

• 授权和完整性管理器（Authorization and Integrity Manager）

• 事务管理器（Transaction Manager）

• 文件管理器（File Manager）

• 缓存管理器（Buffer Manager）

存储管理器实现的物理结构

• 数据文件（Data File）。存储数据库的数据的文件。
• 数据字典（Data Dictionary）。存储元数据即数据库的结构或模式。
• 索引（Index）。提供快速访问数据库数据的一种数据结构。

查询处理器

查询处理器（Query Processor）的组件包括：

• DDL 解释器（DDL Interpreter）
• DML 编译器（DML Compiler）
• 查询评估引擎（Query Evaluation Engine）

事务管理

真实场景中的数据操作往往需要具备一些基本的特性。如：

• 原子性（Atomicity）。一组数据操作组成一个逻辑的单元，这些操作必须全部完成或者全部失败。
• 一致性（Consistency）。数据的操作必须是正确的。如 A 转账给 B，A 和 B 的总金额必须是不变的。
• 持久性（Durability）。数据可以长久的保存。

事务（Transaction）是在数据库应用程序中执行单个逻辑功能的操作的集合。事务是一个原子性和一致性的单元。事务管理器由并发控制管理器（Concurrency-Control Manager）和恢复管理器（Recovery Manager）组成。其中，并发控制管理器负责的是：当多个事务同时修改数据库时，保证每个事务都是正确的。恢复管理器负责的是：当事务发生错误时恢复原始数据状态。

为了确保数据的一致性，程序员有责任去定义合适的事务。确保数据的原子性和持久性则是数据库系统本身的职责。

数据库的架构

数据库系统由多个组件构成，它的系统结构如下图所示：

数据库的体系结构可以是中心化的 client-server 结构，也可以是平行的、分布式的结构。

数据库应用程序通常划分为两层或者三层结构。如下图所示：

其它

数据挖掘和信息检索

数据挖掘（Data Mining）是指半自动分析大型数据库，从中找到有用的模式的过程。数据挖掘不同于机器学习，机器学习是处理大量的磁盘中的数据文件，而数据挖掘指的是处理数据库中的数据。由于很多查询是十分复杂的，很难使用 SQL 进行查询，所以需要使用数据挖掘技术。数据挖掘可以从数据中分析出有价值的规律，它可以帮助企业执行更好的决策。

数据仓库（Data Warehouse）可以在一个站点中一统一的模式收集不同来源的数据。提供为用户提供了一个统一的数据接口。

信息检索（Information Retrieval）是指查询无结构的文本数据。

其它特性（非关系型）数据库

在某些数据库系统的应用领域，关系型数据模型是受限制的。我们需要其它的数据模型来处理这些应用领域。常见的非关系型模型，如

• 对象基于的数据模型（Object-Based Data Model）。它可以便捷的实现面向对象编程的数据存储。

• 半结构化的数据模型（Semistructured Data Model）。它的特点是相同类型的单个数据项可能具有不同的属性集。

• 键值数据模型（Key-value Data Model）。它是使用 map 或字典实现的。每一个 key 关联一个集合。键值数据模型没有查询语言，它使用简单的 get, put, 和 delete 命令去操作数据。它具有快速存取，可扩展性和可靠性等特点。

数据库的用户和管理员

与数据库系统进行交互的人群可以以分为：数据库用户和数据库管理员。

不同类型的数据库用户的不同交互方式为：

• 普通的用户。通过应用程序与数据库系统进行功能。
• 应用开发人员。通过编程语言与数据库系统交互，开发应用程序，提供用户接口。
• 专业人员。直接使用数据库查询语言操作数据库系统。

数据库管理员的作用：

• 定义模式。通过执行 DDL 来创建数据库模式（Schema）。
• 定义存储结构和访问方式。
• 修改模式和物理组织。
• 授权数据的访问。
• 日常维护。周期性的备份数据库。确保有充足的磁盘空间。监控数据库系统的运行状态等等。

小结

• 首先认识了数据库系统，知道了它是什么和为什么，以及了解数据的表现形式、数据库语言等基本的数据库系统相关的概念。

• 然后介绍了具体类型的数据库，了解了关系型数据库。以及如何设计数据库。

• 接着介绍了数据库系统的内部结构，了解了存储，查询和事务等核心的数据库系统的组件。

• 最后讲了一些和数据库系统相关的其它概念。

References

[1] Database System Concept (6th) by Avi Silberschatz, Henry F. Korth, and S. Sudarshan

操作系统安全

操作系统安全问题

• 系统帐号密码攻击。用户帐号密码被破解导致：1. 破坏系统文件。2. 安装恶意软件（间谍软件、病毒软件）。3. 比特币勒索。
• 借助第三方软件服务攻击系统。1. 利用 Redis 将 SSH 密钥写入到 authorized_keys config set dir /root/.ssh, config set dbfilename authorized_keys。2. 利用 Redis 设置挖矿定时任务 config set dir /etc, config set dbfilename crontab。

操作系统防护措施

• 系统和软件包更新，防止低版本漏洞攻击。保持操作系统打上最新的补丁，保证使用最新版本的软件。
  • 手动定期更新，或者设置自动更新（Unattended Upgrades）。
• 设置系统防火墙
  • 仅开放必要端口，如：22 for SSH，80 for HTTP，443 for HTTPS，VPS 端口等。其它端口设置 IP 白名单。
• 系统帐号保护
  • 设置高强度 root 密码。
  • 定期更新 root 密码。
  • 不使用 root 帐号登录。
• 远程登录保护
  • 修改 SSH 默认端口。
  • SSH 登录使用公钥登录。定期更换公钥。
  • 关闭 root 登录。
  • 关闭密码登录功能。
  • 系统防火墙设置 SSH 登录 IP 白名单。
• 数据保护
  • 定期对操作系统进行镜像备份。
• 防止第三方软件服务漏洞攻击（虽然有防火墙，但不能保证防火墙被同事或其他人修改。可以在防火墙的基础上，再做一些防护）
  • 使用 Docker 以 Non-Root User (Rootless mode) 身份运行软件服务（如：Redis）。

数据库安全

数据库安全问题

• 登录帐号攻击。用户帐号被破解导致：1. 用户隐私信息泄露。2. 数据库被删除或篡改。3. 比特币勒索。

数据库防护措施

• 一般保护
  • 修改数据库默认端口。
• 数据保护
  • 开启MySQL 的 binlog 和 redo log。
  • 定期手动（或定时脚本自动）进行异地备份数据库（或增量同步到备份数据库系统）。
  • 重要的隐私信息加密存储。
• 帐号保护
  • 设置高强度 root 密码。
  • 不使用 root 帐号登录数据库。
  • 不同数据库设置不同的用户帐号。
  • 不要把帐号密码明文写在项目配置文件中。
• 远程登录保护
  • 设置数据库远程登录 IP 白名单。
  • 远程登陆使用公钥登录。
  • 使用 MySQL 代理。写一个 LUA 检查脚本，错误登录频率限制，三次错误登录 IP 加入黑名单。
  • 不使用远程登录数据库。通过 SSH 登录服务器，从而本地访问数据库。

应用系统安全

应用系统安全问题

• 登录帐号攻击。1. 字典攻击或暴力攻击，获取用户的帐号密码。从而获取用户隐私，执行恶意操作。
• 网络通信安全攻击。1. 监听网络通信数据。2. 篡改网络数据。3. 网站伪造。钓鱼网站。
• XSS 攻击。1. 页面注入恶意脚本<script>，获取用户的 Cookie 信息，从而登录用户帐号。2. 让原始用户执行不当操作。如 <img src="http://mybank.com/transfermoney?amount=1000&toaccount=14512">
• SQL 注入攻击。1. 执行未授权的恶意 SQL。如';<some SQL statement>;--2. 跳过登录密码验证。
• DOS / DDoS 攻击。1. 拒绝服务攻击，大量请求服务器，导致正常用户无法使用网站应用。

应用系统防护措施

• 一般保护
  • 使用加密的域名解析服务，不暴露服务器 IP 地址。
  • 使用 Cloudflare proxied DNS 或者 Cloudflare Tunnel，不暴露服务器 IP 地址。
  • 使用 Nginx 代理，隐藏应用端口。
  • 应用端口仅能被代理服务器访问，系统防火墙设置应用端口访问的 IP 白名单。
  • 定期备份应用的数据文件。
• 登录保护
  • 错误登录频率限制。要求输入验证码。
  • 使用 Tow-Factor 认证，如：短信验证码。
  • 异地登录邮件提醒。
  • 禁止弱口令。需要设置高强度用户密码。
• 网络通信保护
  • 使用 HTTPS 协议通信。
  • 客户端用户密码加密和加盐传输。
• XSS 攻击防护
  • 不允许用户输入的文本显示为 HTML 标签。
  • 阻止 XSS 攻击运行在其它网站。1. HTTP 请求头的 referer 检查。2. 不仅仅通过 cookie 中的session 来识别用户，判断用户 session 需要检查是否为原始用户认证通过的 IP 地址。
  • 添加和修改操作使用 HTTP POST 请求。
• SQL 注入防护
  • Java 数据库操作使用 PreparedStatement 对象。
• DoS / DDoS 防护
  • 异常高频率访问 IP ，使用 Fail2ban 进行限制和加入黑名单。
  • Cloudflare DDoS Protection and Web Application Firewall (WAF).
• 使用审计追踪用户行为。检查、分析和阻止恶意行为。
• 部署入侵侦测系统。记录和分析恶意攻击行为。
• 部署蜜罐系统。检测未知的攻击，识别潜在风险。

References

[1] 5 Linux SSH Security Best Practices To Secure Your Systems

[2] Preventing brute-force attacks on MySQL? - serverfault

[3] Database System Concepts - Section 9.7: Application Security

算法分析方法

• 渐进分析（Asymptotic Analysis）

常见的算法设计策略

• 动态规划（Dynamic Programming）
• 分治（Divide and Conquer）
• 贪心（Greedy Algorithm）
• 回溯（Backtracking）

常见的排序算法

• 插入排序（Insertion Sort）
• 冒泡排序（Bubble Sort）
• 选择排序（Selection Sort）
• 希尔排序（Shellsort）
• 归并排序（Mergesort）
• 快速排序（Quicksort）
• 堆排序（Heapsort）
• 基数排序（Radix Sort）

常见的搜索算法

• 二分查找（Binary Search）

常见的数据结构操作算法

• 二叉树的遍历（递归和循环实现方式）
  • 先序遍历（Pre-order Traversal）
  • 中序遍历（In-order Traversal）
  • 后序遍历（Post-order Traversal）
  • 层级遍历（Level-order Traversal）
• 图的搜索
  • 深度优先搜索（Depth-first Search, DFS）
  • 广度优先搜索（Breadth-first Search, BFS）

算法策略

算法策略是指设计和解决一类问题的通用方法或模板。也可以称为算法范式（Algorithm Paradigm）。常见的算法策略，如动态规划、分治、贪心和回溯等。每个算法策略有它的设计思路，解题步骤。算法策略往往提供了优化算法的功能，使用算法策略比直接法（枚举法，穷举法）有更好的效率。

动态规划

介绍动态规划

动态规划（Dynamic Programming）是一种数学优化方法和一种算法策略。这个方法是 Richard Bellman 在1950 年发明的。它指的是通过递归的方式，将问题分解为更简单的子问题，从而简化一个复杂的问题。

动态规划问题必须具备两个属性：最优子结构和重叠的子问题。如果一个问题有最优子结构，但没有重叠的子问题，那么它是一个分治问题。

最优子结构（Optimal Substructure）。如果一个问题可以通过“将问题分解为子问题和递归地找到子问题的最优解”来最优地解决，那么称它有最优子结构。也可以说，得到一个问题的最优解可以通过子问题的最优解来实现。如果一个问题具有最优子结构，较大问题和它的子问题之间的存在关联，这种关系称为 Bellman 方程。

重叠的子问题（Overlapping Sub-Problem）。求解过程中递归地求解相同的子问题，没有产生新的子问题。也可以说，问题和子问题存在一个固定的关系表达式，如 F(n) = F(n-1) + F(n-2) ，F(n) = F(n-1) * 2 + 1。所有的子问题可以用一个固定的算法代码去实现。

解决动态规划问题的两种方法：

• 自顶向下方法（Top-down Approach）。将子问题的结果存储在列表中，当我们要解决新的子问题时，我们会首先检查是否已经解决。如果结果已经记录在列表中，可以直接使用它，否则我们解决子问题并将其结果添加到列表中。如：我们可以通过 F(n) = F(n-1) + F(n-2) 得到问题的结果，先检查子问题结果列表中有没有子问题 F(n-1) 和 F(n-2) 的结果，如果有就直接使用，没有就求解这两个子问题。依次往下递归，每个子问题只计算一次。
• 自底向上方法（Bottom-up Approach）。一旦按照子问题递归地制定了问题地解决方案，我们可以尝试自底向上地去解决问题。自底向上地方法大部分不需要记录每个子问题的结果，只需要替换记录几个需要地子问题结果。具体过程：通过使用较小的子问题的结果迭代生成越来越大的子问题结果。如，已知子问题 F40 和 F41 的结果，可以直接计算出 F42 的结果。

解题步骤

1. 判断一个问题是否是动态规划问题。

判断问题是否具有最优子结构和重叠的子问题等特性。

2. 构造出问题与子问题之间的关系表达式

常见的动态规划问题的子问题关系表达式，见附录一

3. 使用自顶向下或者自底向上求解。

例子

求第 n 个斐波那契数。

直接法简单的解决方法。T(n) = O(2 ^ n), S(n) = O(1)

int fib(int n)
{
	if (n <= 1)
		return n;
	return fib(n-1) + fib(n-2);
}

动态规划自顶向下方法。T(n) = O(n), S(n) = O(n)

int fib(int n, auto &lookup)
{
	if (n <= 1)
		return n;
	if (lookup.find(n) == lookup.end())
		lookup[n] = fib(n-1, lookup) + fib(n-2, lookup);
	return lookup[n];
}

动态规划自底向上方法。T(n) = O(n), S(n) = O(1)

int fib(int n)
{
	if (n < 1)
		return n;
	int prev = 0, curr = 1;
	for (int i = 0; i < n-1; i++)
	{
		int newFib = prev + curr;
		prev = curr;
		curr = newFib;
	}
	return curr;
}

分治

介绍分治

分治（Divide and Conquer）是一个基于多分支递归的算法设计范式。它将一个问题递归的分解为两个或多个子问题，直到它们足够简单能够直接求解。

解题步骤

分析问题得到分解策略。

根据分解策略，递归地求解。

例子

参考快速排序、归并排序算法。

贪心

介绍贪心算法

贪心算法（Greedy Algorithm）是一个算法设计范式。它在每个阶段做出局部最优选择，以寻求全局最优。

解题步骤

根据贪心策略一小段一小段的求解，最后得到问题的最优解。

回溯

介绍回溯

回溯（Backtracking）是一种算法范式，用于查找某些计算问题的所有结果。它逐步的构建候选对象，一旦确定候选对象无法得到有效的结果立刻将其放弃。

回溯是解决约束满足问题的重要工具。它可以快速测试是否能得出满足条件的有效结果。如填字游戏，数独，棋盘等问题。回溯算法通常比对所有对象的暴力枚举（Brute Force Enumeration）更有效率，因为它通过一个测试减少了很多候选对象。

常见类型：

• 路径选择。如：最短路径，是否存在路径，打印所有存在路径。这类问题的背景：迷宫，国际象棋，二维数组，图。

解题步骤

1. 判断是否是一个回溯问题。

2. 设定一个开始点，进行循环遍历。

3. 当前结果是否满足条件。如果是，打印结果。如果不是，循环递归所有的有效的下一个候选对象。

例子

N Queens problem.

#include <iostream>
#include <cstring>
using namespace std;

#define N 8

int count = 0;

bool isSafe(char mat[][N], int row, int col)
{
	for (int i = 0; i < row; i++)
	{
		if (mat[i][col] == 'Q')
		{
			return false;
		}
	}
	
	for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
	{
		if (mat[i][j] == 'Q')
		{
			return false;
		}
	}
	
	for (int i = row, j = col; i >= 0 && j < N; i--, j++)
	{
		if (mat[i][j] == 'Q')
		{
			return false;
		}
	}
	
	return true;
}

void NQueen(char mat[][N], int row)
{	
	if (row == N)
	{
		cout << ++count << endl;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				cout << mat[i][j] << " ";
			}
			cout << endl;
		}
		cout << endl;
		return;
	}
	
	// place Queen at every square in current row r
    // and recur for each valid movement 
	for (int k = 0; k < N; k++)
	{
		if (isSafe(mat, row, k))
		{
			// place queen on current square
			mat[row][k] = 'Q';
			// recur for next row
			NQueen(mat, row+1);
			// backtrack and remove queen from current square 
			mat[row][k] = '-';
		}
	}
	return;
}

int main()
{
	// mat[][] keeps track of position of Queens in current configuration
	char mat[N][N];
	
	// initalize mat[][] by '-'
    memset(mat, '-', sizeof mat);
	
	int row = 0;
	NQueen(mat, row); // N=8 has 92 possible N-Queen result 
	return 0;
}

关于算法设计的思路

1. 思考问题的直接法的解决方法。

2. 考虑优化。是否存在大量重复的操作？是否存在不必要的操作？

3. 考虑算法设计策略。

问题的局部最优解能不能得到全局最优。如果能，考虑使用贪心算法。

问题能不能递归地分解为子问题求解（是否具有最优子结构）。如果能，考虑使用分治法，或者动态规划。

附录一

常见的动态规划问题的子问题关系表达式。

Fibonacci

         | n                  (n <= 1)
Fib(n) = |
         | Fib(n-1) + F(n-2)   (n > 1)

Longest Common Subsequence (LCS)

             | 0                              (i == 0 or j == 0)
LCS[i][j] =  | LCS[i-1][j-1] + 1              (X[i-1] = Y[j-1])
             | max(LCS[i-1][j], LCS[i][j-1])  (X[i-1] != Y[j-1])

Shortest Common Supersequence (SCS)

             | i+j                            (i=0 or j=0)
SCS[i][j] =  | SCS[i-1][j-1] + 1              (X[i-1] = Y[j-1])
             | min(SCS[i-1][j] + 1, SCS[i][j-1] + 1)  (X[i-1] != Y[j-1])

Longest Increasing Subsequence (LIS)

         | 1    (n=1)
LIS(n) = | 
         | max(L(i))    0 < i <= n

The Levenshtein distance (Edit distance)

             | max(i, j)                       when min(i, j) = 0
             
dist[i][j] = | dist[i - 1][j - 1]              when X[i-1] == Y[j-1]
             
             | 1 + minimum { dist[i - 1][j],   when X[i-1] != Y[j-1]
             |               dist[i][j - 1],
             |               dist[i - 1][j - 1] }

References

[1] Dynamic programming - Wikipedia

[2] How to solve a Dynamic Programming Problem ? - Geeksforgeeks

[3] Introduction to Dynamic Programming - Techie Delight

[4] Divide-and-conquer algorithm - Wikipedia

[5] Backtacking - Wikipedia

基本数据结构

List

List 的抽象数据类型

列表（List）包含一组按顺序排列的相同类型的元素，它的操作如下：

• get() - 返回给定位置的一个元素。
• insert() - 插入一个元素在指定位置。
• remove() - 删除第一个元素。
• removeAt() - 删除一个特定位置的元素。
• size() - 返回列表元素的数量。
• isEmpty() - 返回列表是否为空。
• isFull() - 返回列表是否已满。
• clear() - 清空列表的内容。

List 的实现

Array List

数组是列表的一种实现，它在内存中是连续的空间。

优点

• 它可以快速的随机访问。

缺点

• 插入和删除性能不太好，需要大量的元素位置移动。

应用场景

• 简单的存储一组数据。

Linked List

链表是一个线性结构，它是列表的另一种实现，它在内存中是非连续的空间。每个元素称为节点，相邻的两个节点由指针进行连接。

优点

• 它具有很好的扩展性，快速的插入和删除。

缺点

• 随机访问（按位置访问）性能不好。节点的访问必须从前往后依次遍历。
• 比数组消耗更多的内存。在使用的指针上。
• 需要更多的读取时间。在内存中是不连续的，CPU 一次只能获取一个元素，

应用场景

• 迭代器。

Array List vs Linked List

Stack

Stack 的抽象数据类型

栈（Stack）是一个线性的数据结构。它遵循一个特殊的操作顺序。后进先出（Last In First Out, LIFO），它的操作如下：

• push()
• pop()
• peek()
• size()
• claer()

Stack 的实现

栈可以基于数据实现，也可以基于链表实现。

优点

• 方便的按照某种循序访问数据。

缺点

• 只用于特定场合。

应用场景

• 逆序输出。
  • 进制转换。
• 递归嵌套。
  • 括号匹配
  • 栈混洗（Stack Permutation）。通过一个中间栈，重新排序原始栈的数据顺序。。
• 延迟缓冲。
  • 中缀表达式。操作符以中缀形式处于操作数中间的算术表达式。
  • 逆波兰表达式。不需要括号的后缀表达式。
• 栈式计算。

Queue

Queue 的抽象数据类型

队列（Queue）是一个线性结构。它和栈类似有特殊的操作顺序。先进先出（First In First Out, FIFO）。它的操作如下：

• enquque()
• dequeue()
• peek()
• size()
• claer()

Queue 的实现

队列可以基于数组实现，也可以基于链表实现。

优点

• 方便的按照某种循序访问数据。

缺点

• 只使用在特定的场合。

应用场景

• 系统任务调度。

Binary Tree

Binary Tree 的抽象数据类型

二叉树（Binary Tree）是一个树结构，每个节点最多有两个子节点，分别表示为左子树和右子树。它的操作：

• getRoot()
• isEmpty()
• size()
• contains()
• find()
• toString()
• iteratorInOrder()
• iteratorPreOrder()
• iteratorPostOrder()
• iteratorLevelOrder()

Binary Tree 的实现

二叉树通过指针关联节点实现。

优点

• 可以表示树结构的数据关系。

缺点

• 大量的指针消耗。

应用场景

• 用于搜索。通过 binary search tree 可以支持快速的搜索、插入和删除，复杂度都是 O(log n)。
• 用于压缩。使用在 Huffman Coding。
• 用于数据库的索引的实现。

Graph

Graph 的抽象数据类型

图（Graph）由一组有限个顶点（Vertex）和有限的边（Edge）组成。它的操作如下：

• addVertex(vert)
• addEdge(fromVert, toVert)
• addEdge(fromVert, toVert, weight)
• getVertex(vertKey)

Graph 的实现

图可以通过邻接表（adjacency List），也可以邻接矩阵（adjacency Matrix）实现。

应用场景：

• 用于计算机网络的路由，找到最小花费路径。

• 社交媒体应用，用户之间的关联。

• 地图应用。如，找到最优的行驶路线。

• 电商网站。推荐商品。

其它数据结构

Dictionary

Dictionary 的抽象数据类型

字典（Dictionary）高效地组织数据，支持快速地存储和查找。每个元素由一个 key 和一个复合类型（对象）组成<key, E>。通过 key 来唯一标识一个对象，可以通过 key 来查找对象。它的操作如下：

• insert(key, object)
• remove(key)
• find(key)
• size()
• clear()

Hash Table

Hash Table 的抽象数据类型

哈希表（Hash Table）是一个由链表组成的数组结构。它使用哈希函数计算一个元素值在数组中的索引。它的操作：

• put(key, value)
• get(key)
• containsKey(key)
• contains(value)
• remove(key)

Hash Table 的实现

哈希表由链表数组实现。

优点

• 快速的查找。
• 快速的插入和删除。

缺点

• 不保证元素的顺序。不能随机访问。

数据结构的选择

插入删除/扩展性

数据的容量需要很好的扩展性，或者频繁的插入和删除，选择动态的数据结构（指针关联）比较合适。如链表，二叉树等等。不足之处是指针结构对随机存取效率没有静态结构（连续空间）好。

搜索

简单的搜索即从第一个元素一直比较直到最后一个元素。如数组，它的复杂度是 O(n)。

更高效率搜索的数据结构，哈希表的复杂度为 O(1)，有序数组复杂度为 O(log n)，搜索二叉树的复杂度为 O(log n)

综合考虑

兼顾搜索和插入：可以考虑哈希表和搜索二叉树。有序数组虽然搜索复杂度和搜索二叉树一样，但是有序数组的插入性能不好。

兼顾搜索和随机存取：可以考虑有序数组。

数据结构的总结

组成形式：连续空间，不连续（指针）空间。

结构关系类型：线性，树状，图

本质：存储一组元素，表示元素之间的关系，提供操作元素的方法。

数据结构的总结：

• 数据结构是用来表示数据和操作数据的。

• 有些数据结构只适用于特殊的场景。

• 一个好的数据结构可以大幅度提高算法的效率。

• 不存在一种数据结构在所有方面都优于另一个数据结构，每个数据结构都有自己的优缺点。数据结构的选择是一个权衡利弊和妥协的过程。

References

[1] Data Structures and Algorithm Analysis in C++ (3rd) by Clifford A. Shaffer

[2] Abstract Data Types - GeeksforGeeks

[3] The BinaryTree ADT

[4] The Graph Abstract Data Type

[5] Linked List - Wikipedia

[6] What are the applications of binary trees? - Stack Overflow

[7] What are real life applications of graphs? - Quora