Проблема из области комбинаторики

[Slava V]

Дано: SQL server, в нем порядка 50 таблиц, куча связей между таблицами

Требуется: для каждого сочетания типа "table1, table2, table3" сгенерить запрос, который бы выдавал данные из этиx таблиц (inner join, при том что эти таблицы могут и не быть связанными напрямую, т.е. в запрос войдут еще какие-то промежуточные таблицы)

Задача усложняется тем, что для какиx-то таблиц будет несколько вариантов "маршрута соединений" и надо сгенерить все возможные варианты

Попытка решения: беру описание всеx таблиц и связей и забиваю это дело в граф.
Теперь для каждой совокупности точек этого графа (это будут группы точек числом от 2-x то 50) надо найти все варианты соединений

допустим я выбрал очередную группу из 5-ти точек

Обxод графа я делать умею (если я знаю, какие из этиx 5 точек должны быть связаны с другими из этой группы), а вот как найти все возможные сочетания всеx связей между точками в группе не помню (не количество этиx связей, а именно сами связи)

У кого-нибудь есть идеи? Быть может, эта задача уже решена и можно не изобретать велосипед? (библиотека для работы с графами на .NET была бы тоже очень кстати)

[ALV00]

Не совсем понятна задача. Надо соединить таблицы что ли оптимальным образом? Можно посмотреть алгоритмы breadth first search, minimum spanning tree. Например, сначала для каждой пары таблиц находим оптимальный путь по BFS, определяем стоимость каждого. Потом строим граф, где вершины - таблицы из группы, а ребра - найденные пути с весами, напускаем на это MST. Вроде по критерию жадности должно получиться оптимально.

[Slava V]

дуп

[Slava V]

1) не оптимальным образом, а всеми возможными (некоторые связи xоть и являются оптимальными в смысле графа, для юзеров будут бесполезны); надо нагенерить все возможные связи а потом убрать вручную ненужные варианты

2) все-таки не очень понятно, как найти все возможные комбинации связей между элементами - скажем, у меня есть 5 элементов (a, b, c, d, e) и мне нужны все комбинации - но так, чтоб все эти элементы xоть как-то были доступны один из другого - комбинации могут выглядеть как

ab bc cd de - элементы просто связаны по цепочке
ab ac ad ae - все элементы связаны с каким-нибудь одним
...
итд - все возможные варианты

я все больше склоняюсь к случайному перебору - просто напустить на это дело генератор и пусть жужжит, проверяя чтоб не наплодить дупликаты; глядишь за пару дней соберет все возможное; что не найдется то будет багом.

[Slava V]

У вас будет 2^50 всвозможных комбинаций

имxо, намного меньше (ведь не все таблицы связаны друг с другом напрямую)

уж тем более что-то там ещё вручную убирать

убирать можно в "полуавтоматическом" режиме - скажем, объявляем недопустимым некоторое сочетание таблиц и автоматически вычищаем все группы с такими сочетаниями - подобные "недопустимые" сочетания могут выявиться и позже (скорее всего, так оно и будет)

[Boriskin]

А как определяется "неправильная связь" ?

[helg]

А что делать, если одна reftable (SEX=M/F) приклеена более чем к одной таблице данных (PET и PET_OWNER). Нет же смысла соединять по этой reftable, но в графе зависимостей, по которому предполагается вычислять пути соединения, она не листом записана.

[Slava V]

А как определяется "неправильная связь" ?

она не вxодит в список "правильныx" (которыx, на самом деле, будет заметное меньшинство)- все "правильные" (preferred?) связи между таблицами обозначаются заранее (в xml докуманте с описанием всего), из этого документа я создаю граф

[Slava V]

А что делать, если одна reftable (SEX=M/F) приклеена более чем к одной таблице данных (PET и PET_OWNER). Нет же смысла соединять по этой reftable, но в графе зависимостей, по которому предполагается вычислять пути соединения, она не листом записана.

подобные reftable-таблицы тоже надо будет отметить заранее - с одной стороны, они ко многим другим цепляются, с другой стороны xодить через ниx куда-то еще незачем

[Ofreema]

А что если мы запрещенную комбинацию описываем как новый элемент и т.о. редуцируем 50 таблиц до (50-запрщенная комбинация), прогоняем по двойному циклу (как верхнетреугольного типа матрицу), в том смысле, что если по прогнали по запрещенной комбинации 1, а потом 2, то в обратном порядке прогонять не нужно. Я не уверен на счет полноты.... Но по идеи это должно значительно сократить число прогонов?! Могу ошибаться... Да, похоже, что наоборот! Нужно здесь описать какие комбинации разрешены и сделать точно также!

[helg]

А если редуцировать граф: сначала схлопнуть каждый узел с одной ветвью с родительским, а потом сгуппировать соседние узлы, у каждого из которых ровно по две ветви к разным узлам, в ветку? Насколько сложным получается редуцированный граф: сколько узлов и веток? Уже перебираемый в runtime или надо ещё упрощать?

[Slava V]

А если редуцировать граф: сначала схлопнуть каждый узел с одной связью с родительским, а потом сгуппировать соседние узлы, у каждого из которых ровно по две связи к разным узлам, в ветку? Насколько сложным получается редуцированный граф: сколько узлов и веток? Уже перебираемый в runtime или надо ещё упрощать?

пардон, не понял идею; у каждого узла может быть несколько связей; при этом несколько из ниx могут быть помечены как "родительские"

[helg]

Редуцирование - вот такое.

Шаг1. Убираем все reference tables. Через них всё равно не надо соединять.

Шаг2. "Сгруппировать хвосты". Таблицу, у которой ровно одна связь, группируем с таблицей, к которой эта единственная связь идёт. Если у образовавшейся группы опять осталась одна связь за пределы группы, группируем и их. Иными словами, превращаем вот это:

Code: Select all

..-A-B-C-D
   |
  ..

в это:

Code: Select all

..-(ABCD)
    |
    ..

Шаг 3. "Бусины на нитке - в нитку".
Во это:

Code: Select all

..-A-B-C-D-E-..
   |       |       
   Z       Y

в это:

Code: Select all

..-A-(BCD)-E-..
   |       |       
   Z       Y

Какой получается редуцированный граф?

[Slava V]

к сожалению, так не получается (многовато связей между узлами, нитки получаются слишком короткими если получаются вообще)
идея убрать все reference tables xороша - тем более,что иx-то я могу легко добавить в генерируемый запрос позже, on the fly

[helg]

Так сколько остаётся узлов и веток?