Hierarchikus adatkezelés SQL-lel PHP-ben III.
A sorozat első részében megismerkedhettünk a hierarchikus listák kezelésének legegyszerűbb módjával. Az algoritmusok rekurzívak voltak, ebből következően csak kisebb méretű listák kezelésére voltak alkalmazhatók. A második részben az első módszernél hatékonyabb, robusztusabb, de egyben jóval bonyolultabb elméletet ismerhettünk meg. A módszerre az angol szakirodalom nested tree néven hivatkozik. A sorozat harmadik részében az előző rész elméletét követve egy általános, jól használható osztály kifejlesztése lesz a cél. Az osztály feltételezi a MySQL 5.1 vagy későbbi kiadású adatbázisszervert, továbbá a tranzakció kezelés végett az InnoDB adattábla típus javasolt.
Az ábrán a mezőket b-től f-ig neveztem el, míg az egyedi azonosítók nincsenek feltüntetve az egyszerűbb szemléltetés végett (pl.: a[id] = 1, b[id] = 2, c[id] = 3 …).
Az adatszerkezetnél megfigyelhető:
A táblát
Az osztály neveAzért, hogy az osztály a jövőben is felhasználható legyen, a tábla értékei tetszőleges mezőkkel kiterjeszthetők lesznek. A cikkben az
Felvesszük az adatbázisba a
Azon elemeket, melyeknek nincs gyermekük, levelek nevezzük. A levelekre igaz, hogy elem[jobb] − elem[bal] = 1. A függvény lényege a következő lekérdezés:
A feladatot aCsomópont levelei azok az elemek, amelyeknek már nincs gyermeke, de egy közös (tetszőleges) őstől származnak.
Egyes esetekben a csomópontnak is szerepelnie kell az eredményhalmazban, máskor nem, ezért erre felkészítjük a metódust.
Az eddig tárgyalt lekérdezéseket érdemes egy helyre gyűjteni, és a
A csomópont bal és jobb értéke fontos adat, ezért azt a programkódban érdemes meghatározni.
A példa elején lévő csomópont bal és jobb értékének a meghatározása egy összetettebb
A funkció teljes kódja:
A metódus működése és paraméterei hasonlóak lesznek a levelek lekérdézéséhez. Szükség lehet a teljes fára, egy részfára és egy olyan részfára, amikor a csomópont is benne van a listában.
Végeredményként a hierarchiát listákban, kombinált listákban, táblázatokban, menüpontokban láthatjuk viszont. Azért, hogy a szülő–gyermek viszonyt később szemléltetni tudjuk, a mélységet is visszaadja a metódus. Tekinthetjük a fa tetjét nulla mélységnek, de a kód alapértelmezésként a csompópontot tekinti az induló pontnak a hierarchiában.
A lekérdezés váza a következő lesz:A metódus a feljebb tárgyalt igényeknek is meg kell hogy feleljen, ezért a lekérdezésekből több variációt is készít, továbbá a mélység-eltolódással nem az SQL szervert terheljük, hanem a PHP kódra bízzuk. A metódus fejléce a következő lesz:
Egy csomópont szülőire a csomóponttal és a csomópont nélkül lehet szükségünk.
A lista egy asszociatív tömbben fog elhelyezkedni, amiben az egyedi azonosító és a csomópont neve fog szerepelni. Az SQL kód a következő:A metódus a következő lesz:
Ahogy a problémát megértjük, úgy fogunk rájönni, hogy ez az adattárolási forma nem kifejezetten kedvez a közvetlen gyermekek lekédezésének. Azt tudjuk, hogy a csomópont gyermekei egy szintel mélyebben helyezkednek el, mint a megadott csomópont, azt azonban nem tudjuk, hogy a megadott csomópont hol is helyezkedik el a hierarchiában. Első lépésben így a gyermekek mélységét, azaz szülő mélysége+1-et kell meghatároznunk. Ha a mélység megvan, akkor az összes adott mélységű elemet le kell kérdeznünk, akiknek a szülője azonos, azaz a bal és jobb értékeik a szülő bal és jobb értéke között helyezkednek el. A lekérdezések a következők lesznek:
A metódust fel kell készíteni továbbá, hogy a legfelső szintű elmeket is lekérdezze. A metódust a
Az testvérek lekérdezése még kevésbé erőforrásmentes, mint amit az előbbi példában láthattunk. Az elv hasonló a közvetlen gyermekerk meghatározásához, annyi különbséggel, hogy itt először a szülőt kell meghatározni. A szülő meghatározását követően az implementáció megegyezik az előbbiekben tárgyaltakkal. A testvérek kinyerésénél még előfordulhat, hogy nincs szükségünk magára a csomópontra amit megadtunk. A megvalósítás a
A hierarchia módosítása még érdekesebb és egyeben bonyolultabb feladat. Ha a téma érdekel, és lenne kedved továbbdolgozni, örömmel várnám a cikk IV. részét.
■ A sorozatban megjelent
- Hierarchikus adatkezelés SQL-lel PHP-ben I.
- Hierarchikus adatkezelés SQL-lel PHP-ben II.
- Hierarchikus adatkezelés SQL-lel PHP-ben III.
Ismétlés
A relációs adatbázisok nem támogatják a hierarchikus adattárolást, a hierarchikus listák tárolására azonban különböző lehetőségek állnak rendelkezésre. A cikkben tárgyalt eljárás olyan listák esetén használható fel hatékonyan, ahol a lekérdezések száma nagyságrendekkel magasabb, mint a módosításoké (törlés, létrehozás, mozgatás). Az alábbi ábrán lévő megoldást alkalmazzuk:1. ábra – hierarchikus adatszerkezet
- Egy számlálót 1-től indítva folyamatosan növelünk, majd az összes elem bal és jobb oldalához rendelünk.
- A számozást a lista csúcsától kezdjük, az első elemnek a bal oldalát megszámozzuk (b[bal] = 1).
- Ha az aktuális elemnek van gyermeke, akkor a gyermekre lépünk, és a bal értéket a számláló értékére állítjuk (c[bal] = 2).
- Ha az aktuális elem nem szülő (nincs gyermeke), akkor a jobb oldalához rendeljük a számláló értékét (d[jobb] = 4).
- A jobb oldali értéket követően, ha az elemnek van testvére, akkor annak bal értékét állítjuk be (d[bal] = 5).
- Ha nem szülő, és testvére sincs, akkor a szülője jobb oldalának adjuk a számláló értékét (c[jobb] = 7).
- Addig folytatjuk az elemek bal és jobb oldalának a meghatározását, amíg el nem érjük a legfelső szint utolsó elemének jobb oldali értékét (b[jobb] = 10).
Az ábrán a mezőket b-től f-ig neveztem el, míg az egyedi azonosítók nincsenek feltüntetve az egyszerűbb szemléltetés végett (pl.: a[id] = 1, b[id] = 2, c[id] = 3 …).
Az adatszerkezetnél megfigyelhető:
- az elem levél (azaz nincs gyermeke), ha elem[jobb] − elem[bal] = 1;
- a szülő gyermekeinek száma: (szülő[jobb] − szülő[bal] − 1) / 2;
- a gyermek szülője az az elem, amelyre: gyerek[bal] > szülő[bal] és gyerek[jobb] < szülő[jobb];
- a két érték (bal, jobb) közül egyik mindig páratlan, míg a másik páros érték;
- az első szintű elemek páratlan, a második szintűek páros bal értéket vesznek fel, és ez így ismétlődik, ahogy mélyül a hierarchia;
- az elemek mélységének meghatározására ez a módszer nem kielégítő;
- integritási hibát jelez, ha max_elem > számláló < 1, vagy a bal és jobb elemek közül valamelyik ismétlődik;
- amennyiben megsérül valamely elem bal vagy jobb értéke, csak manuális módon állítható helyre a hierarchia.
Az adattábla
Az első részben a hierarchia tárolása az azonosító és a szülő azonosítójának elmentésével történt. Ez a módszer gyors adatmódosítást, azonban lassú és nehézkes lekérdezést eredményezett. A második részben az elemek egyedi azonosítóját, bal és jobb értékét mentettük el. A MySQL-ben aleft
és right
szavak foglaltak, ezért a lft
és rgt
mezőket fogjuk használni az egyedi azonosító és az elem neve mellet.A táblát
hierarchy
néven hozzuk létre az alábbi mezőkkel:id
– int (egyedi azonosító)
name
– varchar(250) (név)
lft
– int (számláló bal oldali értéke)
rgt
– int (számláló jobb oldali értéke)
SQL script letöltése (853 byte)
Az új osztály
Hasonlóan a cikk második részéhez, egy új osztály létrehozása lesz a cél. A korábban már tárgyalt metódusokat azonban már a PHP 5 szigorúan objektumorientált programozási technikájának megfelelően, illetve a MySQL tranzakciókezelési lehetőségeit felhasználva fogjuk megvalósítani.Az osztály neve
clsDBHierarchy
lesz, a clsDBHierarchy.php
állományban tároljuk, és a PEAR:MDB2 osztálykönyvtárral fog együttműködni. Az osztály váza a következő:
<?php
class clsDBHierarchy
{
/** Hierarchia tábla neve */
protected $table;
/** adatbáziskezelő osztálykönyvtár (singleton - PEAR:MDB2) */
protected $db;
/** adatbázis és az adattábla képes e tranzakciókezelésre */
protected $transaction;
/** opcionális paraméterek a fában (hierarchia kiterjesztése */
protected $fields = array();
/* a fields változóból generált */
private $fieldsTag = '';
private $readMode = 'compact';
public function __construct($table = 'hierarchy', $transaction = true)
{
$this->db =& MDB2::singleton();
$this->table = $table;
$this->transaction = $transaction;
}
/** a hierarchia kiegészítő mezőinek meghatározása
*
* @param string mező neve a táblában
* @param string ...
*/
public function setFields() {
$numargs = func_num_args();
if ($numargs < 1) {
return false;
}
for ($i = 0; $i < $numargs; $i++) {
$this->fields[] = func_get_arg($i);
}
return true;
}
// …
?>
id
, lft
, rgt
mezők mellé a name
, mint szemléltető mező került felvételre. Azonban, ha más mezőket is szeretnénk felhasználni az adattárolásnál, akkor ennek megfelelően kiegészíthetjük az osztályt. A példa bemutatja az osztály felhasználását, továbbá a name
mezőt kiegészíti az age
és description
mezőkkel:
<?php
// PEAR osztálykönyvtár meghatározása
set_include_path('./pear/');
require_once 'MDB2.php';
// adatbáziskapcsolat beállításai
define('DB_SERVER', 'localhost'); // adatbázist tároló gép neve, vagy IP címe
define('DB_TYPE', 'mysqli'); // adatbázis típusa
define('DB_USER', 'hierarchy') // felhasználói név
define('DB_PASS', '12345'); // felhasználójának jelszava
define('DB_DATABASE', 'hierarchydb'); // adatbázis neve
define('DSN', DB_TYPE . '://' . DB_USER . ':' . DB_PASS . '@' . DB_SERVER . '/' . DB_DATABASE);
$options = array('debug' => 2, 'result_buffering' => false, 'portability' => MDB2_PORTABILITY_ALL);
$mdb2 =& MDB2::singleton(DSN, $options);
// hiba esetén a futás megszakad
if (PEAR::isError($mdb2)) {
die($mdb2->getMessage());
}
// asszociatív lekérdezési mód legyen az alapértelmezett
$mdb2->setFetchMode(MDB2_FETCHMODE_ASSOC);
// UTF-8 karakterkódolás használata
$mdb2->setCharset('utf8');
$hierarchy = new clsDBHierarchy('hierarchy', true);
// hierarchia kiegészítése a megjegyzés és kor mezőkkel
$hirearchy->addCustomFields('description', 'age');
$id_node = 123;
// $id_node csomópont szülő elemeinek a lekérdezése
$parents = hierarchy->getParents($id_node);
// szülők kiírása a képernyőre
print_r($parents);
?>
Adatszerkezet
2. ábra – összetettebb hierarchia
Felvesszük az adatbázisba a
hierarchy
táblát, amihez az egyedi azonosító, bal és jobb értékét és a név mezőneveket megadjuk. Ha további adatokat szeretnénk eltárolni, érdemes egy másik (adat) táblában rögzíteni ezeket.Tábladefiníció
hierarchy CREATE TABLE `hierarchy` (
`id` int(10) unsigned NOT NULL auto_increment,
`name` varchar(50) collate utf8_hungarian_ci default NULL,
`lft` int(10) unsigned default NULL,
`rgt` int(10) unsigned default NULL,
PRIMARY KEY (`id`),
KEY `idxLeft` (`lft`),
KEY `idxRight` (`rgt`)
) ENGINE = MyISAM AUTO_INCREMENT = 1 DEFAULT CHARSET = utf8 COLLATE = utf8_hungarian_ci;
Tesztadatok
INSERT INTO `hierarchy` (`id`,`name`,`lft`,`rgt`) values
(1,'a', 1, 30), (2, 'b', 2, 11), (3, 'c', 3, 8), (4, 'd', 4, 5),
(5, 'e', 6, 7), (6, 'f', 9, 10), (7, 'g', 12, 29), (8, 'h', 13, 22),
(9, 'i', 14, 19), (10, 'j', 15, 16), (11, 'k', 17, 18),
(12, 'l', 20, 21), (13, 'm', 23, 24), (14, 'n', 25, 26), (15, 'o', 27, 28);
Levél elemek kinyerése
3. ábra – levél elemek kinyerése
Azon elemeket, melyeknek nincs gyermekük, levelek nevezzük. A levelekre igaz, hogy elem[jobb] − elem[bal] = 1. A függvény lényege a következő lekérdezés:
SELECT id, name FROM hierarchy WHERE rgt - lft = 1 ORDER BY lft
A feladatot a
getAllLeaves()
metódus láthatná el (lásd később, miért nem).
<?php
/** Összes levél kinyerése az adatbázisból
*
* @return array array(($id), ...)
*/
public function getAllLeaves()
{
$res = array();
$sql = "SELECT id, name FROM {$this->table} WHERE rgt - lft = 1 ORDER BY lft";
$arrData = $this->db->query($sql)->fetchRows();
foreach($arrData as $data) {
$res[$data['id']] = $data['name'];
}
return $res;
}
?>
4. ábra – kiválaszott csomópont levelei
Egyes esetekben a csomópontnak is szerepelnie kell az eredményhalmazban, máskor nem, ezért erre felkészítjük a metódust.
5. ábra – kiválaszott csomópont levelei II.
Az eddig tárgyalt lekérdezéseket érdemes egy helyre gyűjteni, és a
getLeaves()
metódust kiterjeszteni.A csomópont bal és jobb értéke fontos adat, ezért azt a programkódban érdemes meghatározni.
-- a csomópont bal és jobb értékének meghatározása
SELECT lft, rgt FROM hierarchy WHERE id = {id_node}
-- összes levélelem
SELECT lft, rgt FROM hirearchy WHERE id = 1
ORDER BY lft;
-- egy csomópont alatti levelek
SELECT lft, rgt FROM hirearchy
WHERE rgt - lft = 1
AND lft > {node_left} AND rgt < {node_right}
ORDER BY lft;
-- csomópont is szerepeljen a listában
SELECT lft, rgt FROM hirearchy
WHERE node = {id_node}
OR (id = rgt - lft = 1 AND (lft > {node_left} AND rgt < {node_right})
A példa elején lévő csomópont bal és jobb értékének a meghatározása egy összetettebb
SELECT
-tel is megvalósítható lett volna, azonban látni fogjuk a későbbi metódusok összetettségét és az okot, hogy miért PHP-ban lett megvalósítva. A metódus fejléce a következő lesz: getLeaves($node = '', $inNode = false)
, továbbá a getAllLeaves()
függvény elhagyható az osztályunkból, mert egyszerűen egy üres sztringet megadva a metódus visszaadhatja az összes levelet. Nem létező vagy hibás paraméterrel megadott csomópont esetén a visszatérési érték egy üres tömb lesz. A rendezés következtében a csomópont mindig az első helyen fog szerepelni a lekérdezési tömbben.A funkció teljes kódja:
<?php
/** Levél elemek kinyerése az adatbázisból
*
* @param int $node csak a csomópont alatti levelek igénye (alapértelmezés: teljes fa)
* @param bool $inSelf maga a csomópont is benne lesz a lekérdezésben, ha igaz (alapértelmezés: hamis)
*
* @return array array(['id' => 'name', ...])
*/
public function getLeaves($node = '', $inNode = false)
{
if ($node == '') {
// teljes fa lekérdezése
$sql = "SELECT id, name
FROM {$this->table}
WHERE rgt - lft = 1
ORDER BY lft";
$arrData = $this->db->query($sql)->fetchAll();
$res = array();
foreach($arrData as $data) {
$res[$data['id']] = $data['name'];
}
} else {
// megadott csomópont alatti elemek lekérdezése
$sql = "SELECT lft, rgt FROM {$this->table} WHERE id = " . $this->db->quote($node, 'integer');
//$row = $this->db->query($sql)->fetchRow();
list($parent_left, $parent_right) = $this->db->query($sql)->fetchRow(MDB2_FETCHMODE_ORDERED);
if ($inNode) { // csomópont is benne lesz listában
$sql = "SELECT id, name
FROM {$this->table}
WHERE lft = " . $this->db->quote($parent_left) . "
OR rgt - lft = 1
AND lft > " . $this->db->quote($parent_left) . "
AND rgt < " . $this->db->quote($parent_right) . "
ORDER BY lft";
} else { // csomópont nélküli lista
$sql = "SELECT id, name
FROM {$this->table}
WHERE rgt - lft = 1
AND lft > " . $this->db->quote($parent_left) . "
AND rgt < " . $this->db->quote($parent_right) . "
ORDER BY lft";
}
echo $sql;
$arrData = $this->db->query($sql)->fetchAll();
$res = array();
foreach($arrData as $data) {
$res[$data['id']] = $data['name'];
}
}
return $res;
}
?>
Részfa kinyerése
6. ábra – részfa kinyerése
7. ábra – részfa kinyerése (csomóponttal)
A metódus működése és paraméterei hasonlóak lesznek a levelek lekérdézéséhez. Szükség lehet a teljes fára, egy részfára és egy olyan részfára, amikor a csomópont is benne van a listában.
Végeredményként a hierarchiát listákban, kombinált listákban, táblázatokban, menüpontokban láthatjuk viszont. Azért, hogy a szülő–gyermek viszonyt később szemléltetni tudjuk, a mélységet is visszaadja a metódus. Tekinthetjük a fa tetjét nulla mélységnek, de a kód alapértelmezésként a csompópontot tekinti az induló pontnak a hierarchiában.
A lekérdezés váza a következő lesz:
SELECT node.id AS id
, node.name AS name
, COUNT(parent.name)-1 AS depth
FROM hierarchy AS node
, hierarchy AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
ORDER BY node.lft
getTree($node = '', $inNode = false, $relDepth = true)
, és a kód:
<?php
/** Fa/Részfa kiolvasása
*
* @param int $node csak a csomópont alatti levelek igénye (alapértelmezés: teljes fa)
* @param bool $inSelf maga a csomópont is benne lesz a lekérdezésben, ha igaz (alapértelmezés: hamis)
* @param bool $relDepth relatív mélység korrekció (alapértelmezés: bekapcsolva)
*
* @return array array(['id' => 'name', ...])
*/
public function getTree($node = '', $inNode = false, $relDepth = true)
{
if ($node == '') {
// teljes fa lekérdezése
$sql = "SELECT node.id AS id
, node.name AS name
, COUNT(parent.name) - 1 AS depth
FROM {$this->table} AS node
, {$this->table} AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
ORDER BY node.lft";
$res = $this->db->query($sql)->fetchAll();
} else {
$sql = "SELECT lft, rgt FROM {$this->table} WHERE id=" . $this->db->quote($node, 'integer');
list($parent_left, $parent_right) = $this->db->query($sql)->fetchRow(MDB2_FETCHMODE_ORDERED);
if ($inNode) { // csomópont is benne lesz listában
$parent_left--;
$parent_right++;
}
$sql = "SELECT node.id AS id
, node.name AS name
, COUNT(parent.name) - 1 AS depth
FROM {$this->table} AS node
, {$this->table} AS parent
WHERE node.lft > {$parent_left}
AND node.rgt < {$parent_right}
AND node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
ORDER BY node.lft";
$res = $this->db->query($sql)->fetchAll();
// relatív mélység korrekció (csomópont mélység: 0)
if ($relDepth) {
if (isset($res[0])) {
$nodeDepth = $res[0]['depth'];
for ($a = 0; $a < count($res); $a++) {
$res[$a]['depth'] -= $nodeDepth;
}
}
}
}
return $res;
}
?>
Szülők kiolvasása
8. ábra – elem őseinek megállapítása
Egy csomópont szülőire a csomóponttal és a csomópont nélkül lehet szükségünk.
A lista egy asszociatív tömbben fog elhelyezkedni, amiben az egyedi azonosító és a csomópont neve fog szerepelni. Az SQL kód a következő:
SELECT id, name
FROM hierarchy
WHERE (lft < {node_left} AND rgt > {node_right}) OR id = {id_node}
ORDER BY lft
getParents($node = '', $inNode = false)
, a kód:
<?php
/** Elem szülőinek a kinyerése
*
* @param int $node csak a csomópont alatti levél elemek igénye (alapértelmezés: teljes fa)
* @param bool $inSelf maga a csomópont is benne lesz a lekérdezésben, ha igaz (alapértelmezés: hamis)
*
* @return array array(['id' => 'name', ...])
*/
public function getParents($node, $inNode = false)
{
$sql = "SELECT lft, rgt FROM {$this->table} WHERE id = " . $this->db->quote($node, 'integer');
list($node_left, $node_right) = $this->db->query($sql)->fetchRow(MDB2_FETCHMODE_ORDERED);
if ($inNode) { // csomópont is benne lesz listában
$sqlOrNode = "OR id = {$node}";
}
$sql = "SELECT id, name
FROM {$this->table}
WHERE lft < {$node_left} AND rgt > {$node_right} {$sqlOrNode}
ORDER BY lft
";
echo $sql;
$arrData = $this->db->query($sql)->fetchAll();
$res = array();
foreach($arrData as $data) {
$res[$data['id']] = $data['name'];
}
return $res;
}
?>
Csomópont közvetlen gyermekei
9. ábra – csomópont kövzvetlen gyerekeinek a megállapítása
Ahogy a problémát megértjük, úgy fogunk rájönni, hogy ez az adattárolási forma nem kifejezetten kedvez a közvetlen gyermekek lekédezésének. Azt tudjuk, hogy a csomópont gyermekei egy szintel mélyebben helyezkednek el, mint a megadott csomópont, azt azonban nem tudjuk, hogy a megadott csomópont hol is helyezkedik el a hierarchiában. Első lépésben így a gyermekek mélységét, azaz szülő mélysége+1-et kell meghatároznunk. Ha a mélység megvan, akkor az összes adott mélységű elemet le kell kérdeznünk, akiknek a szülője azonos, azaz a bal és jobb értékeik a szülő bal és jobb értéke között helyezkednek el. A lekérdezések a következők lesznek:
-- mélység lekérdezése
SELECT count(*) + 1 as depth
FROM hierarchy
WHERE lft < {node_left} AND rgt > {node_right}
ORDER BY lft; --> {children_depth}
-- a gyermekek lekérdezése
SELECT node.id AS id
, node.name AS name
FROM hierarchy AS node,
hierarchy AS parent
WHERE node.lft > (node_left) and node.rgt < {node_right}
AND node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
HAVING COUNT(parent.name)-1 = {children_depth}
ORDER BY node.lft
A metódust fel kell készíteni továbbá, hogy a legfelső szintű elmeket is lekérdezze. A metódust a
getChildren($node = '')
fejléccel hozzuk létre, a kód a következő:
<?php
/** elem gyermekeinek lekérdezése
*
* @param csomópont meghatározása (nem kötelező, alapértelmezés szerint gyökér)
*
*/
function getChildren($node = '')
{
// ha nem
if ($node != '') {
$sql = "SELECT lft, rgt FROM {$this->table} WHERE id = " . $this->db->quote($node, 'integer');
list($node_left, $node_right) = $this->db->query($sql)->fetchRow(MDB2_FETCHMODE_ORDERED);
// csomópont alatti elemek meghatározása
$sql = "SELECT count(*) + 1 as depth
FROM hierarchy
WHERE lft < {$node_left} AND rgt > {$node_right}
ORDER BY lft";
$children_depth = $this->db->query($sql)->fetchOne();
// gyerek elemek lekérdezése
$sql = "SELECT node.id AS id
, node.name AS name
FROM hierarchy AS node,
hierarchy AS parent
WHERE node.lft > ($node_left) and node.rgt < {$node_right}
AND node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
HAVING COUNT(parent.name) - 1 = {$children_depth}
ORDER BY node.lft";
} else { // legfelső színtű csomópontok meghatározása
$sql = "SELECT node.id AS id
, node.name AS name
FROM hierarchy AS node,
hierarchy AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
HAVING COUNT(parent.name) - 1 = 0
ORDER BY node.lft";
}
$arrData = $this->db->query($sql)->fetchAll();
$res = array();
foreach($arrData as $data) {
$res[$data['id']] = $data['name'];
}
return $res;
}
?>
Elem testvérei
10. ábra – testvérelemek megállapítása
Az testvérek lekérdezése még kevésbé erőforrásmentes, mint amit az előbbi példában láthattunk. Az elv hasonló a közvetlen gyermekerk meghatározásához, annyi különbséggel, hogy itt először a szülőt kell meghatározni. A szülő meghatározását követően az implementáció megegyezik az előbbiekben tárgyaltakkal. A testvérek kinyerésénél még előfordulhat, hogy nincs szükségünk magára a csomópontra amit megadtunk. A megvalósítás a
getBrothers($node, $inNode = false)
metótusban öltött testet:
<?php
/** Csomópont testvérelemeinek a lekérdezése
*
* @param string $node csomópont meghatározása
* @param bool $inNode a csomópont szerepeljen e a listában (alapértelmezésként nem)
* @return array array(['id' => 'name', ...])
*/
public function getBrothers($node, $inNode = false) {
// csomópont bal és jobb értékének kiolvasása
$sql = "SELECT lft, rgt FROM {$this->table} WHERE id = " . $this->db->quote($node, 'integer');
list($node_left, $node_right) = $this->db->query($sql)->fetchRow(MDB2_FETCHMODE_ORDERED);
// csomópont szülő elemének meghatározása
$sql = "SELECT parent.id
FROM hierarchy AS node
, hierarchy AS parent
WHERE parent.lft < {$node_left} AND parent.rgt > {$node_right}
AND parent.lft < node.lft
AND parent.rgt > node.rgt
ORDER BY parent.lft DESC
LIMIT 1";
$parent_id = $this->db->query($sql)->fetchOne();
// ha a csomópontnak van szülő eleme (nem őselem)
if ($parent_id != "") {
// szülő bal és jobb értékének kiolvasásása
$sql = "SELECT lft, rgt FROM {$this->table} WHERE id={$parent_id}";
list($parent_left, $parent_right) = $this->db->query($sql)->fetchRow(MDB2_FETCHMODE_ORDERED);
// csomópont elhelyezkedésének mélysége a hierarchiában
$sql = "SELECT count(*)+1 as depth
FROM hierarchy
WHERE lft < {$parent_left} AND rgt > {$parent_right}
ORDER BY lft";
$children_depth = $this->db->query($sql)->fetchOne();
// csomópont ne szerepeljen a listában
if (!$inNode) {
$sqlNoNode = " AND node.id <> ".$this->db->quote($node, 'integer');
}
// gyerek elemek lekérdezése
$sql = "SELECT node.id AS id
, node.name AS name
FROM hierarchy AS node,
hierarchy AS parent
WHERE node.lft > ($parent_left) and node.rgt < {$parent_right}
AND node.lft BETWEEN parent.lft AND parent.rgt {$sqlNoNode}
GROUP BY node.name
HAVING COUNT(parent.name)-1 = {$children_depth}
ORDER BY node.lft";
$arrData = $this->db->query($sql)->fetchAll();
} else { // ha a csomópont őselem (nincs szülője)
$sql = "SELECT node.id AS id
, node.name AS name
FROM hierarchy AS node,
hierarchy AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
HAVING COUNT(parent.name)-1 = 0
ORDER BY node.lft";
$arrData = $this->db->query($sql)->fetchAll();
}
$res = array();
foreach($arrData as $data) {
$res[$data['id']] = $data['name'];
}
return $res;
}
?>
Zárszó
A bal és jobb érték és egy kis matematika felhasználásával programunkkal viszonylag egyszerűen le tudtunk kérdezni egy hierarchikus adatszerkezetet. A cikk önmagában nem állja meg a helyét, hiszen kézzel szinte lehetetlen az adatok felvitele, ezért a következő részben megismerhetjük az adatok felvitelét, törlését és a csomópontok, levelek átmozgatását.A hierarchia módosítása még érdekesebb és egyeben bonyolultabb feladat. Ha a téma érdekel, és lenne kedved továbbdolgozni, örömmel várnám a cikk IV. részét.
Oracle & Postgres
Adatbázis kezelő rétegek
cakePHP
-cs-
Sanyi
Filerendszer
Nyisd meg a kódját :)
Hasonlóság az XMLel
Még nem olvastam el a cikket, sajnos nem volt rá időm, viszont arra gondoltam, hogy egy hierarchikus adatkezelés valamennyire hasonlít az XMLre, szóval akár lehetne írni olyan osztályt is, ami az XPath bizonyos elemeit használja a lekérdezésekhez, az SQLt pedig ez alapján generálja. Csomópontok kezelésénél a DOM és az XPath szerintem már elég jól bevált, ezért gondolom azt, hogy lehet, hogy jobb lenne átvenni az ottani szintaxist. (Nem feltétlenül a teljeset, csak a szükséges elemeket.)
Erről mi a véleményed?
XML, JQuery
public function update($id_node){}
public function insert($node, $after=true){}
public function addParent($node, $wrap=false){}
public function addChild($node, $last=true){}
public function delete($node, $delChildren=false, $inNode=true){}
A wrap annyit jelent, hogy a megadott csomópont az új elem gyereke lesz, avagy sem. A csomópont átrendezésével még nem foglalkoztam.
:-)
furcsaság a cikkben
Ezt a részt nem is értem (az indoklást a hülyenév használatra). A MySQL remekül támogatja évek óta az escape-elést, a `left` és `right` a fordított aposztrófokkal remekül használható mezőnévként. A fordított aposztróf nem csak valami látványelem. Illett volna utánanézni ennek az egészen alapvető dolognak, mert ez a sületlenség valahogy keményen kilóg a cikkből, ami egyébként szerintem remek, és nagy jelentőségű a közösség szélesebb rétegeinek okosítása tekintetében.
És még egy kis apróság.
Minden esetre erősíthetőnek látom a szerkezetet úgy, hogy ha a fenti három főértékhez (id, left, right) letárolunk egy negyediket is, a parentet. Ha left/right érték sérül, a parentek alapján rekurzív technikával újraépíthető a struktúra, az alapelvek nem sérülnek. Ha a kiírást két lépésben valósítjuk meg, először a parent kiírásával, és csak utána a bal/jobb érték kiírásával, akkor a két lépés között rekurzívan ellenőrizhető is a konzisztencia, és szükség szerint javítható.
integritási hiba
Korábbi hozzászólásodban kérdezted, hogy a left és right foglalt neveket miért is említettem meg. Több oka volt, egyrészt nem szeretem az escape-elést. Mert valóban foglalt név és ez is érdekesség: http://dev.mysql.com/doc/refman/5.0/en/reserved-words.html. Az internetről Mike Hillyer kiváló írását értelmezve http://dev.mysql.com/tech-resources/articles/hierarchical-data.html sajátítottam el az elméleti alapokat.
Bár lehet, hogy közhely, de még az első hozzászólásokból érdeklődtek, hogy miért is írtam meg ezt a cikket, hiszen számos ember megtette korábban előttem. Egyszerűen, mert magyarul nem találkoztam elég egyszerű és megfelelően komplex leírással. Továbbá sajnáltam volna az első két cikket nem folytatni, azok után, hogy megismertem az elméleti részét a nested tree-knek.
Gráfok
Erről tudtok adni valami olyan linket, amiből tanulni lehet?
Illetve fentebb szó esett, hogy ilyen típusú adattárolásnál (mármint a fa szerkezetnél) érdemes még eltárolni a mélységet és a "sorrendet (order)".
A sorrenden mit értetek?
Ilyennel még úgy komolyabban nem volt dolgom, úgyhogy nem tudom értelmezni ezt a részét, mert ha eltároljuk a jobb és bal értékét, a mélységét akkor mi lenne a sorrend?
Nem így
Mindenesetre általános gráfok tárolására léteznek komplex rendszerek, de ezek mindenképpen sokkal bonyolultabbak mint egy hierarchikus fa.
Ilyenek például a KiokuDB. És azért van pár cikk is erről.
Tudom
Sőt azzal is hogy vannak irányított gráfok, körök stb...
A mélységi és szélességi bejárás is megvan, csak az van, hogy eddig mindezt TurboPascalban tanultam ahol egy előre meghatározott mátrixot használtunk adattárolási célra. A már megszerzett tudásomat szerettem volna átültetni web-re, és úgy gondolom, hogy ha már mysqlban tárolom az adatokat van értelesebb módja is mint felvenni egy hatalmas mátrixot...
Köszi a linkek amiket adtál, mondjuk a KiokuDB kiesik alapból mert a Perl-t nem ismerem...
Engem am konkréten a gráfok eltárolása érdekelne...
Am még mindeig nem tudom mire jó a fa struktúránál a sorrend...
A hierarchikus listánál a
Bináris fa
Platformfüggetlenség
Vagy inkább létezik élet a MySQL-n túl is. Ha lehet, én pl. nem szeretek ilyen adott SQL specifikus dolgokat használni, lehetőség szerint minél inkább hordozható kódot írok. PostgreSQL-ben pl. az idézőjel közé kell tenni a mezőneveket, ha escapelni akarjuk. Másik kedvencem a LIMIT x,y. LIMIT n OFFSET m -t érti a Pg és a MySQL is, előzőt viszont nem.
mikor?
Kb mikorra lehet számítani a következő részre? nagyon érdekelne
Preorder iteratív bejárás
Kicsit át kellett szerkesztenem, végülis teljes sikerrel jártam, miután átírtam :)
Bővebb infó az algoritmusról PHP nyelven: itt
Nem rossz
Én mondjuk csináltam egy Fa nevű osztályt, amibe felépítek egy DOM szerű struktúrát tömbökből (nem Elementekből), és oda szórom be a sorokat, aztán pedig egy rekurzív megjelenítővel jelenítem meg őket. Előnye, hogy a rekurzív megjelenítőm úgy van megírva, hogy sablon-ból be lehessen lőni, hogy egy levélnek, ill. ágnak milyen legyen a HTML (vagy egyéb) kódja, hátránya, hogy a köztes lépés miatt valamivel lassabb.
Mondjuk a rendszer nem csak ilyesmire jó, hanem valamilyen fa visszakonvertálására sorokká, stbstb... Persze ezt még át kell gondolni, hogy a modell és a megjelenítés különváljanak (valszeg nem csak 1 osztály lesz belőle).
Egyelőre még ismerkedem a hierarchikus dolgokkal, de nagyon tetszik ez a fajta megközelítés.
Csatlkoznék nf3rno korábbi
sql lekérdezés nem működik
Elkezdtem átkonvertálgatni a példa programot PDO-ra, illetve ezen belül is postgreSQL-re...
De a következő sql kérésnél hibával leáll:
ERROR: column "node.g_id" must appear in the GROUP BY clause or be used in an aggregate function
LINE 1: SELECT node.g_id AS id, node.g_name AS name, COUNT(*) - 1 AS...
Aggregate
Itt amúgy egy speciális esetről van szó. A node.g_id és node.g_name egy-egy kapcsolatban vannak - egy name csak egyszer és egy id-vel szerepel - vagyis mindegy melyikre GROUP BY-olunk az eremény ugyanaz lesz (e két mező felfogható egyetlen mezőként, ezért ez nem logikai hiba). A probléma, hogy ezt az adatbázis kezelőnek senki nem mondta meg.