Рекурсия в sqlite3

Question

Имеется таблица (id, parent_id). Допустимо наличие нескольких предков. Нужно написать на си/с++ с помощью sqlite функцию find(i,k), которая найдет ID всех предков i-го элемента таких, что до них можно дойти от i-го элемента проходя k раз по ссылке на предка.

Вопрос в следующем: можно ли sql таблицу преобразовать в двумерный массив? Тогда было бы все просто. Если нельзя, то как быть?

в смысле? таблица сама по себе и есть двумерный массив. ты не с той стороны вопрос задаешь. спроси себя - что тебе дает интерфейс бд и как ты можешь по нему пройтись циклом (курсоры и т.д.) погугли iterate over sqlite c++/python/php и/или как в этом же цикле уложить в вектор c++ данные из sqlite — strangeqargo, May 14 '16 at 23:44
Просто открываете документацию и читаете как делаются hierarhical query штатными средствами SQLite. — Alex Krass, May 14 '16 at 23:47
Мне бы примеры конкретных функций sqlite. В интернете ничего не могу найти подходящего.
Или костыль какой-нибудь... — Алексей, May 15 '16 at 09:22

edem · Accepted Answer · 2016-05-15T01:18:59.290

2

Тестовая таблица с данными:

create table test (
    id integer,
    parent_id integer,
    name text
);

insert into test values
    (1, null, 'Адам'),
    (2, 1, 'Каин'),
    (3, 1, 'Авель'),
    (4, 2, 'Енох'),
    (5, 4, 'Ирад'),
    (6, 5, 'Мехиаель'),
    (7, 6, 'Мафусал'),
    (8, 7, 'Ламех');

Рекурсивный запрос, который выдаст предков (path) для данного id с заданной глубиной k (depth) может быть таким:

with recursive m(depth, path, id, name) as (
    select 1, id path, id, name from test where parent_id is null
    union all
    select depth + 1, path || ',' || t.id, t.id, t.name 
    from test t, m where t.parent_id = m.id
) select * from m
where depth = 2 and id = 3;

Выдаст:

2|1,3|3|Авель

edited May 15 '16 at 01:18

answered May 15 '16 at 00:52

edem

5,970

Ваш запрос не компилируется. Выводит ошибки.
И зачем нам поле Name? Оно же не нужно. Выводиться на экран должны только (предок) предки, к которому(-ым) мы дойдем за k переходов.
– Алексей May 15 '16 at 07:35
и, исходя из вашей таблицы, запрос должен ничего не выводить, так как за 2 хода он не найдет потомка (1 ход - это переход по ссылке 3 - 1, а так как у 1 нет родителей, то дальнейших переходов не случится. – Алексей May 15 '16 at 07:42
@Алексей какие ошибки? Поле name дли примера (не нужно - удалите). Выводиться на экран должно лишь то, что задумано в вопросе. Вы же спрашивали про "как быть?" и "Мне бы примеры конкретных функций sqlite.", вот для этих целей и написан данный ответ. – edem May 15 '16 at 15:16
ругается на два вертикальных слеша. Я правильно понял, что ваш запрос выводит через запятую всех потомков, которых встречает при переходах по ссылке? – Алексей May 15 '16 at 15:32
Да, только предков, а не потомков. || - это конкатенация строк просто. – edem May 15 '16 at 16:05
А как сделать так, чтобы он выводил не всех, которых встречает, пока делает k переходов, а только тех, которых встретит на k-том переходе? – Алексей May 15 '16 at 17:01

create table test ( id integer, parent_id integer, );

insert into test values
      (1, null),
      (2, 1),
      (3, 1),
      (4, 2),
      (5, 7),
      (1, 5),
      (7, 6),
      (8, 7);
with recursive m(depth, path, id) as (
    select 1, id path, id, name from test where parent_id is null
    union all
    select depth + 1, path id, t.id 
    from test t, m where t.parent_id = m.id
) select * from m
where depth = 4 and id = 3;

– Алексей May 15 '16 at 17:17

в общем, код ломается при depth > 2. Как мне кажется, это из-за того, что depth + 1 всегда равен двум, он не работает, как depth = depth + 1 – Алексей May 15 '16 at 17:22

Рекурсия в sqlite3

1 Answers1