Графическая база данных

В этой статье есть несколько проблем. Помогите улучшить ее или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалять эти сообщения ) Данная статья , возможно, содержит оригинальное исследование .Пожалуйста, улучшите его, проверив сделанные заявления и добавив встроенные цитаты . Заявления, состоящие только из оригинальных исследований, должны быть удалены. ( август 2016 г. )( Узнайте, как и когда удалить это сообщение ) В статье чрезмерно много ссылок на первоисточники .Пожалуйста, улучшите эту статью, добавив вторичные или третичные источники . Найти источники:  "База данных Graph" – новости  · газеты  · книги  · ученый  · JSTOR ( август 2016 г. )( Узнайте, как и когда удалить это сообщение ) Для проверки данной статьи необходимы дополнительные цитаты .Пожалуйста, помогите улучшить эту статью , добавив ссылки на надежные источники . Неподтвержденный материал может быть оспорен и удален. Найти источники:  "Graph database" – новости  · газеты  · книги  · ученый  · JSTOR ( август 2016 г. )( Узнайте, как и когда удалить это сообщение ) ( Узнайте, как и когда удалить это сообщение )

Графовая база данных ( GDB ) — это база данных , которая использует графовые структуры для семантических запросов с узлами , ребрами и свойствами для представления и хранения данных. ^[1] Ключевым понятием системы является граф (или ребро или связь). Граф связывает элементы данных в хранилище с набором узлов и ребер, ребра представляют связи между узлами. Связи позволяют связывать данные в хранилище напрямую и, во многих случаях, извлекать их с помощью одной операции. Графовые базы данных сохраняют связи между данными в качестве приоритета. Запрос связей выполняется быстро, поскольку они постоянно хранятся в базе данных. Связи можно наглядно визуализировать с помощью графовых баз данных, что делает их полезными для сильно взаимосвязанных данных. ^[2]

Графовые базы данных обычно называют базами данных NoSQL . Графовые базы данных похожи на сетевые модели баз данных 1970-х годов, поскольку обе представляют общие графы, но сетевые модели баз данных работают на более низком уровне абстракции ^[3] и не имеют простого обхода по цепочке ребер. ^[4]

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

По состоянию на 2021 год ^{[обновлять]}ни один язык графовых запросов не был принят повсеместно так же, как SQL для реляционных баз данных, и существует большое разнообразие систем, многие из которых тесно связаны с одним продуктом. Некоторые ранние усилия по стандартизации привели к появлению языков запросов от нескольких поставщиков, таких как Gremlin , SPARQL и Cypher . В сентябре 2019 года члены Объединенного технического комитета ISO/IEC 1 (ISO/IEC JTC 1) одобрили предложение о проекте по созданию нового стандартного языка графовых запросов (ISO/IEC 39075 Information Technology — Database Languages ​​— GQL). GQL предназначен для использования в качестве декларативного языка запросов к базам данных, как SQL. Помимо интерфейсов языка запросов, к некоторым графовым базам данных осуществляется доступ через интерфейсы прикладного программирования (API).

Графовые базы данных отличаются от графовых вычислительных машин. Графовые базы данных — это технологии, которые являются переводами реляционных баз данных онлайн-обработки транзакций (OLTP). С другой стороны, графовые вычислительные машины используются в онлайн-аналитической обработке (OLAP) для массового анализа. ^[5] Графовые базы данных привлекли значительное внимание в 2000-х годах из-за успехов крупных технологических корпораций в использовании фирменных графовых баз данных, ^[6] а также внедрения графовых баз данных с открытым исходным кодом .

В одном исследовании сделан вывод о том, что СУРБД «сопоставима» по производительности с существующими механизмами анализа графов при выполнении графовых запросов. ^[7]

В середине 1960-х годов навигационные базы данных , такие как IMS компании IBM , поддерживали древовидные структуры в своей иерархической модели , но строгую древовидную структуру можно было обойти с помощью виртуальных записей. ^{[8] [9]}

Графовые структуры могли быть представлены в базах данных сетевых моделей с конца 1960-х годов. CODASYL , который определил COBOL в 1959 году, определил язык сетевых баз данных в 1969 году.

Размеченные графы могли быть представлены в графовых базах данных с середины 1980-х годов, таких как Логическая модель данных. ^{[10] [11]}

Коммерческие объектные базы данных (ODBMS) появились в начале 1990-х годов. В 2000 году Object Data Management Group опубликовала стандартный язык для определения структур объектов и отношений (графов) в своей публикации ODMG'93.

