Lecture | Database Review

Data

什么是数据

数据的集合是数据库的主要研究对象之一。数据集通常具有大规模、有结构等特征。因此为了方便研究，下面先探究数据的定义和表示方式。

首先数据是一种数学对象，而数据的集合自然在数学概念上拥有集合之间的各种运算。例如集合之间的关系包括交并补差。集合可以赋予一定的代数结构，使得数据之间可以进行运算。在集合的角度下还可以为数据赋予拓扑概念，由此可以考察数据间是否存在邻近关系。除此之外，若对集合赋予距离，我们还可以度量数据之间的距离和相似度。若数据之间可以定义序关系，则可以在数据集上实现各种各样的算法，例如排序。

Relation 关系

当把数据视作是关系时，可以从结构和运算角度进行分析。

• 偏序关系：当数据中可以定义序结构时，数据之间的关系存在偏序关系，因此可以在上面定义一系列的算法。最典型的例子是我们可以根据一定的偏序关系对数据进行排序
• 拓扑关系：如果需要考察数据之间的相邻结构，则可以从拓扑关系上考察数据的结构
• 运算关系：可以在数据之间定义运算，考察数据之间的代数结构
  • 关系直接是可以进行运算的。由于关系是集合，因此必然可以进行集合间的运算。常见的关系运算包括笛卡尔积、投影运算、选择运算、交并补差和判断元素是否属于集合等运算。而通过关系间的运算，我们又可以产生出新的集合。
• 度量关系：如果可以在数据上定义某种度量，进而定义出范数和距离，可以考察数据上的测度结构

当数据具有一定的结构时，非常适合用关系模型描述数据。

Geometry 几何

这是一个比较有趣的角度。将数据视作高维空间中的点，而事实上，在AI领域，几乎所有工作都是将实体数据编码成高维空间的中的向量。对于一般的数据而言，我们同样可以将其视作空间中的一点，数据之间的关系转化为空间中点之间的关系，比较特殊的关系包含点的共线、共面问题。而具有一定关系的点的集合可能可以在空间中具有某种特殊的几何结构，或与某个几何结构有着同构的关系。更一般而言，所有的数据分布在高维空间中的流形上，我们使用的数据是在流形上的采样。而实际上在某些任务中真正有用的数据并不需要非常高维的流形采样，数据带有一定的冗余，在这些任务中只需要一些低维的投影就能表示这些数据并且符合任务需要。如此一来就必然存在一个映射，使得高维流形上的数据能与低维空间中的某些点一一对应。由于映射是一一的，因而同样存在反函数使得这些低维空间中的点能映射回高维空间。而事实上，我们只知道这些函数是一定存在的，但并不能获得显式的表达式，因此称为隐函数。

流形假设：现实中很多高维数据集实际上是沿着高维空间内的低维潜流形分布，即潜特征嵌入空间。流形假设的结果是看起来需要很多变量描述的数据集，实际上只需要较少变量就能完成描述。在高维流形的局部，可以用低维的欧几里得空间进行近似，而欧几里得空间可以很容易找到对应的基底来描述该流形的局部。

在数据不具有一定的结构时，比较适合用流形结构描述数据，如从现实数据中采样的文本、图像和视频数据，都可以假设其分布在一定的流形结构上，进而得知存在一个隐函数可以将这些数据映射到低维空间中。映射完成后可以在低维空间中分析数据的结构并进行数据查询，这也是目前大部分深度学习模型需要学习的模式。

Internet 网络

互联网的特点包括开放、大数据、去中心化等，当数据在网络上进行共享时，其传输过程可以用图来表示。问题在于互联网的开放性和数据的存储仿佛是相悖的。互联网上的数据允许任何人进行修改，而数据的存储需要保持一致性。因此为了让互联网实现数据的存储并保持数据的一致性，互联网上的数据必须遵守数据共识（Agreement），即数据的值是互联网群体所认同的值，互联网的各个使用者对该值具有共识，而某一方强制修改该值时，此时被修改的数据只能获得小部分的认同，因此修改后的值不被互联网所认可，从而保持了数据存储的一致性。

由于互联网的规模很大，因此要求系统具有很强的可扩展性。可扩展性分为存储扩展性和计算扩展性，从而衍生出来了P2P模型和Map-Reduce操作

Artificial Intelligence 人工智能

数据与人工智能有很强的联系。

Reasoning：推理实际上是数据集合上的运算。其中推理中涉及到的项和函数与集合中的元素对应，而推理中的谓词与集合或者关系对应，逻辑演算即集合的运算。在此基础上，一阶逻辑演算可以简化为关系代数运算。

