Tipp für MySQL Abfrage

Hallo ich habe eine Frage bezüglich einer SQL-Abfrage in
de.comp.lang.php.misc gestellt, die anscheinend hier besser aufgehoben ist.
Daher wiederhole ich die Frage hier noch einmal:

ich brauche einen Tipp für eine Abfrage einer MySQL Tabelle mit SQL und PHP.

Ich habe eine Tabelle mit ca. 4000 Datensätzen.
Jeder Datensatz hat einen Wert 'x' und einen Wert 'y'. (beide als float)

Nun möchte ich zu einem bestimmten Datensatz abfragen, welcher andere
Datensatz aus der Tabelle diesem am nächsten ist.
Ob der nächstgelegene Wert x oder y ist und wie groß die Differenz ist.

Also: suche alle 'x'-Werte aus der Tabelle und gebe den aus, der am nächsten
am 'x'-Wert meines Datensatzes dran ist.
Gleichzeitig möchte ich ausgeben, um wieviel dieser Datensatz größer oder
kleiner als mein originaler ist (wobei man das sicher auch mit php später
machen kann).

Beispiel:
ID1 x=100 y=100
ID2 x=150 y=300
ID3 x=600 y=310

Wenn ich in diesem Beispiel den Datensatz ID2 abfrage, sollte bei der
Abfrage nach dem nächstgelegenen x die ID1 mit einem x-Abstand von 50
gefunden werden.
Bei einer Abfrage nach y sollte die ID3 mit einem Abstand von 10 ausgegeben
werden.

Im Idealfall würde ich diese beiden Abfragen gerne verbinden.
Suche den Datensatz, der insgesamt (also x und y) meinem Abfragedatensatz am
nächsten kommt, wobei dann der größere der beiden Werte herangezogen werden
sollte.
Das würde im obigen Fall zu folgendem Ergebnis führen:
Der näher gelegene Datensatz zu ID2 ist der Datensatz ID1, da hier der
größte Abstand 200 (im y Wert) ist.
Beim dritten aber ist der Abstand 450 (im x Wert)
In diesem Fall wäre irrelevant, dass bei ID3 der Abstand des y-Wertes nur 10
ist, da wir den größeren der beiden Abstände brauchen.

Anwendung:
In einer Webseite werden für jeden Datensatz Symbole auf einer Karte
erzeugt, (nicht alle 4000 auf einmal, aber bis zu 100 auf einer Kachel), die
gemäß der Angaben in x und y plaziert werden sollen (x und y sind
geo-Koordinaten).
Leider liegen manche Objekte so nah beisammen, dass sie sich in der
Darstellung stark überlappen, und somit das untere nicht mehr erkannt wird.
Die GEO-Koordinaten dürfen nicht verändert werden.
Mit der SQL Abfrage oben möchte ich alle Objekte finden, die näher als ein
Vorgabewert beieinander liegen und mittels PHP zu einem Sammelobjekt
umdefinieren.
Wenn nur x oder y, nicht aber beide nah beieinander sind, gibt es keine
Überlappung und der Datensatz soll deshalb nicht berücksichtigt werden.
Darum muss ich abfragen, ob der Abstand meines Objektes zu dem weiter
entfernten Wert (x oder y) größer oder kleiner ist, als mein Vorgabewert.

Ich habe leider absolut keine Idee, wie diese SQL Abfrage auszusehen hat.


Vielen Dank für jede Hilfe,
Martin Nadoll

Re: Tipp für MySQL Abfrage

Martin Nadoll schrieb:

> Hallo ich habe eine Frage bezüglich einer SQL-Abfrage in
> de.comp.lang.php.misc gestellt, die anscheinend hier besser aufgehoben ist.
> Daher wiederhole ich die Frage hier noch einmal:

Es gibt auch de.comp.datenbanken.mysql, die in diesem Fall eine noch
bessere Wahl gewesen wäre.

> [lange Vorrede]
>
> Anwendung:
> [kurzer Sinn]
> Darum muss ich abfragen, ob der Abstand meines Objektes zu dem weiter
> entfernten Wert (x oder y) größer oder kleiner ist, als mein Vorgabewert.

Die Entfernung zweier Punkte voneinander ergibt sich nicht aus direktem
Koordinatenvergleich, sondern aus der Abstandsfunktion, hier die
einfache Euklidische Norm. Sei P(x_0|y_0) der der Vergleichspunkt,
Q(x|y) der Punkt, dessen Abstand zu P bestimmt werden soll. Dann ist der
Abstand d=\sqrt{(x-x_0)^2+(y-y_0)^2} (Satz des Pythagoras).
Da du dich im Wesentlichen nur für die Rangfolge interessierst, reicht
es aus d^2 zu betrachten, also die Summe (x-x_0)^2+(y-y_0)^2.

> Ich habe leider absolut keine Idee, wie diese SQL Abfrage auszusehen hat.