Несколько усовершенствований графовых баз данных появились в начале 1990-х годов и получили дальнейшее развитие в конце 1990-х годов с попытками индексировать веб-страницы.

В середине-конце 2000-х годов стали доступны коммерческие графовые базы данных с гарантиями ACID , такие как Neo4j и Oracle Spatial and Graph .

В 2010-х годах стали доступны коммерческие графовые базы данных ACID, которые можно было масштабировать горизонтально . Кроме того, SAP HANA привнесла в графовые базы данных технологии in-memory и столбчатые технологии. ^[12] Также в 2010-х годах стали доступны многомодельные базы данных , которые поддерживали графовые модели (и другие модели, такие как реляционные базы данных или документно-ориентированные базы данных ), такие как OrientDB , ArangoDB и MarkLogic (начиная с версии 7.0). В это время графовые базы данных различных типов стали особенно популярны в анализе социальных сетей с появлением компаний социальных сетей. Также в течение десятилетия стали доступны облачные графовые базы данных, такие как Amazon Neptune и Neo4j AuraDB .

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

Графовая база данных — это база данных, основанная на теории графов . Она состоит из набора объектов, которые могут быть узлами или ребрами.

• Узлы представляют сущности или экземпляры, такие как люди, предприятия, счета или любой другой элемент, который нужно отслеживать. Они примерно эквивалентны записи, отношению или строке в реляционной базе данных или документу в базе данных хранилища документов.
• Ребра , также называемые графами или отношениями , — это линии, которые соединяют узлы с другими узлами; представляя отношения между ними. Значимые закономерности возникают при изучении соединений и взаимосвязей узлов, свойств и ребер. Ребра могут быть направленными или ненаправленными. В ненаправленном графе ребро, соединяющее два узла, имеет единственное значение. В направленном графе ребра, соединяющие два разных узла, имеют разные значения в зависимости от их направления. Ребра являются ключевым понятием в графовых базах данных, представляя собой абстракцию, которая напрямую не реализована в реляционной модели или модели хранилища документов .
• Свойства — это информация, связанная с узлами. Например, если бы Википедия была одним из узлов, она могла бы быть связана с такими свойствами, как веб-сайт , справочный материал или слова, начинающиеся с буквы w , в зависимости от того, какие аспекты Википедии относятся к данной базе данных.

Модель графа с помеченными свойствами представлена ​​набором узлов, отношений, свойств и меток. Как узлы данных, так и их отношения именованы и могут хранить свойства, представленные парами ключ-значение . Узлы могут быть помечены для группировки. Ребра, представляющие отношения, обладают двумя качествами: они всегда имеют начальный узел и конечный узел и направлены; ^[13] делая граф направленным графом . Отношения также могут иметь свойства. Это полезно для предоставления дополнительных метаданных и семантики отношениям узлов. ^[14] Прямое хранение отношений обеспечивает обход за постоянное время . ^[15]

В модели графа RDF каждое добавление информации представлено отдельным узлом. Например, представьте себе сценарий, в котором пользователь должен добавить свойство имени для человека, представленного как отдельный узел в графе. В модели графа с маркированным свойством это будет сделано путем добавления свойства имени в узел человека. Однако в RDF пользователь должен добавить отдельный узел, называемый , hasNameсоединяющий его с исходным узлом человека. В частности, модель графа RDF состоит из узлов и дуг. Нотация графа RDF или утверждение представлены: узлом для субъекта, узлом для объекта и дугой для предиката. Узел может быть оставлен пустым, литералом и/или идентифицирован URI . Дуга также может быть идентифицирована URI. Литерал для узла может быть двух типов: простой (нетипизированный) и типизированный. Простой литерал имеет лексическую форму и, необязательно, языковой тег. Типизированный литерал состоит из строки с URI, который идентифицирует определенный тип данных. Пустой узел может использоваться для точной иллюстрации состояния данных, когда данные не имеют URI . ^[16]

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

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

Базовый механизм хранения графовых баз данных может различаться. Некоторые зависят от реляционного движка и «хранят» графовые данные в таблице ( хотя таблица является логическим элементом, поэтому этот подход накладывает еще один уровень абстракции между графовой базой данных, системой управления графовой базой данных и физическими устройствами, где данные фактически хранятся). Другие используют хранилище «ключ-значение» или документоориентированную базу данных для хранения, что делает их по своей сути структурами NoSQL . Узел будет представлен как любое другое хранилище документов, но ребра, которые связывают два разных узла, содержат специальные атрибуты внутри своего документа; атрибуты _from и _to.

