List:Hamburg MySQL Users Group« Previous MessageNext Message »
From:Ralf Eggert Date:May 15 2007 10:21am
Subject:Re: [OT ?] Binaerbaum verschieben
View as plain text  
Hallo Lenz,

> Ich vermute Du kennst Mike Hillyer's Artikel über "Managing Hierarchical Data
> in MySQL"?  Hilft Dir das vielleicht weiter?
> 
> http://dev.mysql.com/tech-resources/articles/hierarchical-data.html

Danke für den Link. Nur wie viele andere Quellen hört der Artikel leider
genau da auf, wo es interessant wird. Es wird zwar das Auslesen, Anlegen
und Löschen erläutert, aber eben nicht das Verschieben von Teilbäumen.

Nach vielem Herumprobieren habe ich das Problem aber mittlerweile lösen
können. Im Anhang ist meine Methode zum Verschieben von Teilbäumen.
Bisher hat das Verschieben keinerlei Probleme gemacht. Ich weiss aber
nicht, ob es auch Situationen gibt, wo es nicht klappt. Ich verwende
Zend_Db aus dem Zend Framework, aber ich hoffe, das Prinzip wird anhand
der Inline Doku klarer.

Das Gute an der Lösung ist meiner Meinung nach, dass das Verschieben
wirklich nur mit Hilfe von drei UPDATEs realisiert wird. Vielleicht kann
ein schlauer Kopf aus meiner konkreten Umsetzung eine eher allgemein
gültige Lösung ableiten?

Mit freundlichem Gruß,

Ralf Eggert



    /**
     * Move destination subtree
     * 
     * Moves a destination from one superior node to another superior node
     * 
     * @param integer $id destination id 
     * @param integer $superior new superior id
     * @return boolean 
     */
    public function moveDestination($id = null, $superior = null)
    {
        // check for id
        if (is_null($id) || is_null($superior))
        {
            return false;
        }
        
        // read current and superior data
        $currentData  = $this->find($id);
        $superiorData = $this->find($superior);
        
        // check for recursive movements
        if (   $currentData['destination_left' ] < $superiorData['destination_left' ]
            && $currentData['destination_right'] > $superiorData['destination_right'])
        {
            return false;
        }
        
        // check for no movements
        if (   $currentData['destination_left' ] > $superiorData['destination_left' ]
            && $currentData['destination_right'] < $superiorData['destination_right']
            && $currentData['destination_level'] == $superiorData['destination_level'] + 1)
        {
            return false;
        }
        
        // build select to read all subordinate ids for subtree to be moved
        $select = $this->_db->select();
        $select->from('destination_main AS current_destination', array());
        $select->from('destination_main AS subordinate_destination', array('destination_id', 'destination_level'));
        $select->joinLeft('destination_text', 'subordinate_destination.destination_id = desttext_id', array('desttext_url'));
        $select->where('current_destination.destination_id = ?', $id);
        $select->where('subordinate_destination.destination_left >= current_destination.destination_left');
        $select->where('subordinate_destination.destination_left < current_destination.destination_right');
        $select->group('subordinate_destination.destination_id');
        $select->group('subordinate_destination.destination_left');
        
        // fetch datasets
        $subordinateIds = $this->_db->fetchAssoc($select);
        
        // calculate values
        $currentLeft   = $currentData ['destination_left' ];
        $currentRight  = $currentData ['destination_right'];
        $superiorLeft  = $superiorData['destination_left' ];
        $superiorRight = $superiorData['destination_right'];
        
        if ($currentRight < $superiorRight)
        {
            $min = $currentLeft;
            $max = $superiorRight;
            
            $add1 = $currentLeft - $currentRight - 1;
            $add2 = $superiorRight - $currentLeft;
        }
        else
        {
            $min = $superiorRight;
            $max = $currentRight + 1;
            
            $add1 = $currentRight - $currentLeft + 1;
            $add2 = $superiorRight - $currentRight - 1;
        }
        
        // calculate level
        $addlevel = $superiorData['destination_level'] - $currentData['destination_level'] + 1;
        
        // amend left values for tree
        $row  = array('destination_left' => new Zend_Db_Expr('destination_left + ' . $add1));
        $where = $this->_db->quoteInto('destination_left >= ?', $min);
        $where.= ' AND ' . $this->_db->quoteInto('destination_left < ?', $max); 
        $result = $this->_db->update($this->_name, $row, $where);
        
        // amend right values for tree
        $row  = array('destination_right' => new Zend_Db_Expr('destination_right + ' . $add1));
        $where = $this->_db->quoteInto('destination_right >= ?', $min);
        $where.= ' AND ' . $this->_db->quoteInto('destination_right < ?', $max); 
        $result = $this->_db->update($this->_name, $row, $where);
        
        // amend right values for tree
        $row  = array(
            'destination_left'  => new Zend_Db_Expr('destination_left + '  . $add2),
            'destination_right' => new Zend_Db_Expr('destination_right + ' . $add2),
            'destination_level' => new Zend_Db_Expr('destination_level + ' . $addlevel),
        );
        $where  = 'destination_id IN (' . implode(',', array_keys($subordinateIds)) . ')';
        $result = $this->_db->update($this->_name, $row, $where);
        
        // return success
        return true;
    }



