Re: Parts explosion with repeated subtrees

It looks to me that it's a badly designed schema to begin with.

(Food_Item -> Item_Type) and food_item is not candidate key.

Technically what you have is a DAG (directed acyclic graph) and not a forest. What it boils down to is the transitive closure. What's about this problem that is different from any other parts explosion problem ?

Transitive closure should have been part of SQL and SQL based products ages ago, and probaby it's not yet, but can be solved relatively painful using Db2 recursive queries, Oracle CONNECT BY operator, or using hand made "materialized view" tables updated via triggers. I don't know what's the problem with "trees". Vendors don't pay attention to the users (they're busy implementing other UFOs like XML, "objects" and object pointers), the SQL committee doesn't pay attention to anyone. I mean recursive queries might be a cool trick in theory but it can't address the basic needs of the user: a safe and simple way to resolve the transitive closure.

Joe, you have to confess that you orchestrated this whole thing, so that you can publish a whole book full of twisted and mind boggling Joe Celko style SQL, solving a problem that in a normal world would be absolutely trivial :)

How about SQL committee specify a TRANSITIVE CLOSURE JOIN, abd vendors implement it correctly, would you still publish a book on trees in SQL ?

best regards,
Costin Cozianu

--CELKO-- wrote:
> Another tree oriented problem.
>
> Imagine that we have a forest of trees called "Menu" which stores the
> menu items for a restaurant. The first level under the root is the
> dishes served. Each dish is then decomposed into its ingredients; the
> ingredient can be either simple (salt, water, milk, flour, etc) or it
> can have a recipe of its own (Béarnaise sauce, Hollandaise sauce,
> etc.)
>
> Let me build a tree of each dish or recipe down to its most basic
> simple ingredients:
>
> CREATE TABLE Menu
> (dish_name VARCHAR (25) NOT NULL,
> food_item VARCHAR (25) NOT NULL,
> item_type CHAR (6) NOT NULL DEFAULT ‘simple'
> CHECK (item_type IN (‘dish', ‘recipe', ‘simple')),
> PRIMARY KEY (dish_name, food_item),
> << constraints >>);
>
> INSERT INTO Menu
> VALUES (‘Eggs Benedict', ‘English Muffin', ‘simple'),
> (‘Eggs Benedict', ‘Canadian Bacon', ‘simple'),
> (‘Eggs Benedict', ‘Egg', ‘simple'),
> (‘Eggs Benedict', ‘Béarnaise sauce', ‘recipe');
>
> INSERT INTO Menu
> VALUES (‘Béarnaise sauce', ‘Dill', ‘simple'),
> (‘Béarnaise sauce', ‘Hollandaise sauce', ‘recipe');
>
> INSERT INTO Menu
> VALUES (‘Hollandaise sauce', ‘Egg‘, ‘simple'),
> (‘Hollandaise sauce', ‘Lemon Juice‘, ‘simple'),
> (‘Hollandaise sauce', ‘Butter‘, ‘simple');
>
> If I put the Menu into a nested set model, I would want to build a
> full tree for each menu item. However, things like ‘Béarnaise sauce'
> and ‘Hollandaise sauce' are going to appear all over the place.
>
> I can recursively expand each ingredient which has a recipe of its own
> until I have a result set of only simple ingredients.
>
> But is there another model or better query which would allow us to
> find all the simple ingredients of a given dish?

Is it not proven that transitive closure is impossible in SQL ? Received on Sat Dec 14 2002 - 16:35:58 CET