Parent left and right in partner_category

Asked by Quentin THEURET @Amaris

How is computed the parent left and the parent right of a partner category ?

Question information

Language:
English Edit question
Status:
Solved
For:
Odoo Server (MOVED TO GITHUB) Edit question
Assignee:
No assignee Edit question
Solved by:
Raphael Collet (OpenERP)
Solved:
Last query:
Last reply:
Revision history for this message
Numérigraphe (numerigraphe) said :
#1

They are special fields that the server computes when the parent changes.
Lionel Sausin.

Revision history for this message
Best Raphael Collet (OpenERP) (rco-openerp) said :
#2

Yes, parent_left and parent_right are special fields that are related to the parent_id field. The purpose of those fields is to make queries within the hierarchy execute efficiently: with parent_left and parent_right, you can retrieve all the descendants of a node without making recursive queries.

Consider two nodes A and B in the hierarchy. A and B can be partner categories, for instance. Their integer fields parent_left and parent_right are such that:

        B is a descendant of A in the hierarchy (defined by parent_id)

if and only if

        A.parent_left < B.parent_left, B.parent_right and B.parent_left, B.parent_right < A.parent_right

So, imagine that you have six partner categories like below. You can assign parent_left and parent_right by traversing the tree. The result is show in parentheses next to each node. Note that the values there are optimal; in practice, you can leave gaps in the numbers.
 - Customers (1, 10)
     - Consumers (2, 3)
     - Partners (4, 9)
        - Basic Partners (5, 6)
        - Gold Partners (7, 8)
 - Suppliers (11, 12)

You can retrieve all the subcategories of Customers with a single SQL query. Note that the values 1 and 10 are the parent_left and parent_right of Customers; they can be retrieved as part of the query itself.

        SELECT id FROM partner_category
        WHERE parent_left > 1 AND parent_left < 10

The last remark is that parent_left and parent_right can be updated without traversing the whole hierarchy. Removing a node does not require any change. For adding a node, you can adapt the parent_left and parent_right with two UPDATE queries: one to "make some space" between the parent_left and parent_right of the node's ascendants, and one to shift the parent_left and parent_right of all the nodes "at the right" of the new position. So parent_left and parent_right can be maintained efficiently.

I hope this helps understanding how they work.

Cheers,
Raphael

Revision history for this message
Quentin THEURET @Amaris (qtheuret) said :
#3

Thanks Raphael Collet (OpenERP), that solved my question.

Revision history for this message
Quentin THEURET @Amaris (qtheuret) said :
#4

Le 07/02/2012 11:05, Raphael Collet (OpenERP) a écrit :
> Your question #186704 on OpenERP Server changed:
> https://answers.launchpad.net/openobject-server/+question/186704
>
> Raphael Collet (OpenERP) proposed the following answer:
> Yes, parent_left and parent_right are special fields that are related to
> the parent_id field. The purpose of those fields is to make queries
> within the hierarchy execute efficiently: with parent_left and
> parent_right, you can retrieve all the descendants of a node without
> making recursive queries.
>
> Consider two nodes A and B in the hierarchy. A and B can be partner
> categories, for instance. Their integer fields parent_left and
> parent_right are such that:
>
> B is a descendant of A in the hierarchy (defined by parent_id)
>
> if and only if
>
> A.parent_left < B.parent_left, B.parent_right and
> B.parent_left, B.parent_right < A.parent_right
>
> So, imagine that you have six partner categories like below. You can assign parent_left and parent_right by traversing the tree. The result is show in parentheses next to each node. Note that the values there are optimal; in practice, you can leave gaps in the numbers.
> - Customers (1, 10)
> - Consumers (2, 3)
> - Partners (4, 9)
> - Basic Partners (5, 6)
> - Gold Partners (7, 8)
> - Suppliers (11, 12)
>
> You can retrieve all the subcategories of Customers with a single SQL
> query. Note that the values 1 and 10 are the parent_left and
> parent_right of Customers; they can be retrieved as part of the query
> itself.
>
> SELECT id FROM partner_category
> WHERE parent_left > 1 AND parent_left < 10
>
> The last remark is that parent_left and parent_right can be updated
> without traversing the whole hierarchy. Removing a node does not
> require any change. For adding a node, you can adapt the parent_left
> and parent_right with two UPDATE queries: one to "make some space"
> between the parent_left and parent_right of the node's ascendants, and
> one to shift the parent_left and parent_right of all the nodes "at the
> right" of the new position. So parent_left and parent_right can be
> maintained efficiently.
>
> I hope this helps understanding how they work.
>
> Cheers,
> Raphael
>
Hello Raphael,

Thanks for your great explanations ! I now understand the concept of the
parent_left and parent_right.

Thanks a lot !

Cheers,

--
Quentin THEURET

Revision history for this message
abbes (bafbes) said :
#5

Hi Raphael,

There exist a simpler a simpler explanation :

The siblings children of each parent are contained into exclusive intervals, in which parent_left is the lower bound and parent_right is the upper bound where the lower bound of the leftmost child is lower then the parent's lower bound and the upper bound of the rightmost child is lower than the parent's upper bound. So that we only need to choose a big difference between parent_left and parent_right for elements that we expect to have many children.

In the given example, the sibling intervals for Customers share the interval (1,10) into (2, 3) and (4, 9) and no room is left to create other siblings.

I hope this explanation is clearer.
Cheers,

Revision history for this message
abbes (bafbes) said :
#6

We can also consider the formula :
Maximum number of children = parent_right - parent_left+1

Revision history for this message
abbes (bafbes) said :
#7

I could find a detailed description of this concept : https://en.wikipedia.org/wiki/Nested_set_model