Как моделировать и запрашивать наследование в иерархии строк в таблице базы данных?

Question

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

Древовидная структура

---

  Foo
  /  \
Bar1 Bar2

Таблица базы данных

---

 id | parent_id | name  | attribute 1 | attribute 2
 1  | null      | Foo   | 0.4         | "tastes like chicken"
 2  | 1         | Bar 1 | null        | "doesn't everything"
 3  | 1         | Bar 2 | 0.2         | null

(В производстве я бы использовал дополнительный столбец (столбцы) для хранения древовидной структуры, но для простоты это опущено.)

В этой системе Bar1 наследовал бы значение 0,4 для атрибута 1, а Bar2 наследовал бы значение «на вкус как курица» для атрибута 2.

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

1. Поскольку мне нужно иметь возможность экспортировать из базы данных в исходном формате, я не могу просто предварительно рассчитать и кэшировать «отсутствующие» записи. Или я могу? Обратите внимание, что кэширование было бы несколько разумным, поскольку обновление может изменить значения в Foo, которые должны распространяться на Bar1 и Bar2.

2. Существуют ли стандартные инструменты базы данных или параметры SQL, которые могли бы правильно "строить" записи Bar в одном (или относительно небольшом количестве) запросах? Я знаю об общих табличных выражениях, и кажется, что это на полпути к решению, но это вернет дерево строк, и тогда потребуется дальнейшая обработка для надлежащего заполнения всех атрибутов.

3. Есть ли у них другие советы и рекомендации по работе с этим типом данных и структурой базы данных? Может быть, это глупый вопрос, но у меня нет формального образования в области программирования, поэтому многие концепции для меня совершенно новые.

Обратите внимание, что создание отдельных таблиц для различных ветвей невозможно, так как дерево может иметь произвольную глубину. Предполагаемый размер дерева составляет ~ 3000 дочерних записей, с деревом глубиной 3 уровня и тысячами деревьев для хранения.

Я работаю с Django, если это имеет значение, но полукомфортно работаю с необработанными SQL-запросами (например, я создаю приложение Django для управления направленными ациклическими графами , которое использует в основном необработанный SQL из-за сложный сгруппированный и имеющий пункты).

Answer 1

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

Использование таблицы

create table Tree(
  id serial primary key check(id > 0),
  parent int references Tree(id),
  name varchar(100) not null unique check(length(name)>0),
  attr1 int,
  attr2 varchar(15),
  constraint charlength check(id > parent)
);

заполнено этими данными

insert into Tree (name, parent, attr1, attr2)
          values ('Foo', null, 5, 'high'), -- will have id 1
                 ('Bar1', 1, null, 'low'), -- will have id 2
                 ('Bar2', 1, null, null),
                 ('Bar3', 2, null, null);

запрос

with recursive parents(id, name, attr1, attr2, parent, level, who) as (
  select id, name, attr1, attr2, parent, 1, id
    from Tree t
    where t.name in ('Bar3', 'Bar2')
  union all
  select t.id, p.name, coalesce(p.attr1, t.attr1), coalesce(p.attr2, t.attr2), t.parent, p.level+1, p.who
    from parents p, Tree t
    where t.id = p.parent
  ) select distinct on (who) who, name, attr1, attr2
      from parents
      order by who, level desc;

приводит к (с моей программой ruby, оборачивающей запросы):

{"attr1"=>"5", "name"=>"Bar2", "attr2"=>"high", "who"=>"3"}
{"attr1"=>"5", "name"=>"Bar3", "attr2"=>"low", "who"=>"4"}

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