MySQL - Нестандартный SQL запрос

[rus-4-ever]

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

неделю голову ломаю, с SQL знаком был только со стандартными простыми запросами.



Цель: есть база данных объектов . у каждого есть ДО 10 координат x,y,z

Составил таблицу примерно так.:



Idобъекта ; Nкоординат ; x1 ; y1 ; z1; x2 ; y2 ; z2 ... ; x10 ; y10 ; z10



Цель: Найти другой объект, с которым совпадает наибольшее ЧИСЛО координат.



Думал вынести координаты каждой точки в отдельную таблицу, но проще не становится.



Есть ли варианты решения этой задачи???



PS. Таблица объектов в перспективе будет довольно большой: несколько тысяч объектов.

[Iska]

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

[rus-4-ever]

Спасибо. Тему оставлю открытой, на случай если вдруг у кого нибудь предложения еще найдутся.

[rus-4-ever]

Цитата Iska:



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

MySQL - Нестандартный SQL запрос

Откуда следует именно такой алгоритм поиска? В исходной постановке такого нет, имхо.

Например, может быть объект в котором совпадают только координаты x и y, причем все, а z - все не совпадают, тогда такой объект имеет 20 совпадений - достаточно много, а он при алгоритме Iska выявляться не будет.



По-моему, можно просто втупую перебирать все объекты и сравнивать соответсвующие координаты x1 c x1, y1 c y1 и т.п.,

а в 31 "координату"-счетчик S записывать-насчитывать совпадения.

После перебора всех элементов базы надо будет просто отсортировать ее по убыванию счетчика.

На простановку счетчиков - около 300 000 операций сравнения (много?). Сортировка - стандартная операция.



Вообще для составления правильного алгоритма, надо понимать "физический смысл" математической модели, который не рассказан.

[Iska]

Цитата rus-4-ever:



есть база данных объектов . у каждого есть ДО 10 координат x,y,z

…

Найти другой объект, с которым совпадает наибольшее ЧИСЛО координат.

MySQL - Нестандартный SQL запрос

Цитата alef2474:



Например, может быть объект в котором совпадают только координаты x и y, причем все, а z - все не совпадают

MySQL - Нестандартный SQL запрос

alef2474, поздравляю! Не каждому удаётся так просто сказать новое слово в Евклидовой геометрии .

[LilLoco]

Доброе утро!



Вчера прочитал эту тему, после Up темы. Пока ехал в электричке, было время немного поразмышлять. Так как в SQL я еще не силен, прошу сильно не пинать) Пришла в голову такая вот идея.



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



PHP код:

Код: Выделить всё

(x1-x2) + (y1-y2) + (z1-z2) = 0 

Всего координат может быть до 10. Значит необходимо посчитать сколько "нулей" получается в выражении. Для этого объединяем все эти 10 выражений через Union, и ищем сумму таких выражений. Причем, если выражение равно нулю, то для Union используем 1. Кусок кода:



PHP код:

Код: Выделить всё

SELECT SUM(X) FROM (
SELECT CASE WHEN ((X1 - X1) + (Y1 - Y1) + (Z1 - Z1)) = 0 THEN 1 ELSE 0 END AS X
    UNION ALL
SELECT CASE WHEN ((X2 - X2) + (Y2 - Y2) + (Z2 - Z2)) = 0 THEN 1 ELSE 0 END
    UNION ALL
SELECT CASE WHEN ((X3 - X3) + (Y3 - Y3) + (Z3 - Z3)) = 0 THEN 1 ELSE 0 END
...
        UNION ALL
SELECT CASE WHEN ((Xn - Xn) + (Yn - Yn) + (Zn - Zn)) = 0 THEN 1 ELSE 0 END) 

Ну а далее - дело фантазии.

Для примера идет простая сортировка. Выводится столбец с исходным номером объекта (FindFor), другими объектами (Finded), и количеством совпадений (cnt).

Полный код ниже.

читать дальше »

PHP код:

Код: Выделить всё

SELECT aa.*, X = ROW_NUMBER() OVER (PARTITION BY aa.FindFor Order By cnt DESC)
FROM (Select FindFor = a.id, Finded = b.id, cnt = (SELECT SUM(X) FROM (
SELECT CASE WHEN ((X1 - X1) + (Y1 - Y1) + (Z1 - Z1)) = 0 THEN 1 ELSE 0 END AS X
    UNION ALL
SELECT CASE WHEN ((X2 - X2) + (Y2 - Y2) + (Z2 - Z2)) = 0 THEN 1 ELSE 0 END
    UNION ALL
SELECT CASE WHEN ((X3 - X3) + (Y3 - Y3) + (Z3 - Z3)) = 0 THEN 1 ELSE 0 END
...
        UNION ALL
SELECT CASE WHEN ((Xn - Xn) + (Yn - Yn) + (Zn - Zn)) = 0 THEN 1 ELSE 0 END)  d)
    from Таблица a
    left join Таблица b on a.id  b.id) aa 

[Iska]

LilLoco, идея хороша. Но! Искать совпадения нужно не только среди Объект1.X1 и Объект2.X1, а Объект1.X1 и Объект2.X1 + Объект1.X1 и Объект2.X2 + … + Объект1.X1 и Объект2.XN и т.д. Понимаете? Придётся сравнивать каждую координату объекта со всеми координатами всех прочих объектов.

[LilLoco]

Цитата Iska:



Понимаете?

MySQL - Нестандартный SQL запрос

Теперь да) Думал, что только соответствующие Просто не совсем понятно, как объект может задаваться несколькими координатами.



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

Т.е. как то так:

Id, ObjectId, CoordId, X, Y, Z

где ObjectId - номер объекта,

CoordId - порядковый номер координат,

X,Y,Z - координаты.

И после этого при Left Join сводить по не ObjectId и по не CoordId. Ну и немного изменить подзапрос?

[Iska]

Цитата LilLoco:



Теперь да) Думал, что только соответствующие

MySQL - Нестандартный SQL запрос

Угу. Я тоже поначалу точно так думал. Начал лепить таблицу, затем запрос… А спустя время осознал, что в принципе-то может быть и так:



Код:

Код: Выделить всё

Объект1; 1,1,1; 2,2,2; 3,3,3.
Объект2; 2,2,2; 3,3,3; 1,1,1.

(утрирую, конечно, но суть видна).




Цитата LilLoco:



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

MySQL - Нестандартный SQL запрос

Меня тоже весьма удивили объекты со строго ограниченным и равным числом вершин (число координат N жёстко определено структурой таблицы).

[LilLoco]

Цитата Iska:



Меня тоже весьма удивили объекты

MySQL - Нестандартный SQL запрос

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