一、图灵机图示

下图是图灵机的简单示意图 : 图灵机由 无穷长的带子 , 读头 , 状态 组成 ;

带子 :

无穷长度 , 每个格子有一个字符 ;

读头 :

上图中的箭头是读头 , 用于读写数据 ;

读头作用是 读取带子上的字符 , 然后擦掉该字符 , 写入新的字符 ;

然后该读头可以 向左或向右移动一格单位 ;

状态 :

箭头上的矩形框中表示当前的状态 , 状态个数是有限多个 , 其作用是指挥图灵机如何进行计算 ;

上述图灵机是理想的图灵机 , 带子是无穷长的 , 带子上的字符是有限多个 , 状态是有限多个 , 指令也是有限多个 ;

二、图灵机形式定义

图灵机要素 :

① 有限多状态集 , $\mathrm{Q}$ ;

② 有限多个字符集 , $\mathrm{\Sigma }$ ;

③ 带子字符集 , $\mathrm{\Gamma }$ , 包含 $\mathrm{\Sigma }$ ;

④ 转换函数 , 即指令集 , $\delta$ ;

⑤ 开始状态 , ${\mathrm{q}}_0$ , 包含在 $\mathrm{Q}$ 中 ;

⑥ 空白字符 , $\mathrm{u}$ , 包含在 $\mathrm{\Gamma }-\mathrm{\Sigma }$ ( 相对补集 ) 集合中 ;

⑦ 一些接受状态 , $\mathrm{F}$ , 其中 $\mathrm{F}\subseteq \mathrm{Q}$ ;

指令与转换函数 : 图灵机是根据指令进行计算的 , 指令 是一个 转换函数 $\delta$ ;

转换函数 $\delta$ 两个输入参数 :

• 参数一 : 状态 $\mathrm{q}$ , 该状态是 $\mathrm{Q}$ 中的元素 , $q\in \mathrm{Q}$ ;
• 参数二 : 带子字符 $Z$ , 该字符是 $\mathrm{\Gamma }$ 集合中的元素 , $\mathrm{Z}\in \mathrm{\Gamma }$ ;

转换函数 $\delta$ 输出是一个三元组 :

• 输出一 : 状态 $\mathrm{p}$ ;
• 输出二 : 带子字符 $\mathrm{Y}$ ;
• 输出三 : 方向 $\mathrm{D}$ , 向左或向右 , 读取头下面要移动的方向 ;

指令 $\delta$ 表示的含义解析 :

$\delta (\mathrm{q},\mathrm{Z})=(\mathrm{p},\mathrm{Y},\mathrm{D})$ 转换函数 , 其中 $\mathrm{q},\mathrm{Z}$ 是两个输入 , $\mathrm{p},\mathrm{Y},\mathrm{D}$ 是三个输出 ,

开始时图灵机的 状态是 $\mathrm{q}$ 状态 , 读取头指向的字符是 $\mathrm{Z}$ ,

执行该转换函数 $\delta$ , 会将 状态转变为 $\mathrm{p}$ 状态 , 将 读取头指向的带子上的字符 $\mathrm{Z}$ 擦除 , 并改为 $\mathrm{Y}$ , 然后 沿着 $\mathrm{D}$ 方向 , 移动一格单位 ;

其中 $\mathrm{D}$ 方向可以是 $\mathrm{L}$ 向左移动 , 也可以是 $\mathrm{R}$ 向右移动 ;

数据结构的形式定义： 数据结构是一个二元组Data_Structures=(D, S)，其中，D是数据元素的有限集，S是D上关系的有限集。
说明： 数据结构的定义只说明了数据结构的一个方面，强调的是数据元素之间的逻辑关系。由于数据结构是计算机操作的对象，因此它还有另外一个很重要的方面，就是数据的存储结构，即怎么在计算机中表示出数据的逻辑结构。

数据的逻辑结构： 即数据元素之间的关系，分为4类：

1.线性结构

实质上是一个序列。

2.树形结构

像一个树，一个根可以开展出多个分支。

3.图状结构

4.集合结构

这里集合的概念与数学中集合的概念是相同的。集合结构中数据元素之间不存在任何关系，但是从某种意义上来说，也是一种关系。

