Hierarchy (BOM) using closure table with triggers in DAL?

[BigBaaadBob]

Has anyone implemented a closure table with triggers approach to hierarchy (specifically for a Bill of Materials (BOM) pattern) in Web2Py's DAL?

I've seen Massimo's implementation of Preorder Traversal which doesn't work for BOM patterns where there are multiple roots. The Adjacency Table method is slow for large trees.

In a Bill of Materials situation, there are multiple roots in the main table, like this:

db.define_table('item',

    Field('name', type='string', length=128, label=T('Name')))

db.define_table('bill_of_materials',

    Field('parent_item_id', type='reference item', notnull=True, label=T('Parent Item')),

    Field('child_item_id', type='reference item', notnull=True, label=T('Child Item')),

    Field('quantity', type='decimal(8,2)', default='1.0', label=T('Quantity')))

[BigBaaadBob]

I went ahead and coded something up, inspired by Massimo's Preorder Traversal example. I wouldn't be offended if people suggest how to make it better/faster, perhaps by combining stuff in the Link function into one query instead of many.

# Demonstrate closure tables. Deletion of nodes is left as an exercise to the reader.

# See: http://dirtsimple.org/2010/11/simplest-way-to-do-tree-based-queries.html 

from gluon import DAL, Field

db=DAL('sqlite://closure.db') 

db.define_table(

    'thing',

    db.Field('name')

)

db.thing.truncate()

db.define_table(

    'closure',

    db.Field('parent', type='reference thing'),

    db.Field('child', type='reference thing'),

    db.Field('depth', type='integer')

)

db.closure.truncate()

def link(parent_id,child_id):

    """ link(1,3) """

    p = db.closure.with_alias('p')

    c = db.closure.with_alias('c')

    rows = db((p.child==parent_id) & (c.parent==child_id)).select(

            p.parent.with_alias('parent'),

            c.child.with_alias('child'),

            (p.depth+c.depth+1).with_alias('depth'))

    for row in rows:

        db.closure.insert(parent=row.parent, child=row.child, depth=row.depth)

    

def add_node(name,parent_name): 

    """ add_node('Fruit','Food') """

    child_id=db.thing.insert(name=name)

    db.closure.insert(parent=child_id, child=child_id, depth=0)

    if parent_name is not None:

        parent_id=db(db.thing.name==parent_name).select().first().id

        link(parent_id, child_id)

    

def ancestors(name): 

    """ print ancestors('Red')""" 

    node=db(db.thing.name==name).select().first()

    return db((db.closure.child==node.id) & (db.closure.parent != node.id)).select(

        db.thing.name, left=db.thing.on(db.thing.id==db.closure.parent), orderby=db.closure.depth)

def descendants(name): 

    """ print descendants('Fruit')""" 

    node=db(db.thing.name==name).select().first()

    return db((db.closure.parent==node.id) & (db.closure.child != node.id)).select(

        db.thing.name, left=db.thing.on(db.thing.id==db.closure.child), orderby=db.closure.depth)

def closure():

    """ print closure() """

    parent = db.thing.with_alias('parent')

    child = db.thing.with_alias('child')

    return db().select(db.closure.id, parent.name, child.name, db.closure.depth,

                       left=(parent.on(parent.id == db.closure.parent),

                             child.on(child.id == db.closure.child)))

def test(): 

    add_node('Food',None) 

    db.commit()

    print closure()

    add_node('Vehicle',None) 

    db.commit()

    print closure()

    add_node('Fruit','Food') 

    db.commit()

    print closure()

    add_node('Meat','Food') 

    db.commit()

    print closure()

    add_node('Red','Fruit') 

    db.commit()

    print closure()

    add_node('Chevy','Vehicle') 

    db.commit()

    print closure()

    print "descendants of 'Food'"

    print descendants('Food') 

    print "ancestors of 'Red'"

    print ancestors('Red')

test() 

[Val K]

Why do you have to use this crutches (despite they are genius)? Now, even Sqlite3 supports 'with recursive' queries.

And what do you mean under BOM  and large tree? If we are talking about BOM of  real (physical) object like a car or even an aircraft carrier, I think  it is not large tree

 only if you don't want to have BOAOM (bill of atoms of materials) 

[BigBaaadBob]

I'm just trying to find a good solid way of doing the BOM pattern using the DAL, and pretty much all of the decent articles I've found say the Closure Table method is the best trade-off, especially for large-ish and deep-ish BOM structures. 

But, I'm not dogmatic. How would you code up a version using "with recursive" queries using the DAL? If you post a running example it would be great at informing the group!

[Dave S]

On Wednesday, November 21, 2018 at 10:33:13 AM UTC-8, BigBaaadBob wrote:

