лекция. Учебник по sql если вы хотите узнать, что такое sql этот сайт для вас
 Скачать 7.88 Mb.
|
|
name John Smith Tom Рекурсивные СТЕ У CTE есть еще одно важное назначение. С его помощью можно написать рекурсивный запрос, т.е. запрос, который, написанный один раз, будет повторяться многократно пока истинно некоторое условие. Рекурсивный CTE имеет следующий вид: 1. WITH <имя> [( <список столбцов> )] 2. AS ( 3. < SELECT ... > -- анкорная часть 4. UNION ALL -- рекурсивная часть 5. < SELECT FROM <имя>… > 6. WHERE <условие продолжения итераций> 7. ) От обычного CTE-запроса рекурсивный отличается только рекурсивной частью, которая вводится предложением UNION ALL. Обратите внимание, что в рекурсивной части присутствует ссылка на имя CTE, т.е. внутри CTE ссылается само на себя. Это, собственно, и есть рекурсия. Естественно, анкорная и рекурсивная части должны иметь одинаковый набор столбцов. В MySQL рекурсивные CTE (как и обычные) появились в версии 8. Их синтаксис фактически отличается от синтаксиса SQL Server только одним словом RECURSIVE: 1. WITH RECURSIVE <имя> [( <список столбцов> )] 2. AS ( ... и так далее Перейдем к примеру. Рассмотрим задачу получения алфавита, т.е. таблицы алфавитных символов - прописных латинских букв. Чтобы было с чем сравнивать, решим сначала эту задачу с помощью генерации числовой последовательности, которая рассматривалась в параграфе 8.1 1. SELECT CHAR ( ASCII ( 'A' ) +5 * ( a -1 ) + b -1 ) AS num 2. FROM ( SELECT 1 a UNION ALL SELECT 2 UNION ALL SELECT 3 3. UNION ALL SELECT 4 UNION ALL SELECT 5 UNION ALL SELECT 6 4. ) x CROSS JOIN 5. ( SELECT 1 b UNION ALL SELECT 2 UNION ALL SELECT 3 6. UNION ALL SELECT 4 UNION ALL SELECT 5 7. ) y 8. WHERE 5 * ( a -1 ) + b <= 26 9. ORDER BY 1 ; А вот решение с помощью рекурсивного CTE 1. WITH Letters AS ( 2. SELECT ASCII ( 'A' ) code, CHAR ( ASCII ( 'A' )) letter 3. UNION ALL 4. SELECT code +1 , CHAR ( code +1 ) FROM Letters 5. WHERE code +1 <= ASCII ( 'Z' ) 6. ) 7. SELECT letter FROM Letters; В запросе анкорной части определяем ASCII-код первой буквы алфавита и соответствующий ему символ. В запросе рекурсивной части мы просто увеличиваем ASCII-код на единицу, обращаясь к CTE в предложении FROM. В результате к строке с первым символом будут последовательно добавляться (UNION ALL) строки со следующими буквами в порядке их ASCII-кодов. Итерации будут продолжаться до тех пор, пока условие code +1 <= ascii('Z') будет истинным, т.е. пока не будет добавлена буква "Z". Оператор 1. SELECT letter FROM Letters собственно и служит для обращения к CTE, запуска рекурсии и вывода результата. Все остальное можно считать определением. Следует заметить, что по умолчанию допускается 100 итераций. Это значит, что если условие прекращения итераций не выполнено ранее, то рекурсия будет остановлена после выполнения 100 итераций. Максимальное число итераций можно изменить с помощью «хинта» 1. OPTION ( MAXRECURSION N ) где N – максимальное число итераций. Значение 0 не ограничивает число итераций. Нужно с осторожностью использовать это значение, т.к. оно чревато зацикливанием. Если запрос не был завершен в пределах указанного числа итераций, возникает ошибка (полученные к этому моменту строки возвращаются): The statement terminated. The maximum recursion N has been exhausted before statement completion. (Выполнение оператора прервано. Достигнут предел максимального числа итераций N до завершения выполнения оператора). В MySQL наша задача будет иметь аналогичное решение: 1. WITH RECURSIVE Letters AS ( 2. SELECT ASCII ( 'A' ) code, CHAR ( ASCII ( 'A' )) letter 3. UNION ALL 4. SELECT code +1 , CHAR ( code +1 ) FROM Letters 5. WHERE code +1 <= ASCII ( 'Z' ) 6. ) 7. SELECT letter FROM Letters; Давайте решим еще одну задачу в качестве ответа на вопрос, который мне неоднократно встречался на просторах Интернет. Преобразовать текст в столбце таблицы таким образом, чтобы каждое слово начиналось с заглавной буквы. Вот пример данных и требуемый результат: name rep delta Delta KSI PSI Ksi Psi alfa beta gamma zeta Alfa Beta Gamma Zeta ALfa and omegA Alfa And Omega За небольшим числом исключений (среди которых можно упомянуть аббревиатуры и инициалы) можно считать, что слову внутри текста предшествует пробел. Это можно использовать в качестве критерия поиска нужных нам элементов текста. Предлагаю реализовать такой достаточно примитивный алгоритм: 1. Первую букву текста делаем прописной, а остальные - строчными. 2. Затем каждую конструкцию "пробел+буква" переводим в верхний регистр. С первым пунктом алгоритма все просто: 1. SELECT name, UPPER ( LEFT ( name, 1 )) + LOWER ( SUBSTRING ( name, 2 , LEN ( name ) - 1 )) rep 2. FROM 3. ( SELECT 'ALfa and omegA' AS name 4. UNION ALL SELECT 'alfa beta gamma zeta' 5. UNION ALL SELECT 'KSI PSI' 6. UNION ALL SELECT 'delta' 7. ) X; name rep ALfa and omegA Alfa and omega alfa beta gamma zeta Alfa beta gamma zeta KSI PSI Ksi psi delta Delta Для реализации второго пункта есть варианты. Поскольку букв латинского алфавита не так много (26), можно просто сделать 26 замен. Я не поленюсь и приведу полный вариант, чтобы вы могли поэкспериментировать с запросом. Итак, 1. SELECT name, REPLACE ( REPLACE ( REPLACE ( REPLACE ( REPLACE ( REPLACE ( 2. REPLACE ( REPLACE ( REPLACE ( REPLACE ( REPLACE ( REPLACE ( 3. REPLACE ( REPLACE ( REPLACE ( REPLACE ( REPLACE ( REPLACE ( 4. REPLACE ( REPLACE ( REPLACE ( REPLACE ( REPLACE ( REPLACE ( 5. REPLACE ( REPLACE ( rep, ' a' , ' A' ) , ' b' , ' B' ) , ' c' , ' C' ) , ' d' , ' D' ) , 6. ' e' , ' E' ) , ' f' , ' F' ) , ' g' , ' G' ) , ' h' , ' H' ) , ' i' , ' I' ) , ' j' , ' J' ) , ' k' , ' K' ) , 7. ' l' , ' L' ) , ' m' , ' M' ) , ' n' , ' N' ) , ' o' , ' O' ) , ' p' , ' P' ) , ' q' , ' Q' ) , ' r' , ' R' ) , 8. ' s' , ' S' ) , ' t' , ' T' ) , ' u' , ' U' ) , ' v' , ' V' ) , 9. ' w' , ' W' ) , ' x' , ' X' ) , ' y' , ' Y' ) , ' z' , ' Z' ) 10. FROM ( 11. SELECT name, UPPER ( LEFT ( name, 1 )) + LOWER ( SUBSTRING ( name, 2 , LEN ( name ) -1 )) rep 12. FROM 13. ( SELECT 'ALfa and omegA' AS name 14. UNION ALL SELECT 'alfa beta gamma zeta' 15. UNION ALL SELECT 'KSI PSI' 16. UNION ALL SELECT 'delta' 17. ) X 18. ) Y; Нетрудно догадаться, что следующий вариант будет использовать рекурсивный CTE. Сначала напишем два простых CTE , которые формируют наш тестовый пример и определяют ASCII-код первой буквы алфавита (A) - не писать же константу. :-) Далее последует анкорная часть, которая выполняет ранее описанную операцию приведения всего текста к нижнему регистру с заглавной первой буквой. Здесь же выполним замену символа с кодом code и предшествующим ему пробелом на... него же. Пусть вас не смущает такая, казалось бы, бесполезная замена. Дело в том, что для регистронезависимых баз данных символы 'a' и 'A' не различаются. Давайте пока на этом остановимся и посмотрим результат. 1. WITH NM ( name ) AS 2. ( SELECT 'ALfa and omegA' AS name 3. UNION ALL SELECT 'alfa beta gamma zeta' 4. UNION ALL SELECT 'KSI PSI' 5. UNION ALL SELECT 'delta' 6. ) , 7. Ascii_code AS ( 8. SELECT ASCII ( 'A' ) AS code 9. ) , 10. Repl ( name, code, rep ) AS 11. ( SELECT name, code, REPLACE ( UPPER ( LEFT ( name, 1 )) + 12. LOWER ( SUBSTRING ( name, 2 , LEN ( name ) - 1 )) , ' ' +CHAR ( code ) , ' ' +CHAR ( code )) rep 13. FROM Ascii_code, NM 14. ) 15. SELECT name, rep FROM Repl; name rep ALfa and omegA Alfa And omega alfa beta gamma zeta Alfa beta gamma zeta KSI PSI Ksi psi delta Delta Добавим, наконец, рекурсивную часть, в которой мы выполним замену буквы с кодом code+1. Рекурсия будет продолжаться до тех пор, пока не будет нарушено условие code < ASCII('Z'), т.е. пока мы не переберем все буквы. Что же мы получим на выходе? К строкам, которые были получены в результате выполнения анкорной части, на каждой итерации будут добавлены (UNION ALL) те же строки с заменой очередной буквы. Отметим большой объем результата при использовании данного метода; в нашем случае это 4х26 = 104 строки. Из этого множества строк нас интересуют только те, которые получены в результате последней итерации, т.е. когда были выполнены все замены. Этой последней итерации соответствует условие code = ASCII('Z'), которое и используется в финальном запросе: 1. WITH NM ( name ) AS 2. ( SELECT 'ALfa and omegA' AS name 3. UNION ALL SELECT 'alfa beta gamma zeta' 4. UNION ALL SELECT 'KSI PSI' 5. UNION ALL SELECT 'delta' 6. ) , 7. Ascii_code AS ( 8. SELECT ASCII ( 'A' ) AS code 9. ) , 10. Repl ( name, code, rep ) AS 11. ( SELECT name, code, REPLACE ( UPPER ( LEFT ( name, 1 )) + 12. LOWER ( SUBSTRING ( name, 2 , LEN ( name ) - 1 )) , ' ' +CHAR ( code ) , ' ' +CHAR ( code )) rep 13. FROM Ascii_code, NM 14. UNION ALL 15. SELECT name, code +1 code, REPLACE ( rep, ' ' + CHAR ( code +1 ) , ' ' + char ( code + 1 )) rep 16. FROM Repl 17. WHERE code < ASCII ( 'Z' ) 18. ) 19. SELECT name, rep FROM Repl WHERE code=ASCII ( 'Z' ) ; Я хотел бы предостеречь вас от чрезмерного увлечения рекурсивными CTE, поскольку они зачастую проигрывают в производительности "традиционным" методам. Я не буду далеко ходить за примерами и сравню два представленных здесь метода. Увеличив количество обрабатываемых строк до 10000, я получил такое время использования CPU: метод на основе REPLACE: 842 ms рекурсивный метод: 6615 ms Безусловно, есть задачи, которые нельзя решить непроцедурно в рамках стандарта SQL-92. В этих случаях использование рекурсивных CTE вполне обоснованно. В остальных случаях я бы рекомендовал выполнять тесты производительности для альтернативных решений. Кстати, в Oracle и PostgreSQL есть встроенная функция INITCAP, которая решает данную задачу: 1. SELECT INITCAP ( name ) 2. FROM 3. ( SELECT 'ALfa and omegA' AS name 4. UNION ALL SELECT 'alfa beta gamma zeta' 5. UNION ALL SELECT 'KSI PSI' 6. UNION ALL SELECT 'delta' 7. ) X; Вы можете использовать консоль , чтобы убедиться в этом. О генерации числовых последовательностей в SQL Server В очередной реализации MS SQL Server 2005 появилась возможность использования рекурсивных CTE конструкций, позволяющих реализовывать циклы для генерации числовых последовательностей и итерационных вычислений. Введение в рекурсии MS SQL Server можно найти в соответствующих руководствах Microsoft, учебнике и Интернете. В данном параграфе мы рассмотрим только новые примеры, помогающие в ее практическом освоении. Самым простым примером использования рекурсивного CTE является генерация ограниченной числовой последовательности натурального ряда: 1,2,3, ... N. 1. WITH Series ( a ) AS 2. ( 3. SELECT 1 4. UNION ALL 5. SELECT a +1 FROM Series WHERE a < 100 6. ) 7. SELECT * FROM Series; Эта конструкция предназначена для генерации последовательности целых чисел (в виде одноколоночной таблицы) от 1 до 100. А. Итерационные вычисления В элементарной и высшей математике есть много интересных последовательностей, обладающих замечательными свойствами. Некоторые последовательности сходятся, и их можно использовать для реализации вычислительных алгоритмов или для вычисления алгебраических и трансцендентных чисел, значений тригонометрических функций, для нахождения корней уравнений, решения систем линейных алгебраических уравнений и пр. Другие последовательности, такие как факториал n!, коэффициенты бинома Ньютона, числа Фибоначчи представляют собой расходящиеся последовательности, которые имеют широкое использование в теории вероятности и математической статистике. Эти последовательности получаются с помощью итераций (рекурсий SQL Server), например: A1, A2, A3, A4 = fun(A1, A2, A3). Здесь A1, A2, A3 - начальные значения для итерационного процесса, fun - функция для вычисления 4-го, пятого и т.д. чисел, которая всегда задействует предыдущие 3 числа. Предположим, что процесс стартует с трех одинаковых чисел A1 = A2 = A3 = 1. Тогда схема реализации с использованием рекурсивных CTE будет иметь следующий вид: 1. WITH TABLE ( iter, A1, A2, A3, A4 ) AS 2. ( 3. SELECT iter = 1 , A1 = 1 , A2 = 1 , A3 = 1 , A4 = fun ( 1 , 1 , 1 ) 4. UNION ALL 5. SELECT iter + 1 , A1 = A2, A2 = A3, A3 = A4, A4=fun ( A2, A3, A4 ) 6. FROM TABLE WHERE iter < 50 7. ) 8. SELECT * FROM TABLE ; Здесь колонка iter введена для вывода номера итерации, колонка [A1] содержит пятьдесят первых членов последовательности, [A2], [A3] и [A4] – вспомогательные колонки для хранения необходимых промежуточных результатов. Обобщением такого подхода является следующий пример. Пусть n >= 1, m >= 1. Тогда последовательные вычисления A[n+1] = fun(A[1], A[2], …, A[n]) A[n+2] = fun(A[2], A[3], …, A[n+1]) … A[n+m] = fun(A[m], A[m+1], …, A[m+n-1]) приводят к генерации m (m >= 1) новых членов последовательности A[n+1],…, A[n+m]. Мы не будем приводить примера использования рекурсии в общем случае, так как это возможно разве что в виде некоторого псевдокода. Читатели могут попытаться построить конкретные примеры самостоятельно. Отметим, что результирующая таблица выглядит следующим образом: A[1] A[2] … A[n] A[n+1] A[2] A[3] … A[n+1] A[n+2] … A[m+1] A[m+2] … A[m+n-1] A[m+n] B. О последовательности чисел Фибоначчи Последовательность Фибоначчи может быть вычислена с помощью следующей итерационной формулы: A[i+2] = A[i] + A[i+1]; i = 1,…, n; A[1] = A[2] = 1. Здесь очень легко увидеть аналогию с общим случаем предыдущего пункта, если ввести функцию f(x,y)=x+y. Для хранения номера итерации i можно использовать колонку [iter], для A[i] используется колонка [a], для A[i+1] и A[i+2] - колонки [b] и [c]. Колонка [d] не потребуется. Используя общий подход, расчет чисел Фибоначчи можно выразить следующим кодом: 1. WITH Fibonacci ( iter,a,b,c ) AS 2. ( 3. SELECT iter= 1 , a= 1 , b= 1 , c= 1+1 4. UNION ALL 5. SELECT iter +1 , a=b, b=c, c=b+c 6. FROM Fibonacci WHERE b < 1000 7. ) 8. SELECT * FROM Fibonacci; Приведем результат запроса для вычисления чисел Фибоначчи, меньших 1000 (они находятся во втором столбце таблицы). iter a b c 1 1 1 2 2 1 2 3 3 2 3 5 4 3 5 8 5 5 8 13 6 8 13 21 7 13 21 34 8 21 34 55 9 34 55 89 10 55 89 144 11 89 144 233 12 144 233 377 13 233 377 610 14 377 610 987 15 610 987 1597 16 987 1597 2584 С. Нахождение корней уравнений Большой раздел математического и функционального анализа посвящен нахождению корней уравнений функции одного и многих переменных. Корнем уравнения g(x) = 0 называется число r (или вектор r), удовлетворяющее условию: g(r) = 0. Общим методом решения таких уравнений является сведение задачи к задаче о неподвижной точке: x=f(x). Смысл такого сведения состоит в нахождении такой функции f, при которой уравнения g (x) = 0 и x = f(x) являются эквивалентными. Кроме того, оператор f должен быть сжимающим. То есть, если значение r1 находится рядом с решением r, то значение r2=f(r1) должно быть еще ближе к решению: abs(r-r2) < A * abs(r-r1), где положительная константа A меньше единицы (A<1) и не зависит от выбора значения r1. Сжимающих отображений может быть много. Предпочтительными являются те из них, для которых константа A принимает меньшее значение. Чем меньше константа, тем быстрее сходится процесс нахождения корня уравнения g(x): r2 = f(r1), r3 = f(r2), r4 = f(r3) … Приведем иллюстрирующий пример на SQL. D. Итерационное вычисление квадратного корня Квадратный корень из числа a – это решение уравнения x*x = a. В терминах предыдущего пункта это корень уравнения g(x) = 0, где функция g(x) = x*x - a. Вычисление этих чисел SQL-запросом труда не представляет - есть встроенная функция sqrt(a) или power(a,0.5). Тем не менее, проиллюстрируем на примере нахождения квадратного корня подход, который может использоваться в случаях, когда нет соответствующей встроенной функции, а сжимающее отображение известно. Итерационный аналитический алгоритм для вычисления квадратного корня известен из курса школьной математики, и изложен, например, здесь Его можно записать в виде сжимающего отображения x = f(x), где f(x)=1/2*(x+a/x). Легко убедиться в том, что уравнение x = 1/2*(x + a/x) эквивалентно уравнению x*x = a для x <> 0. Читатель с математическим образованием может попытаться доказать, что это преобразование действительно сжимающее, и, следовательно, может быть использовано для итерационного процесса нахождения корня уравнения. Для иллюстрации алгоритма приведем пример sql-кода для вычисления квадратного корня из числа a = 3: 1. WITH Square3 ( a,b,c ) AS 2. ( 3. SELECT 1 , CAST ( 3 AS float ( 53 )) , CAST ( 3 AS float ( 53 )) 4. UNION ALL 5. SELECT a +1 , 1 ./ 2 .* ( b +3 /b ) , 1 ./ 6 .* 3 * ( c +3 ./c ) FROM Square3 WHERE a < 7 6. ) 7. SELECT iteration=a, Exact=sqrt ( CAST ( 3 AS float ( 53 ))) , Res1=b, Res2=c 8. FROM Square3; Здесь столбец [a] введен для вывода номера итерации, столбцы [b] и [c] вычисляют квадратный корень двумя арифметически эквивалентными способами. Итерации не используют встроенные операции sqrt или power, но для контроля мы вывели в колонке exact значение квадратного корня, вычисленное с помощью встроенной функции. |