数据库技术中的语法推断、图数据库与流图挖掘

### 数据库技术中的语法推断、图数据库与流图挖掘 #### 语法推断 语法推断在多个领域有着重要的应用。在某些情况下，对于集合 \(T_0 = \{(a, 200), (aa, 100), (aaa, 50)\}\)，出现特定情况的概率小于千分之一。这是因为从模型中随机抽取 350 个字符串的样本，应该至少包含一些较长的字符串，如 `aaaa` 或 `aaaaa`。除了严格的出现概率，还可以基于其他因素进行评估，比如贝叶斯与先验概率分布的比较，以及基于信息理论的差异比较。 语法推断的传统应用领域是句法模式识别，它假设模式类可以用语法模型表示，并自动学习这些模型。其他应用领域包括语音和自然语言处理、光学字符识别、信息检索、基因分析、序列预测和密码学等。 在数据库方面，XML 数据库中用于查询优化的选择性估计的最新工作可归类为随机语法推断。语法推断也适用于数据挖掘和知识发现。随机语法推断是许多压缩技术的关键部分，更好的模型直接对应更高的压缩比。 对于结构化文档集合，语法是作为数据库模式的自然表示，半结构化和 XML 数据库也是如此。如果数据没有显式创建的模式，语法推断就适用于此类数据。例如，Fankhauser 和 Xu 描述了一个学习语法用于自动标记的系统；Shafer 介绍了 GB（语法构建器）引擎，它通过概括以 SGML 样式标记的示例来生成语法；Ahonen 等人使用基于可表征的正则语言子类（他们称之为 (k - h) 上下文语言）的更经典语法推断方法；Goldman 和 Widom 描述了使用自动构建的 DataGuides 来浏览数据库结构和制定查询；Young - Lai 和 Tompa 则研究将随机语法推断应用于相关问题。 #### 图数据库 图数据库是一种数据模型符合某种图（或网络、链接）结构的数据库。其数据模型通常由节点（或顶点）和（有向）边（或弧、链接）组成，节点代表概念（或对象），边代表这些概念（对象）之间的关系（或连接）。节点通常用概念或对象的名称标记，边用关系类型标记，更复杂的标记可能涉及将属性 - 值对集合与节点和/或边关联起来。此外，还可能允许更复杂的结构，如嵌套图或超图，也可能限制为特定类型的图结构，如无环图或有根节点的图。 用户通常可以使用高级查询语言查询图数据库，图查询语言旨在方便查询与图相关的属性，例如通过图（网络）中未指定长度的路径（路线）连接的节点。 图数据库的概念源于人们认识到在许多应用中，单个概念实例之间的单一关系类型本身可能形成图结构，如超文本或网页文档中的链接结构、地理数据库中的道路连接、生物数据库中的路径，以及最近的社交网络和链接开放数据中的连接。在这些应用中，用户常需要查询数据库中的路径，而所需路径的长度不一定预先确定或已知。 图数据库通常由一组图组成，每个图由节点集 \(N\) 和边集 \(E\) 构成，边可以是有向或无向的，节点和边都可能有标签。例如，一个简单的有向图中，节点标签表示人名，边标签表示人与人之间的关系，可代表简单社交网络的一小部分。 基于这样的图数据，用户可以进行多种查询，包括常规查询（如查找相互认识的人对）、“模式级”查询（如查找 Alice 参与的关系），还可以使用正则表达式指定感兴趣的路径上的边标签序列模式。例如，正则表达式 `(know|friend - of)+` 指定了一个或多个标记为 “knows” 或 “friend of” 的边的序列。正则表达式在半结构化数据查询路径信息方面已被广泛研究，并被添加到用于资源描述框架（RDF）的 SPARQL 查询语言中。 根据应用领域的不同，图数据库还有许多其他有用的查询形式，如最短路径查询、子图同构查询、近似图匹配或查找完全子图等。在社交网络中，查询通常涉及节点的“连接程度”或其在网络中的“影响力”。 与传统数据库不同，图数据库的数据可能没有显式的模式描述，这是半结构化数据的一个特征。不过，研究人员已经为图数据库定义了各种形式的模式语言，模式指定的约束可以为节点分配类型、规定允许的边标签，并限制参与每个关系的节点类型。 图数据库系统的一个主要问题是查询的高效评估。考虑到社交网络对应的图数据库的规模和查询的复杂性，这是一个持续研究的领域。图数据库也可以分布式存储，这带来了更多挑战。为了支持高效查询评估，已经开发了适用于图数据的索引结构，特定的索引结构仅支持特定类别的查询。图查询的优化也得到了研究，可以在物理层面选择合适的查询计划，或在逻辑层面发现冗余查询组件。 一些应用需要比简单节点和边更复杂的图结构，例如使用超图来建模超文本，引入超节点模型，其中节点本身可以包含图，或者在 HyC 系统的超图中定义“blobs”。近年来，已经开发了许多图数据库产品，如 Neo4J、Sparksee 和 Apache Giraph 等。 图数据库的应用领域非常广泛，包括社交网络、超文本和网络、国家安全（或刑事调查）应用中的语义关联发现、化学结构建模、地理信息系统、书目引用分析、分类和部分 - 整体关系表示、数据来源图以及语义网等。在生物学中，也有众多应用，如代谢途径、信号传导途径、基因调控网络、基因聚类和蛋白质相互作用网络。 #### 图流挖掘 图流挖掘关注在数据流模型的通常约束下（即顺序访问数据流和有限内存），估计图 \(G\) 的属性或在 \(G\) 中查找模式。给定数据流 \(A = \langle a_1, a_2, \cdots, a_m \rangle\)，其中每个数据项 \(a_k \in [n] \times [n]\)，自然地定义了一个无向、无权图 \(G = (V, E)\)，其中 \(V = \{v_1, \cdots, v_n\}\)，\(E = \{\langle v_i, v_j \rangle : a_k = (i, j) \text{ for some } k \in [m]\}\)。 该领域存在多种常见变体： - **多遍模型**：在图挖掘中，常考虑可以对数据流进行多遍处理的算法。在 W - Stream 模型中，算法允许在每一遍处理时向数据流写入注释，这些注释可在后续遍中使用，该模型有足够的能力模拟 PRAM 算法。Stream - Sort 模