图集的查询语言：数据建模问题 [英] query language for graph sets: data modeling question

问题描述

假设我有一组有向图。我需要查询这些图。我想为图形建模任务获得最佳选择的感觉。到目前为止，我有这些选项，但请不要犹豫，建议其他人：

• 专有实现（矩阵）
  和图遍历算法。 RDBM和SQL选项（太耗费空间）

RDF和SPARQL选项太慢了）

你们会提出什么建议？问候。

编辑：只回答Mad的问题：

• 每个比较小，不超过200个顶点，400个边。然而，其中有数百个。




• 查询频率：很难说，它是一个实验系统。 b

• 速度：不是实时的，但实际的，比如说4-5秒的上衣。

>解决方案

你没有给我们足够的信息来回答一个深思熟虑的答案。例如：这些图的大小是多少？您希望查询这些图表的频率是多少？你需要实时回应这些查询吗？更多关于你的应用程序的用途，你的目的是什么，将是有帮助的。

无论如何，为了抵消假设基于SQL的DBMS无法处理的常见响应图结构有效，我会给一些参考：

关系数据库中的图形转换（.pdf），作者：G. Varro，K. Friedl，D. Varro，发表于 2004年基于图形工具（GraBaTs）的国际研讨会;

5结论和未来工作



在论文中，我们提出了一个新的图转换引擎基于现成的
关系数据库。在勾画出我们方法的主要概念之后，我们将
带出了几个测试用例，通过将它与
AGG [5]和PROGRES [18]工具的转换引擎进行比较来评估我们的原型实现。


从我们的实验中可以得出的主要结论是关系型
数据库提供了一个很有前途的候选作为图
转换引擎的实现框架。我们提请注意这样一个事实，即我们有前途的实验性
结果是通过使用最坏情况评估方法获得的，即通过重新计算
从零开始应用的下一个规则的观点仍然非常低效，$ b特别是$ b，对于具有大量独立匹配
的相同规则的模型转换。 ...

他们使用 PostgreSQL a>作为DBMS，这可能不是特别擅长这种应用程序。你可以尝试 LucidDB ，看看它是否更好，正如我怀疑的那样。

增量SQL查询（这里有多篇论文，您应该专注于维护SQL中图传递闭包）：

< blockquote> ..我们展示了如果允许一些辅助关系，传递闭包，交替路径，相同代和其他递归查询可以在SQL中维护，事实上，它们都可以使用至多arity 2的辅助关系来维护。 ..

增量维护一阶逻辑和SQL中的最短距离和传递闭包。

$ b

编辑：您可以提供更多详情......我认为最好的方法是用一个主存储器专用图形库进行实验y和基于DBMS的解​​决方案，然后仔细评估两种解决方案的优点和缺点。例如：需要安装DBMS（如果您不使用一个可嵌入的数据库管理系统，如 SQLite ），只有您知道您的应用程序是否需要部署以及您的用户是。另一方面，DBMS为您提供了直接的好处，如持久性（我不知道图形库支持其图形的支持），事务管理和其他无数事情。这些与您的应用程序有关吗？再次，只有你知道。

Suppose I have a set of directed graphs. I need to query those graphs. I would like to get a feeling for my best choice for the graph modeling task. So far I have these options, but please don't hesitate to suggest others:

• Proprietary implementation (matrix) and graph traversal algorithms.

• RDBM and SQL option (too space consuming)

• RDF and SPARQL option (too slow)

What would you guys suggest? Regards.

EDIT: Just to answer Mad's questions:

• Each one is relatively small, no more than 200 vertices, 400 edges. However, there are hundreds of them.

• Frequency of querying: hard to say, it's an experimental system.

• Speed: not real time, but practical, say 4-5 seconds tops.

解决方案

You didn't give us enough information to respond with a well thought out answer. For example: what size are these graphs? With what frequencies do you expect to query these graphs? Do you need real-time response to these queries? More information on what your application is for, what is your purpose, will be helpful.

Anyway, to counter the usual responses that suppose SQL-based DBMSes are unable to handle graphs structures effectively, I will give some references:

Graph Transformation in Relational Databases (.pdf), by G. Varro, K. Friedl, D. Varro, presented at International Workshop on Graph-Based Tools (GraBaTs) 2004;

5 Conclusion and Future Work

In the paper, we proposed a new graph transformation engine based on off-the-shelf relational databases. After sketching the main concepts of our approach, we carried out several test cases to evaluate our prototype implementation by comparing it to the transformation engines of the AGG [5] and PROGRES [18] tools.
The main conclusion that can be drawn from our experiments is that relational databases provide a promising candidate as an implementation framework for graph transformation engines. We call attention to the fact that our promising experimental results were obtained using a worst-case assessment method i.e. by recalculating the views of the next rule to be applied from scratch which is still highly inefficient, especially, for model transformations with a large number of independent matches of the same rule. ...

They used PostgreSQL as DBMS, which is probably not particularly good at this kind of applications. You can try LucidDB and see if it is better, as I suspect.

Incremental SQL Queries (more than one paper here, you should concentrate on " Maintaining Transitive Closure of Graphs in SQL "): "

.. we showed that transitive closure, alternating paths, same generation, and other recursive queries, can be maintained in SQL if some auxiliary relations are allowed. In fact, they can all be maintained using at most auxiliary relations of arity 2. ..

Incremental Maintenance of Shortest Distance and Transitive Closure in First Order Logic and SQL.

Edit: you give more details so... I think the best way is to experiment a little with both a main-memory dedicated graph library and with a DBMS-based solution, then evaluate carefully pros and cons of both solutions.

For example: a DBMS need to be installed (if you don't use an "embeddable" DBMS like SQLite), only you know if/where your application needs to be deployed and what your users are. On the other hand, a DBMS gives you immediate benefits, like persistence (I don't know what support graph libraries gives for persisting their graphs), transactions management and countless other. Are these relevant for your application? Again, only you know.

这篇关于图集的查询语言：数据建模问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！