20

我开始深入研究图形数据库，但我不知道这些图形是如何在内部存储的。假设我有这张图（取自维基百科）：

如何将此图序列化为键值对象？（例如 Python 字典）

我想象两个字典，一个用于顶点，一个用于边缘：

{'vertices':
 {'1': {'Name': 'Alice', 'Age': 18},
  '2': {'Name': 'Bob', 'Age': 22},
  '3': {'Type': 'Group', 'Name': 'Chess'}},
 'edges':
 {'100': {'Label': 'knows', 'Since': '2001/10/03'},
  '101': {'Label': 'knows', 'Since': '2001/10/04'},
  '102': {'Label': 'is_member', 'Since': '2005/7/01'},
  '103': {'Label': 'Members'},
  '104': {'Label': 'Members'},
  '105': {'Label': 'is_member', 'Since': '2011/02/14'}},
 'connections': [['1', '2', '100'], ['2', '1', '101'],
                 ['1', '3', '102'], ['3', '1', '103'],
                 ['3', '2', '104'], ['2', '3', '105']]}

但我不确定，这是否是最实际的实现。也许“连接”应该在“顶点”字典中。那么，使用键值对象实现图形数据存储的最佳方式是什么？我可以在哪里阅读更多关于它的信息？

可能相关，但不重复：如何在某些数据结构中表示一个奇怪的图

4

6 回答 6

12

正常模式是没有单独的connections结构，而是将信息放入edges结构中。这给出了类似的东西：

{
'vertices': {
    '1': {'Name': 'Alice', 'Age': 18},
    '2': {'Name': 'Bob', 'Age': 22},
    '3': {'Type': 'Group', 'Name': 'Chess'} },
'edges': [
    {'from': '1', 'to': '2', 'Label': 'knows', 'Since': '2001/10/03'},
    {'from': '2', 'to': '1', 'Label': 'knows', 'Since': '2001/10/04'},
    {'from': '1', 'to': '3', 'Label': 'is_member', 'Since': '2005/7/01'},
    {'from': '3', 'to': '1', 'Label': 'Members'},
    {'from': '3', 'to': '2', 'Label': 'Members'},
    {'from': '2', 'to': '3', 'Label': 'is_member', 'Since': '2011/02/14'} ] }
于 2013-11-18T07:04:37.183 回答
5

似乎没问题 - 每个对象都有它，没有重复。它有利于“阅读和处理目的”。但没有“最佳”代表。它总是取决于你的目的。您希望能够通过名称快速找到顶点吗？或按日期边缘？或者您想快速测试两个顶点是否连接？或相反 - 您想快速修改图表的某些部分？每个目的都需要不同的数据库表数据结构

于 2012-07-15T23:02:15.367 回答
4

这些图表是如何在内部存储的

如何将此图序列化为键值对象

这些问题是不同的，他们需要不同的答案。

在前一种情况下，主要要求可能是有效地执行复杂的查询。
我建议调查现有的工业强度解决方案。

在 NoSQL 术语中，这些嵌套的键值对象是文档。因此，人们可以研究图形是如何存储在“分层”多模型数据库中的：

  • 支持图数据模型，以及
  • 使用底层文档数据模型。

此类数据库的示例包括 ArangoDB、OrientDB、Azure CosmosDB。

您也可以将“文档数据模型”替换为“宽列数据模型”，因为可以将宽列数据模型视为二维键值模型。

此类数据库的示例是 DataStax Enterprise Graph，也许还有 Grakn。

例如，在 ArangoDB 中，边存储为常规文档，但存储在特殊集合中。

显然，使用的数据结构可能伴随着额外的索引等（或没有）。

那么，使用键值对象实现图形数据存储的最佳方式是什么？

我可以在哪里阅读更多关于它的信息？

我建议来自 ArangoDB 的另一篇文章：

于 2018-10-29T23:33:15.377 回答
2

我会对 Eamonn 的回答做一些改动。

每个顶点和边都有 3 个东西.. id、Label 和 Properties

{
'vertices': {
    '1': {'Label' : Person, 'Properties' : { 'Name': 'Alice', 'Age': 18}},
    '2': {'Label' : Person, 'Properties' : {'Name': 'Bob', 'Age': 22}},
    '3': {'Label': 'Group', 'Properties' : { 'Name': 'Chess'} },
'edges': [
    '4' : {'from': '1', 'to': '2', 'Label': 'knows', 'Properties':{'Since': '2001/10/03' , 'Until' : '2001/10/03'}},
    '5' : {'from': '2', 'to': '1', 'Label': 'knows', 'Properties':{'Since': '2001/10/04', 'Until' : '2001/10/05'}}
 ]
}

这样，您可以按顶点/边、它们的标签和它们的属性进行查询。

于 2018-10-31T10:05:27.350 回答
1

我会像这样序列化它，除了你应该根据你正在查找的内容选择键。我假设您使用的是 id，但也许使用名称可能会更好。

{
    'members': {
        '1': {
            'id': '1',
            'name': 'Alice',
            'age': 18,
            'groups': {
                '3': {
                    'path': 'groups.3',
                    'since': '2005-07-01'
                }
            },
            'knows': {
                '2': {
                    'path': 'members.2',
                    'since': '2001-10-03'
                }
            }
        },
        '2': {
            'id': '2',
            'name': 'Bob',
            'age': 22,
            'groups': {
                '3': {
                    'path': 'groups.3',
                    'since': '2011-02-14'
                }
            },
            'knows': {
                '1': {
                    'path': 'members.1',
                    'since': '2001-10-04'
                }
            }
        }
    },
    'groups': {
        '3': {
            'id': '3',
            'name': 'Chess',
            'members': {
                '1': { 'path': 'members.1' },
                '2': { 'path': 'members.2' }
            }
        }
    }
}

如果您有一种方法可以序列化对图的其他部分的引用，那么您可以将图直接序列化为键值对，这就是我所使用'path'的。如果我将其反序列化为字典，我可能会考虑将路径值替换为它们所引用的实际字典。请记住，这可能会导致循环引用，如果您将其序列化为 json 或其他内容，可能会导致问题。

于 2018-10-31T13:33:38.383 回答
1

我也会为结构添加邻接。我的看法是这样的，

{
  'vertices': {
    '1': {'Name': 'Alice', 'Age': 18},
    '2': {'Name': 'Bob', 'Age': 22},
    '3': {'Type': 'Group', 'Name': 'Chess'} 
   },
'edges': {
 '100' : {'from': '1', 'to': '2', 'Label': 'knows', 'Since': '2001/10/03'},
 '101': {'from': '2', 'to': '1', 'Label': 'knows', 'Since': '2001/10/04'},
 ....
  },
'adjacency': {
  '1': ['101', '102'],
  ...
  }
}

这样我可以很容易地找到与我的顶点相邻的边，而不是遍历所有边。

于 2018-10-31T14:04:10.420 回答