CSE 132A Lecture Notes - Lecture 9: Embedded Sql

• School: UCSD
• Department: Computer Science and Engineering
• Course: CSE 132A
• Professor: Victor Vianu

Document Summary

Find the pairs of nodes that are connected by some directed path. Find pairs of nodes at distance 1 union. Find pairs of nodes at distance at most k union. Case 2: (select x. a, y. b from g x, tk-1 y. One solution: extend sql with recursion (not part of standard!) Create recursive view t as (select * from g) Ex: friends: drinkers who frequent the same bar. Some systems forbid arithmetic or aggregate functions in selects in recursive definitions. T = g { insert into t. Ex: computing a0 a1 a2 a3 a4 a5 a6 a7 a8. Compare to linear recursion (goes 1 by 1, very slow!) Double recursion goes by faster (it can join 2 jumps in successive iterations) - log2 (diameter) Union (select x. a, y. b from x, t y) Union (select x. a, y. b from t x, y.