I'm just trying to find a good solid way of doing the BOM pattern using the DAL, and pretty much all of the decent articles I've found say the Closure Table method is the best trade-off, especially for large-ish and deep-ish BOM structures. 

It would be interesting to hear your use case.  Are you into a scheduling problem like the airport/flight example?  Or an organizational example where you need to quickly find the director in the hierarchy above one us grunts?

But, I'm not dogmatic. How would you code up a version using "with recursive" queries using the DAL? If you post a running example it would be great at informing the group!

On Wednesday, November 21, 2018 at 9:56:48 AM UTC-8, Val K wrote:

Why do you have to use this crutches (despite they are genius)? Now, even Sqlite3 supports 'with recursive' queries.

And what do you mean under BOM  and large tree? If we are talking about BOM of  real (physical) object like a car or even an aircraft carrier, I think  it is not large tree

 only if you don't want to have BOAOM (bill of atoms of materials) 

My BOM experience is more with circuit boards, and there would probably a dozen part numbers for resistors and and a dozen part numbers for capacitors, and more than a dozen ICs.  But there could be a dozen or a hundred boards using part X, and if you need to figure out which boards are affected when the manufacturer stops manuffing the part, it starts getting interesting.  If you also make boxes the boards go into, then the hierarchy gains another level (although not many entries at that level).

 

Interesting reading.

/dps
 

[BigBaaadBob]

The use case is manufacturing. Large complicated manufacturing with special requirements. And SAP need not apply... :-)

[Val K]

running example: 

# fake table in which result of recursive select will be temporary stored
# id-values will be inherited from parent_child table

db.define_table('entry_collector',

        Field('child', 'integer'),

        Field('xpath', 'json'), # array of ids,  xpath[0] == root, xpath[-1] == child

        Field('root', 'integer'),

        Field('xdepth', 'integer'),

        migrate_enabled = False,

        fake_migrate = True

    )

def with_recursive(parent, child, roots_select, q, *fields, **select_kwargs):

    """

    parent, child  - fields obj ( like  db.parent_child.parent, db.parent_child.child )

    roots_select - sql string (like 'select 123 as id' or db(db.person.id.belongs([11,22,33])._select(db.person.id))

    q, fields, select_kwargs  - args that will pass to dal: db(q).select(*fields, **select_kwargs)

    select_kwargs may include 'entry_collector' - name of fake table for recursive (default is 'entry_collector')
    returns a regular rows dal object (nothing new)

    """

    entry_collector = select_kwargs.pop('entry_collector', 'entry_collector')

    args = Storage(

        entry = parent.table._tablename,

        parent = parent.name,

        child  = child.name,

        entry_collector = entry_collector,

        roots = roots_select

    )

    rec_sql_s = \

    """

        WITH RECURSIVE

        %(entry_collector)s(id, child, xpath, root, xdepth) AS

            (SELECT NULL, id, "[" || id || "]", id, 0 FROM (%(roots)s)

             UNION

             SELECT  %(entry)s.id,

                     %(entry)s.%(child)s,

                     rtrim(xpath,"]") || "," || %(entry)s.%(child)s || "]",

                     %(entry_collector)s.root,

                     %(entry_collector)s.xdepth + 1

                 FROM %(entry_collector)s

                 JOIN %(entry)s ON

                     NOT instr(%(entry_collector)s.xpath,  %(entry)s.%(parent)s || "," )

                     AND %(entry)s.%(parent)s = %(entry_collector)s.child

                 ORDER BY 5 DESC /* means BY xdepth  */

            )

    """ % args

    q = db(q)

    dal_select = q._db._adapter._select_aux

    def patch_select(*args, **kwargs):

        if args:

            is_recursive = False

            for fld in args[1]:

                if  fld.table._tablename == entry_collector:

                    is_recursive = True

                    break

            if is_recursive:

                args = list(args)

                args[0] = rec_sql_s + args[0]

                print 'with rec: ', args[0]

        return dal_select(*args, **kwargs)

    q._db._adapter._select_aux = patch_select

    try:

        ret = q.select(*(fields + (db[entry_collector].id,)),  **select_kwargs)

    finally:

        q._db._adapter._select_aux = dal_select

       return ret

[Ben Duncan]

What database are you using ?

In our e-file system, we have something similar with  court cases, but we use db functions to do the heavy lifting

for use, since in postgres they can be called with a select directly ...

Ben Duncan

DBA / Chief Software Architect

Mississippi State Supreme Court

Electronic Filing Division

--
Resources:
- http://web2py.com
- http://web2py.com/book (Documentation)
- http://github.com/web2py/web2py (Source code)
- https://code.google.com/p/web2py/issues/list (Report Issues)
---
You received this message because you are subscribed to the Google Groups "web2py-users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to web2py+un...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Val K]

It is sqlite3 example and it also uses db function...

I do not quite understand what confuses you