1

关系数据库经常用于存储各种风格的图（树、有向图、无向图……）。

那么为什么没有一个主要的 DBMS（Microsoft、MySql、Oracle、PostgreSQL、SqlLite，仅举几个字母顺序）包含将关系视为图形的库支持？

一些理想的功能，例如：

  • 约束检查（连通性、非循环性、平面性……）
  • 常用功能（最短路径、最小生成树、传递闭包、最大流/最小割、团检测、哈密顿/欧拉循环......）
  • 提高上述任何一项的性能所需的辅助数据结构

在数据库之外建立对其中一些事物的支持很复杂，因为（除其他原因外）：

  • 它本质上很复杂（图书馆在这里提供帮助）
  • 大量数据通常支持简短的答案：运行最短路径算法的外部客户端需要与数据库非常“健谈”，或者需要检索比需要的数据量大得多的数据；任何一种选择都对网络不利
  • 当完整性依赖于图论约束时保持完整性需要访问所有建议的更新，因此需要一个触发器，并且在许多系统中从触发器访问现有图形库很复杂
  • DBMS 存储管理器和优化器具有独特的定位，可以解决辅助数据结构的问题，就像它们处理索引一样

这不是一个修辞问题，我实际上想知道是否有有趣的技术（或历史）原因。

4

3 回答 3

2

我曾在一个研究小组工作，对开发 RDF(S) 数据数据库感兴趣，这些数据基本上是标记图或三元组 [主题、谓词、对象]，它们基本上是图边：[sourceNode, edgeLabel,目标节点]。

要问的问题，以了解问题的难度：您将为标记图构建什么样的索引？您必须利用常见的“属性”（每个“谓词”是主体的属性，具有对象的值），并相应地索引边缘，因此您可以快速找到“是否存在名为'hasAge'的边缘价值大于 18" 的人。

为了说明，这里有一个简单的方法，它是模式无视的（并且与传统数据库研究的相反方向完全一致，一致同意模式是好的）。它完全忽略了任何模式信息（本文提供了有用的上下文）。只需将所有内容存储在三个大表中（s：主题，p：谓词，o：对象）：

  1. [s, p, o]
  2. [p, o, s]
  3. [o, s, p]

这三个足以回答任何有效地评估任何带有（至多）主语、（至多）谓词和（至多）宾语的查询（即形式为(s, *, *), (*, p, *), (*, *, o), (s, p, *), (s, *, o), (*, p, o),的查询(s, p, o)）。复杂的查询虽然包含许多“路径表达式”（即您描述的数据，您可以找到满足某些条件的某些路径），每一个都被转换为这些（大！）表之一上的自联接，这不是所有这些都高效，这是一个问题。

在那里，这是一个放在口袋里的简单图形数据库。:)

总之，这是一个活跃的研究领域。我不了解当前的最新技术，但我见过像AllegroGraph和其他声称效果非常好的产品。

于 2010-01-14T01:48:50.727 回答
0

Oracle 支持图形功能（Oracle Locator/Oracle Spatial）和语义 Web 功能。

于 2009-10-24T05:47:37.487 回答
0

我怀疑您的问题包含其自己答案的开头。

对于通用数据库，您列出的常用功能根本不需要。是的，图形操作当然需要它们，但很少用于客户计费。当然，关系数据库可以将图形存储在表中，但图形操作超出了我所见过的任何 SQL 版本的能力。

您在数据库之外编写对其中一些东西的构建支持很复杂。确实如此，这就是为什么我们都得到如此多的报酬。但是在数据库中建立对这些东西的支持会同样复杂，不是吗？

于 2010-01-14T02:07:32.260 回答