Работа с n-арными деревьями на PL/SQL

Представьте себе почти классическую ситуацию: есть какие-то данные в БД (одна, две и более таблиц), и надо эти данные обработать хитрым образом, а затем сохранить результат в отдельную таблицу для последующего представления данных пользователю.

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

Допустим, что в процессе обработки данных, нам необходимо построить дерево.

На Delphi структуру узла дерева можно описать так:

type
  PNode = ^TNode;
  TNode = record
    Parent: PNode;            // ссылка на родительский узел
    Childs: array of PNode;   // ссылки на дочерние узлы
    // данные в ноде
    Data: Integer;
    // ...
  end;

Процедура создания узла дерева в этом случае может быть такой:

function CreateNode(Parent: PNode; Data: Integer): PNode;
begin
  New(Result);
  Result^.Parent := Parent;
  Result^.Data := Data;
end;

Ну и процедура перебора всех дочерних узлов:

procedure IterateChilds(Parent: PNode);
var
  i: Integer;
  Child: PNode;
begin
  for i := Low(Parent^.Childs) to High(Parent^.Childs) do
  begin
    Child := Parent^.Childs[i];
    // работаем с дочерним узлом:
    Child^.Data := 1;
    // перебираем дочерние рекурсивно:
    IterateChilds(Child);
  end;
end;

Думаю, приведённого кода достаточно, чтобы понять, о чём идёт речь.

 

Теперь попробуем сделать что-то подобное на стороне сервера.

Интерпретируемый язык PL/SQL, используемый в СУБД Oracle, очень мощное средство в умелых руках. Однако он имеет ряд неприятных ограничений. Например в PL/SQL нет указателей, а потому и нельзя ссылаться на типы данных, которые ещё не объявлены (или объявлены по коду ниже). Поэтому, если написать так:

  type t_childs is table of t_node index by pls_integer;
  type t_node is record (
    --parent  pointer?
    childs  t_childs,
    data    integer
  ); 

то получим ошибку при компиляции. Да и не понятно, как сослаться на родительскую ноду?

Столкнувшись с такой проблемой, я уж было хотел решить поставленную задачу с использованием объектов. Но объект в Oracle – это тип SQL, а логику обработки данных надо реализовывать в PL/SQL, а отсюда есть некоторые неприятные моменты. Например, не все типы данных PL/SQL можно использовать в SQL. Да и работа с объектами  происходит медленнее, чем с PL/SQL массивами (коллекциями).

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

Таким образом, структуру данных на PL/SQL можно описать так:

  type t_childs is table of pls_integer index by pls_integer;
  type t_node is record (
    self_idx        pls_integer,    -- индекс из таблицы g_nodes, указывает на себя
    parent_idx      pls_integer,    -- индекс из таблицы g_nodes, указывает на родительский узел
    pchild_idx      pls_integer,    -- индекс из таблицы child_idxs родительского узла
    child_idxs      t_childs,       -- набор индексов из таблицы g_nodes, указывающих на дочерние узлы
    -- полезные данные:
    some_data       pls_integer,
    -- ..
  ); 
  type t_nodes is table of t_node index by pls_integer;
  g_nodes     t_nodes;        -- хранилище узлов дерева
  g_nodes_seq pls_integer;    -- счётчик узлов
  p_root_node pls_integer;    -- указатель на корневой узел

Здесь стоит обратить внимание на:

• g_nodes – это коллекция узлов, объявленная как index by pls_integer, это означает, что g_nodes отдельно инициализировать не нужно.


• g_nodes_seq – это счётчик узлов, сохранённых в g_nodes, по большому счёту можно обойтись и без него, но он нужен для удобства.


• p_root_node – индекс, по которому будет хранится корень дерева.

Теперь для построения дерева, нам понадобятся следующие функции:

function get_next_seq return pls_integer is
begin
  g_nodes_seq := nvl(g_pc_nodes_seq, 0) + 1;
  return g_nodes_seq;
end;

function create_node(parent_idx_ in pls_integer, pchild_idx_ in pls_integer, data_ in pls_integer) return pls_integer
is
  p_node  pls_integer;
begin
  p_node := get_next_seq;
  
  g_nodes(p_node).self_idx := p_node; 
  g_nodes(p_node).parent_idx := parent_idx_;
  g_nodes(p_node).pchild_idx := pchild_idx_;
  if pchild_idx_ is not null then
    --if g_nodes(parent_idx_).child_idxs.exists(pchild_idx_) then
    --  raise...
    --end if;  
    g_nodes(parent_idx_).child_idx(pchild_idx_) := p_node;
  end if;
  g_nodes(p_node).data := data_;
           
  return p_node;
end;

function create_root(data_ in pls_integer) return pls_integer is
begin
  p_root_node := create_node(null, null, data_);
  return p_root_node;
end;

Думаю, тут всё понятно: дерево начинаем строить с корня (create_root), затем создаём узлы (create_node).

Итерация дерева делается так:

procedure iterate_tree(p_node in pls_integer)
is
  i       pls_integer;
  p_child pls_integer;
begin
  -- goto first child             
  i := g_nodes(p_node).child_idxs.first;
  while i is not null
  loop
    p_child := g_nodes(p_node).child_idxs(i);
    -- do something
    g_nodes(p_child).data := 1;
    -- iterate childs
    iterate_tree(p_child);
    -- goto next child
    i := g_nodes(p_node).child_idxs.next(i);
  end loop;  
end;

Ну, в общем, примерно так. Немного громоздко получилось, но работает и работает достаточно быстро.

Если навигация “вверх” от узла не требуется, то можно упростить описание структуры t_node.