Почему основные СУБД не имеют графической функциональности? - PullRequest
1 голос
/ 24 октября 2009

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

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

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

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

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

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

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

Ответы [ 3 ]

2 голосов
/ 14 января 2010

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

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

Для иллюстрации приведем простой подход, который не учитывает схемы (и идет совершенно в противоположном направлении традиционного исследования баз данных, в котором совершенно единодушно соглашается, что схемы хороши ). Он полностью игнорирует любую информацию схемы ( этот документ предоставляет полезный контекст). Просто храните все в трех больших таблицах (s: subject, p: предикат, 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 и другие, которые требуют очень хороших результатов.

0 голосов
/ 14 января 2010

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

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

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

0 голосов
/ 24 октября 2009

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

...