7

Задача не практическая. Хочется оценить, какими подходами ее можно решить на SQL'ях разных диалектов (PostgreSQL, SQLite3, MySQL). И как сложно это решаемо.

Задача

Есть таблица с положительными числами [0..N]. Нужно вывести в порядке возрастания все числа из указанной таблицы, которые входят в последовательность Фибоначчи.

2 ответа 2

5

Генератор без использования таблиц для SQLite, postgresql:

WITH Recursive Q(Num,Prev) as(
   select 1,1
  union all
   select Q.Num+Q.Prev,Q.Num
     from Q
    where Q.Num<10000
)
select Num from Q

Если надо выбрать из них только те числа, что есть в некой таблице - то в итоговый select добавить join с этой таблицей для проверки наличия числа в ней.

Для MS SQL и Oracle - убрать из запроса выше фразу Recursive. Для Oracle дополнительно добавить from DUAL после select 1,1.

Для MySQL требуется опорная таблица с нужным количеством записей, содержимое этих записей значения не имеет:

select @tmp:=@Prev+@Num as Num, @Prev:=@Num, @Num:=@tmp
  from seqnum, (select @Prev:=1, @Num:=1) A
 order by Num

Это опять же генератор. Для проверки наличия в некой таблице - заключить в подзапрос и сделать join.

2
  • И еще раз сенкс! Вопрос пока "принимаю" без проверки, ибо праздник начался ))) Ну а потом обязательно поразбираюсь. Тема рекурсии для меня неведома, больше всего манит посмотреть EXPLAIN этого хозяйства. Всех благ в новом году!)))
    – Majestio
    31 дек 2016 в 12:40
  • 1
    Пару слов в защиту MySQL. В MySQL8/MariaDB10.2 тоже будет WITH RECURSIVE. Для 8-ки уже можно пощупать. Тут - sqlinfo.ru/articles/info/27.html - перевод одной из статей на эту тему как раз с примером поиска чисел Фибоначи. С наступающим!
    – retvizan
    31 дек 2016 в 18:11
1

Отвечаю сам себе :) пока для PostgreSQL:

Решается в несколько этапов:

1) Поиск максимального значения в таблице

2) CROSS JOIN всей таблицы с результатом выборки от хранимой процедуры по соответствию

CREATE OR REPLACE FUNCTION fib(f INTEGER) 
RETURNS SETOF INTEGER
LANGUAGE SQL
AS $$
WITH RECURSIVE t(a,b) AS (
        VALUES(0,1)
    UNION ALL
        SELECT greatest(a,b), a + b AS a FROM t
        WHERE b < $1
   )
SELECT a FROM t;
$$;

где аргументом будет максимальное значение из таблицы

Для SQLite3 и MySQL ждем-c ... ) Хотя, чего греха таить, возможно и для PostgreSQL без хранимой процедуры.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.