Гарантия уникального назначения суррогатного ключа - максимальное соответствие для двудольного графика

Question

Я поддерживаю хранилище данных с несколькими источниками данных о классе сущностей, которые должны быть объединены. Каждый источник имеет естественный ключ, и что должно произойти, так это то, что один и только один суррогатный ключ создается для каждого естественного ключа на все времена. Если одна запись из одной исходной системы с конкретным естественным ключом представляет ту же сущность, что и другая запись из другой исходной системы с другим естественным ключом, один и тот же суррогатный ключ будет присвоен обоим.

Другими словами, если исходная система A имеет естественный ключ ABC, представляющий ту же сущность, что и естественный ключ DEF исходной системы B, мы назначим один и тот же суррогатный ключ для обоих. Таблица будет выглядеть так:

SURROGATE_KEY   SOURCE_A_NATURAL_KEY    SOURCE_B_NATURAL_KEY
 1               ABC                     DEF

Это был план. Тем не менее, эта система была в производстве в течение некоторого времени, и назначение суррогатного ключа беспорядок. Исходная система A выдаст естественный ключ ABC за один день до того, как исходная система B узнает об этом. DW присвоил ему суррогатный ключ 1. Затем исходная система B начала давать естественный ключ DEF, который представляет собой то же самое, что и естественный ключ исходной системы A ABC. DW неправильно дал этот комбинированный суррогатный ключ 2. Таблица будет выглядеть так:

SURROGATE_KEY   SOURCE_A_NATURAL_KEY    SOURCE_B_NATURAL_KEY
 1               ABC                     NULL
 2               ABC                     DEF

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

Небольшой поиск в Google показывает, что это можно смоделировать как проблему соответствия в двудольном графе:

Википедия - Соответствует

MIT 18.433 Комбинаторная оптимизация - Примечания к лекциям по недвудольному сопоставлению

Мне нужна простая для понимания реализация (не оптимально выполняемая) алгоритма путей, деревьев и цветов Эдмонда. У меня нет формальных знаний по математике или CS, и у меня есть самоучка, и сегодня вечером я не нахожусь в свободном пространстве по математике. Кто-нибудь может помочь? Хорошо написанное объяснение, которое ведет меня к реализации, будет высоко оценено.

EDIT:

Математический подход оптимален, потому что мы хотим максимизировать глобальную пригодность. Жадный подход (сначала возьмите все экземпляры A, затем B, затем C ...) рисует вас в локальный угол максимума.

В любом случае, я заставил бизнес-аналитиков сделать это вручную (все 20 миллионов из них). Я помогаю им с функциями для оценки качества глобального соответствия. Это идеально, так как они все равно подписывают, так что моя задняя сторона покрыта.

Не использование суррогатных ключей не меняет проблему соответствия. Все еще существует естественное отображение ключей 1: 1, которое необходимо обнаружить и поддерживать. Суррогатный ключ является удобным якорем для этого, и ничего более.

Answer 1

У меня сложилось впечатление, что вы идете об этом неправильно; как говорит cdonner, есть и другие способы просто перестроить структуру ключей, не проходя через этот беспорядок. В частности, вы должны гарантировать, что естественные ключи всегда уникальны для данной записи (нарушение этого условия привело вас в этот беспорядок!). Наличие как ABC, так и DEF идентифицирующих одну и ту же запись является катастрофическим, но в конечном итоге подлежащим ремонту. Я даже не уверен, зачем вам вообще нужны суррогатные ключи; хотя у них действительно есть много преимуществ, я бы подумал о том, чтобы перейти к чисто реляционным отношениям и просто удалить их из вашей схемы, в духе Селко; это может просто вытащить тебя из этого беспорядка. Но это решение должно быть принято после просмотра всей схемы.

Чтобы рассмотреть ваше потенциальное решение, я вытащил свою копию DB 100 * * * * Введение в теорию графов , второе издание, в котором описывается алгоритм цветения на стр. 144. Вам понадобятся некоторые математические знания, и с математической нотацией, и с теорией графов, чтобы следовать алгоритму, но достаточно кратко, что я думаю, что это может помочь (если вы решите пойти по этому пути). Если вам нужно объяснение, сначала обратитесь к ресурсу по теории графов (Википедия, ваша локальная библиотека, Google, где угодно) или спросите, не находите ли вы то, что вам нужно.

3.3.17. Алгоритм. (Алгоритм цветения Эдмондса [1965a] --- эскиз).

Ввод. График G, соответствие M в G, M -ненасыщенная вершина u.

Идея. Исследуйте M - чередующиеся пути от u, записывая для каждой вершины вершину, из которой она была достигнута, и сжимаясь, когда обнаруживается. Поддерживайте множества S и T, аналогичные тем, которые установлены в алгоритме 3.2.1, с S, состоящим из u, и вершинами, достигнутыми вдоль насыщенных ребер. Достижение ненасыщенной вершины дает увеличение.

Инициализация. S = {u} и T = {} (пустой набор).

Итерация. Если S не имеет немаркированной вершины, остановитесь; M -умножение пути от u отсутствует. В противном случае выберите неотмеченный v в S. Чтобы исследовать из v, последовательно рассмотрите каждый y в N(v) так, чтобы y не было в T.

Если y ненасыщен m, то проследите от y (при необходимости расширяя цветения), чтобы сообщить о M -умножении (u, y) -path.

Если y находится в S, то цветение найдено. Приостановите исследование v и сожмите цветок, заменив его вершины в S и T одной новой вершиной в S. Продолжите поиск с этой вершины в меньшем графе.

В противном случае y соответствует некоторому w на M. Включите y в T (достигнуто с v) и включите w в S (достигнуто с y).

После изучения всех таких соседей v отметьте v и выполните итерацию.

Алгоритм, описанный здесь, выполняется за время O (n ^ 4), где n - количество вершин. Запад дает ссылки на версии, которые работают так же быстро, как O (n ^ 5/2) или O (n ^ 1/2 м) (m - количество ребер). Если вам нужны эти ссылки или цитаты из оригинальной статьи Эдмондса, просто спросите, и я выкопаю их из индекса (какой тип отстой в этой книге).

Answer 2

Я думаю, что вам было бы лучше, если бы вы установили набор правил и атаковали вашу таблицу сопоставления клавиш набором простых запросов, которые обеспечивают выполнение каждого правила итеративным способом. Может быть, я упрощаю, потому что твой пример прост.

Ниже приведены примеры правил - только вы можете решить, какие из них применяются:

• если есть дубликаты, используйте самый низкий (самый старый) суррогатный ключ
• использовать натуральные ключи из строки с самым высоким (самым последним) суррогатным ключом
• использовать естественные ключи из наиболее полной строки сопоставления
• использовать самые последние вхождения каждого натурального ключа
• ...?

Написание запросов, которые перестраивают ваше сопоставление клавиш, становится тривиальным, как только вы установили правила. Я не уверен, как это может быть математическая задача?

Answer 3

Если вы ищете реализацию, библиотека Eppsteins PADS имеет алгоритм сопоставления, это должно быть достаточно быстро для ваших целей, общий алгоритм сопоставления находится в CardinalityMatching.py. Комментарии в реализации объясняют, что происходит. Библиотека проста в использовании, чтобы предоставить граф на Python, вы можете представить граф, используя словарь G, такой, что G [v] дает список (или набор) соседей вершины v.

Пример:

G = {1: [1], 2:[1,3], 3: [2,4], 4:[3]}

дает линейный график с 4 вершинами.