Trees: Adjacency List

[fixxxer]

Trees: Adjacency List

Сразу скажу, что nested sets для данной задачи не подходит, ибо инсертов будет много - посему adjacency list. Патчить postgresql тоже не хочу - на серверах стоит из rpm binary, и пересобирать везде-везде слишком накладно. Знаю о наличии contrib/ltree, но лексикографические деревья не подходят. Сделал так:

[sql]
create table adjtree(
node_id bigserial primary key,
parent_id bigint default null,
...
);

alter table adjtree add foreign key (parent_id) references adjtree (node_id) on delete cascade;
alter table adjtree add check (parent_id IS NULL or node_id <> parent_id);
[/sql]
...

create or replace function pathto(bigint) returns setof bigint as $$
declare
  num alias for $1;
  parent bigint;
begin
  select into parent parent_id from adjtree where node_id=num;
  while parent is not null loop
    return next parent;
    select into parent parent_id from adjtree where node_id=parent;
  end loop;
  return;
end;
$$ language plpgsql;

create or replace function descedants(bigint) returns setof bigint as $$
declare
  r record;
  r1 record;
begin
  for r in select node_id from adjtree where parent_id=$1 loop
    return next r.node_id;
    for r1 in select * from descedants(r.node_id) loop
      return next r1.descedants;
    end loop;
  end loop;
  return;
end;
$$ language plpgsql;

[sql]
-- Usage:
-- select * from adjtree where node_id in (select * from pathto($1));
-- select * from adjtree where node_id in (select * from descedants($1))
[/sql]

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

 

[neko]

интересно что можно посоветовать человеку который очевидно прочел документацию и знает уже все про DAG

я могу только сказать, что если тебе это доставит удовольствие можешь попробовать переипсать функции на pl/php
заодно и нам расскажешь как оно работает ;-)

 

[fixxxer]

ну не все же на вопросы по register_globals отвечать.
например, мне интересно, как можно было бы обойтись без вложенных циклов в descedants. проблема в том, что return next не умеет возвращать set :/

 

[neko]

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

-~{}~ 27.04.05 14:20:

не чето я глупость ляпнул неподумав