Recursive tree-like query on same table using Slick

[Jacobus]

Hi guys,

I realise this is a difficult-to-do thing, even in plain SQL, but I was hoping the Slick community may have found a reasonable solution to querying a single table with id's and parent id's where parent id's refer to id's in the same table.

I've asked this question on SO also, but have had no luck so far
http://stackoverflow.com/q/15070620/828757

Here's a straight copy and paste of the problem I'm trying to solve:

My table data forms a tree structure where one row can reference a parent row in the same table.

What I am trying to achieve, using Slick, is to write a query that will return a row and all it's children. Also, I would like to do the same, but write a query that will return a child and all it's ancestors.

In other words:

findDown(1) should return

List(Group(1, 0, "1"), Group(3, 1, "3 (Child of 1)"))

findUp(5) should return

List(Group(5, 2, "5 (Child of 2)"), Group(2, 0, "2"))

Here is a fully functional worksheet (except for the missing solutions ;-).

package com.exp.worksheets

import scala.slick.driver.H2Driver.simple._

object ParentChildTreeLookup {

  implicit val session = Database.forURL("jdbc:h2:mem:test1;", driver = "org.h2.Driver").createSession()

  session.withTransaction {
    Groups.ddl.create
  }

  Groups.insertAll(
    Group(1, 0, "1"),
    Group(2, 0, "2"),
    Group(3, 1, "3 (Child of 1)"),
    Group(4, 3, "4 (Child of 3)"),
    Group(5, 2, "5 (Child of 2)"),
    Group(6, 2, "6 (Child of 2)"))

  case class Group(
    id: Long = -1,
    id_parent: Long = -1,
    label: String = "")

  object Groups extends Table[Group]("GROUPS") {
    def id = column[Long]("ID", O.PrimaryKey, O.AutoInc)
    def id_parent = column[Long]("ID_PARENT")
    def label = column[String]("LABEL")
    def * = id ~ id_parent ~ label <> (Group, Group.unapply _)
    def autoInc = id_parent ~ label returning id into {
      case ((_, _), id) => id
    }

    def findDown(groupId: Long)(implicit session: Session) = { ??? }

    def findUp(groupId: Long)(implicit session: Session) = { ??? }
  }

}

A really bad, and static attempt at findDown may be something like:

private def groupsById = for {
  group_id <- Parameters[Long]
  g <- Groups; if g.id === group_id
} yield g

private def childrenByParentId = for {
  parent_id <- Parameters[Long]
  g <- Groups; if g.id_parent === parent_id
} yield g


def findDown(groupId: Long)(implicit session: Session) = { groupsById(groupId).list union childrenByParentId(groupId).list }

But, I'm looking for a way for Slick to recursively search the same table using the id and id_parent link. Any other good ways to solve the problem is really welcome. Keep in mind though, that it would be best to minimise the number of database round-trips.

Kind regards,

Jacobus

[Christopher Vogt]

Relational queries are not suited for tree-like structures. You mentioned in stack overflow post that the depth of your trees will typically be shallow. Why not implement the recursion on the client side, along the lines of your supposedly bad findDown implementation shown here? You may run n queries with n being the depth of your tree, but if your tree is shallow, is that a problem? Otherwise I would agree with the recommendations on stack overflow. Either implement a stored procedure in the DB and hook it into Slick or use some database which has support for tree queries such as H2.

your http://stackoverflow.com/questions/15070620/recursive-tree-like-table-query-with-slick

[Jacobus]

Thank you very much for for the insight and advice Christopher, you nudged me in the right direction - seems that CTE (common table expressions) is what I'm looking for - http://en.wikipedia.org/wiki/Hierarchical_and_recursive_queries_in_SQL

And they are supported both in PostgreSQL (my production database) and H2 (for testing):
http://www.postgresql.org/docs/current/interactive/queries-with.html
http://www.h2database.com/html/advanced.html#recursive_queries

Should I treat these like one would normally write plain SQL using Slick, or are there any gotcha's I should be aware of?

Kind regards,
Jacobus

On Tue, Feb 26, 2013 at 11:19 PM, Christopher Vogt <jan.christ...@gmail.com> wrote:

Relational queries are not suited for tree-like structures. You mentioned in stack overflow post that the depth of your trees will typically be shallow. Why not implement the recursion on the client side, along the lines of your supposedly bad findDown implementation shown here? You may run n queries with n being the depth of your tree, but if your tree is shallow, is that a problem? Otherwise I would agree with the recommendations on stack overflow. Either implement a stored procedure in the DB and hook it into Slick or use some database which has support for tree queries such as H2.

your http://stackoverflow.com/questions/15070620/recursive-tree-like-table-query-with-slick

--
 
---
You received this message because you are subscribed to the Google Groups "Slick / ScalaQuery" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scalaquery+...@googlegroups.com.

For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Christopher Vogt]

Should I treat these like one would normally write plain SQL using Slick, or are there any gotcha's I should be aware of?

I don't see why not. Please share a code snippet, when you get it to work as a reference for future visitors of this post :).

[Matthew Pocock]

Is there any work on using macros to compile scala into stored procedures? I get really fed up of writing these things in a different language for each target DB, and then backing off to client-side logic where this can't be done.

Matthew

On 26 February 2013 21:19, Christopher Vogt <jan.christ...@gmail.com> wrote:

Relational queries are not suited for tree-like structures. You mentioned in stack overflow post that the depth of your trees will typically be shallow. Why not implement the recursion on the client side, along the lines of your supposedly bad findDown implementation shown here? You may run n queries with n being the depth of your tree, but if your tree is shallow, is that a problem? Otherwise I would agree with the recommendations on stack overflow. Either implement a stored procedure in the DB and hook it into Slick or use some database which has support for tree queries such as H2.

your http://stackoverflow.com/questions/15070620/recursive-tree-like-table-query-with-slick

--
 
---
You received this message because you are subscribed to the Google Groups "Slick / ScalaQuery" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scalaquery+...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

--

Dr Matthew Pocock

Integrative Bioinformatics Group, School of Computing Science, Newcastle University

mailto: turingate...@gmail.com

mailto: matthew...@ncl.ac.uk

gchat: turingate...@gmail.com

msn: matthew...@yahoo.co.uk

irc.freenode.net: drdozer

skype: matthew.pocock

tel: (0191) 2566550

mob: +447535664143

[Adam Jorgensen]

Another scheme that can be used to avoid recursive queries is the Nested Set model as described in http://www.pure-performance.com/2009/03/managing-hierarchical-data-in-sql/

This scheme has the advantage of being implementable in pretty much any SQL database and is extremely fast to read, although writing is intensive...

[Christopher Vogt]

> Is there any work on using macros to compile scala into stored procedures? I get really fed up of writing these things in a different language for each target DB, and then backing off to client-side logic where this can't be done.

What are you using the stored procedures for? Which databases do you target?

Chris