как обнаружить все возможные способы объединения двух таблиц для получения значительных результатов.

Question

Учитывая две таблицы (только данные), я хочу узнать все возможные способы объединения двух таблиц для получения значительных результатов. Каждый путь соответствует отображению атрибутов из одной таблицы в другую. Сила соединения для отображения M из таблицы T1 в T2 представляет собой процент строк из T1, которые присоединяются к некоторой строке T2 под отображением M. Меня интересует поиск всех отображений с поддержкой, превышающей порог t. Это очень дорогостоящая операция, так как число возможных отображений экспоненциально в количестве атрибутов. Таким образом, я подумываю рассмотреть методы выборки для открытия соединения.

Для пример, рассмотрите TPC-H контрольная база данных. Скажем, нам дали таблицы для клиентов и заказов отношение. У нас есть необработанные данные. Мы не знаем, что соответствует каждому атрибуту. Теперь, увидев данные, мы должны иметь возможность выводить, что customer.customer_id и orders.customer_id присоединяются к столбцам с высокой поддержкой, но не customer.customer_age и orders.customer_id. Точно так же мы должны найти все возможные объединения и упорядочить их в соответствии с их поддержкой. Поскольку проверка всех возможных сочетаний атрибутов очень дорого, нам нужен эффективный метод, который будет использоваться.

Настоящий случай использования: мне дается необработанный массив данных, где столбцы изолированы (предположим, что две таблицы для простоты). Я хочу узнать, какие из возможных объединений можно использовать с эффективностью поддержки. (Примечание: Поскольку я не знаю ничего о типе атрибутов, я думаю рассмотреть все из них как строки и использовать выборку)

Понятно, что требуется выборка. Мои вопросы касаются только следующего.

Что такое хорошая стратегия выборки здесь? Какие метаданные должны быть рассчитаны для определения размеров выборки? Может ли выборка каждой таблицы выполняться независимо или должна быть скоррелирована?

Answer 1

Одной из возможностей было бы проанализировать статистические свойства каждого отдельного столбца. Таким образом, вы обнаружите, что customers.id и orders.cust_id имеют одинаковые распределения, и вы даже не попробовать, чтобы соответствовать orders.item_count против customers.age:

      min max average variance ... 
orders.item_count   1  29  3.1782  ... 
customers.age    18  75  38.45  ... 
customers.id    17239 29115 23177  ... 
orders.cust_id   17445 29037 23491  ... 

Кроме того, эти свойства могут быть получены из выборки каждой таблицы, без проверки целая таблица. Но для правильной оценки поддержки вам потребуется сделать единую выборку, которая может быть такой же дорогостоящей, как и дополнительное сканирование полной таблицы. Однако вы бы это сделали, только если статистические свойства выглядят многообещающими. Ваша стоимость будет равна n + m + k (n * m) с надежным малым k.

Я знаю, что это не так много, но, возможно, это может быть начало.

(Это один из многих возможных значения значительного: «два столбца относятся к одной и той же сущности» Ваш пробег может изменяться.).

Обновление: MySQL не очень хорошо подходит для предварительной разработки, где мы фактически вообще не используем функции RDBMS. Вы можете рассмотреть запуск начального анализа, например, Hadoop.

Как это сделать

Одна части данных, которые требуются, это оценка приблизительной числа строк в таблицах А и В. В противном случае, вещи получить действительно волосатые (и производительность выходит из окна) ,

1. Начало сканирования На данный момент мы прочитали один ряд, и мы знаем, что поля будут находиться в таблице A. Мы также знаем, что таблица А имеет один миллиард строк, и мы знаем (из особенностей нашего система), что мы не можем позволить себе читать более десяти миллионов строк и не писать более миллиона.

Итак, мы начинаем читать таблицу A, пропускающую каждые 100 строк (1 бит/10 мил). Мы будем выбирать один ряд каждые 1000 (1 млрд./1 ​​мил). Таким образом, мы сохраним один ряд из десяти (1000/100) в SampleA. Пока мы читаем, мы накапливаем статистические данные по каждому столбцу, т. Е. Имеем в памяти для каждого столбца список значений, таких как Col12_Min, Col12_Max, Col12_Sum, Col12_SumSquare, .... Мы можем добавить другие эвристические параметры, такие как Col12_Increasing и Col12_Decreasing, и добавим 1 к Col12_Increasing каждый раз, когда прочитанное значение больше предыдущего, добавим 1 к _Decreasing, если оно меньше. Это позволяет быстро распознать строки «счетчик», если таблица кластеризована.

Вся концепция выборки/чтения по одной строке для каждого N требует, чтобы таблица не имела регулярных распределений на этой частоте: если, например, столбец 23 содержит идентификатор клиента, за исключением случаев, когда один раз каждые сто строк, когда он содержит нуль, читая эту колонку с периодом 100, мы будем читать все нули и делать неправильные выводы. Если это так, извините; слишком много требований, и для удовлетворения их всех вы не можете использовать ярлыки - вам нужно читать каждую строку. Сложный достаточно случай не может быть решён простым способом.