Производительность поиска данных зависит от скорости доступа от одного конкретного узла к другому. Поскольку смежность без индексов заставляет узлы иметь прямые физические адреса ОЗУ и физически указывать на другие соседние узлы, это приводит к быстрому извлечению. Собственная графовая система с смежностью без индексов не должна проходить через какие-либо другие типы структур данных для поиска связей между узлами. Непосредственно связанные узлы в графе сохраняются в кэше после извлечения одного из узлов, что делает поиск данных даже быстрее, чем при первом извлечении узла пользователем. Однако такое преимущество имеет свою цену. Смежность без индексов жертвует эффективностью запросов, которые не используют обходы графа . Собственные графовые базы данных используют смежность без индексов для обработки операций CRUD над сохраненными данными.

Было признано несколько категорий графиков по типу данных. Gartner предлагает пять основных категорий графиков: ^[17]

• Социальный граф : это о связях между людьми; примерами являются Facebook , Twitter и идея шести степеней разделения.
• Граф намерений: он касается рассуждений и мотивации.
• График потребления: также известный как «график платежей», график потребления широко используется в розничной торговле. Компании электронной коммерции, такие как Amazon, eBay и Walmart, используют графики потребления для отслеживания потребления отдельных клиентов.
• График интересов : отображает интересы человека и часто дополняется социальным графиком. Он имеет потенциал следовать предыдущей революции веб-организации, отображая веб по интересам, а не индексируя веб-страницы.
• Мобильный граф: он построен на основе мобильных данных. Мобильные данные в будущем могут включать данные из сети, приложений, цифровых кошельков, GPS и устройств Интернета вещей (IoT).

Начиная с работы Эдгара Ф. Кодда 1970 года о реляционной модели ^[18] , реляционные базы данных стали фактическим отраслевым стандартом для крупномасштабных систем хранения данных. Реляционные модели требуют строгой схемы и нормализации данных , которая разделяет данные на множество таблиц и удаляет любые дублирующиеся данные в базе данных. Данные нормализуются для сохранения согласованности данных и поддержки транзакций ACID . Однако это накладывает ограничения на то, как можно запрашивать отношения.

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

По сравнению с реляционными базами данных графовые базы данных часто быстрее для ассоциативных наборов данных ^{[ нужна цитата ]} и более точно соответствуют структуре объектно-ориентированных приложений. Они могут масштабироваться более естественно ^{[ нужна цитата ]} для больших наборов данных, поскольку им обычно не нужны операции соединения , которые часто могут быть дорогими. Поскольку они меньше зависят от жесткой схемы, их позиционируют как более подходящие для управления специальными и меняющимися данными с развивающимися схемами.

Напротив, системы управления реляционными базами данных обычно быстрее выполняют ту же операцию с большим количеством элементов данных, позволяя манипулировать данными в их естественной структуре. Несмотря на преимущества графовых баз данных и недавнюю популярность по сравнению с ^{[ требуется цитата ]} реляционными базами данных, рекомендуется, чтобы сама графовая модель не была единственной причиной замены существующей реляционной базы данных. Графовая база данных может стать актуальной, если есть доказательства улучшения производительности на порядки и снижения задержки. ^[19]

Реляционная модель собирает данные вместе, используя информацию в данных. Например, можно искать всех «пользователей», чей номер телефона содержит код города «311». Это можно сделать, выполнив поиск в выбранных хранилищах данных или таблицах , просматривая выбранные поля телефонных номеров для строки «311». Это может быть трудоемким процессом в больших таблицах, поэтому реляционные базы данных предлагают индексы , которые позволяют хранить данные в меньшей подтаблице, содержащей только выбранные данные и уникальный ключ (или первичный ключ) записи. Если номера телефонов индексированы, тот же поиск будет выполняться в меньшей индексной таблице, собирая ключи соответствующих записей, а затем просматривая основную таблицу данных для записей с этими ключами. Обычно таблица хранится таким образом, что позволяет выполнять поиск по ключу очень быстро. ^[20]

Реляционные базы данных изначально не содержат идею фиксированных отношений между записями. Вместо этого связанные данные связываются друг с другом путем сохранения уникального ключа одной записи в данных другой записи. Например, таблица, содержащая адреса электронной почты пользователей, может содержать элемент данных с именем userpk, который содержит первичный ключ записи пользователя, с которой он связан. Чтобы связать пользователей и их адреса электронной почты, система сначала ищет первичные ключи выбранных записей пользователей, ищет эти ключи в столбце userpkв таблице электронной почты (или, что более вероятно, в их индексе), извлекает данные электронной почты, а затем связывает записи пользователей и электронной почты, чтобы создать составные записи, содержащие все выбранные данные. Эта операция, называемая соединением , может быть вычислительно затратной. В зависимости от сложности запроса, количества соединений и индексирования различных ключей системе может потребоваться выполнить поиск по нескольким таблицам и индексам, а затем отсортировать все это, чтобы сопоставить их вместе. ^[20]

