Зачем индексировать узлы или индексированное свойство лучше в базе данных графа?

Я просто попадаю в базы данных графов, и у меня, похоже, возникает проблема с выбором "index node" или "индексированного свойства" для отслеживания таких вещей, как "node type". Поскольку у меня нет реального опыта до сих пор, у меня нет никакой информации для принятия решения, и оба подхода кажутся одинаково действительными.

Итак, вопрос: Каковы компромиссы между двумя подходами и как влияет на масштаб (например, количество узлов)?

Для примера сценария предположим, что существуют два типа "вещей": User и Product, а ребра между узлами пользователя и узлами Product не имеют большого значения, но то, что нас беспокоит если нам нужны свойства type: User и type: Product для каждого node, или если мы хотим, чтобы каждый node имел ребро, указывающее назад на User node и a Product node, соответственно.

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

_{Примечание. Я смотрю на Neo4j и Titan в частности, но я думаю, что это будет иметь тенденцию применяться и в более общем плане.}

Ответ 1

Во-первых, вам нужно спросить себя: нужно ли индексировать тип вершины / node? То есть вам нужно получить вершины/узлы по их типу, скажем, получить все "пользовательские" вершины из графика или вам нужно отвечать на запросы, которые начинаются с получения всех вершин данного типа, а затем фильтруют/обрабатывают их дальше?

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

Однако недостатком этого подхода является то, что это не будет масштабироваться, потому что вы строите индекс низкой селективности. Это означает, что, вероятно, будет очень много вершин типа "пользователь" или "продукт", и все они должны быть связаны с записью индекса для "пользователя" или "продукта" соответственно. Это делает поддержание и запрос этого индекса очень дорогостоящим и трудно масштабируемым (предположим, что в facebook есть индекс типа: в элементе "фото" есть миллиарды вершин под ним). Если вы еще не заняты масштабированием, это может сработать.

Если ответ на вопрос нет, я предлагаю моделировать типы как вершины/узлы в графе. То есть имеют вершину пользователя и вершину продукта и край, помеченный как "тип" от каждого пользователя до "пользовательской" вершины и т.д.

Преимущество этого подхода заключается в том, что вы используете график для моделирования своих данных, а не для строковых значений вне вашей базы данных, представляющих важную информацию о типе. Когда вы создаете приложение, база данных графов станет его центральным компонентом и длится долгое время. Поскольку языки программирования и разработчики приходят и уходят, вы не хотите, чтобы моделирование данных и информация о типе отображались с ними и столкнулись с вопросом: "Что означает SPECIAL_USER?" Скорее, иметь вершину SPECIAL_USER и добавить к ней информацию о происхождении, т.е. Кто создал этот тип, что он представляет и краткое описание - все в базе данных.

Одна из проблем с этим подходом заключается в том, что вершины "пользователь" и "продукт" будут иметь много ребер, инцидентов на них, поскольку ваше приложение масштабируется. Другими словами, вы создаете суперноды, которые создают проблемы масштабирования. Вот почему Титан представил концепцию однонаправленного края. Однонаправленный край похож на ссылку в сети: начальная вершина указывает на другую вершину, но эта вершина не знает о краю. Поскольку вы не хотите переходить от вершины "пользователя" ко всем пользовательским вершинам, вы не теряете ничего, кроме достижения масштабируемости и производительности.

Ответ 2

Какой запрос вы хотите задать? В Neo4j вы создадите индекс User и Product или даже объедините их в одном, а затем сможете задавать такие вещи, как

start bob = node:User(name='Bob') match ....

и даже полнотекстовый поиск. Для удобства проверки, что node является пользователем или продуктом, вы можете иметь свойство все еще на узлах, просто для удобного и быстрого обхода. Если вы не переходите от User/Product к узлам экземпляра (для этого вы делаете поиск по индексу), вы можете даже выполнить проверку, связав связь Product или User с узлами типа (супер), давая вы просматриваете, как

start s = node:User(name='Bob') match s-[r]-(product)-[typeRel:PRODUCT]->() return product

НТН

Ответ 3

Очень важная причина индексации была пропущена здесь. Предположим, у вас есть сложный граф со многими различными свойствами и многими различными типами node, и вы хотите сопоставить шаблон с "человеком", у которого есть куча свойств.

Без индексов у вас нет опции, кроме как пересечь график, график, в котором, возможно, только 0,01% узлов имеют тип человека. И обход может не достигать несвязанных областей графика.

Вместо этого, если я проиндексировал человека, я просто перебираю каждого человека и выполняю поиск локально вокруг каждого человека, чтобы увидеть, совпадает ли его шаблон.

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

Мораль: если вы предусмотрели вариант использования, где будет много поиска графа с определенным типом node в качестве границы node в вашем шаблоне (например, здесь много поисков "людей с шаблоном X",), то вы должны индексировать эти узлы для улучшения производительности поиска.

Если вы собираетесь искать такие вещи, как "все узлы в двух ссылках человека Питер", тогда индексирование лица по их имени будет иметь решающее значение и позволит обеспечить постоянную производительность во времени независимо от размера графика - поскольку вы, по существу, смотрите вверх расположение Петра в хеш-таблице.