数据的存储结构： 逻辑结构在存储器中的映像，或者说，逻辑结构在计算机中的表示。
要想实现逻辑结构在计算机中的表示，应该从数据结构的定义考虑，分别考虑 数据元素的映像方法 和关系的映像方法 。
【数据元素的映像方法】
用二进制位(bit)的位串来表示数据元素。
比如： （321）₁₀可以用（101000001）₂来表示，A可以用（001000001）₂来表示。当然，在这里用的是ASCII码。
【关系的映像方法】
所有的关系都可以用一个有序对<x, y>来表示，所以，可以把这个有序对<x, y>看作是关系的基本单位。关系的映像方法就是表示有序对<x, y>的方法。
有序对<x, y>在计算机中有2种表示方法：
1.顺序映像
以存储位置的相邻来表示后继关系，简单来说，对于有序对<x, y>，y的存储位置和x的存储位置差一个常量C（C为正，且C是一个隐含值）。
对于顺序映像，整个数据结构只含数据元素本身的信息，没有其他附加的信息。
比如：
对于线性结构（a₁, a₂, a₃），其存储结构如下：

2.链式映像（非顺序映像）
在整个结构中，有序对<x, y>中x和y的存储位置之间没有固定的关系，即它们的存储位置是随意的，这时x和y的后继关系就需要用一个附加信息（指针）来表示。
这个附加信息需要与x绑定在一起，换句话说，这个数据元素x的存储映像是一个节点，这个节点包含两部分信息：一部分信息是数据元素x的映像，另一部分信息是指向后继元素的指针。

本人就职于国际知名终端厂商，负责modem芯片研发。
在5G早期负责终端数据业务层、核心网相关的开发工作，目前牵头6G算力网络技术标准研究。

关系数据库

关系数据库简介

• 美国🗽IBM公司的E.F.Codd
  1970年提出关系数据模型E.F.Codd, “A Relational Model of Data for Large Shared Data Banks”《Communication of the ACM》
  1970之后，提出了关系代数和关系演算的概念
  1972年提出了关系的第一、第二、第三范式的规范化理论
  1974年提出了关系的BC范式
  奠定了关系数据库的理论基础
• 关系数据库系统是支持关系模型的数据库系统
• 关系模型由数据结构、关系操作集合和完整性约束三部分组成
• 单一的数据结构------关系🔗
  但关系模型的这种简单的数据结构能够表达丰富的语义，描述出现实世界的实体以及实体间的各种联系
• 关系操作
  • 关系模型中常用的关系操作包括两类：
    ⭐查询操作：选择、投影、连接、除、并、交、差
    ⭐增加、删除、修改操作
  • 特点：操作的对象和结果均是集合；一次一集合
  • 关系数据语言：
    🔸三类：关系代数语言、关系演算语言和具有关系代数和关系演算双重特点的语言

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

关系

• 在关系模式中，数据是以二维表的形式存在的，这个二维表就叫做关系

• 关系理论是以集合代数理论为基础的，因此我们可以用集合代数给出二维表的“关系”定义

