图数据库简笔

简介

  • 图领域分类:联机事务图的持久化,类似于OLTP;离线图分析技术,类似于OLAP
  • 主流图模型:属性图、资源描述框架RDF三元组、超图
  • 图数据库两个重要特性:底层存储、处理引擎
    • 原生图存储 vs 序列化图存储
    • 原生图处理(免索引邻接,即元素直接与邻居相连)
    • 图数据库中实体之间的关联是“一等公民”

Graphdb Magic

关联数据的挑战(SQL and NoSQL)

  • SQL数据库
    • 数据关系表达成本高、且不易维护
    • 反向查询、递归反向查询代价更大,如Bob的朋友的朋友们
  • NoSQL,如键值、文档、列存储
    • 添加数据关联,一般采用聚合存储模型,即增加外键
  • 一句话,SQL和NoSQL在关联数据处理中成本高,主要原因是实体之间的关联不是作为“一等公民”存在的,而是隐含的,无论是关系型数据库中的索引,还是聚合存储模型中的外键

利用图的数据建模

  • 关联原生的建模方式
  • 常见的图查询语言,Cypher/SPARKQL/Gremlin/Graql

图数据库的内部设计

  • 原生图处理(免索引邻接)比重索引图效率高,考虑下,索引的算法复杂度可能是O(log(n)),而查找直接邻接的复杂度为O(1);遍历一个m步的网络,索引算法复杂度为O(mlog(n)),免索引邻接为O(m)
  • 原生图存储,以neo4j为例
  • Cache replacement policies

图论预分析

  • 图论和图算法是计算机科学已经成熟和易于理解的领域
  • 深度优先搜索有利于解决,试图顺着一条路径来发现离散的信息
  • 广度优先搜搜有利于解决,寻径算法或对整个关系图系统地搜寻
    • Dijkstra
    • A-Star
  • 强联系、弱联系、三元闭包、局部桥
© 2019 InnoTrek All Rights Reserved.
Theme by hiero