SQL all rows in child 'categories' and child child 'categories' : recursive?

Question

I'm having trouble writing a query that solves the following problem, which I believe needs some kind of recursiveness:

I have a table with houses, each of them having a specific house_type, p.e. house, bungalow, etc. The house_types inherit from each other, also declared in a table called house_types.

table: houses
id | house_type
1  | house
2  | bungalow
3  | villa
etcetera...

table: house_types
house_type | parent
house      | null
villa      | house
bungalow   | villa
etcetera...

In this logic, a bungalow is also a villa and a villa is also house. So when I want to get all villas, house 2 and 3 should show up, when I want to get all houses, house 1, 2 and 3 should show up, when I want all bungalows, only house 3 should show up.

Is a recursive query the answer and how should I work this out. I use knex/objection.js in a node.js application.

Answer 1

Here is a recursive CTE that gets every pair in the hierarchy:

with recursive house_types as (
      select 'house' as housetype, null as parent union all
      select 'villa', 'house' union all
      select 'bungalow', 'villa'
     ),
     cte(housetype, alternate) as (
       select housetype, housetype as alternate
       from house_types
       union all
       select ht.housetype, cte.alternate
       from cte join
            house_types ht
            on cte.housetype = ht.parent
      )
select *
from cte;

(The house_types CTE is just to set up the data.)

You can then join this to other data to get any level of the hierarchy.

Answer 2

To start with @gordon-linoffs answer is awesome. I'm just here to add specifics how to do this with knex / objection.js.

That sounds like pretty nasty db design. I would denormalise the type data so that queries would be easier to make without recursive common table expressions (knex doesn't support them currently).

Anyways here is some runnable code how to do objection.js models and type info denormalisation on JavaSript side for being able to make queries that you are trying to do: https://runkit.com/mikaelle/stackoverflow-43554373

Since stackoverflow likes to have code also contained in the answer I'll copy paste it here too. Example uses sqlite3 as DB backend but the same code works also with postgres.

const _ = require('lodash');
require("sqlite3");

const knex = require("knex")({ 
  client: 'sqlite3', 
  connection: ':memory:' 
});

const { Model } = require('objection');

// init schema and test data
await knex.schema.createTable('house_types', table => {
  table.string('house_type');
  table.string('parent').references('house_types.house_type');
});

await knex.schema.createTable('houses', table => {
  table.increments('id');
  table.string('house_type').references('house_types.house_type');
});

await knex('house_types').insert([
  { house_type: 'house', parent: null },
  { house_type: 'villa', parent: 'house' },
  { house_type: 'bungalow', parent: 'villa' }
]);

await knex('houses').insert([
  {id: 1, house_type: 'house' },
  {id: 2, house_type: 'villa' },
  {id: 3, house_type: 'bungalow' }
]);

// show initial data from DB
await knex('houses')
  .join('house_types', 'houses.house_type', 'house_types.house_type');

// create models
class HouseType extends Model {
  static get tableName() { return 'house_types' };

  // http://vincit.github.io/objection.js/#relations
  static get relationMappings() {
    return {
      parent: {
        relation: Model.HasOneRelation,
        modelClass: HouseType,
        join: {
          from: 'house_types.parent',
          to: 'house_types.house_type'
        }
      }
    }
  }
}

class House extends Model {
  static get tableName() { return 'houses' };

  // http://vincit.github.io/objection.js/#relations
  static relationMappings() { 
    return {
      houseType: {
        relation: Model.HasOneRelation,
        modelClass: HouseType,
        join: {
          from: 'houses.house_type',
          to: 'house_types.house_type'
        }
      }
    }
  }
}

// get all houses and all house types with recursive eager loading
// http://vincit.github.io/objection.js/#eager-loading
JSON.stringify(
  await House.query(knex).eager('houseType.parent.^'), null, 2
);

// however code above doesn't really allow you to filter 
// queries nicely and is pretty inefficient so as far as I know recursive
// with query is only way how to do it nicely with pure SQL

// since knex doesn't currently support them we can first denormalize housetype
// hierarchy (and maybe cache this one if data  is not changing much)
const allHouseTypes = await HouseType.query(knex).eager('parent.^');

// initialize house types with empty arrays
const denormalizedTypesByHouseType = _(allHouseTypes)
  .keyBy('house_type')
  .mapValues(() => [])
  .value();

// create denormalized type array for every type 
allHouseTypes.forEach(houseType => {
  // every type should be returned with exact type e.g. bungalow is bungalow
  denormalizedTypesByHouseType[houseType.house_type].push(houseType.house_type);
  let parent = houseType.parent;
  while(parent) {
    // bungalow is also villa so when searched for villa bungalows are returned
    denormalizedTypesByHouseType[parent.house_type].push(houseType.house_type);
    parent = parent.parent;
  }
});

// just to see that denormalization did work as expected
console.log(denormalizedTypesByHouseType);

// all villas
JSON.stringify(
  await House.query(knex).whereIn('house_type', denormalizedTypesByHouseType['villa']),
  null, 2
);