WikiDer > База данных графиков

Эта статья поднимает множество проблем. Пожалуйста помоги Улучши это или обсудите эти вопросы на страница обсуждения. (Узнайте, как и когда удалить эти сообщения-шаблоны) Эта статья возможно содержит оригинальные исследования. Пожалуйста Улучши это к проверка заявленные претензии и добавление встроенные цитаты. Заявления, содержащие только оригинальные исследования, следует удалить. (Август 2016 г.) (Узнайте, как и когда удалить этот шаблон сообщения) Эта статья слишком полагается на Рекомендации к основные источники. Пожалуйста, улучшите это, добавив вторичные или третичные источники. (Август 2016 г.) (Узнайте, как и когда удалить этот шаблон сообщения) Эта статья нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален. Найдите источники: «База данных графиков» – Новости · газеты · книги · ученый · JSTOR (Август 2016 г.) (Узнайте, как и когда удалить этот шаблон сообщения) (Узнайте, как и когда удалить этот шаблон сообщения)

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

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

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

Для получения данных из базы данных графов требуется язык запросов Кроме как SQL, который был разработан для манипулирования данными в реляционной системе и поэтому не может "элегантно" обрабатывать обход графа.^{[мнение]} По состоянию на 2017 год^{[Обновить]}, ни один универсальный язык запросов на основе графов не был принят так же, как SQL был принят для реляционных баз данных, и существует большое количество систем, чаще всего тесно связанных с одним продуктом. Были предприняты некоторые усилия по стандартизации, что привело к появлению языков запросов от разных поставщиков, таких как Гремлин, SPARQL, и Сайфер. Помимо интерфейсов на языке запросов, доступ к некоторым базам данных графов осуществляется через интерфейсы прикладного программирования (API).

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

История

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

Графические структуры могли быть представлены в базах данных сетевых моделей с конца 1960-х годов. КОДАСИЛ, который определил КОБОЛ в 1959 году определил язык сетевых баз данных в 1969 году.

Помеченные графики могут быть представлены в графических базах данных середины 1980-х годов, таких как логическая модель данных.^[3][8]

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

В середине-конце 2000-х годов коммерческие базы данных графов с КИСЛОТА такие гарантии, как Neo4j и Oracle Spatial и Graph стал доступен.

В 2010-х годах коммерческие базы данных графов ACID, которые могли быть масштабируется по горизонтали стал доступен. Дальше, SAP HANA привел в памяти и столбчатый технологии графических баз данных.^[9] Также в 2010-е гг. многомодельные базы данных поддерживающие модели графов (и другие модели, такие как реляционная база данных или документно-ориентированная база данных) стали доступны, например OrientDB, ArangoDB, и MarkLogic (начиная с его версии 7.0). За это время особенно популярны графовые базы данных различных типов. анализ социальных сетей с появлением компаний в социальных сетях.

Фон

Базы данных графов используют узлы, свойства и ребра.

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

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

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

Графические модели

График помеченных свойств

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

Структура описания ресурсов (RDF)

Пример RDF-графа

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

Он используется в Facebookпротокол Open Graph, «позволяющий любой веб-странице иметь те же функции, что и любой другой объект на Facebook»^[14] и Семантическая сеть.

Характеристики

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

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

Место хранения

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

Безиндексная смежность

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

Типы графиков

Есть несколько типов графиков, которые можно разделить на категории. Gartner предлагает пять широких категорий графиков:^[15]

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

Сравнение с реляционными базами данных

С Эдгар Ф. Кодддокумент 1970 г. реляционная модель,^[16] реляционные базы данных де-факто были отраслевым стандартом для крупномасштабных систем хранения данных. Однако реляционные модели требуют строгой схемы и нормализация данных наложенные ограничения на то, как можно запрашивать отношения.

Традиционно базы данных разрабатывались с использованием реляционной модели, в которой данные нормализуются для поддержки ACID транзакции. В процессе нормализации данных удаляются все повторяющиеся данные в базе данных. Цель нормализации данных - сохранить согласованность данных. Реляционная модель обеспечивает выполнение транзакций ACID, разделяя данные на множество таблиц.

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

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

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

Примеры

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

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

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

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

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

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

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

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

ВЫБРАТЬ p2.person_name ИЗ люди p1 ПРИСОЕДИНИТЬСЯ друг НА (p1.person_id = друг.person_id)ПРИСОЕДИНИТЬСЯ люди p2 НА (p2.person_id = друг.friend_id)КУДА p1.person_name = 'Джек';

Тот же запрос может быть переведен на -

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

  МАТЧ(p1:человек)-[:ДРУГ-С]-(p2:человек)КУДАp1.имя="Джек"ВОЗВРАЩАТЬСЯp2.имя

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

    ПРЕФИКС пена: <http://xmlns.com/foaf/0.1/>ВЫБРАТЬ ?имяКУДА { ? s а          пена:Человек .         ? s пена:имя  "Джек" .         ? s пена:знает ? o .         ? o пена:имя  ?имя .       }

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

    ПРЕФИКС пена: <http://xmlns.com/foaf/0.1/>ВЫБРАТЬ ?имяКУДА { ? s пена:имя     "Джек" ;           пена:знает    ? o .           ? o пена:имя  ?имя .      }

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

  ВЫБРАТЬ люди.имяИЗ (       SPARQL ПРЕФИКС пена: <http://xmlns.com/foaf/0.1/>              ВЫБРАТЬ ?имя              КУДА { ? s пена:имя  "Джек" ;                          пена:знает ? o .                      ? o пена:имя  ?имя .                    }    ) В КАЧЕСТВЕ люди ;

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

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

Список баз данных графов

Ниже приводится список примечательный Графические базы данных:

Языки программирования графовых запросов

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

Смотрите также

• Преобразование графа
• Иерархическая модель базы данных
• База данных объектов
• База данных RDF
• Структурированное хранилище
• Текстовый график

Рекомендации