[opengeodb] Neue, bessere "Hierarchies" sind wieder da!
Simon Schmid
hakky0815 at gmail.com
Don Dez 27 03:15:54 CET 2007
Hallo zusammen,
ich bin ein grosser Fan von der OpenGeoDB, leider war es in meinen
bisherigen Projekten nicht notwendig sie zu verwenden. In meinem
jetzigen Projekt soll sie aber ein wesentlicher Bestandteil sein.
Doch ich habe mühe mich mit der Datenbankstruktur in der Version
0.2.5a anzufreunden. Es ist _sehr_ mühselig Abfragen zu formulieren.
Speziell wenn man z.B. einen Hierarchie Baum einer Ortschaft bilden
will, oder z.b alle Landkreise eines Bundeslandes aufzulisten.
Ich hatte folgendes vor:
Eine Schrittweise Selektierung des Wohnorts. Zuerst soll das Land
(DE,AT,FL,CH) gewählt werden, anschliessen Bundesland/Kanton/....,
dann der Landkreis oder halt auch Kreisfreie Stadt.
Und genau da sind wir beim Problem, es gibt Bundesländer mit
Regierungsbezirke und welche ohne, sowohl gibt es auch Kreisfreie
Städte! Das ganze ist also eine ganz schöne Knacknuss, wenn man es in
einem SQL query abfragen möchte.
Zudem ist das Parent-ID Modell (Adjacency List, Teil von ist wiederum
teil von....) extrem langsam weil es rekursive Abfragen benötigt
(Self-Joins) und bei einer so wuchtigen tabelle wie geodb_textdata
hängt es ziemlich....
Ich bin nunmal ein wenig perfektionistisch veranlagt was solche Dinge
angeht und wollte das nicht so akzeptieren. Die alte "hierarchies"
Datenstruktur ist zudem auch sehr beschränkt und Datenbanktechnisch
unklug (soll kein Vorwurf sein!).
Ich habe mich entschieden die ganzen "locations" als nested set zu
ordnen. Ein nested set bringt sehr viele Vorteile beim Abfragen, ist
zugleich aber mühsam zu updaten. Doch überwiegen hier die Abfragen
_deutlich_. Zudem kann das Nested Set innerhalb von wenigen Minuten
komplett neu aufgebaut werden.
Für alle die nicht mit dem Nested Set Modell vertraut sind, sollten
sich hier einlesen:
- http://www.klempert.de/nested_sets/artikel/
- http://guxx.de/2007/05/30/nested-sets/
- http://phpperformance.de/nested-sets-hierarchische-strukturen-und-baeume-in-mysql/
- http://www.php-resource.de/tutorials/read/21/3/
Und ebenfalls sehr gut, aber auf Englisch:
- http://dev.mysql.com/tech-resources/articles/hierarchical-data.html
Mal vorne weg, die Erstellung des Nested Sets, löscht keinerlei daten
aus der opengeodb! Also keine Sorge! Ihr solltet nur keine Tabelle
namens "geodb_tree" haben, sonst wird sie überschrieben.
Ich verwende folgende Tabelle (datenbank: geodb, tabellenname: geodb_tree):
DROP TABLE IF EXISTS `geodb`.`geodb_tree`;
CREATE TABLE `geodb`.`geodb_tree` (
`loc_id` int(11) unsigned NOT NULL,
`lft` int(11) unsigned NOT NULL,
`rgt` int(11) unsigned NOT NULL,
`level` tinyint(3) NOT NULL,
UNIQUE KEY `locid` USING BTREE (`loc_id`),
KEY `rgt` USING BTREE (`rgt`),
KEY `lft` USING BTREE (`lft`),
KEY `level` (`level`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
Kurze Erklärung: loc_id beinhaltet die übliche loc_id (wie logisch),
lft beinhaltet den left-wert, rgt den right-wert, level bezieht sich
auf das level von der loc_id (Bei Bundesländern z.b 3 oder bei
Landkreisen 5 etc., es wird also die EBENE der loc_id aus
geodb_textdata verwendet).
Nun, wie bekommen wir unsere Daten da rein? Ich habe mir dafür ein
kleines PHP Skript auf Kommandozeile gebastelt.
Es ist gut dokumentiert, deswegen erspar ich mir einen zusätzlichen
Kommentar ;) - Alternativ gibt es das ganze auch gut formatiert unter:
http://pastebin.com/f5e906e3e
<?php
// PDO - Verbindung zur Datenbank, PDO ist nur in neueren PHP
Versionen verfuegbar! ---> http://php.net/pdo
$GLOBALS['dbh'] = new PDO('mysql:host=localhost;dbname=geodb', 'root', '');
echo "Connected to DB\n";
// leere ein eventuell vorhandenes nested set
$GLOBALS['dbh']->exec('DELETE FROM geodb_tree WHERE 1=1');
echo "Nested Set is empty now\n";
// fuege hauptknoten ein, mit loc_id = 0, Level ist 1, Left-Wert
ist 1, Right-Wert ist 2
$GLOBALS['dbh']->exec("INSERT INTO `geodb_tree` (`loc_id`,
`level`, `lft`, `rgt`) VALUES (0, 1, 1, 2)");
echo "Inserted root node\n";
/*
--------- HINWEIS -----------
Ich werde mich bemuehen, die Tage das Script so zu aendern
dass direkt DE/AT/CH/FL eingefuegt werden. (Versprochen am: 27.12.07 )
--------- HINWEIS ------------
*/
// fuege Deutschland hinzu (DE hat loc_id = 105) , das Level von
Deutschland ist 2 und der Right-Wert des Elternelements ist 2!
echo "Adding Germany\n";
addsubtree(105, 2, 2);
// rekurisve funktion zur erzeugung des nested sets, loc_id sollte
bekannt sein, level bezieht sich auf die Ebene der aktuellen loc_id,
parent_rgt ist der Right-Wert des Elternelements
function addsubtree($locid, $level, $parent_rgt)
{
// fuege knoten hinzu
addleaf($locid, $level, $parent_rgt);
// gebe gerade hinzugeuegte loc_id aus!
echo $locid ."\n";
// hole alles was direkt "Teil von" der aktuellen loc_id ist
(text_type = 400100000)
$entries = $GLOBALS['dbh']->query("SELECT loc_id FROM
geodb_textdata WHERE text_type = 400100000 AND text_val = $locid");
// gibt es kein untergeordnetes element -> return
if($entries->rowCount() <= 0) { return; }
// gehe alle "Teile von" der aktuellen loc_id durch
foreach($entries as $cEntry)
{
// hole den aktuellen RGT-Wert des gerade eingefuegten
Eltern-Elements
$res = $GLOBALS['dbh']->query("SELECT rgt FROM geodb_tree
WHERE loc_id = $locid");
$cRgt = $res->fetch();
// hole level der einzufuegenden loc_id (mittels text_type
= 400200000)
$res = $GLOBALS['dbh']->query("SELECT text_val FROM
geodb_textdata WHERE loc_id = " . $cEntry[0] . " AND text_type =
400200000");
$cLevel = $res->fetch();
// manche datensaetze haben kein level mitangegeben wie
z.b loc_id = 18048 - deshalb wird das level auf -1 (unbekannt)
gesetzt
if(!$cLevel[0])
{
$cLevel[0] = -1;
}
// rufe die funktion rekursiv auf
addsubtree($cEntry[0], $cLevel[0], $cRgt[0]);
}
return;
}
// diese funktion fuegt einen neuen knoten / blatt ein die
parameter kann man aus der addsubtree(...) funktion entnehmen
function addleaf($locid, $level, $parent_rgt)
{
// bringe RGT und LFT werte auf aktuellen Stand
if($GLOBALS['dbh']->exec("UPDATE geodb_tree SET rgt=rgt+2
WHERE rgt >= " . $parent_rgt) === false)
{
error(1, "UPDATE geodb_tree SET rgt=rgt+2 WHERE rgt >= " .
$parent_rgt);
exit;
return;
}
// dito
if($GLOBALS['dbh']->exec("UPDATE geodb_tree SET lft=lft+2
WHERE lft > ". $parent_rgt ) === false)
{
error(2, "UPDATE geodb_tree SET lft=lft+2 WHERE lft > ".
$parent_rgt);
exit;
return;
}
// fuege neuen knoten / blatt hinzu
if($GLOBALS['dbh']->exec("INSERT INTO geodb_tree (loc_id,
level, lft, rgt) VALUES (".$locid.", ". $level . ", ".$parent_rgt ." ,
".$parent_rgt." +1)") === false)
{
error(3, "INSERT INTO geodb_tree (loc_id, level, lft, rgt)
VALUES (".$locid.", ". $level . ", ".$parent_rgt ." , ".$parent_rgt."
+1)");
exit;
return;
}
}
// $num gibt an bei welchem Query (Update #1, Update #2, Insert)
ein fehler aufgetreten ist, $sql beinhaltet das SQL statement
function error($num, $sql)
{
echo "Error while inserting - Query# " . $num . " !\n";
print_r($GLOBALS['dbh']->errorInfo());
echo "\n\n---------------------\n\n";
echo $sql;
echo "\n\n";
}
?>
Das wäre einmal geschafft! Es sollten so um die 15'000 Einträge für
DEUTSCHLAND werden ;) Ich habe wie gesagt bisher erst Deutschland
hinzugefügt. AT/CH/FL kommen noch!
Wie man das ganze abfragen kann, ist aus den Links über Nested Sets zu
entnehmen. Aber als kleines Schmankerl hier ein paar Queries:
--> Abfrage aller Bundesländer (Ebene 3):
SELECT
g2.loc_id, gt.text_val
FROM
geodb_textdata AS gt,
geodb_tree AS g,
geodb_tree AS g2
WHERE
g.loc_id =105 AND
g2.lft > g.lft AND
g2.rgt < g.rgt AND
g2.level = 3 AND
gt.loc_id = g2.loc_id AND gt.text_type = 500100000
GROUP BY
g2.loc_id
Diese Abfrage dauert bei mir aufm 2 jahre alten Laptop der voll im
Betrieb ist im Schnitt (von 100 Queries) 0.0021 Sekunden! Hurra ;)
Ohne GROUP BY ist's noch schneller.
--> Abfrage aller Landkreise (Ebene 5) eines Bundeslands (ohne
Berücksichtigung der Regierungsbezirke)
SELECT
g2.loc_id, gt.text_val
FROM
geodb_textdata AS gt,
geodb_tree AS g,
geodb_tree AS g2
WHERE
g.loc_id = (LOC_ID EINES BUNDESLANDES Z.B 117 FUER NRW) AND
g2.lft > g.lft AND
g2.rgt < g.rgt AND
g2.level = 5 AND
gt.loc_id = g2.loc_id AND gt.text_type = 500100000
GROUP BY
g2.loc_id
Wie man sieht sind die beiden Abfrage beinahe identisch bis auf die
loc_id, und auf die Ebene! Wenn ihr sämtliche Landkreise in ganz DE
wollt, könnt ihr einfach das obige Query ändern und g.loc_id = 105
machen! Dann habt ihr alle Landkreise, und was sonst noch auf Ebene 5
ist in DE ;)
Wenn ihr wollt könnte ich mal eine kleines Kochbuch mit den gängisten
Abfragen machen. Es ist aber auch genauso einfach selbst zu
bewerkstelligen wenn ihr die obigen links durchlest!
Das Nested Set Modell schlägt das alte Modell in Sachen Performance um
Längen in der ABFRAGE ;)
Viel Spass beim Ausprobieren wünscht
Simon