• 为了从集合论的角度给出关系的定义，我们先引入域和笛卡尔积的概念 ：
  ⭐域（Domain）

  • 域是一组具有相同数据类型的值的集合，又称为值域（用D表示）
    例如，整数、实数、字符串的集合
  • 域中所包含的值的个数称为域的基数（用m表示）
  • 关系中用域表示属性的取值范围
    例如：
    D1={李力，王平，刘伟} m1=3
    D2={男，女} m2=2
  • 域中的值无排列次序，如D2={男，女}={女，男}

  ⭐笛卡尔积（Cartesian Product）

  • 给定一组域D1，D2，…，Dn(它们可以包含相同的元素，即可以完全不同，也可以部分或全部相同)。D1，D2，…，Dn的笛卡尔积为D1×D2×…×Dn={（d1，d2，…，dn）| di∈Di，i=1，2，…，n}
  • 有定义可以看出，笛卡尔积也是一个集合
    其中：
    ①元素中的每一个di叫做一个分量（Component），来自相应的域（di∈Di）；
    ②每一个元素（d1，d2，…，dn）叫做一个n元组（n-tuple），简称元组（Tuple）。但元组不是di的集合，元组的每个分量（di）是按序排列的，如：（1，2，3）≠（2，3，1）≠（1，3，2）；而集合中的元素是没有排序次序的，如：1，2，3）＝（2，3，1）＝（1，3，2）
    ③若Di（i=1，2，…，n）为有限集，Di中的集合元素个数称为Di的基数，用m_i（i=1，2，…，n）表示，则笛卡尔积D1×D2×…×Dn的基数M（即元素（d1，d2，…，dn）的个数）为所有域的基数的累乘之积，即M＝$$\prod _{i=1}^n{m}_i$$ 例如：
    上述表示教师关系中姓名、性别两个域的笛卡尔积为
    D1×D2={李力，男），（李力，女），（王平，男），（王平，女），（刘伟，男），（刘伟，女）}
    其中：
    🔹 李力、王平、刘伟、男、女都是分量
    🔹（李力，男），（李力，女）等是元组
    🔹其基数M=m1×m2=3*2=6
    🔹元组的个数为6
    ④笛卡尔积可用二维表的形式表示
    例如，上述的6个元组可表示成下表👇

    姓名	性别
    李力	男
    李力	女
    王平	男
    王平	女
    刘伟	男
    刘伟	女

    由上例可以看出，笛卡尔积实际是一个二维表，表的框架由域构成，表的任意一行就是一个元组，表中的每一列来自同一域，如第一个分量来自D1，第二个分量来自D2。

  ⭐关系（Relation）

  • 笛卡尔积D1×D2×…×Dn的任一子集称为定义在域D1，D2，…，Dn上的n员关系，可用R（D1×D2×…×Dn）表示。
    如上例D1×D2笛卡尔积的子集可以构成教师关系T1，如下表：
    
  • 几点说明
    • R为关系名，n称为关系的目或度（Degree）
      当n=1时，称为单元关系
      当n=2时，称为二元关系
      … …
      当n=n时，称为n元关系
    • 关系是笛卡尔积的有限子集，即是一个二维表，行对应一个元组、列对应一个域、每列的名称称为属性
    • n目关系必有n个属性

  ⭐属性、码的概念

  • 候选键与关键字
    • 能唯一标识关系中元组的属性或属性集，则称该属性或属性集为候选键（Candidate Key），也称候选关键字或候选码。如：
      ■ “学生关系”中的学号能唯一的标识每一个学生，则属性学号是学生关系的候选键
      ■ 在“选课关系”中，只有属性的组合“学号+课程号”才能唯一地区分每一条选课记录，则属性集“学号+课程号”是选课关系的候选键
    • 如果一个关系中有多个候选键，可以从中选择一个作为查询、插入和删除元组的操作变量，被选用的候选键称为主关系键（Primary Key），或简称为主键、主码、关系键、关系字。
      例如：在学生关系中假设存在身份证号属性，则“学号”和“身份证号”都可以作为学生关系的候选键，如果选定“学号”作为数据操作的依据，则“学号”为主关系键
    • 主关系键是关系模型中的一个重要概念。每一个关系必须选择一个主关系键，选定以后，不能随意改变。每个关系必定有且仅有一个主关系键，因为关系的元组无重复，至少关系的所有属性的组合可作为主关系键，通常用较小的属性组合作为主关系键
  • 主属性与非码属性
    • 主属性（Prime Attribute）：包含在任何一个候选码中的各属性称为主属性
    • 非码属性（Non-Prime Attribute）：不包含在任何候选码中的属性称为非码属性，或非主属性（Non-key Attribute）
    • 在最简单的情况下，一个候选码只包含一个属性，如学生关系中的“学号”，教师关系中的“教师号”
    • 在最极端的情况下，所有属性的组合是关系的候选码，这时称为全码（All-Key）
      例如：假设有教师课程参考书关系TCB，分别有三个属性 教师号（T）、课程号（C）和参考书（B）。一个教师可以讲授多门课程；一门课程可以为多个教师讲授，它们使用相同的一套参考书；同样每种参考书可以供多门课程使用。在这种情况下，T、C、B三者之间是多对多关系，（T,C,B）三个属性的组合是关系TCB的候选码，称为全码，T，C，B都是主属性
    • 关系的类型
      • 基本关系（通常又称为基本表或基表）：实际存在的表，实际存储数据的逻辑表示
      • 查询表：查询结果对应的表
      • 视图表：由基本表或其它视图表导出的表，是虚表，不对应实际存储的数据

  ⭐关系的基本性质

  • 尽管关系与二维表格、传统的数据文件是非常类似的，但它们之间又有重要的区别
  • 严格地说，关系是种规范化了的二维表中行的集合，为了使相应的数据操作简化，在关系模型中，对关系做了种种限制，关系具有如下特性：
    • 关系中不允许出现相同的元组。因为数据上集合中没有相同的元素，而关系是元组的集合，所以作为集合元素的元组应该是唯一的
    • 关系中元组的顺序（即行序）是无关紧要的，在一个关系中可以任意交换两行的次序。因为集合中的元素是无序的，所以作为集合元素的元组也是无序的。根据关系的这个性质，可以改变元组的顺序使其具有某种排序，然后按照顺序查询数据，可以提高查询速度。
    • 关系中属性的顺序是无关紧要的，即列的顺序可以任意交换。交换时，应连同属性名一起交换，否者将得到不同的关系
    • 同一属性名下的各个属性值必须来自同一个域，是同一类型的数据。即列是同质的
    • 关系中各个属性必须有不同的名字，不同的属性可来自同一个域，即它们的分量可以取自同一个域
      例如：有下表中的关系，职业与兼职是两个不同的属性，但它们取自同一个域，职业={教师，公务员，企业主}👇
      
    • 关系中的每一个分量必须是不可分的数据项，或者说所有属性值都是原子的，即是一个确定的值，而不是值的集合。属性值可以是空值，表示“未知”或“不可使用”，即不可“表中有表”。满足此条件的关系称为“规范化关系”，否则称为“非规范化关系”。
      例如：下表中，籍贯含有省、市/县两项，出现了“表中有表”的现象，则为非规范化关系，而把籍贯分成省、市/县两列，将其规范化👇
      