Learning：通过学习得到的模型能在一定程度上反映对象的结构（一般而言是非结构化对象），且数据是高维空间中的点，而学习方式可以实现数据维度之间的隐函数依赖关系。因而学习通过几何模型，可以抓取非结构对象内部的函数依赖关系。

Data Model

结构化数据和非结构化数据是可收集数据的两大类别，结构化数据是整齐地放入数据表的数据，包括数字、短文本和日期等离散数据类型。由于其大小或性质，非结构化数据无法整齐地放入数据表：例如，音频和视频文件以及大型文本文档。更多资料。

数据模型要求具有可表达的、有效的等特点。因此部分数据模型需要一定的元数据来描述数据结构。数据结构即一定的schema模式。

结构化数据

数据模型是用来描述结构化数据的概念和工具，一般维护了数据的结构、运算和限制。常用的数据模型有关系型数据模型和图数据模型等。

• 关系型数据模型：关系型数据模型中所有的数据都被表示成表格，表格抬头反映的是该组数据遵循的模式。表格的标题定义的是该组数据的一组属性，每个属性有属性名和数据类型。而表格的主体部分则用于存储实际的数据，一条数据对应表格主体中的一行，一条数据中的每个值都唯一对应标题中的属性。该数据模型上的运算本质上还是集合间的运算。
  • 在该数据模型上的查询：用户对该数据模型的一个查询对应于求集合间运算结果的一个子集。不同的数据表格通过笛卡尔积连接在一起，然后通过某些运算后，最后再进行选择操作，得到查询结果。

非结构化数据

非结构化的数据可以看作是数据空间中的一个点。

数据空间：数据空间可以表示成定义了一定结构的数据集合（域）。

非结构化的数据采样自数据空间。设数据空间 $D = \lbrace (xi, y_i) \rbrace{i=0}^nS \sub DSDSDSf_w^Sx_i\hat{y_i}y_i(x_i, y_i) \in SSf_w^Sf_w^SSS(x_i, y_i) \in D \ S$ 同样有着很好的拟合能力。

互联网数据

互联网数据通常是开放的和大规模的。由于其开放性，任何类型的数据都可以存储在网上，因此需要的schema-free的数据模型。而由于其大规模，因此数据的查询需要支持大规模并发和张量计算，同时查询的数据需要去冗余，即需要去中心化。

人工智能

在AI中，推理与数据模型中的逻辑数据相对应，逻辑数据可以通过一阶逻辑谓词进行演算，即数据之间的关系代数演算。而AI中归纳学习可以对应于非结构化的数据，AI学习的模型是对数据集合的一种编码，模型可以描述数据集合的某些性质。

Data System

数据的扩展性讨论

计算机体系结构

数据对应的计算模型与当前的计算机体系结构有关，经典的体系结构为Von Neumann模型。这类型的计算机在进行运算时，CPU会从多级的存储结构中读取/写入数据，而其中的瓶颈就在于读写磁盘的速度。目前较为前沿的技术聚焦于存算一体化、超算模型等。当前缓解瓶颈的读写速度体现在分布式并行、云计算、P2P计算等技术。所有的数据在分布式系统中的进行传输构成数据流，而对于张量形式的数据，即为张量流。

存储扩展性

问题建模：我们希望数据的存储能最小化IO次数。假设 是schema 的实例， 是磁盘块 $BiDisk = \lbrace B_i \rbrace{i=0}^nm: r(R) \rightarrow Diskr(R)Qr(R)Q \sub r(R)$。我们的目标是求解

$$\argmin_m \| m(Q) \|$$

也就是需要设计一种索引方式，使得每一个查询来时能快速访问到对应的数据。目前常用Hash形式或树形式进行数据的索引结构。

对于单结点单磁盘块的存储、对于单结点多磁盘块的存储、对于多结点的存储。

计算扩展性

由于目前的数据量愈发庞大，因此要求一些计算模型能够支持大规模同步并发（BSP）。在张量层可以经过TPU进行并行计算，而在计算图层分析和解决图之间的依赖问题。为了实现BSP，现代的计算模型实现了Map-Reduce操作，通过编写Map-Reduce并将这些操作分配给对应的线程，可以实现同步并发。

• 哪些集合运算可以并发执行
• 如何在同步并发时保持数据的一致性
  • 调度和序列化，加锁协议
  • Transaction

数据的高效性讨论

吞吐量

吞吐量指的是单位时间内处理的transaction数量，由系统的并行能力和调度器共同决定

处理单位查询所需时间

由系统的IO索引机制优化决定

Application