《图数据库查询与算法正确性验证》.pdf

1、如何对图计算结果进行正确性验证演讲人：孙宇熙-Ultipa-创始人图计算定义01千奇百怪的错误0203如何验证？04如何优化？目录何为图计算Part 011940-50最短路径算法出现1960随机图理论运筹学1980-90社交网络互联网理论基础1995Web搜索引擎Google2000美国为首算力霸权2010图数据库单独出现2023GQL图数据库国际标准一二三四12345671736著名的七桥问题图论（数学）模型出现2023/3/125图计算解决的典型问题问题:假设两个账户间有1000笔交易，用单边图构造会需要1002个点，2000条边；多边图只需要 2个点，1000条边！1/3的资源占用单边

2、图通常面对边（关系）缺乏过滤的手段!单边图多边图 关联关系查询 影响力计算 网络化计算 模式识别 社区识别 量化计算 行为模式查询 实控人查询 风险穿透与计量 流动性风险 资债管理 营销、预测、特征工程关系型数据如何转换（迁移）为图数据？ACCOOCAOTTPPPDACCCATTOOOAccount(A)Card(C)Phone(P)Transaction(T)Own(O)TRX(T)Device(D)VS.VS.SchemaSimple GraphMulti-GraphAccounts TablePIDNameGenderCategoryP001Ricky SunM1P002Monica L

3、iuF2P003Abrham L.M3Cards TableCIDtypelevelopen_branchphonepidc001debitregularSan Francisco415xxxxxxxp001c002credit/Shenzhen139xxxxxxxxp002c003debitvipDubai868xxxxxxxp003Transactions TableTrxIDpay_card_idrecv_card_idAmtDeviceIDt001c001c00 x12000uuid-123t002c002c01x24000uuid-234t003c003c02x3600uuid-43

4、21不止一种图数据建模方式！2023/3/127图计算vs.图数据库图计算框架图数据库静态vs.动态数据多为静态需支持实时变化的数据OLAP vs.OLTPOLAPOLTP+OLAP的场景兼而有之单边图 vs.多边图多为单边图模式需支持多边图是否支持属性过滤一般不支持必须支持是否持久化数据一般不支持必须支持应用场景学术界为主工业界为主数据一致性N/A需支持ACID图算法丰富度常见简单图算法更丰富、复杂的图算法与查询查询接口或语言API，非GQLAPI/SDK,以及GQL图计算结果为何会错与验证方法Part 02/03跳(Hop)从一个顶点通过关联边Hop到另一个顶点p 在图拓扑结构中:A ho

5、p is walking from one node to another via an edgep 在表结构中:A hop is joining one record to another among two or three tablesp 多跳:Form a path of continuous nodes and edgesCOURSECIDxxxxxxENROLLMENTEnrIDsidcidSTUDENTSIDxxxdidDEPARTMENTDIDxxxxxxSDCstudyInofferedByenrollOn沿着边的方向跳逆着边的方向跳K邻或邻或K-Hop(BFS)起点:nod

6、e on bulls eye邻居:nodes on the ringsEdge:right145910118730263-hop1-hop2-hop4321p 定义：如果从顶点 A 到顶点 B 需要最少 K 跳，则 dingdianB 是定点 A 的（第）K 跳邻居。p K 邻索引：从某顶点出发到其任一邻居的无权重最短路径的长度。p K 邻索引发生变化的原因一定是因为导致 K 邻遍历结果产生变化的因素出现了变动，例如边的方向、Schema、属性字段或点、边实体发生了变动。p 在某些情况下，K 邻索引可能完全不存在例如搜索或遍历的限定条件变化所致。1.源数据验证结果正确性验证K邻查询2.多模式K