algorithm - 在基于树的结构中继承属性的最佳方式是什么？

Question

我有一个简单的 CMS 系统，它有一个简单的树状层次结构:

我们的页面 A 到 E 具有以下层次结构:A -> B -> C -> D -> E

所有的页面都是同一个类，并且有父子关系。

现在，假设我有一个我想在页面之间继承的属性。假设 A 是红色的:A(红色)-> B -> C -> D -> E

在这种情况下，B 到 E 将继承“红色”。

或者更复杂的场景:A(红色)-> B -> C(蓝色)-> D -> E

B 继承红色，D/E 都是蓝色。

解决此类问题的最佳方法是什么？我有一个包含 6,000 多片叶子的树结构，其中大约 100 片叶子具有可继承的属性。这 100 多片叶子的属性都保存在数据库中。对于没有显式属性的叶子，我查找祖先并使用 memcached 来保存属性。然后有非常复杂的算法来处理这些缓存的过期。这非常令人费解，我想重构为更简洁的解决方案/数据结构。

有没有人有什么想法？

谢谢!

Answer 1

有一种数据模型可以让你完美地表达这种信息，那就是RDF/RDFS。 RDF是基于三元组(主语、谓语、宾语)和 URI 对数据建模的 W3C 标准；和 RDFS ，除其他外，允许您描述类层次结构和属性层次结构。好处是有很多库可以帮助您创建和查询此类数据。

例如，如果我想说一个特定的文档 Lion 属于 Animal 类，而 programmer 属于 Geek ，我可以说:

doc:lion rdf:type class:mamal .
doc:programmer rdf:type class:Geek .

现在我可以声明类的层次结构，并说每个哺乳动物都是动物，每个动物都是生物。

class:mamal rdfs:subClassOf class:animal .
class:animal rdfs:subClassOf class:LivingThing .

而且，每个极客都是人，每个人都是生物:

class:geek rdfs:subClassOf class:human .
class:human rdfs:subClassOf class:LivingThing .

有一种语言，类似于SQL，叫做SPARQL查询这种数据，例如，如果我发出查询:

SELECT * WHERE {
       ?doc rdf:type class:LivingThing .
}

其中 ?doc 是一个变量，它将绑定(bind) class:LivingThing 类型的事物。我会得到此查询的结果 doc:lion 和 doc:programmer 因为数据库技术将遵循 RDFS 的语义，因此通过计算类的闭包它会知道 doc:lion 和 doc:programmer 是 class:LivingThing。

同理查询:

SELECT * WHERE {
       doc:lion rdf:type ?class .
}

会告诉我 doc:lion 是 class:mamal class:animal 的 rdf:type 并且类:LivingThing。

就像我刚才解释的那样，使用 RDFS，您可以创建属性的层次结构，并说:

doc:programmer doc:studies doc:computerscience .
doc:lion doc:instint doc:hunting .

我们可以说 doc:skill 和 doc:instint 这两个属性都是 doc:knows 的子属性:

doc:studies rdfs:subPropertyOf doc:knows .
doc:instint rdfs:subPropertyOf doc:knows .

随着查询:

SELECT * WHERE {
       ?s doc:knows ?o .
}

我们会知道狮子会打猎，程序员会计算机科学。

大多数 RDF/RDFS 数据库都可以轻松处理您在问题中提到的元素数量，并且有很多选择可以开始。如果您是 Java 用户，可以看看 Jena , 还有 .Net lije 的框架 this one或 Python 与 RDFLIB

但最重要的是，查看您的 CMS 文档，因为可能有插件可以将元数据导出为 RDF。例如，Drupal 在这种情况下相当先进(参见 http://drupal.org/project/rdf