Но, полагая, что случай более реалистичен, мы делаем то же самое для таблицы B, которая идет в SampleB.

Когда закончите, у нас есть две гораздо меньшие таблицы, информация о столбцах и проблема.

«Свободный для всех» присоединиться матрица, такие как

 ACol1 ACol2 ACol3 ... AColN 
BCol1  ?  ?  ?   ? 
BCol2  ?  ?  ?   ? 
BCol3  ?  ?  ?   ? 
... 
BColM  ?  ?  ?   ? 

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

 ACol1 ACol2 ACol3 ... AColN 
BCol1   ?     
BCol2  ?    ?   
BCol3     ?   ? 
... 
BColM     ?   

Но теперь то, что мы можем ожидать, когда мы присоединяемся SampleA.cust_id против SampleB.cust_id? SampleA содержит только одного клиента каждые тысяч. Поэтому, когда вы пытаетесь присоединиться к SampleA и SampleB, мы можем ожидать получить не более 0,1% соответствия. Учитывая идентификатор клиента из SampleB, вероятность его сбора в SampleA составляет 1/1000.

Теперь мы можем выполнить дополнительную проверку: проверьте, уникальны ли столбцы или нет. Мы увидим, что SampleA.cust_id уникален, а SampleB.cust_id - нет. Это говорит нам о том, что соединение, если оно выполняется, будет одно-ко-многим.

Предположим, что мы знаем (из статистических данных), что SampleA.cust_id содержит числа в диапазоне 10000000-20000000 и содержит 53000 строк и SampleB.cust_id содержит числа в том же диапазоне и содержит 29000 строк; если два столбца были , а не, коррелированный, , но имел эти параметры, мы ожидаем, что генерация одного числа в случайном порядке в диапазоне десять миллионов в ширину (что мы делаем, когда мы извлекаем строку из SampleB и читаем ее cust_it) вероятность 53000/10000000 = 0,53% соответствия строки в SampleA.

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

Когда мы достаточно ограничили количество пар столбцов, мы можем запустить «тест поддельного соединения», снова прочитав все A (другое полное сканирование таблицы) и проверив, что все значения SampleB.cust_id действительно присутствуют.

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

Также: все вышеперечисленное справедливо для один столбец VS один столбец отношений. Комбинированные ключи - это совсем другая возможность червей вообще, и статистический анализ, если это возможно, потребует очень разных инструментов - BigData и что-то вроде OLAP - и, прежде всего, очень разных (и массивных) затрат на обработку.

Answer 2

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

Вы можете легко генерировать SQL, что нужно как-то вроде:

select max(name1) as name1, max(name2) as name2, 
     count(*) as totalvalues, 
     sum(in1) as totalvalues_table1, 
     sum(in2) as totalvalues_table2, 
     sum(in1*in2)/count(*) as measure 
from (select value, max(name1) as name1, max(name2) as name2, 
      max(inone) as in1, max(intwo) as in2 
     from ((select 'col1' as name1, NULL, col1 as value, 1 as inone, 0 as intwo from table1 t1) 
      union all 
      (select NULL, 'col1', col1, 0, 1 from table2 t2) 
      ) tt 
     group by value 
    ) v; 

«мера» дает некоторое представление о перекрытии, на уровне значений. Вы можете использовать sum() для получения строк, но тогда у вас есть проблема, что в некоторых таблицах есть много строк, чем у других.

Вы можете автоматически генерировать SQL для всех столбцов, используя таблицу INFORMATION_SCHEMA.COLUMNS, которая доступна в большинстве баз данных (все реальные базы данных имеют аналогичный метод для получения метаданных, даже если имя вида/таблицы отличается).

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

Answer 3

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

Соответствие типам данных. Целые числа не присоединяются к строкам; даты не объединяются с поплавками. Точно, точность. 4 байтовых целых числа не объединяются с 2 байтовыми целыми числами; Строки с 50 макс не соответствуют строкам длиной 128 макс. Если вы конвертируете все в строки ... как вы сообщаете двоичный код из целого числа из плавающей точки от времени от строки до Unicode?

«Значительная» статистическая корреляция зависит от типа отношения. Статистика для (один к одному), (от одного до одного или больше), (от одного до нуля или больше), (от одного до нуля или одного), все можно сделать, но они не похожи друг на друга. Можете ли вы исключить (многие-ко-многим) в своих данных?

Без сканирования всех данных любая выборочная статистика вызывает сомнения. Были ли данные упорядочены по одному столбцу? Что делать, если где-то где-то клонится редкая информация, что делает ее более распространенной, чем она есть?

Большое большое допущение: соединения между отдельными столбцами. Если есть «составные идентификаторы столбца» (и это происходит), и вы делаете ставку в порядке (col1 + col2 против col2 + col1), он становится намного сложнее, чем анализ (m * n). Вы указали, что знаете что-нибудь об этих данных, которые вы выбрали ...

Без каких-либо разумных исходных предположений или догадок вы просто не столкнетесь ни с чем с такой проблемой без серьезных усилий и времени.