-- phpMyAdmin SQL Dump
-- version 2.8.2
-- http://www.phpmyadmin.net
-- 
-- Host: localhost
-- Erstellungszeit: 10. Mai 2007 um 08:33
-- Server Version: 4.0.25
-- PHP-Version: 4.4.2
-- 
-- Datenbank: `travello_portal`
-- 

-- --------------------------------------------------------

-- 
-- Tabellenstruktur f
-- 

CREATE TABLE `destination_main` (
  `destination_id` smallint(5) unsigned NOT NULL auto_increment,
  `destination_left` smallint(5) unsigned NOT NULL default '0',
  `destination_right` smallint(5) unsigned NOT NULL default '0',
  `destination_level` tinyint(3) unsigned NOT NULL default '0',
  `destination_status` enum('approved','blocked') NOT NULL default 'approved',
  `destination_type` enum('world','continent','country','region','province','archipelago','island','city','cityzone') NOT NULL default 'world',
  `destination_old_id` smallint(5) unsigned default NULL,
  PRIMARY KEY  (`destination_id`)
) TYPE=InnoDB AUTO_INCREMENT=1771 ;

-- --------------------------------------------------------

-- 
-- Tabellenstruktur fTabelle `destination_text`
-- 

CREATE TABLE `destination_text` (
  `desttext_id` smallint(5) unsigned NOT NULL default '0',
  `desttext_lang` char(2) NOT NULL default 'de',
  `desttext_name` varchar(64) NOT NULL default '',
  `desttext_type` enum('normal','female','male','plural') NOT NULL default 'normal',
  `desttext_url` varchar(64) NOT NULL default '',
  PRIMARY KEY  (`desttext_id`,`desttext_lang`),
  KEY `foreign_desttext_id` (`desttext_id`)
) TYPE=InnoDB;

-- 
-- Constraints der exportierten Tabellen
-- 

-- 
-- Constraints der Tabelle `destination_text`
-- 
ALTER TABLE `destination_text`
  ADD CONSTRAINT `destination_text_ibfk_1` FOREIGN KEY (`desttext_id`) REFERENCES `destination_main` (`destination_id`) ON DELETE CASCADE ON UPDATE NO ACTION;
Thread
[OT ?] Binaerbaum verschiebenRalf Eggert27 Apr
  • Re: [OT ?] Binaerbaum verschiebenLenz Grimmer15 May
    • Re: [OT ?] Binaerbaum verschiebenJan Kneschke15 May
    • Re: [OT ?] Binaerbaum verschiebenRalf Eggert15 May