CTE in kdb recursive query

Community Support
1

Following is the CTE example in sql server. I have to do similar recursion in KDB. Is KDB support recursive queries or something close to it? Currently i can think of creating functions and hold the temporary data of each recursion into something…

USE AdventureWorks2012;GOWITH DirectReports(ManagerID, EmployeeID, Title, EmployeeLevel) AS ( SELECT ManagerID, EmployeeID, Title, 0 AS EmployeeLevel FROM dbo.MyEmployees WHERE ManagerID IS NULL UNION ALL SELECT e.ManagerID, e.EmployeeID, e.Title, EmployeeLevel + 1 FROM dbo.MyEmployees AS e INNER JOIN DirectReports AS d ON e.ManagerID = d.EmployeeID )SELECT ManagerID, EmployeeID, Title, EmployeeLevel FROM DirectReportsORDER BY ManagerID;GO



Following is the CTE example in sql server. I have to do similar recursion in KDB. Is KDB support recursive queries or something close to it. Currently i can think of creating functions and hold the temporary data of each recursion into something...



    USE AdventureWorks2012;GOWITH DirectReports(ManagerID, EmployeeID, Title, EmployeeLevel) AS ( SELECT ManagerID, EmployeeID, Title, 0 AS EmployeeLevel FROM dbo.MyEmployees WHERE ManagerID IS NULL UNION ALL SELECT e.ManagerID, e.EmployeeID, e.Title, EmployeeLevel + 1 FROM dbo.MyEmployees AS e INNER JOIN DirectReports AS d ON e.ManagerID = d.EmployeeID )SELECT ManagerID, EmployeeID, Title, EmployeeLevel FROM DirectReportsORDER BY ManagerID;GO
2

See scan/over on code.kx.com

3

Hi Manish,

I am not sure if scan and over can solve the CTE problem.

4

I’m not familiar at all with CTE, but sounded like the right ballpark because you asked about recursion.. over/scan will use progressive results as the parameter(s) for the function. A simple example is sum/sums:

q)(+/) 1 2 3

6

q)(+) 1 2 3

1 3 6

(replace + with your own function that will take a table as a parameter and perform some operation on it)

5

Perhaps you can narrow down your question to a specific topic in kdb+. As Manish said over/scan can be used to get progressive results. And .z.s can be used to build recursive functions.<o:p></o:p>

<o:p> </o:p>

As a side note from your sql query I don’t see any case where recursion is needed. Care to clarify?<o:p></o:p>

<o:p> </o:p>

Kim<o:p></o:p>

<o:p> </o:p>

Von: personal-kdbplus@googlegroups.com [mailto:personal-kdbplus@googlegroups.com] Im Auftrag von Manish Patel
Gesendet: Donnerstag, 27. Februar 2014 13:54
An: personal-kdbplus@googlegroups.com
Betreff: Re: [personal kdb+] CTE in kdb recursive query<o:p></o:p>

<o:p> </o:p>

I’m not familiar at all with CTE, but sounded like the right ballpark because you asked about recursion.. over/scan will use progressive results as the parameter(s) for the function. A simple example is sum/sums:<o:p></o:p>

<o:p> </o:p>

q)(+/) 1 2 3<o:p></o:p>

6<o:p></o:p>

q)(+) 1 2 3<o:p></o:p>

1 3 6<o:p></o:p>

<o:p> </o:p>

(replace + with your own function that will take a table as a parameter and perform some operation on it)<o:p></o:p>

<o:p> </o:p>

<o:p> </o:p>

<o:p> </o:p>

<o:p> </o:p>

On Thu, Feb 27, 2014 at 12:23 PM, Vikas Agarwal <vikasa.agarwal@gmail.com> wrote:<o:p></o:p>

Hi Manish,<o:p></o:p>

<o:p> </o:p>

I am not sure if scan and over can solve the CTE problem.

6

Thanks for the reply.
I understand over/scan used to get progressive results and somehow in CTE also I need progressive result. But I am not able to map it with the way CTE works. I will try to figure out something

e.g of CTE is

http://technet.microsoft.com/en-us/library/ms186243(v=sql.105).aspx

7

Hey Vikas,

I looked into the link you posted there and came out with something like such:

/ Build example tables

t:flip"isssii"$EmployeeIDFirstNameLastNameTitleDeptIDManagerID!()

t insert (1; Ken; Sanchez; $“Chief Executive Officer”;16;0N)

t insert (273; Brian; Welcker; $“Vice President of Sales”;3;1)

t insert (274; Stephen; Jiang; $“North American Sales Manager”;3;273)

t insert (275; Michael; Blythe; $“Sales Representative”;3;274)

t insert (276; Linda; Mitchell; $“Sales Representative”;3;274)

t insert (285; Syed; Abbas; $“Pacific Sales Manager”;3;273)

t insert (286; Lynn; Tsoflias; $“Sales Representative”;3;285)

t insert (16; &nbsp;David;Bradley; $“Marketing Manager”; 4; 273)

t insert (23; &nbsp;Mary; Gibson; $“Marketing Specialist”; 4; 16)

/ group EmployeeID in correct order

r:{exec EmployeeID from t where ManagerID in x}[0N]

/ index r to get Level

update Level:{where x in’r}@'ManagerID from t

EmployeeID FirstName LastName Title DeptID ManagerID Level

---------------------------------------------------------------------------------

1 Ken Sanchez Chief Executive Officer 16 0

