SQL query to find final overridden id in adjacency list / closure table

Question

I have an adjacency list table called attribute (which also has a closure table called attribute_closure mapped for ease of recursion).

Each entry in the attribute table is one of 4 hierarchical types, with each type able to inherit and override it's parent type's entries. The four possible types are, by hierarchy, category, product_line, product, model. So category has a tree of attributes defined, which product_line inherits and can at any point override, and so on for product and model.

This is pre-existing structure for a pre-existing application, so any suggestions to restructure are unusable :-)

So, the adjacency list attribute, has the following columns: id, parent_id, overrides_id, with overrides_id (if set) being a reference to attribute.id, same for parent_id. If overrides_id is set, parent_id will always match the value of the overridden attribute's parent_id.

For each hierarchical type, there is a supporting table mapping the type to the attribute, i.e. - category_id, attribute_id.

I need to be able to get back a full attribute tree, with all overrides respected.

Example data (this specific example only goes to product level, but you get the idea). Please flesh out further with your own sample data as needed.

attribute

+-------+-----------+--------------+
|   id  | parent_id | overrides_id |
+-------+-----------+--------------+
|  6036 |      5931 |         NULL |
|  6069 |      5931 |         6036 |
| 30955 |      5931 |         6069 |
+-------+-----------+--------------+

category_attribute

+-------------+--------------+
| category_id | attribute_id |
+-------------+--------------+
|           2 |         6036 |
+-------------+--------------+

product_line_attribute

+-----------------+--------------+
| product_line_id | attribute_id |
+-----------------+--------------+
|              16 |         6069 |
+-----------------+--------------+

product_attribute

+------------+--------------+
| product_id | attribute_id |
+------------+--------------+
|         69 |        30955 |
+------------+--------------+

Querying a tree that contains the above attributes, should result in only attribute id 30955 being returned, as the other 2 attributes shown should be made obsolete by 30955.

As mentioned, I also have a typical closure table, which maps out ancestor, descendant, level. Extra brownie points if you can include a result that uses the closure to return a tree with overrides having taken affect. :-)

Answer 1

Solution I ended up going with, was to build a second closure table which represented the hierarchy of the overrides (so similar to building a closure based on parent_id, but instead using overrides_id). This allows me to then query to find the entire hierarchy of overrides for any given attribute.

I had hoped to find a query-to-end-them-all, but going with a second closure table was simpler, better on performance, etc.