Напротив, графовые базы данных напрямую хранят связи между записями. Вместо того, чтобы находить адрес электронной почты, просматривая ключ пользователя в userpkстолбце, запись пользователя содержит указатель, который напрямую ссылается на запись адреса электронной почты. То есть, выбрав пользователя, указатель можно перейти непосредственно к записям электронной почты, нет необходимости искать в таблице электронной почты, чтобы найти соответствующие записи. Это может устранить дорогостоящие операции соединения. Например, если кто-то ищет все адреса электронной почты для пользователей в коде города «311», движок сначала выполнит обычный поиск, чтобы найти пользователей в «311», но затем извлечет адреса электронной почты, следуя ссылкам, найденным в этих записях. Реляционная база данных сначала найдет всех пользователей в «311», извлечет список первичных ключей, выполнит еще один поиск любых записей в таблице электронной почты с этими первичными ключами и свяжет соответствующие записи вместе. Для этих типов общих операций графовые базы данных теоретически будут быстрее. ^[20]

Истинная ценность графового подхода становится очевидной, когда выполняется поиск, который имеет глубину более одного уровня. Например, рассмотрим поиск пользователей, у которых есть «подписчики» (таблица, связывающая пользователей с другими пользователями) в коде города «311». В этом случае реляционная база данных должна сначала найти всех пользователей с кодом города в «311», затем найти любого из этих пользователей в таблице подписчиков, а затем, наконец, найти таблицу пользователей, чтобы извлечь соответствующих пользователей. Напротив, графовая база данных будет искать всех пользователей в «311», затем следовать обратным ссылкам через отношение подписчиков, чтобы найти пользователей-подписчиков. Это позволяет избежать нескольких поисков, поисков и использования памяти, связанных с хранением всех временных данных из нескольких записей, необходимых для построения вывода. В терминах нотации «большой О» этот запрос будет занимать время, т. е. пропорционально логарифму размера данных. Напротив, реляционная версия будет выполнять несколько поисков, плюс время, необходимое для объединения всех записей данных. ^[20]${\displaystyle O(\log n)+O(1)}$${\displaystyle O(\log n)}$${\displaystyle O(n)}$

Относительное преимущество поиска графа растет с ростом сложности запроса. Например, кто-то может захотеть узнать «тот фильм о подводных лодках с актером, который был в том фильме, с тем другим актером, который играл главную роль в « Унесенных ветром ». Для этого сначала требуется, чтобы система нашла актеров в «Унесенных ветром » , нашла все фильмы, в которых они снимались, нашла всех актеров во всех этих фильмах, которые не были главными в « Унесенных ветром» , а затем нашла все фильмы, в которых они снимались, наконец, отфильтровав этот список по тем, описания которых содержат «подводная лодка». В реляционной базе данных это потребовало бы нескольких отдельных поисков по таблицам фильмов и актеров, выполнения еще одного поиска по фильмам о подводных лодках, нахождения всех актеров в этих фильмах, а затем сравнения (больших) собранных результатов. Напротив, база данных графа будет проходить от «Унесенных ветром» до Кларка Гейбла , собирать ссылки на фильмы, в которых он снимался, собирать ссылки из этих фильмов на других актеров, а затем следовать ссылкам из этих актеров обратно к списку фильмов. Полученный список фильмов можно затем искать по запросу «подводная лодка». Все это можно сделать с помощью одного поиска. ^[21]

Свойства добавляют еще один уровень абстракции к этой структуре, что также улучшает многие общие запросы. Свойства по сути являются метками, которые можно применять к любой записи, или в некоторых случаях также к ребрам. Например, можно пометить Кларка Гейбла как «актер», что затем позволит системе быстро находить все записи, которые являются актерами, в отличие от режиссера или оператора камеры. Если метки на ребрах разрешены, можно также пометить связь между « Унесенными ветром» и Кларком Гейблом как «ведущий», и, выполняя поиск по людям, которые являются «ведущим» «актером» в фильме « Унесенные ветром », база данных выдаст Вивьен Ли , Оливию де Хэвилленд и Кларка Гейбла. Эквивалентный запрос SQL должен будет полагаться на добавленные данные в таблице, связывающие людей и фильмы, что усложняет синтаксис запроса. Такого рода метки могут улучшить производительность поиска при определенных обстоятельствах, но, как правило, более полезны для предоставления дополнительных семантических данных для конечных пользователей. ^[21]

