Блог

Мне нужно смоделировать граф (или его можно рассматривать как рекурсивное дерево (ы), поскольку обычно оно состоит из одного или небольшого числа корней) на основе объектов, имеющих дочерние элементы:

 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
  

Итак, это будет использоваться для создания инструкций. Мне нужен аналогичный способ выполнения запросов. Мне нужны простые запросы, такие как:

 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 есть дети (b, c, x, y, z)

Мне нужно, чтобы запросы после этого соответствовали соответствующим образом всем инструкциям. Итак, другими словами, я не могу просто запустить запрос и установить свойство для всех результатов, поскольку тогда это не будет применяться к новым вещам, добавленным позже.

И, конечно, мне нужно, чтобы это было очень быстро 🙂 У меня было бы порядка 1000 узлов, 1000 выражений выражения пути и запрос на 100 000 выражений пути.

Есть ли что-то, что хорошо справляется с подобными вещами?

Я просмотрел что-то вроде RDF / OWL, но, похоже, у него нет никакой поддержки путей.

Если я правильно понимаю ваш вопрос, вы говорите о запросе на основе выводов, сделанных на основе отношений объектов. Если это так, вам нужно взглянуть на RDF и SPARQL http://www.w3.org/TR/rdf-sparql-query / и все поле семантического содержимого.

В подобной проблеме я в конечном итоге реализовал свой собственный Trie (в моем случае, на Java) с классом Node, который содержит дочерние узлы и способен проверять, соответствует ли ему оставшийся путь (что подразумевает, что все его предки подсвечивали зеленым цветом свою часть пути перед ним.

Это довольно быстро, и код довольно компактный. Надеюсь, это поможет!

не уверен, что это именно то, что вам нужно, но для меня это звучит как предложения oracle CONNECT BY и START WITH.

например, у вас могла бы быть таблица под названием NODES с этими столбцами:

• ИДЕНТИФИКАТОР как первичный ключ
• PARENT_ID, указывающий на идентификатор этой же таблицы
• ЦВЕТ … и все, что вам еще нужно

а затем выполните запрос такого рода

ВЫБЕРИТЕ ID, PARENT_ID, COLOR ИЗ УЗЛОВ, НАЧИНАЮЩИХСЯ С PARENT_ID РАВНО НУЛЮ, ПОДКЛЮЧИТЕСЬ ПО ПРЕДЫДУЩЕМУ ID = PARENT_ID

добавляя любое предложение, которое вам нужно, т. Е. ГДЕ COLOR = ‘BLUE’, оно также содержит условие nocycle для вашего примера a / b / d / a / b / d.

вот дополнительная информация

http://www.adp-gmbh.ch/ora/sql/connect_by.html

Насколько я понимаю вопрос, вы хотите смоделировать дерево, которое может поддерживать рекурсию. Я могу ответить с точки зрения дизайна таблицы sql. Для этого есть 2 способа: 1) используйте модель смежности, в которой вы будете хранить ключ в одном столбце, а дочерний — в другом

 Parent Child
Null   A
A      B
A      C
B      D
B      E
  

2) Вы можете использовать левое значение и правое значение, определенные как модель вложенного набора, и это обеспечивает хорошую производительность. Прочитайте эту статью от гуру SQL Джо Селко, и она даст вам больше подсказок
http://en.wikipedia.org/wiki/Nested_set_model

Графическая модель сильно отличается от реляционной модели, я думаю, вам следует использовать какую-нибудь базу данных NoSQL.

Поиск узлов по частичным путям реализован в MongoDB только для деревьев, но должен осуществляться с помощью простой в написании графической реализации на прикладном уровне: http://www.mongodb.org/display/DOCS/Trees in MongoDB

Существует несколько баз данных, ориентированных на графы:

• Neo4J: график NoSQL базы данных с открытым исходным кодом.
• Dex: высокопроизводительная графическая база данных.
• HyperGraphDB
• InfoGrid — база данных Internet graph

Также рекомендуем вам прочитать эту статью: Запрос данных RDF с точки зрения базы данных Graph, особенно главу 3.2 о языке запросов graph

Я действительно не уверен в каких-либо готовых материалах для решения такого рода проблем, но если бы я собирался моделировать древовидную структуру, я бы, вероятно, просто создал набор классов c # (или какой-либо другой объектно-ориентированный язык). Общая идея заключается в том, что вы настраиваете класс для узла, затем класс для самого графика с функциями для добавления узлов, удаления узлов, поиска определенных путей и т.д. (устанавливаете «цвет» путей). Затем вы могли бы даже сохранять матрицы, представляющие различные графические структуры и пути, в БД, если это то, что вы ищете.

Мне трудно уточнить, когда в вашем вопросе на самом деле не указано, какой подход вы хотите использовать. Вы ищете что-то готовое для этого? Если нет, ознакомьтесь с этим набором руководств по созданию графиков на c # (хотя те же концепции могут применяться к любому языку OO). http://msdn.microsoft.com/en-us/library/ms379574.aspx