Какой лучший способ наследовать свойства в древовидной структуре?

Question

У меня есть простая система CMS, которая имеет простую древовидную иерархию:

У нас есть страницы от A до E, которые имеют следующую иерархию: A -> B -> C -> D -> E

Все страницы относятся к одному классу и имеют отношения родитель-потомок.

Теперь, допустим, у меня есть свойство, которое я хочу унаследовать среди страниц. Допустим, А красный: A (красный) -> B -> C -> D -> E

В этом случае от B до E наследуют "красный".

Или более сложные сценарии: A (красный) -> B -> C (синий) -> D -> E

B наследует красный, а D / E будет синим.

Что было бы лучшим способом решить что-то подобное? У меня есть древовидная структура с более чем 6000 листьев, и около 100 из них имеют наследуемые свойства. Эти 100 или около того листьев сохраняют свои свойства в базе данных. Для листьев без явных свойств я ищу предков и использую memcached для сохранения свойств. Кроме того, существуют очень сложные алгоритмы для обработки устаревших кэшей. Это ужасно запутанно, и я бы хотел, чтобы рефакторинг превратился в более чистое решение / структуру данных.

У кого-нибудь есть идеи?

Спасибо!

Answer 1

Существует модель данных, которая позволяет вам идеально выразить такую ​​информацию, а именно RDF / RDFS. RDF - это стандарт W3C для моделирования данных на основе троек (субъект, предикат, объект) и URI;и 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 - это переменная, которая будет связывать вещи типа class:LivingThing.В результате этого запроса я получу doc:lion и doc:programmer, потому что технология базы данных будет следовать семантике RDFS и, следовательно, вычисляя закрытие классов, она узнает, что doc:lion и doc:programmer равны class:LivingThing.

Таким же образом запрос:

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

Скажет мне, что doc:lion составляет rdf:type из class:mamal class:animal и class: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 , этот или Python с RDFLIB

Но самое главное, взгляните на документацию вашей CMS, потому что, возможно, есть плагины для экспорта метаданных в виде RDF.Drupal, например, довольно продвинут в этом случае (см. http://drupal.org/project/rdf

Answer 2

Если ваша проблема связана с производительностью ...

Я предполагаю, что вы захотите сэкономить в памяти все эти наследуемые свойства (или, возможно, у вас есть лот из них), в противном случае это можно легко решить с помощью виртуальных свойств.

Если вам нужны редкие наследуемые свойства, например, если вы моделируете, как распространяются свойства HTML DOM или CSS, вам необходимо:

1. Сохранить указатель на родительский узел (для перехода вверх)
2. Используйте хэш-словарь для хранения свойств внутри каждого класса (или каждого экземпляра, в зависимости от ваших потребностей) с ключом по имени
3. Если свойства не зависят от экземпляра, используйте статический словарь класса
4. Если свойства могут быть переопределены экземпляр за экземпляром, добавьте словарь экземпляра сверху
5. Получая доступ к свойству, начинайте находить его на листе, сначала посмотрите словарь экземпляров, затем словарь статических классов, затем поднимитесь по дереву

Конечно, вы можете добавить больше функций. Это похоже на то, как Windows Presentation Foundation решает эту проблему с помощью DependencyProperty.

Если ваша проблема связана с базой данных ...

Если вместо этого ваша проблема состоит в том, чтобы избежать чтения базы данных, чтобы пройтись по дереву (то есть загрузить родителей, чтобы найти унаследованные свойства), вам потребуется выполнить какое-то кэширование для родительских значений. Или же, когда вы загружаете лист из базы данных, вы можете загрузить все его родительские элементы и создать в памяти словарь основных объединенных свойств.

Если вы хотите избежать нескольких поисков в базе данных, чтобы найти каждого родителя, один прием состоит в том, чтобы закодировать путь к каждому узлу в текстовое поле, например, «1.2.1.3.4» для листа на 6-м уровне. Затем загружайте только те узлы, которые имеют пути, начинающиеся с подстрок. Затем вы можете получить полный родительский путь в одном запросе SQL.