The Forum for Discussion about The Third Manifesto and Related Matters

You need to log in to create posts and topics.

Generalized transitive closure explanations?

12
Quote from johnwcowan on October 8, 2019, 7:51 pm

Other than what's in VSS 6, is there any informal explanation of generalized transitive closure with clear examples?  All I can find is incomprehensibly formal papers, which may help if you already have an informal understanding — but I don't.

Thanks.

Have you seen http://shark.armchair.mb.ca/~erwin/relalgintro_0105.html#GTCLOSE ?

Quote from AntC on October 9, 2019, 3:30 am
Quote from dandl on October 8, 2019, 11:24 pm

...

IMO what is presented as GTC is not very generalised and in point of fact not all that useful.

Indeed. If we're thinking outside of TTM, I'm of the school of: let's use the right tool for the job. Expressing not-very-GTC in a D  " is like a dog's walking on his hind legs. It is not done well; but you are surprised to find it done at all." [Dr Johnson]

If you have a tool like Google's map-reduce and/or lambda expressions and/or maps and folds, use the database engine to give you a stream of raw tuples from the database, do the rest natively in some Higher-Order language. For full functionality, you'll probably need the credit card transform aka Tying the knot.

I've a strong suspicion such a technique was anticipated in Hall, Hitchcock, Todd 1975 -- but probably they kept it sotto voce for fear of scaring the horses.

No, really, on the one hand that's almost always overkill, and on the other it doesn't always fit the problem.

If you have made the decision to store your network/tree/graph data structure in relational form, you're going to need TC, GTC or while to extract useful data, long before the thing gets big enough to justify the effort of connecting to outside tools. You need some form of TC to expand the tuples to generate all the possible paths. Only if the numbers gets large enough is it worth invoking an external map reduce to handle the aggregation side.

There are also heaps of interesting problems for which a recursive solution is a good fit, and for which map reduce is not. Map-reduce is a big hammer, but not every problem is a nail.

Andl - A New Database Language - andl.org
12