Реляционные базы данных очень хорошо подходят для плоских макетов данных, где связи между данными находятся только на одном или двух уровнях в глубину. Например, бухгалтерской базе данных может потребоваться поиск всех позиций для всех счетов-фактур для данного клиента, запрос с тремя соединениями. Графовые базы данных нацелены на наборы данных, которые содержат гораздо больше ссылок. Они особенно хорошо подходят для систем социальных сетей , где отношения «друзья» по сути неограниченны. Эти свойства делают графовые базы данных естественным образом подходящими для типов поиска, которые все чаще встречаются в онлайн-системах и в средах больших данных . По этой причине графовые базы данных становятся очень популярными для крупных онлайн-систем, таких как Facebook , Google , Twitter и подобных систем с глубокими связями между записями.

Для дальнейшей иллюстрации представьте себе реляционную модель с двумя таблицами: peopleтаблица (со столбцом person_idи person_name) и friendтаблица (со столбцом friend_idи person_id, который является внешним ключом таблицы people). В этом случае поиск всех друзей Джека приведет к следующему SQL-запросу.

SELECT p2 . person_name FROM people p1 JOIN friend ON ( p1 . person_id = friend . person_id ) JOIN people p2 ON ( p2 . person_id = friend . friend_id ) WHERE p1 . person_name = 'Джек' ;                   

Тот же запрос можно перевести как --

• Cypher , язык запросов к графовой базе данных

  СОВПАДЕНИЕ ( стр.1 : персона { имя : 'Джек' } ) -[ : ДРУГ_С_ИМЕНЕМ ] - ( стр.2 : персона ) ВОЗВРАТ стр.2.имя    

• SPARQL — язык запросов к графовой базе данных RDF, стандартизированный W3C и используемый в нескольких хранилищах RDF Triple и Quad .
  • Длинная форма

    ПРЕФИКС  foaf :  <http://xmlns.com/foaf/0.1/>SELECT  ?name WHERE  {  ?s  a  foaf : Person  .  ?s  foaf : name  "Jack"  .  ?s  foaf : knows  ?o  .  ​​?o  foaf : name  ?name  .  }

  • Краткая форма

    ПРЕФИКС  foaf :  <http://xmlns.com/foaf/0.1/>SELECT  ?name WHERE  {  ?s  foaf : name  "Джек"  ;  foaf : knows  ?o  .  ​​?o  foaf : name  ?name  .  }

• SPASQL, гибридный язык запросов к базе данных, который расширяет SQL с помощью SPARQL

  SELECT  people.name FROM ( SPARQL PREFIX foaf : < http://xmlns.com/foaf/0.1/> SELECT ? name WHERE { ?s foaf : name "Джек" ; foaf : knows ?o . ​​?o foaf : name ?name . } ) AS people ;                         

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

Также есть результаты, которые указывают на то, что простые, сжатые и декларативные запросы графовых баз данных не обязательно обеспечивают хорошую производительность по сравнению с реляционными базами данных. В то время как графовые базы данных предлагают интуитивное представление данных, реляционные базы данных предлагают лучшие результаты, когда требуются операции с множествами. ^[15]

Ниже приведен список известных графовых баз данных:

• AQL (язык запросов ArangoDB) : язык запросов, подобный SQL, используемый в ArangoDB как для документов, так и для графиков.
• Язык запросов Cypher (Cypher): декларативный язык запросов графа для Neo4j , который обеспечивает произвольный и программный (SQL-подобный) доступ к графу. ^[45]
• GQL : предлагаемый стандартный язык графовых запросов ISO
• GraphQL : язык запросов и манипулирования данными с открытым исходным кодом для API. Dgraph реализует модифицированный язык GraphQL, называемый DQL (ранее GraphQL+-)
• Gremlin : язык программирования графов, являющийся частью проекта Apache TinkerPop с открытым исходным кодом ^[46]
• SPARQL : язык запросов для баз данных RDF, который может извлекать и обрабатывать данные, хранящиеся в формате RDF.
• регулярные запросы пути , теоретический язык для запросов к графовым базам данных

• Графическое преобразование
• Иерархическая модель базы данных
• Журнал данных
• Вадалог
• База данных объектов
• База данных RDF
• Структурированное хранилище
• Текстовый график
• Wikidata — родственный проект Wikipedia, который хранит данные в графовой базе данных. Обычный просмотр веб-страниц позволяет просматривать узлы, следовать по ребрам и выполнять запросы SPARQL .