1

I read a long time ago about a pattern/technique for easily querying for all "descendants" of a record (no need to use CONNECT TO, which is not standard and not available with JPA).

I remembered the pattern being called "nested sets", but now that I am documenting I went to check that and found that "nested sets" is somewhat similar, but not the same.

Typically, it applies to a single table with a 1-N relationship to himself, v.g a table of Person where each record has a Mother attribute that is a foreign key to person.

ERD

In order to easily find all of the descendants of a given record, the technique worked like this:

  • When a record was inserted, the Path attribute would be calculated and stored.

    • If the record has no "mother", it would be just the record's id followed by a separator (v.g., a dot). So, INSERT INTO PERSON(Id, Name, Mother, Path) VALUES(1, 'Alice' null, '1.').
    • If the record has a "mother" record, it would prefix the path attribut with the mother path. So, PERSON(Id, Name, Mother, Path) VALUES(2, 'Betty', 1, '1.2.'); and PERSON(Id, 'Carol', Mother, Path) VALUES(3, 2, '1.2.3.');

To search, say, all of Carol descendants (including herself), it becomes as simple as SELECT * FROM Person WHERE Path LIKE '1.%'.

Of course, the cost is that Path is not in a normal form (it is an attribute that does not depend only of its id), so extra care is needed when inserting, deleting or updating records.

Anybody knows the name of this technique? As I said above, I thought it was nested sets but Wikipedia says I am wrong.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.