A mincut algorithm finds the minimal number of edges to cut in a cycled graph so it becomes without cycles.
http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem i.e. applying such algorithm over the graph of table dependencies (foregnkey), one gets some minimal number of foreign keys to make use_alter=True. there might be many solutions. or in the mapper/relation graph, find which relations to make post_update=True so although obj-relaltions are cycling, the mapper/relations have no cycles. is it more clear now? > a circular relationship between two mappers means that a dependency > sort revealed that the mapper-level dependency graph contains > cycles. that portion of the sort is then thrown away and replaced > with a dependency sort where the nodes are individual object > instances. > > so sort #1 is mappers as nodes and edges are relations. sort #2 is > object instances and the relationships between them. > > also the rest of your questions are impossible for me to answer > since i do not know what a "mincut" is, and a wikipedia search > indicated its some kind of network optimization theory. i dont > really see how optimization can apply to a dependency graph of > database tables. > > one thing to note is, if i were rewriting the entire flush system > from scratch, i would probably do it based on tables and rows > directly instead of mappers and instances. > > On Feb 2, 9:45 am, svilen <[EMAIL PROTECTED]> wrote: > > i am asking this, because so far i am considering both > > table/foregn-key graph and mapper/relation graph same, thus > > applying the mincut for the table/foregnkey (which sets > > fkey.use_alter=True) also to the other (which sets respective > > relation.post_update=True). > > > > And in 99% of cases, this works. > > Exceptions become some 3 level concrete-inheritances. i know > > concrete inheriting of relations is broken (not inherited at > > all), but it does work if u re-add the relation again, with > > proper tables, foregn_keys, remote_side etc inside. > > > > Which sort-of makes the relation a different relation - the base > > one can have some characteristics different from the inheriting > > one (e.g. post_update, lazy etc). > > > > And now cutting the graph-edges as of the foreignkey on the > > inheriting mapper does not work because the obj-dependency graph > > does not make difference between a concrete mapper and > > non-concrete mapper, and is always assuming the link to be > > through the base mapper, and the relation there is not a > > post_update (in the example). > > > > or something of sorts. > > > > So the question really is: should i mincut the relation-graph > > with post_update's in a different way than the > > foregnkeys/use_alters of the underlying tables, or is this > > something to fix in the dependency-graph building for concrete > > inheritances. > > > > there is one example in ticket 452. > > > > bye > > svil > > > > > hallo. > > > > > > AFAI understand from the source, in the graph used for topology > > > sorting in session.flush(), the nodes are representing the > > > objects' mappers. (and not the tables as in > > > metadata.create_all() ). > > > > > > Also, mappers which inherit from others, are replaced by their > > > bases/roots. > > > > > > Edges in the graph are the relations between the mappers, and > > > post_update=True is considered as cut (i.e. is not an edge). > > > And then, the graph of relations is checked for cycles. > > > > > > So if i want to run an automatical mincut algo, it should be > > > over a graph, having root mappers as nodes and all relations as > > > edges. > > > > > > i am right? > > > > > > ciao > > > svil > > > > > > btw, in topological.py: QueueDependencySorter.sort(), > > > the _find_cycles() call is duplicated. > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "sqlalchemy" group. To post to this group, send email to sqlalchemy@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sqlalchemy?hl=en -~----------~----~----~----~------~----~------~--~---
