视频：Basic recursive WITH statement - introduction (12min); demo (30min); Nonlinear and mutual recursion (21min) (1.5x speed)

视频笔记：

Basic SQL Recursion

SQL is not a "Turing complete" language

Simple, convenient, declarative

Expressive enough for most database queries

But basic SQL can't Express unbounded computations

Example 1: Ancestors

ParentOf (parent, child)

Find Mary's ancestors

Example 2: Company hierarchy

Find total salary cost of project 'X'

Example 3. Airline flights

Find cheapest way to fly from A to B

SQL WITH Statement

With R1 As (query-1)

        R2 As (query-2),

        ...

        Rn As (query-n)

<query involving R1, ...Rn (and other tables)>

SQL With Recursive Statement

With Recursive

        R1 As (query-1)

        R2 As (query-2),

        ...

        Rn As (query-n)

<query involving R1, ...Rn (and other tables)>

SQL With Recursive Statement

With Recursive

        R As (base query 

                 Union

        recursive query)

<query involving R (and other tables)>

Union eliminate dupilicates

Linear Recursion (one reference to R)

Nonlinear 

pros: query looks cleaner, converges faster

cons: harder to implement

SQL standard only requires linear

Murual recursion(refer to other relations)

Example: Hubs & Authorities

Link (src,dest)

HubStart (node) AuthStart (node)

Extends expresiveness of SQL

Basic funcitionality: linear recursion

Extended functionality: nonlinear recursion, mutual recursion

Disallowed: recursive subqueries (negative), aggregation