什么是持久化表达有向图的最标准文件格式和符号？

Question

我可以帮您翻译成中文。这段内容是关于持久化个人定向图的。这个问题并不要求完整的图数据库解决方案，而是需要一种文档格式，可以用来保存任意个人定向图。我不知道选择哪种符号和文件格式会是最明智的选择。 我的主要关注点是：

1. 表达能力/灵活性 - 我需要能够表达不同类型的图形。虽然标准用例是简单的有向图，但应该可以表达树、循环图和多重图。至少，我希望支持边缘和节点的标注和加权。描述层次图和边缘组合/超边的符号也非常理想，尽管我知道这样的解决方案可能不存在。

2. 类型系统独立性 - 我对表示图的结构特性很感兴趣。一些解决方案包括可扩展的类型系统，用于类型化边缘和节点（例如RDF/OWL）。如果有明确定义的将类型元素分解为基元（节点/边缘/属性）的规范，则我只对这种表示方式感兴趣。在这里，我试图避免多个等效图的多个表示，其中等价性无法区分。

3. 规范表示 - 应该有一种机制，允许以规范方式表示图形（以便使用规范表示的词汇等效性来确定等价性）。

4. 呈现无关性 - 我希望使用的符号不依赖于图形的呈现方式。这将包括空间方向、颜色、字体等。我只对表示数据感兴趣。DOT语言、DGML或SVG（至少对于这个特定目的）的一个我不喜欢的特点是它们关注视觉表现。

5. 标准化/开放/兼容 - 我要做的实现工作越少，就越好。如果格式已经被标准化并且可靠的工具已经存在于该格式中，则更可取。伴随着这个要求的是另一个要求，即该格式应高度兼容。Microsoft的DGML的专有性质是我厌恶的原因，尽管Visual Studio工具和我主要使用.NET（现在）。W3C发布RDF标准的事实是考虑将RDF的有限子集作为表示工具的动机。我也很欣赏GXL和GraphML，因为它们有很好的文档化xml模式，从而促进了将它们的数据与任何xml兼容的软件包集成的能力。

6. 简单/可读性 - 我欣赏人类可读的语法和易于解释的表示。我也欣赏简化解析的表示。因此，我喜欢GML，但我担心它不够主流，不能成为现实选择。如果JSON或YAML在表示复杂（非DAG）结构的能力上不那么有限，我也会考虑它们的可读性。

7. 效率/简洁表示 - 值得考虑的是，我最终选择的任何格式都必须被持久化并通过某个网络传输。因此，文件大小是一个相关的考虑因素。

概述

我认识到可能无法找到符合我愿望清单上所有标准的解决方案。我只是要求最接近我想要的文件格式，并且不限制不支持的用例的可扩展性。

- smartcaveman

Answer 1

关于 Trivial Graph Format，它是什么？

- Julian Borrero

Answer 2

ObWindyPreamble: 在RDF世界中，有无数不同的表面语法格式可供选择。 RDF本身是数据的抽象元模型，而不是直接的“图形语法”。 当然，您可以直接在RDF中表示图形（因为RDF模型就是图形），但是考虑到您想表示不同类型的图形，您可能需要进行抽象，并实际创建用于表示不同类型图形的RDF词汇表。

总的来说，我不确定RDF是否是您最好的选择，但如果您选择了其中一种，我会说RDF的Turtle语法值得一看。 它确实符合可读性和简单性的要求，同时还是一种标准（嗯，几乎... W3C正在努力将其标准化）并且具有广泛的（开源）工具支持。

RDF模型大致遵循集合语义，这意味着实际上不能强制执行规范的语法表示：两个文件可以按不同顺序包含信息而不影响实际模型，甚至可以包含重复信息。但是，如果在生成文件时强制执行简单的排序算法（大多数RDF解析器/编写器都支持此功能），则应该能够通过基于表面语法的行比较和确定图形等价性来解决问题。

举个简单的例子，假设我们有一个非常简单的定向标记图。

 A ---r1---> B ---r2---> C

您可以直接用RDF表示它，如下所示（使用Turtle语法）：

 @prefix : <http://example.org/> .

 :A :r1 :B .
 :B :r2 :C .

在更抽象的建模中，你可以这样做：

 @prefix g: <http://example.org/graph-model/> .
 @prefix : <http://example.org/> .

 :A a g:Vertex .
 :B a g:Vertex .
 :C a g:Vertex .

 :r1 a g:DirectedEdge ;
     g:from :A ;
     g:to :B .
 :r2 a g:DirectedEdge ;
     g:from :B ;
     g:to :C .

上面的例子当然是过于简单了，但是希望它能说明这个潜在地满足你心愿清单上的很多要求。

顺便说一下，如果你想要更简单的话，N-Triples 也是一种 RDF 语法，它是基于行的，因此可以轻松以流式方式处理。它比 Turtle 稍微冗长一些，但可能会使文件比较更容易。

- Jeen Broekstra

---

我很感激您的见解，这是我一直在考虑的选项之一。我同意Turtle语法是最符合我的要求的RDF风格，然而，从您的回答中并不清楚为什么RDF是最佳选择，甚至您是否认为它是最佳选择。 - smartcaveman

那是因为我不知道它是否合适 :) 我认为它可能适合，但我不知道其他选择。RDF是一种更抽象的数据建模方法，它给你很大的灵活性，但如果你只是想要一个快速且简单的文件格式，那么它可能过于复杂了。 - Jeen Broekstra

我的问题是RDF可以用无限的语法变化来表示单个语义概念。这种属性似乎是一个配方，可以导致：（1）意外的冗余；（2）任意的复杂性；以及（3）在任何具有重要规模本体论的情况下性能非常糟糕。 - smartcaveman

Answer 3

我的想法：

• 我所缺少的是您特定的实际目的/领域。

• 您在特定格式旁提到了通用JSON格式（例如，GraphML是XML的应用程序）。因此，我不确定您是否考虑制作自己的格式。

• 拥有一个“可用于确定等价性的规范表示”是否可以解决图同构问题？

• GraphML似乎涵盖了您的许多理论要求，因此建议您创建其JSON版本。这也将涵盖要求6。

• 然后，您可以创建JSON格式与GraphML（以及可能其他格式）之间的转换器。

• 对于要求7，一切又取决于实际图形大小。我的意思是，如今向该死的移动设备发送几MB并不被认为很多。任何格式中几MB的图形已经是一个相对较大的怪物，具有数万个节点和边缘。

- meaning-matters