ugrás a tartalomhoz

Hierarchikus adatkezelés SQL-lel PHP-ben III.

RajcsanyiZ · 2009. Júl. 16. (Cs), 10.40
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.

A sorozatban megjelent

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 a left é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)


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;
  }
  
  // …
?>
Azé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 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; 
  }
?> 
Csomópont levelei azok az elemek, amelyeknek már nincs gyermeke, de egy közös (tetszőleges) őstől származnak.

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  
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: 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
A metódus a következő lesz: 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.
 
RajcsanyiZ arcképe
RajcsanyiZ
Web alapú programokat fejlesztek. Laravel (PHP alapú) backendet használom az utóbbi években. Kedvelem az alkalmazkodó (responsive) dizájnt, megtámogatva a bootstrap kertrendszerrel és a JQuery javascript toolkit-el. Személyes oldalam: http://rajcsanyizoltan.hu.
1

Oracle & Postgres

Unicorn · 2009. Júl. 16. (Cs), 11.07
Az Oracle nagyon szépen támogatja a hierarchikus lekérdezéseket a START WITH és a CONNECT BY parancsokkal (elég gyors!) Az adatbázisunk intenzíven használ hierarchiákat nem csak olvasásra, hanem írásra is. Sajnos a nested tree párezer rekordnál már használhatatlanná vált ha átrendezés volt, ezért is döntöttünk Oracle mellett. A postgreshez is van kiegészítő, de ha jól emlékszem az nem volt annyira kidolgozott mint az Oracle féle. http://www.postgresql.org/docs/current/static/tablefunc.html
2

Adatbázis kezelő rétegek

fchris82 · 2009. Júl. 16. (Cs), 11.51
A Propelben és a Doctrine-ban is van erre kész megoldás, pontosan ugyan így. Ha vki nem szeretné saját maga megírni az egészet. Hasznos és tanulságos lehet az ottani forráskód tanulmányozása, ha vki nem bírja ki a cikk megjelenését, és kell is neki ;)
3

cakePHP

carstepPCE · 2009. Júl. 16. (Cs), 14.39
Anno a cakePHP-ban is volt az ACL kezeleseben erre megoldas, de sajnos eleg bugos volt. en kijavitottam oket, de azert illett volna nekik is hibatlanul megirni. :-)

-cs-
Sanyi
4

Filerendszer

janoszen · 2009. Júl. 17. (P), 07.12
Húúúú annak idején én SQL-ben tárolt eljárásokkal írtam egy komplett filerendszer-implementációt. Még NTFS-féle ACL-eket is támogatott. Azt hiszem, erre mondják, hogy beteg. :) Azon voltam, hogy írok hozzá WebDAV connectort és FUSE plugint, aztán valahol elmaradt az egész projekt mert nem volt rá érdeklődés.
6

Nyisd meg a kódját :)

prom3theus · 2009. Júl. 23. (Cs), 11.02
Biztos lenne aki tanuljon belőle (engem legalábbis érdekelne, bár nekem most az lett a heppem, hogy egy régi fájlrendszer tervemet PHP wrapper-ként valósítom meg - szvsz ez se kisebb betegség :D)
5

Hasonlóság az XMLel

inf3rno · 2009. Júl. 21. (K), 19.01
Szia!
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?
9

XML, JQuery

RajcsanyiZ · 2009. Júl. 30. (Cs), 20.22
A cikk írásakor a DOM kifejezetten felkeltette az érdeklődésemet amikor az írási műveletekkel kezdtem el foglalkozni. A JQuery névtere nagyon megtetszett, több parancsot, de kicsit máshogy, számomra egyszerűbben készítettem el. Javaslom a IV cikk publikálását követően térjünk vissza a az egyszerűsítésre. Annyit előre megosztok veletek, hogy a metódusok fejléce a következő lesz:

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.
11

:-)

inf3rno · 2009. Júl. 31. (P), 20.47
A 4. cikk mikor jön ki? Kíváncsian várom.
7

furcsaság a cikkben

prom3theus · 2009. Júl. 23. (Cs), 11.06
A MySQL-ben a left és right szavak foglaltak, ezért a lft és rgt mezőket fogjuk használni


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.
8

És még egy kis apróság.

prom3theus · 2009. Júl. 23. (Cs), 11.26
És még egy kis apróság. Ahogyan a szerző is írja, hátránya a fenti megoldásnak, hogy bal vagy jobb érték sérülése esetén a szerkezet csak kézzel állítható helyre. Szerintem nem ártott volna egy-két példát felhozni arra, miért történhet meg, hogy egy bal vagy jobb érték megsérüljön. Korrekt algoritmussal nem kaphat téves értéket. Nagy írási terhelés mellett történhetnek galibák, de a cikk már az elején leszögezi, hogy a módszer nem erre lett kihegyezve, így igazából ez is kilőve. Megfelelően használva a tranzakciókat, más jellegű hiba sem forulhat elő, legfeljebb valami természeti csapás :)

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ó.
10

integritási hiba

