我需要基于具有子项的事物对图进行建模（或者可以将其视为递归树，因为它通常是单个或少量的根）：
a hasChildren (b, c)
b hasChildren (d, e)
c hasChildren (f, g)
d hasChildren (h, a)
现在有隐式路径、a/c/f 和递归路径还有： a/b/d/a/b/d/...
然后我需要通过路径表达式在图表上设置内容，它们的两个属性（这些路径具有颜色：蓝色等），并且改变他们的孩子——也许移除/隐藏他们，或者添加新的孩子。
通过路径表达式，我的意思是这样的：
a/b/** -> color = "blue"
意味着所有以 a/b/ 开头的路径都具有属性 color =“blue”。因此，如果我查询 a/b/d/a/b/d/a 的颜色，它将返回蓝色。但如果我只查询 a 的颜色，此时就没有。
其他表达方式可能是：
**/d/h
a/b/[color="blue"]
a/**/h
So, that will be used to make statements.我需要类似的查询方式。我需要简单的查询，例如：
a/b/d
和更复杂的查询，例如：
a/**[color="blue"] -- descendants that have attribute color = "blue". This could be infinite in recursive case so we can put a restriction on this type of query to have it make sense, like does such a path exist, or just return first one or something.
另外，可以随时添加更多节点。
a hasChildren (b, c, x, y, z)
我需要之后的查询来正确匹配所有语句。换句话说，我不能只运行一个查询并为所有结果设置一个属性，因为那样它就不适用于稍后添加的新内容。
当然，我需要它非常快:)我需要大约 1000 个节点、1000 个路径表达式语句以及对 100,000 个路径表达式的查询。
有什么东西可以很好地处理这种事情吗？
我研究了 RDF/OWL 之类的东西，但它似乎没有任何对路径的支持。
I need to model a graph (or could be seen as a recursive tree(s) since it typically as a single or small number of roots) based on things having children:
a hasChildren (b, c)
b hasChildren (d, e)
c hasChildren (f, g)
d hasChildren (h, a)
Now there are implicit paths, a/c/f and recursive ones as well: a/b/d/a/b/d/...
And then I need to set things on the graph via a path expression, both properties about them (these paths have color: blue, or such) and also changing their children--perhaps removing/hiding them, or adding new children.
By path expression, I mean something like this:
a/b/** -> color = "blue"
would mean that all paths that start with a/b/ have the property color = "blue". So, if I queried for the color of a/b/d/a/b/d/a, it would return blue. But if I queried for the color of just a, at this point there is none.
Other expressions might be:
**/d/h
a/b/[color="blue"]
a/**/h
So, that would be used to make statements. I need similar way of doing querying. I need simple queries such as:
a/b/d
and more complex ones like:
a/**[color="blue"] -- descendants that have attribute color = "blue". This could be infinite in recursive case so we can put a restriction on this type of query to have it make sense, like does such a path exist, or just return first one or something.
Also, more nodes might be added at any time.
a hasChildren (b, c, x, y, z)
I need the queries after that to match appropriately all the statements. So in other words, I can't just run a query and set a property on all the results, since then it won't apply to new things added later.
And of course, I need it to be very fast :) I would have on the order of 1000's of nodes, 1000's of path expression statements, and query on 100,000's of path expressions.
Is there something that handles this type of thing well?
I looked into RDF/OWL kind of thing but it doesn't seem to have any support for paths.
发布评论
评论（6）
如果我正确理解你的问题，那么你正在谈论针对对象关系做出的推论进行查询。如果是这样，您需要看看 RDF 和 SPARQL http://www.w3 .org/TR/rdf-sparql-query/ 以及整个语义内容领域。
If I understand your question correctly, you are talking about querying against inferences made against object relationships. If so, you need to take a look at RDF and SPARQL http://www.w3.org/TR/rdf-sparql-query/ and the whole field of semantic content.
在类似的问题上，我最终实现了我自己的 Trie （在我的例子中，在 Java 中）一个包含 Node 子节点的 Node 类，并且能够检查剩余路径是否与其匹配（这意味着它的所有祖先都将其之前的路径块点亮为绿灯。
它非常快并且代码非常紧凑。希望它有所帮助！
On a similar problem, I ended up implementing my own Trie (in my case, in Java) with a Node class that contains Node children and is able to check if the leftover path matches it (which implies that all its ancestors green lighted their chunk of the path before it.
It's pretty fast and the code's quite compact. Hope it helps!
不确定这是否正是您所需要的，但对我来说，这听起来像 Oracle 的 CONNECT BY 和 START WITH 子句。
例如，您可以有一个名为 NODES 的表，其中包含以下列：
，然后进行此类查询
SELECT ID, PARENT_ID, COLOR FROM NODES START WITH PARENT_ID IS NULL CONNECT BY PRIOR ID = PARENT_ID
添加您需要的任何子句，即 WHERE COLOR='BLUE'
它还有一个针对您的 a/b/d/a/b/d 示例的 nocycle 条件，
这里有更多信息
http://www.adp-gmbh.ch/ora/sql/connect_by.html
not sure if this is exactly what you need but to me it sounds like oracle's CONNECT BY and START WITH clauses.
for instance you could have a table called NODES with these columns:
and then make this kind of query
SELECT ID, PARENT_ID, COLOR FROM NODES START WITH PARENT_ID IS NULL CONNECT BY PRIOR ID = PARENT_ID
adding whatever clause you need i.e. WHERE COLOR='BLUE'
it also has a nocycle condition for your a/b/d/a/b/d example
here's more info
http://www.adp-gmbh.ch/ora/sql/connect_by.html
根据我对这个问题的理解，你想要建模一棵可以支持递归的树。
我可以从sql表设计的角度来回答。有两种方法可以做到这一点
1) 使用邻接模型，将键存储在一列中，将子存储在另一列中
2) 您可以使用定义为嵌套集模型的左手值和右手值，这具有良好的性能。阅读 SQL 大师 Joe Celko 的这篇文章，它会给你更多提示
http://en.wikipedia.org/wiki/Nested_set_model
From what i understand of the question you want to model a tree that can support recursive.
I can answer from sql table design point of view. There are 2 ways to do this
1) use an adjaceny model where you will store the key in one column and the child in the other
2) You can use a Left Hand Value and Right Hand Value as defined as a Nested Set Model and this has good performance. Read this article from the SQL guru Joe Celko and it will give you more hints
http://en.wikipedia.org/wiki/Nested_set_model
图模型与关系模型有很大不同，我认为你应该使用一些 NoSQL 数据库。
MongoDB 中实现了通过部分路径查找节点，仅适用于树，但应该在应用层上通过易于编写的图形实现： http://www.mongodb.org/display/DOCS/Trees+in+MongoDB
面向图形的数据库很少：
另外建议您阅读这篇文章：从图数据库查询 RDF 数据
观点，特别是关于图查询语言的3.2章节
Graph model is quite different from the relational model, I thing you should use some NoSQL db.
Finding nodes by partial paths is implemented in MongoDB, only for trees, but should by easy to write graph implementation on application layer: http://www.mongodb.org/display/DOCS/Trees+in+MongoDB
There are few graph-oriented DBs:
Also recommend that you read this article: Querying RDF Data from a Graph Database
Perspective, especially chapter 3.2 about graph query language
我真的不确定是否有任何预制的东西可以处理此类问题，但如果我要对树结构进行建模，我可能只会创建一组 C# 类（或其他一些面向对象的语言）。总体思路是为节点设置一个类，然后为图形本身设置一个类，其中包含添加节点、删除节点、查找特定路径等功能（设置路径的“颜色”）。如果您正在寻找的话，您甚至可以将代表不同图形结构的矩阵和路径保存到数据库。
当您的问题没有真正指定您想要采取哪种方法时，我很难具体说明。您是否正在寻找预制的东西来执行此操作？如果没有，请查看这套有关在 C# 中创建图形的教程（但相同的概念可以适用于任何 OO 语言）。 http://msdn.microsoft.com/en-us/library/ms379574.aspx
I am really not sure about any pre-made stuff to handle this kind of problem, but if I was going to model a tree structure I would probably just create a set of c# classes (or some other object oriented language). The general idea is you set up a class for a node, then a class for the graph itself with functions to add nodes, remove nodes, find specific paths, etc (set the "colour" of paths). You could then even save matrices representing different graph structures and paths to a DB if that is what you are looking for.
It is hard for me to get specific when your question does not really specify what sort of approach you wanna take. Are you looking for something pre-made to do this? If not, check out this set of tutorials about creating graphs in c# (same concepts could apply to any OO language though). http://msdn.microsoft.com/en-us/library/ms379574.aspx