273 Brian Welcker Vice President of Sales 3 1 1

274 Stephen Jiang North American Sales Manager 3 273 2

275 Michael Blythe Sales Representative 3 274 3

276 Linda Mitchell Sales Representative 3 274 3

285 Syed Abbas Pacific Sales Manager 3 273 2

286 Lynn Tsoflias Sales Representative 3 285 3

16 David Bradley Marketing Manager 4 273 2

23 Mary Gibson Marketing Specialist 4 16 3

Hope this will give you some guidance…

8

these things are much easier in kdb+


you could also use foreign keys for some convenience

(which are just replacing values with pointers to values)


q)t:Employee xcol delete ManagerID from update Manager:t$ManagerID from t:1!t


q)t

Employee| FirstName LastName Title DeptID Manager

--------| --------------------------------------------------------------

1 | Ken Sanchez Chief Executive Officer 16

273 | Brian Welcker Vice President of Sales 3 1

274 | Stephen Jiang North American Sales Manager 3 273

275 | Michael Blythe Sales Representative 3 274

276 | Linda Mitchell Sales Representative 3 274

285 | Syed Abbas Pacific Sales Manager 3 273

286 | Lynn Tsoflias Sales Representative 3 285

16 | David Bradley Marketing Manager 4 273

23 | Mary Gibson Marketing Specialist 4 16


this makes queries rather convenient:

what is the first name and department of my Manager?s Manager?

q)select Manager.Manager.FirstName,Manager.Manager.DeptID from t

FirstName DeptID
----------------


Ken 16
Brian 3
Brian 3
Ken 16
Brian 3
Ken 16
Brian 3


who report to the CEO directly?

q)select from t where Manager.Title like “Chief Executive Officer”
Employee| FirstName LastName Title DeptID Manager
--------| ---------------------------------------------------------
273 | Brian Welcker Vice President of Sales 3 1



To get department Level you could chase the Manager up

q)update chain:(Manager scan)each Manager from t
Employee| FirstName LastName Title DeptID Manager chain
--------| -------------------------------------------------------------------------------
1 | Ken Sanchez Chief Executive Officer 16 t$,0Ni<br>273 | Brian Welcker Vice President of Sales 3 1 t$1 0Ni
274 | Stephen Jiang North American Sales Manager 3 273 t$273 1 0Ni<br>275 | Michael Blythe Sales Representative 3 274 t$274 273 1 0Ni
276 | Linda Mitchell Sales Representative 3 274 t$274 273 1 0Ni<br>285 | Syed Abbas Pacific Sales Manager 3 273 t$273 1 0Ni
286 | Lynn Tsoflias Sales Representative 3 285 t$285 273 1 0Ni<br>16 | David Bradley Marketing Manager 4 273 t$273 1 0Ni
23 | Mary Gibson Marketing Specialist 4 16 `t$16 273 1 0Ni

to get the Level you just count the chaing

q)update Level: -1+count each(Manager scan)each Manager  from t

Employee| FirstName LastName Title DeptID Manager Level
--------| --------------------------------------------------------------------
1 | Ken Sanchez Chief Executive Officer 16 0
273 | Brian Welcker Vice President of Sales 3 1 1
274 | Stephen Jiang North American Sales Manager 3 273 2
275 | Michael Blythe Sales Representative 3 274 3
276 | Linda Mitchell Sales Representative 3 274 3
285 | Syed Abbas Pacific Sales Manager 3 273 2
286 | Lynn Tsoflias Sales Representative 3 285 3
16 | David Bradley Marketing Manager 4 273 2
23 | Mary Gibson Marketing Specialist 4 16 3


Or you could do the scan for everyone at the same time (which is usually faster)

This will keep iterating until there is a layer in the hierarchy

(i.e. every chain has four items, padded with null)

q)update chain:flip Manager scan Manager  from t

Employee| FirstName LastName Title DeptID Manager chain

--------| -------------------------------------------------------------------------
1 | Ken Sanchez Chief Executive Officer 16
273 | Brian Welcker Vice President of Sales 3 1 1
274 | Stephen Jiang North American Sales Manager 3 273 273 1
275 | Michael Blythe Sales Representative 3 274 274 273 1
276 | Linda Mitchell Sales Representative 3 274 274 273 1
285 | Syed Abbas Pacific Sales Manager 3 273 273 1
286 | Lynn Tsoflias Sales Representative 3 285 285 273 1
16 | David Bradley Marketing Manager 4 273 273 1
23 | Mary Gibson Marketing Specialist 4 16 16 273 1

so consequently you get the level a bit differently

q)update Level:sum not null Manager scan Manager  from t

Employee| FirstName LastName Title DeptID Manager Level
--------| --------------------------------------------------------------------
1 | Ken Sanchez Chief Executive Officer 16 0
273 | Brian Welcker Vice President of Sales 3 1 1
274 | Stephen Jiang North American Sales Manager 3 273 2
275 | Michael Blythe Sales Representative 3 274 3
276 | Linda Mitchell Sales Representative 3 274 3
285 | Syed Abbas Pacific Sales Manager 3 273 2
286 | Lynn Tsoflias Sales Representative 3 285 3
16 | David Bradley Marketing Manager 4 273 2
23 | Mary Gibson Marketing Specialist 4 16 3

You should read Stevan Apter’s excellent article on what else is possible with pointer chasing:

http://archive.vector.org.uk/art10500340


Cheers,

Attila

9

Thanks Atilla and WooiKent, that is really helpful.