RajcsanyiZ · 2009. Júl. 30. (Cs), 21.14
Tranzakció és hibakezeléssel az integrációs hibák száma a programozói oldalról közel 0-ra redukálható. Azonban az adatbázisszerverből, vagy netán hardverhibából adódó komplikációkra nem tudunk felkészülni. Főleg nagy hierarchiák esetén egyes ágak kiesnek, más ágak rossz helyre kerülnek, továbbá eltorzítják a fát. A hiba lehetősége elenyésző, de ha nagyobb szerkezetben előfordul, akár javíthatatlan károkat is okozhat, nem beszélve a portál leállásáról. Éles rendszerben a szülő elem (id_parent) elhelyezése kötelező, amíg a mélység (depth) és a sorrend (order) javasolt. Hiba esetén az eredeti struktúra csak az id_parent és az order mezők segítségével állítható hiánytalanul vissza.

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.
13

Gráfok

festo · 2009. Aug. 14. (P), 19.29
Így a téma folyamán felmerült bennem az a kérdés, hogy hogyan érdemes mondjuk egy ismeretségi gráfot tárolni, ahol a lekérdezések és a módosítások száma is magas?
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?
14

Nem így

Poetro · 2009. Aug. 14. (P), 20.10
Hát az biztos, hogy nem így, ugyanis egy gráf nem hierarchikus, ráadásul lehet benne körkörösség. Még ha a körkörösséget el is vesszük, akkor is fontos lehet hogy a gráf az irányított-e.
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.
15

Tudom

festo · 2009. Aug. 16. (V), 18.13
Tisztában vagyok vele, hogy nem így kell.
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...
16

A hierarchikus listánál a

RajcsanyiZ · 2009. Aug. 31. (H), 20.20
A hierarchikus listánál a sorrend az egy szinten lévő elemek egymáshoz viszonyított sorrendjének megállapítására szolgál. A sorrend a hierarchia bejárásánál és a fa újraépítésénél szükséges. Még a hozzászólást korrigálnám a cikk nem faszerkezetet vizsgál, hanem hierarchikus adattárolást. A fa szerkezetben csak két gyereke lehet minden elemnek, az itt tárgyalt cikkben pedig korlátlan számú. Azaz a faszerkezet a hierarchikus lista egy részhalmaza. Amennyiben a hierarchiában hurok képződne a cikk által bemutatott adatszerkezetben, az a szerkezet és a program tönkremenetelét jelentené. Igen érdekes lenne egy olyan cikk is, ami bonyolultabb adatszerkezetekkel is foglalkozna. Talán valaki kedvet kap egy ilyen cikk kidolgozására.
17

Bináris fa

Poetro · 2009. Aug. 31. (H), 23.01
A cikk egy bináris fa ábrázolással épít fel egy fát. A fa ebben a tekintetben abban speciális, hogy kineveztünk egy gyökeret neki. Amennyiben lenne benne kör, akkor nem lenne fa.
12

Platformfüggetlenség

saxus · 2009. Aug. 5. (Sze), 21.25
A fordított aposztróf nem csak valami látványelem.


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.
18

mikor?

agyergorcs · 2009. Okt. 4. (V), 14.04
Hali,

Kb mikorra lehet számítani a következő részre? nagyon érdekelne
19

Preorder iteratív bejárás

rviktor87 · 2009. Nov. 27. (P), 02.43
Épp most írom a szakdogám, és pont ilyesmivel foglalkoztam. Volt egy DOM fát felépítő adatbázisom, ami tárolja a bal-gyereket és a jobb-testvért. A szülő jelzésére végülis nem kellet külön oszlop. A célom az volt, hogy hierarchikusan olvassa be a MySQL adatbázisom, majd utána a megfelelő helyen zárja be a tagokat az algoritmus. A preorder (szülőből induló) iteratív algoritmusra itt találtam.
Kicsit át kellett szerkesztenem, végülis teljes sikerrel jártam, miután átírtam :)
Bővebb infó az algoritmusról PHP nyelven: itt
20

Nem rossz

inf3rno · 2009. Nov. 28. (Szo), 05.43
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.
21

Csatlkoznék nf3rno korábbi

nazinorbi · 2012. Feb. 17. (P), 23.27
Csatlkoznék nf3rno korábbi hozászolásához és pedig mikor készül el a cikk 4. része??? Nagyon Várom
22

sql lekérdezés nem működik

Theo76 · Dec. 21. (Sze), 11.32
Sziasztok!

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:

SELECT node.g_id AS id,
       node.g_name AS name,
       COUNT(parent.g_name) - 1 AS depth
FROM groups AS node,
     groups AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.g_name
ORDER BY node.lft
A hibaüzenet:
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...
23

Aggregate

vbence · Dec. 21. (Sze), 13.40
Igen, valamire való SQL adatbázis nem enged keverni aggregált és nem-aggregált kifejezéseket. A COUNT eredménye több rekord összegzéséből jön ki, a node.g_name pedig fix (ezt kikötötted a GROUP BY kifejezésben), a kérdés, hogy melyik grouppolt rekord node.g_id -jét szeretnéd látni? A legkisebbet? Akkor módosítsd MIN(node.g_id) -re a SELECTben és megoldódik.

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.