Jetzt ist's doch einfach, oder?

MfG
Niels

--
| http://www.kolleg.de · Das Portal der Kollegs in Deutschland |
| http://www.bsds.de · BSDS Braczek Software- und DatenSysteme |
| Webdesign · Webhosting · E-Commerce · Mambo Content Management |
`----------------------------------------------------------- -----´

Re: Tipp für MySQL Abfrage

"Martin Nadoll" wrote:
>
> ich brauche einen Tipp für eine Abfrage einer MySQL Tabelle mit SQL und PHP.

Das PHP kannst du ruhig streichen.

> Ich habe eine Tabelle mit ca. 4000 Datensätzen.
> Jeder Datensatz hat einen Wert 'x' und einen Wert 'y'. (beide als float)
>
> Nun möchte ich zu einem bestimmten Datensatz abfragen, welcher andere
> Datensatz aus der Tabelle diesem am nächsten ist.
> Ob der nächstgelegene Wert x oder y ist und wie groß die Differenz ist.

OK. Offensichtlich hast du keinen mathematischen Background. Aber
vielleicht kannst du dir ja etwas unter einer Abstandsfunktion
vorstellen. Das ist einfach eine Funktion, die den Abstand zweier
Objekte bestimmt. Aus deiner eher vagen Formulierung komme ich zu:

d([x1,y1], [x2,y2]) = min(abs(x1-x2), abs(y1,y2))

Die Frage: gib mir den Punkt dessen Abstand vom Referenzpunkt [x0, y0]
minimal ist, wäre in (My)SQL formuliert:

SET @x0=... , @y0=... ;
SELECT id, IF(ABS(x-@x0) < ABS(y-@y0), ABS(x-@x0), ABS(y-@y0)) as d
FROM ...
ORDER BY d DESC
LIMIT 1;

Deine Vorgabewerte für x0 und y0 kannst du natürlich auch direkt in
die Query einbauen statt MySQL-Variablen zu benutzen.

Allerdings kann diese Query keinen Index benutzen und wird demzufolge
nicht gerade berauschend schnell sein. Für deine 4000 Zeilen muß der
längliche IF() Ausdruck 4000mal ausgerechnet und anschließend die
Ergebnisse sortiert werden. Das wird wohl nicht schnarchlahm, aber
auch sicher nicht rasend schnell.

> Beispiel:
> ID1 x=100 y=100
> ID2 x=150 y=300
> ID3 x=600 y=310
>
> Wenn ich in diesem Beispiel den Datensatz ID2 abfrage, sollte bei der
> Abfrage nach dem nächstgelegenen x die ID1 mit einem x-Abstand von 50
> gefunden werden.
> Bei einer Abfrage nach y sollte die ID3 mit einem Abstand von 10 ausgegeben
> werden.
>
> Im Idealfall würde ich diese beiden Abfragen gerne verbinden.
> Suche den Datensatz, der insgesamt (also x und y) meinem Abfragedatensatz am
> nächsten kommt, wobei dann der größere der beiden Werte herangezogen werden
> sollte.

Das verändert die Abstandsfunktion zu

d([x1,y1], [x2,y2]) = max(abs(x1-x2), abs(y1,y2))

was zwar einigermaßen ungewöhnlich ist, aber was solls.

> Anwendung:
.....
> Mit der SQL Abfrage oben möchte ich alle Objekte finden, die näher als ein
> Vorgabewert beieinander liegen und

Tja und an dieser Stelle wirfst du alle deine bisherigen Aussagen über
den Haufen weil du jetzt einen Referenzpunkt *und* einen Mindestabstand
vorgibst. Aus "gib mir den nächstliegenden Punkt" wird "gib mir alle
Punkte, deren Abstand kleiner ist als..."

Nach deiner Abstandsdefinition erfüllt ein den Referenzkoordinaten
[x0, y0] "nahe" liegender Punkt folgende Bedingung:

x0-d <= x <= x0+d und y0-d <= y <= y0+d

Und genau so kannst du das auch in SQL formulieren:

SET @x0=... , @y0=... , @d=... ;
SELECT id, IF(ABS(x-@x0) > ABS(y-@y0), ABS(x-@x0), ABS(y-@y0)) as d
FROM ...
WHERE x BETWEEN @x0-@d AND @x0+@d
AND y BETWEEN @y0-@d AND @y0+@d
ORDER BY d DESC;

Da beide Koordinaten gegen Konstanten verglichen werden, kann diese
Query auch einen Index (idealerweise auf (x,y)) benutzen. Das ORDER BY
ist hier optional, aber vielleicht findest du es ja toll, die Nachbarn
nach Entfernung sortiert zu bekommen.


XL

Re: Tipp für MySQL Abfrage

Hallo Axel, hallo Niels,

vielen Dank für die ausführlichen Ausführungen. Meine Kenntnisse bezügl.
Mathematik und SQL scheinen in der Tat ausbaufähig zu sein. Ich werde die
Beiträge aber dazu nutzen, mich da rein zu denken.

Gruß,
Martin Nadoll


"Axel Schwenke" schrieb im Newsbeitrag
news:rddchd.mii.ln@idefix.xl.local...
> "Martin Nadoll" wrote:
>>
>> ich brauche einen Tipp für eine Abfrage einer MySQL Tabelle mit SQL und
>> PHP.
>
> Das PHP kannst du ruhig streichen.
>
>> Ich habe eine Tabelle mit ca. 4000 Datensätzen.
>> Jeder Datensatz hat einen Wert 'x' und einen Wert 'y'. (beide als float)
>>
>> Nun möchte ich zu einem bestimmten Datensatz abfragen, welcher andere
>> Datensatz aus der Tabelle diesem am nächsten ist.
>> Ob der nächstgelegene Wert x oder y ist und wie groß die Differenz ist.
>
> OK. Offensichtlich hast du keinen mathematischen Background. Aber
> vielleicht kannst du dir ja etwas unter einer Abstandsfunktion
> vorstellen. Das ist einfach eine Funktion, die den Abstand zweier
> Objekte bestimmt. Aus deiner eher vagen Formulierung komme ich zu:
>
> d([x1,y1], [x2,y2]) = min(abs(x1-x2), abs(y1,y2))
>
> Die Frage: gib mir den Punkt dessen Abstand vom Referenzpunkt [x0, y0]
> minimal ist, wäre in (My)SQL formuliert:
>
> SET @x0=... , @y0=... ;
> SELECT id, IF(ABS(x-@x0) < ABS(y-@y0), ABS(x-@x0), ABS(y-@y0)) as d
> FROM ...
> ORDER BY d DESC
> LIMIT 1;
>
> Deine Vorgabewerte für x0 und y0 kannst du natürlich auch direkt in
> die Query einbauen statt MySQL-Variablen zu benutzen.
>
> Allerdings kann diese Query keinen Index benutzen und wird demzufolge
> nicht gerade berauschend schnell sein. Für deine 4000 Zeilen muß der
> längliche IF() Ausdruck 4000mal ausgerechnet und anschließend die
> Ergebnisse sortiert werden. Das wird wohl nicht schnarchlahm, aber
> auch sicher nicht rasend schnell.
>
>> Beispiel:
>> ID1 x=100 y=100
>> ID2 x=150 y=300
>> ID3 x=600 y=310
>>
>> Wenn ich in diesem Beispiel den Datensatz ID2 abfrage, sollte bei der
>> Abfrage nach dem nächstgelegenen x die ID1 mit einem x-Abstand von 50
>> gefunden werden.
>> Bei einer Abfrage nach y sollte die ID3 mit einem Abstand von 10
>> ausgegeben
>> werden.
>>
>> Im Idealfall würde ich diese beiden Abfragen gerne verbinden.
>> Suche den Datensatz, der insgesamt (also x und y) meinem Abfragedatensatz
>> am
>> nächsten kommt, wobei dann der größere der beiden Werte herangezogen
>> werden
>> sollte.
>
> Das verändert die Abstandsfunktion zu
>
> d([x1,y1], [x2,y2]) = max(abs(x1-x2), abs(y1,y2))
>
> was zwar einigermaßen ungewöhnlich ist, aber was solls.
>
>> Anwendung:
> ....
>> Mit der SQL Abfrage oben möchte ich alle Objekte finden, die näher als
>> ein
>> Vorgabewert beieinander liegen und
>
> Tja und an dieser Stelle wirfst du alle deine bisherigen Aussagen über
> den Haufen weil du jetzt einen Referenzpunkt *und* einen Mindestabstand
> vorgibst. Aus "gib mir den nächstliegenden Punkt" wird "gib mir alle
> Punkte, deren Abstand kleiner ist als..."
>
> Nach deiner Abstandsdefinition erfüllt ein den Referenzkoordinaten
> [x0, y0] "nahe" liegender Punkt folgende Bedingung:
>
> x0-d <= x <= x0+d und y0-d <= y <= y0+d
>
> Und genau so kannst du das auch in SQL formulieren:
>
> SET @x0=... , @y0=... , @d=... ;
> SELECT id, IF(ABS(x-@x0) > ABS(y-@y0), ABS(x-@x0), ABS(y-@y0)) as d
> FROM ...
> WHERE x BETWEEN @x0-@d AND @x0+@d
> AND y BETWEEN @y0-@d AND @y0+@d
> ORDER BY d DESC;
>
> Da beide Koordinaten gegen Konstanten verglichen werden, kann diese
> Query auch einen Index (idealerweise auf (x,y)) benutzen. Das ORDER BY
> ist hier optional, aber vielleicht findest du es ja toll, die Nachbarn
> nach Entfernung sortiert zu bekommen.
>
>
> XL