Почему в основных СУБД нет функций графа?

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

Почему же тогда ни одна из основных СУБД (Microsoft, MySql, Oracle, PostgreSQL, SqlLite, и это лишь некоторые из них в алфавитном порядке) не включает поддержку библиотек для обработки отношений как графов?

Некоторые желательные функции, например:

  • Проверка ограничений (связность, ацикличность, планарность, ...)
  • Обычно необходимые функции (кратчайший путь, минимальное остовное дерево, транзитивное замыкание, максимальный расход/минимальный разрез, обнаружение клики, гамильтоновы/эйлеровы циклы...)
  • Вспомогательные структуры данных, необходимые для повышения производительности для любого из вышеперечисленных

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

  • Это по своей сути сложно (здесь помогают библиотеки)
  • Короткие ответы часто подкрепляются большим количеством данных: внешний клиент, использующий алгоритм кратчайшего пути, должен либо быть очень «болтливым» с базой данных, либо должен получить гораздо больший, чем необходимо, объем данных; любой выбор вреден для сети
  • Поддержание целостности, когда целостность зависит от теоретико-графового ограничения, требует доступа ко всем предлагаемым обновлениям, следовательно, к триггеру, а доступ к существующим библиотекам графов из триггеров во многих системах затруднен.
  • Менеджер хранения и оптимизатор СУБД имеют уникальные возможности для решения вопроса о вспомогательных структурах данных, как и в случае с индексами.

Это не риторический вопрос, я действительно хочу знать, есть ли интересные технические (или исторические) причины.


query-optimization history rdbms graph-theory implementation
person Doug McClean    schedule 24.10.2009    source источник

Ответы (3)


arrow_upward
2
arrow_downward

Я работал в исследовательской группе, заинтересованной, среди прочего, в разработке базы данных для RDF(S) данные, которые в основном представляют собой помеченные графы или тройки [subject, predicate, object], которые в основном являются ребрами графа: [sourceNode, edgeLabel, targetNode].

Вопрос, чтобы оценить сложность проблемы: какие индексы вы собираетесь строить для размеченного графа? Вы должны воспользоваться общими «свойствами» (каждый «предикат» является свойством субъекта со значением объекта) и соответствующим образом индексировать ребра, чтобы вы могли быстро найти, «существует ли ребро под названием «hasAge» для человека со значением больше 18 дюймов.

Для иллюстрации, вот простой подход, который не обращает внимания на схемы (и идет совершенно в направлении, противоположном традиционному исследованию баз данных, которое совершенно единогласно соглашается с тем, что иметь схемы хорошо). Он полностью игнорирует любую информацию о схеме (эта статья предоставляет полезный контекст). Просто храните все в трех больших таблицах (s: subject, p: predicate, o: object):

  1. [s, p, o]
  2. [p, o, s]
  3. [o, s, p]

Этих трех достаточно, чтобы ответить на любую эффективную оценку любого запроса с (максимум) субъектом, (максимум) предикатом и (максимум) объектом (т. е. запросы вида (s, *, *), (*, p, *), (*, *, o), (s, p, *), (s, *, o), (*, p, o), (s, p, o)). Сложные запросы, однако, состоят из множества «выражений пути» (т.е. вы описываете данные, для которых можно найти определенные пути, удовлетворяющие некоторым критериям), каждый из которых транслируется в самосоединение на одной из этих (больших!) все это эффективно, что является проблемой.

Вот простая графическая база данных в кармане. :)

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

person Dimitris Andreou    schedule 14.01.2010

arrow_upward
0
arrow_downward

Oracle поддерживает функции графов (Oracle Locator/Oracle Spatial) и семантические веб-функции.

person tuinstoel    schedule 24.10.2009
comment
О, мило. У меня никогда не было возможности поиграть с Oracle 11. Это выглядит хорошо (если ориентироваться на пространство) до сих пор из документов, которые я читаю. (см. oracle.com/technology/products/spatial/pdf/ 10gr2_collateral/ среди прочих) - person Doug McClean; 24.10.2009
comment
Что ж, и PostgreSQL, и mySQL могут записывать геометрию, которая может включать мультиполигоны, представляющие графы. Но ни один из них на самом деле не поддерживает графы и операции над ними — например, ни один из них не может гарантировать, что хранимая геометрия представляет собой связный граф. - person High Performance Mark; 14.01.2010
comment
Да, и эти общие условия связности, планарности, ацикличности и т. д. могут занять много времени для проверки без соответствующих вспомогательных структур данных. Но это правда, что эта функциональность часто реализована в библиотеках, API которых поддерживает только географические запросы. - person Doug McClean; 15.01.2010

arrow_upward
0
arrow_downward

Я подозреваю, что ваш вопрос содержит зачатки собственного ответа.

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

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

person High Performance Mark    schedule 14.01.2010
comment
Не для выставления счетов клиентам? Конечно, если у вас есть рекурсивно определенный продукт и/или схема заказа (на основе частей). Это было бы так же сложно. Но это было бы сделано несколько раз инженерными командами со строгим контролем качества, а не много-много раз всеми нами. Кроме того, размещение его в базе данных может значительно улучшить производительность. Короткие запросы с короткими ответами могут включать в себя огромные объемы данных и, следовательно, пропускную способность, если они выполняются извне. Существует множество графовых алгоритмов, которые извлекают выгоду из вторичных структур данных (аналогично индексам). - person Doug McClean; 15.01.2010
comment
кратчайший путь, минимальное остовное дерево, транзитивное замыкание, максимальный расход/минимальный разрез, обнаружение клики, гамильтоновы/эйлеровы циклы — для выставления счетов клиентам! - person High Performance Mark; 15.01.2010