Как хранить ориентированный ациклический граф (DAG) как JSON?

Question

Я хочу представить группу обеспечения доступности баз данных в виде текста JSON, и мне интересно, пробовал ли кто-нибудь это делать и какие проблемы он решал, чтобы проверить, действительно ли JSON является группой обеспечения доступности баз данных.

Answer 1

Пометьте каждый узел и составьте список ребер.То есть, для каждого узла храните узлы, к которым у него есть ребра, например:

{
  "a": [ "b", "c", "d" ],
  "b": [ "d" ],
  "c": [ "d" ],
  "d": [ ]
}

Таким способом вы можете хранить многие виды графиков, а не только DAG, поэтому вам потребуется постобработать егочтобы убедиться, что у него нет петель.Просто выберите узел, DFS, если вы видите какой-либо узел более одного раза, это не DAG.Затем удалите все узлы, которые вы только что видели, и повторите все оставшиеся узлы.Делайте это до тех пор, пока не найдете цикл или не удалили все узлы, в последнем случае граф является DAG.

Обратите внимание, что в нем не хранятся родительские узлы, поскольку это избыточная информация.Вы можете создать их после загрузки графика, если вам нужны эти данные.

Answer 2

JSON не имеет собственных средств для представления групп доступности баз данных, если вы не заключите соглашение о представлении связанных данных. JSON-LD (предложение W3C) - это расширение JSON, которое пытается сделать именно это. Предложение можно найти здесь: http://json -ld.org / spec / latest / json-ld / .

Answer 3

Строго говоря, вы не можете сделать это напрямую с JSON. Вам придется придумать свой собственный способ представления объектов, которые можно идентифицировать по ссылке в другом месте структуры данных, а затем вам придется постобработать результат десериализации строки JSON.

Вы не можете сделать это с JSON по той простой причине, что выражение JSON представляет собой граф объектов, и просто нет условий для выражения того, что значение свойства должно быть значением другое свойство в другом месте в структуре данных. Иными словами, ни один объект в графе не может иметь более одного родителя, что означает, что каждый объект является значением ровно одного свойства одного другого объекта.