SQL Соединение на основе множеств | |
---|---|
Igor Korolyov Автор Сообщений: 34580 Дата регистрации: 28.05.2002 |
Возникла недавно любопытная задачка, я слегка упростил её, и вот оно...
Сначала подготовительный код:
Имеется 3 справчоных таблицы - Элементы, Конструкции и состав конструкций. Действует следующее ограничение: В одной конструкции элементы не могут повторяться. Т.е. по сути в таблице FooItem существует ограничение уникальности по полям (FooId, BarId). Одинаковые конструкции также недопустимы. Имеется 2 "рабочие" таблицы - в "детальной" таблице указаны использованные элементы, и на основе этой информации необходимо определить, что же за конструкция должна быть в заголовочной таблице (в шапке). Поле KnownFooId заполненное в примере - это ожидаемый ответ - для облегчения проверки своих вариантов Естественно, что в качестве ответа требуется именно SQL запрос (синтаксиса VFP9, Oracle9 или MSSQL - т.е. подзапросы допустимы где угодно ), а никак не программа. Конечно, запрос не должен использовать никаких особенностей движков СУБД типа RECNO() в фоксе или rownum в оракле... Нет, конечно же можно представить и такие решения - но "вне конкурса" P.S. Задача изначально решалась для Oracle, но 9-й фокс тоже вполне подойдёт. P.P.S. Собственно значения id не важны (не надо искать скрытого смысла в них), просто так я думаю оно будет нагляднее в процессе решения. ------------------ WBR, Igor Исправлено 1 раз(а). Последнее : Igor Korolyov, 18.04.08 19:46 |
Re: SQL Соединение на основе множеств | |
---|---|
leonid Сообщений: 3204 Откуда: Рига Дата регистрации: 03.02.2006 |
Игорь, привет!
Вроде вот так должно работать (по крайней мере, как идея), и достаточно быстро
|
Re: SQL Соединение на основе множеств | |
---|---|
Igor Korolyov Автор Сообщений: 34580 Дата регистрации: 28.05.2002 |
Привет Леонид!
Хм, любопытная идея. А математически доказывается, что сравнивая эти 3 средние мы выходим на точное совпадение? И, конечно, есть существенное ограничение по точности вычислений - вылезет при росте "размера" id... Т.е. для 6-значного BarId это IMHO уже не применимо (в фоксе по крайней мере) - из-за потери точности. Мой вариант не такой замысловатый, но пока не буду раскрывать ------------------ WBR, Igor |
Re: SQL Соединение на основе множеств | |
---|---|
leonid Сообщений: 3204 Откуда: Рига Дата регистрации: 03.02.2006 |
Привет, Игорь!
Теоретически, здесь конечно могут возникнуть "лишние" совпадения, но вероятность очень мала. В конце концов, при любом join-е, который оптимизатор (в том же Oracle) решит выполнить как hash join, такое может случиться. Если такая опасность пугает, можно увеличить количество AVG. А с переполнением легко бороться, если
|
Re: SQL Соединение на основе множеств | |
---|---|
Igor Korolyov Автор Сообщений: 34580 Дата регистрации: 28.05.2002 |
Привет Леонид!
1) Я на 99% уверен, что при любых условиях соединения БУДУТ выполняться корректно. Хэш используется для ускорения, НО он не может быть единственным критерием! Т.е. после проверки хэшей обязательно последует проверка собственно изначальных условий. Если это не так, то я точно прекращаю программировать - по меньшей мере для СУБД 2) Я опасался как раз за переполнение вещественных чисел Возможно потом сооружу тест для оценки скорости вариантов ------------------ WBR, Igor |
Re: SQL Соединение на основе множеств | |
---|---|
leonid Сообщений: 3204 Откуда: Рига Дата регистрации: 03.02.2006 |
Привет, Игорь!
Да, пожалуй ты прав. На 100% я не уверен, но следующую фразу Цитата:скорее всего следует интерпретировать именно так. Хотя, с моей точки зрения, 128-битный хэш в подавляющем большинстве случаев мог бы использоваться и напрямую. Цитата:А вот этого, мне кажется, опасаться не надо. 16 значащих цифр по любому хватит, даже если младшие будут отброшены. В конце концов, сколько этих конструкций может быть - ну миллион от силы. А элементов поди, и того меньше. Вероятность совпадения, даже в приведенном варианте будет очень маленькая, а приведенный вариант врядли самый оптимальный, написал первое, что пришло в голову. Кстати, на MySQL с помощью GROUP_CONCAT это вообще делается абсолютно точно. P.S. В связи с проблемой случайного совпадения, попробовал решить следующую задачу: Даны натуральные числа a1<a2<a3 и b1<b2<b3. Известно, что a1+a2+a3=b1+b2+b3 и a1^2+a2^2+a3^2=b1^2+b2^2+b3^2. Доказать, что a1=b1, a2=b2 и a3=b3, или построить противоречащий пример. Чувствую, что надо строить пример, но как-то... не строится. |
Re: SQL Соединение на основе множеств | |
---|---|
Igor Korolyov Автор Сообщений: 34580 Дата регистрации: 28.05.2002 |
Проблема IMHO не в том что оно "в 99% случаев будет работать", а в том что создаётся потенциальная дыра - т.е. специально подобранными данными злоумышленник сможет нарушить функционирование системы (грубо говоря подберёт себе такой ID, который по хэшу будет совпадать, например, с ID господина Абрамовича и соответственно их банковские счета "сольются" )
Насчёт ID - ты видимо не совсем правильно понял. Дело не в том что "конструкций" будет миллион, а в том что ID могут быть большие - ну например используется одна и та-же последовательность на все таблицы БД. У нас как раз подобный случай - есть достаточно много таблиц "разделяющих" один и тот же генератор ID, а кроме того из-за самопальной системы репликации каждый ключ в 2 младших разрядах содержит "код узла" - т.е. даже таблица в 20 строк имеет 4-значные реальные ID, а вообще размерность поля NUMBER(20) - мапится на тип long (Int64) в C#. Кстати поле ID может быть и не числовым - ну там GUID например... А для него приемлемый хэш считать уже не так то и просто! Так что мне больше нравится вариант с простым сравнением собственно Id-ников P.S. И очень жаль что никто больше не предложил вариантов Самый интерес то когда есть что сравнивать! ------------------ WBR, Igor |
Re: SQL Соединение на основе множеств | |
---|---|
leonid Сообщений: 3204 Откуда: Рига Дата регистрации: 03.02.2006 |
А вот мне кажется, что я не столько не понял, сколько плохо объяснил, что я имею в виду. Большие ID - это не только не плохо, а даже хорошо. Поскольку после перевода во FLOAT перемножить и найти AVG проблемы не будет - переполнение не произойдет - только младшие разряды могут пропасть, а старшие 16 все равно останутся, и их совпадение будет крайне маловероятным для разных ID. Цитата: Да, с GUID такое не пройдет, ну тогда вот еще вариант. Правда сразу скажу, что я его практически не отлаживал, у меня тут девятки нет, так что могут быть обломы
|
Re: SQL Соединение на основе множеств | |
---|---|
Владимир Максимов Сообщений: 14100 Откуда: Москва Дата регистрации: 02.09.2000 |
Лично я не вполне понял задачу. Это вариант поиска слагаемых для составления некоторой фиксированной суммы? В том смысле, что есть набор использованных элементов и надо определить какие конструкции из этих наборов можно создать, чтобы не осталось "лишних" элементов? Или же надо найти взаимно однозначное соответствие между RealItem.RealId и Foo.Id? |
Re: SQL Соединение на основе множеств | |
---|---|
Igor Korolyov Автор Сообщений: 34580 Дата регистрации: 28.05.2002 |
Привет Леонид!
А, т.е. ты считаешь что в данном случае потеря точности сыграет скорее положительную роль... Весьма любопытная мысль! Увы моих знаний явно не хватит на проверку точности такой оценки А вот твой второй вариант - если убрать из count-ов distinct (т.к. я в условии оговорил соответствующие "уникальности") это как раз и есть мой вариант Но что-то мне подсказывает что возможен ещё и 3-й вариант, но вероятно более громоздкий... 2 Владимир Нет, не "слагаемых". Действительно есть набор "использованных элементов", но заранее известно, что им соответствует не более 1-й "конструкции" - причём точно соответствует - ни "лишних деталей" не остаётся, ни добавлять ничего не надо. А соответствие ищется между Real.Id и Foo.Id - на основе сравнения их "состава". Или иначе говоря - поэлементного соответствия составов. ------------------ WBR, Igor |
Re: SQL Соединение на основе множеств | |
---|---|
Владимир Максимов Сообщений: 14100 Откуда: Москва Дата регистрации: 02.09.2000 |
Вариант-то есть, только он будет работать, если заранее известно, что в одной конструкции не может быть больше 3 элементов.
Можно кое-что оптимизировать, в отношении получения значений 2 и 3 элемента, но не стал этого делать. Вобщем-то, все вертится вокруг двух принципиальных вариантов анализа: Вариант 1: "Разворачивание" таблицы состава конструкций, чтобы получить комплектующие не в строках, а в столбцах. Т.е. одна конструкция - одна запись, с фиксированным набором реквизитов. После того, как состав конструкции "развернут" просто сравниваем набор реквизитов. Поскольку по условию задачи набор реквизитов уникален, то получим однозначное соответствие Недостаток этого подхода в том, что ограничено предельное количество элементов конструкции Вариант 2: Подсчет количества элементов в одной конструкции и сопоставление полученных количеств. Эту идею я пока до конца не продумывал. Какой-то "подвох" тут тоже есть... |
Re: SQL Соединение на основе множеств | |
---|---|
leonid Сообщений: 3204 Откуда: Рига Дата регистрации: 03.02.2006 |
Привет, Игорь!
Пожалуй, еще немного поясню, что я имел в виду. Положительную роль играет не сама по себе потеря точности, а то, что она может произойти только в том случае, если все 16 значащих цифр реально используются, а это значит, что имеется по крайней мере 10^16 различных хэшей (даже если мантиссу не принимать во внимание). При этом, сдается мне, что для больших значений распределение по хешам (в силу закона больших чисел) начинает приближаться к нормальному. А в таком случае можно прикинуть вероятность совпадения хэшей для двух различных последовательностей. Если имеется миллион конструкций, то вероятность будет где-то в районе одной миллиардной. И это только для одного хеша - а их три. Так что общая вероятность будет ну уж очень маленькая. Скорее уж для маленьких значений можно подобрать варианты точного совпадения (если это вообще возможно теоретически, чего я не знаю). И еще, не хотел бы я оказаться на месте злоумышленника, которому дали задание подобрать последовательность, по хешу совпадающему с хешем последовательности, скажем, 1234567, 1234568, 1234678, 1236789. Думаю, абсолютно дохлая задача. Цитата:В данном случае у меня distinct - это чисто перестраховка. Чтобы меньше думать. Цитата:Безусловно, есть еще варианты. Я как раз с таких и начинал. Можно написать с использованием подзапросов exists и not exists. Но на этом пути я столкнулся с некоторыми неизвестными мне ограничениями фоксовского SQL. Из документированных это Цитата:Мне как раз нужно было не immediate, а на один дальше. А все-таки было бы интересно сравнить варианты по скорости. Мне кажется, что мой первый вариант будет самым быстрым, тем более, что там есть возможность хеши этолонов конструкций просчитать заранее и хранить в таблице с соответствующими индексами. |
Re: SQL Соединение на основе множеств | |
---|---|
Igor Korolyov Автор Сообщений: 34580 Дата регистрации: 28.05.2002 |
Привет Владимир и Леонид!
Да, насчёт хэшей понятно, хотя, как говориться, и на старуху бывает проруха Поломали же MD5 - а он AFAIK был довольно неплохо математически проверен в своё время. Да и тот же асинхронный шифр RSA например - держится на ГИПОТЕЗЕ о сложности поиска простых множителей - т.е. завтра будет найден какой-то новый способ их получения и вся современная инфраструктура затрещит Я так думаю что вариант Владимира это и будет "тот самый" 3-й вариант. У меня честно говоря просто не хватило терпения отладить такой способ соединения 2 Владимир Да, действительно, в реальной задаче действует бизнес-ограничение и элементов может быть не более 3-х. Но даже для этого случая запрос получился монстрообразным Там всё было ещё более интересно - с каждым элементом связан индекс (т.е. по сути должен учитываться порядок следования элементов) - но реально он увы не соблюдался... ------------------ WBR, Igor |
Re: SQL Соединение на основе множеств | |
---|---|
leonid Сообщений: 3204 Откуда: Рига Дата регистрации: 03.02.2006 |
Привет, Игорь!
Если количество элементов не более 3, легко подобрать хэши, которые будут заведомо давать точное соответствие.
Посмотрел код Владимира. Вообще он решил несколько более сложную задачу: дополнительно вытащил элементы, по которым идет связь. Естественно, это можно сделать только, если известно ограничение на количество элементов в одной конструкции. Но код получился очень громоздкий, понять что-либо очень трудно. Я тоже попробовал решить такую задачу, вроде у меня получилось попроще
|
Re: SQL Соединение на основе множеств | |
---|---|
Igor Korolyov Автор Сообщений: 34580 Дата регистрации: 28.05.2002 |
Привет Леонид!
Ну просто супер! До такого изящного решения не додумался А ведь и правда для 3-х и менее идеально подходит MIN, MAX и SUM (или AVG - не принципиально IMHO). И код с разворотом действительно проще и читабельнее чем у Владимира Заодно видно где там можно применить аналитические функции Оракла! ------------------ WBR, Igor |
Re: SQL Соединение на основе множеств | |
---|---|
leonid Сообщений: 3204 Откуда: Рига Дата регистрации: 03.02.2006 |
IMHO все-таки SUM лучше. С AVG 1,3 и 1,2,3 выдадут одинаковый результат. |
Re: SQL Соединение на основе множеств | |
---|---|
Igor Korolyov Автор Сообщений: 34580 Дата регистрации: 28.05.2002 |
Да, точно Стормозил что-то...
------------------ WBR, Igor |
Re: SQL Соединение на основе множеств | |
---|---|
srkarim Сообщений: 15 Дата регистрации: 04.05.2007 |
Леонид, здравствуйте.
Так как тут все числа целые, то мне кажется для хэш кода прекрасно подойдет sin() (если BarId<10^15): <code> SELECT x.RealId as Id, y.FooId as KnownFooId FROM ; (SELECT RealId, ; SUM(CAST(1000000000*SIN(BarId) as I)) as f0 ; FROM RealItem GROUP BY RealId) x ; JOIN ; (SELECT FooId, ; SUM(CAST(1000000000*SIN(BarId) as I)) as f0 ; FROM FooItem GROUP BY FooId) y ; ON x.f0=y.f0 ; ORDER BY x.RealId DESC </code> Еще прекрасный вариант - SYS(2007,...), наверняка в MySql есть аналог. Сергей
|
Re: SQL Соединение на основе множеств | |
---|---|
leonid Сообщений: 3204 Откуда: Рига Дата регистрации: 03.02.2006 |
2srkarim
Разных хэшей можно придумать много. Синус, наверное, неполохой вариант, но беда в том, что как только начинаются округления, становится практически невозножно доказать, что не будет "лишних" совпадений. Хотя вероятность очень маленькая, но все-таки не 0. С синусами, наверное, даже возможны совпадения конструкций, состоящих из двух элементов. |
© 2000-2024 Fox Club  |