关系模式

• 关系数据库中，关系模式是型，关系是值
• 关系模式是对关系结构的描述，是关系的框架，或称为表框架。它应该：
  • 指出关系由哪些属性构成，这些属性来自哪些域，以及属性与域之间的映像关系
  • 刻画关系必须满足的完整性约束条件
• 定义：关系的描述称为关系模式（Relation Schema）。一个关系模式应当是一个五元组。它可以形式化地表示为：R（U，D，DOM，F）
  其中R为关系名，U为组成该关系的属性名集合，D为属性组U中属性所来自的域，DOM为属性向域的映像集合，F为属性间数据的依赖关系集合
• 关系模式通常可以简记为：R（A1，A2，…，An）
  其中R为关系名，A1，A2，…，An为属性名。而域名及属性向域的映像常常直接说明为属性的类型和长度
• 关系模式是静态的、稳定的；关系是关系模式在某一时刻的状态或内容，动态的、随时间不断变化的

关系数据库模式

• 一组关系模式的集合叫做关系数据库模式
• 关系数据库模式是对关系数据库结构的描述，或者说是对关系数据库框架的描述，与关系数据库模式对应的数据库中的当前值就是关系数据库的内容，称为关系数据库的实例，可以看作是关系的值。
  例如，在教学数据库中，共有五个大系，其关系模式分别为：
  🔹学生（学号，姓名，性别，年龄，系号）
  🔹教师（教师号，姓名，性别，年龄，系号）
  🔹课程（课程号，课程名，课时）
  🔹选课（学号，课程号，成绩）
  🔹授课（教师号，课程号）
  🔹系（系号，系名，地址）
  在每个关系中，又有其相应的数据库的实例，如下图是学生关系模式对应的数据库实例👇
  

关系数据库

• 关系数据库是“一组随时间变化，具有各种度的规范化关系的集合”
• 在关系模型中，实体以及实体间的联系都是用关系来表示。在一个给定的现实世界领域中，相应于所有实体及实体之间的联系的关系的集合构成一个关系数据库
• 由此可见，关系数据库也有型和值的概念，其型就是关系数据库模式，相对固定；其值就是关系数据库内容，代表现实世界中的实体，而实体是随着时间不断变化的，所以其值在不同的时刻会有所变化

关系数据库——关系操作&&关系模型的完整性
关系数据库——关系代数