Tree-Struktur in einer DB abspeichern

[raiha]

Hi,

ich möchte die Struktur eines Trees (Äste und Blätter) in einer HSQL DB abspeichern und dann wieder laden. Hat jemand ne Idee wie man die Datenbasis am besten strukturiert und was man da neben dem Orndernamen mit abspeichert? Hat das vielleicht schonmal jemand gemacht?

Danke Rainer

 

[Bleiglanz]

Königsweg gibts da keinen, weil sich Bäume und SQL nicht besonders gern haben

Möglichkeit A)

fremdschlüssel auf sich selbst (parent_ID)

Möglichkeit B)

sog. Nested Sets (komplex, bitte googeln)

Möglichkeit C)

Manche Monster RDBMS (z.B. DB2) bringen eingebaute Unterstützung für "hierarchische Strukturen" schon mit

 

[AlArenal]

Ich denke die am häufigsten genutze Möglichkeit ist die von Bleiglanz angesprochene Möglichkeit A:

Jeder Node entspricht dabei einem Datensatz. Jeder Datensatz enthält dabei einen Fremdschlüssel auf dieselbe Tabelle, welche die ID des Parent-Nodes enthält. Das dürfte die einfachste Möglichkeit sein einen Baum in einer Datenbank abzubilden. Der Root-Node ist dann dadurch gekennzeichnet, dass seine Parent-ID = 0 ist.

Wie du dann beim Einlesen verfährst hängt davon ab, ob du die Daten einfach nur strunzdoof als Daten behandelst, oder ob z.B. jeder Datensatz von einer Instanz abgebildet wird und wie du die Referenzen auf anderen Nodes ermittelst (Referenz auf Parent in jeder Instanz; externe Map (Node -> Parent); ...). Bei der Abbildung der Daten als Instanzen erzeugst du beim Einlesen der Daten für jeden Satz eine Instanz. Als nächstes durchläufst du deine Instanzen und setzt die Referenz auf die Instanz des Parents....

Ich habs bisher immer so gehandhabt, dass jeder Node ne Referenz auf seinen Parent beininhaltet, ebenso wie eine List mit den Children. Darauf aufbauend ist die Erstellung eines TreeModels ne triviale Angelegenheit, je nach Verwendung können andere Spielarten aber zweckmäßiger / speicher-schonender sein...

 

[André Uhres]

Wenn die verschiedenen Ebenen jeweils nur einen einzigen Datentyp darstellen,
dann könnte man auch pro Ebene eine Tabelle anlegen,
wobei die Tabellen der unteren Ebenen jeweils die Schlüsselfelder der
darüberliegenden Tabellen enthalten.

 

[AlArenal]

Wenn die verschiedenen Ebenen jeweils nur einen einzigen Datentyp darstellen,
dann könnte man auch pro Ebene eine Tabelle anlegen,
wobei die Tabellen der unteren Ebenen jeweils die Schlüsselfelder der
darüberliegenden Tabellen enthalten.

Igitt!
Und dann willst du dynamisch Tabellen anlegen und löschen und dabei die Integrität der Daten gewährleisten? Da ende ich mit möglicherweise hunderten von Tabellen mit jeweils recht wenigen Datensätzen und muss erst nen SELECT machen um auszulesen mit welcher Tabelle ich im nächsten Schritt nen JOIN machen muss...

Da schüttelts mich...

 

[André Uhres]

> Da ende ich mit möglicherweise hunderten von Tabellen

Wieso? Dann hätte der Baum ja hunderte von Ebenen ... also, wirklich...
wenn die Hierarchie fünf Ebenen hat, dann ist das schon viel (Ich muss allerdings
zugeben, daß SQL nicht gerade meine Stärke ist) :lol:

 

[AlArenal]

Jetzt verstehe ich was du meinst.. Da gehst du aber von einem ganz besonderen Spezialfall aus und ehrlich gesagt weiß ich mit deinem "Datentypen" nichts anzufangen.

Die meisten Trees enthalten ja nicht einfach nur Zahlen oder Strings, sondern mehr oder minder komplexe Objekte, die etwas repräsentieren (Dateien, Prozesse, Organisationseinheiten, ...). Persönlich kann ich mir nicht vorstellen jemals mit dynamischen Tabellen in einer SQL-Datenbank zu arbeiten. Auch in deinem Spezialfall nicht...

 

[André Uhres]

> ehrlich gesagt weiß ich mit deinem "Datentypen" nichts anzufangen.

Ja gut, "Datentyp" ist vielleicht als Ausdruck hier nicht sehr glücklich gewählt.
Ich meine damit einfach alles was in eine bestimmte Tabelle reinpasst.
Beispiel:
Die Tabelle "Kundenstammdaten" enthält die Kundennummer, den Namen des Kunden,
seine Adresse, sein Bild, u.s.w.
Die Tabelle der "Lieferungen" enthält die Lieferungsnummer,
die Kundennummer, das Lieferdatum, u.s.w.
"Kundenstammdaten" wäre in diesem Beispiel die oberste Ebene und
"Lieferungen" eine Ebene darunter.
Somit sind mit diesem kleinen Beispiel schon eine ganze Menge von Daten
in nur zwei Ebenen strukturiert, die ganz einfach über die Kundennummer zusammenhängen.

EDIT 28.10.2005 (7:57):
> Buch über Datenstrukturen (wobei ich zum Sedgewick rate)

          Das wird aber teuer.

 

[AlArenal]

Das muss er für sich selbst ausklamüsern. Zunächst gehts ja grundsätzlich darum wie man Bäume in einer Datenbank abbildet, ohne dass er nun einen konkreten Anwendungsfall genannt hat.

Bei gleichen Daten gehts halt über nen Schlüssel auf dieselbe Tabelle für den Parent. Bei deinem Anwendungsfall wäre das ein Fremdschlüssel in ner anderen Tabelle, da ist der Parent einer Lieferung eben ein Kunde...

Das grundsätzliche Vorgehen über den Bezug auf den Parent ändert sich dadurch nicht und kann man so auch in jedem Buch über Datenstrukturen finden (wobei ich zum Sedgewick rate). Nur wenn er allgemein fragt, bekommt er auch ne allgemeine Antwort. Einen Spezialfall kann er sich dann selbst ableiten oder entsprechend nochmal nachfragen.

 

[raiha]

hab ich ne Chance das ganze Tree-Objekt (mit Hibernate oder so) abzuspeichern? Hat das schonmal jemand gemacht?

Danke Rainer

 

[André Uhres]

/*****************************************************************************************************
 * Simple_Tree.java
 ****************************************************************************************************/
package treeDnD1;
import java.awt.*;
import java.awt.event.*;
import java.io.*;
import javax.swing.*;
import javax.swing.tree.*;
public class Simple_Tree extends JFrame implements WindowListener, ActionListener{
    private static final long serialVersionUID = 7526472295622776147L;
    public Simple_Tree() {
        initComponents();
        addWindowListener(this); 
        tree.setDragEnabled(true);
        tree.setShowsRootHandles(true);
        tree.setEditable(true);
    }
    private void initComponents(){
        scroller = new JScrollPane();
        tree = new JTree();
        toolbar = new JToolBar();
        neuB = new JButton();
        nachObenB = new JButton();
        nachUntenB = new JButton();
        setDefaultCloseOperation(WindowConstants.DO_NOTHING_ON_CLOSE);
        scroller.setViewportView(tree);
        getContentPane().add(scroller, BorderLayout.CENTER);
        neuB.setText("Add node");
        neuB.addActionListener(this);
        toolbar.add(neuB);
        nachObenB.setText("Move up");
        nachObenB.addActionListener(this);
        toolbar.add(nachObenB);
        nachUntenB.setText("Move down");
        nachUntenB.addActionListener(this);
        toolbar.add(nachUntenB);
        getContentPane().add(toolbar, BorderLayout.NORTH);
        pack();
    }
    private void addNode(){
        TreePath selectedPath = tree.getSelectionPath();
        if(selectedPath != null){
            Object o = selectedPath.getLastPathComponent();
            if(o != null){
                DefaultMutableTreeNode selectedNode = (DefaultMutableTreeNode) o;
                DefaultMutableTreeNode newChild = new DefaultMutableTreeNode("new node "+count++);
                ((DefaultTreeModel)tree.getModel())
                .insertNodeInto(newChild, selectedNode, selectedNode.getChildCount());
                TreePath newPath = selectedPath.pathByAddingChild(newChild);
                tree.setSelectionPath(newPath);
                tree.startEditingAtPath(newPath);
            }
        }
    }
    private void move(final int direction){
        DefaultTreeModel model = (DefaultTreeModel) tree.getModel();
        MutableTreeNode moveNode = (MutableTreeNode) tree.getLastSelectedPathComponent();
        if(moveNode == null) return ;
        MutableTreeNode parent = (MutableTreeNode) moveNode.getParent();
        if(parent == null) return ;
        int targetIndex = model.getIndexOfChild(parent, moveNode) + direction;
        if(targetIndex < 0 || targetIndex >= parent.getChildCount()) return;
        model.removeNodeFromParent(moveNode);
        model.insertNodeInto(moveNode, parent, targetIndex);
        //make the node visible by scroll to it
        TreeNode[] nodes = model.getPathToRoot(moveNode);
        TreePath path = new TreePath(nodes);
        tree.scrollPathToVisible(path);
        //select the newly added node
        tree.setSelectionPath(path);
    }
    public static void main(String[] args) { 
        Simple_Tree frame = null; 
        File serializeFile = new File(serializeFilename); 
        if (serializeFile.exists()) { 
            try { 
                FileInputStream fileIn = 
                        new FileInputStream(serializeFile); 
                ObjectInputStream in = new ObjectInputStream(fileIn); 
                frame = (Simple_Tree)in.readObject(); 
                
            } catch(IOException ioe) { 
                System.out.println("Error reading file: " + ioe); 
            } catch(ClassNotFoundException cnfe) { 
                System.out.println("No such class: " + cnfe); 
            } 
        } else { 
            frame = new Simple_Tree(); 
        } 
        frame.setVisible(true); 
    } 
    public void windowOpened(WindowEvent e) { }
    public void windowClosing(WindowEvent e) {
        try { 
            FileOutputStream fileOut = 
                    new FileOutputStream(serializeFilename); 
            ObjectOutputStream out = 
                    new ObjectOutputStream(fileOut); 
            out.writeObject(this); 
            out.flush(); 
            out.close(); 
        } catch(IOException ioe) { 
            System.out.println("Error saving frame: " + ioe); 
        } 
        dispose(); 
    }
    public void windowClosed(WindowEvent e) { }
    public void windowIconified(WindowEvent e) { }
    public void windowDeiconified(WindowEvent e) { }
    public void windowActivated(WindowEvent e) { }
    public void windowDeactivated(WindowEvent e) { }
    public void actionPerformed(ActionEvent e) {
        if(     e.getSource()==neuB) addNode(); 
        else if(e.getSource()==nachObenB) move(UP);
        else if(e.getSource()==nachUntenB) move(DOWN);
    }
    private static String serializeFilename ="Simple_Tree.ser"; 
    public JButton neuB;
    public JButton nachObenB;
    public JButton nachUntenB;
    public JScrollPane scroller;
    public JToolBar toolbar;
    public JTree tree;
    private int count=1;
    private final int UP = -1;
    private final int DOWN = 1;
}

 

[raiha]

danke - die Funktionalität ist wirklich super - wie bekomme ich das Tree-Objekt jetzt in die DB gespeichert (mit Hibernate)?

Danke Rainer

 

[André Uhres]

Ups! Das wird ein Weilchen dauern bis ich das rauskrieg (wenn überhaupt).
Den Hibernate muss ich mir erst mal runterladen... :###

 

[André Uhres]

...aber es wäre vielleicht erst mal interessant zu wissen, aus welchem Grund du den "Tree" in einer Datenbank speichern willst,
anstatt in einer flachen Datei (wie das in meinem Beispiel geschieht) ?

 

[Guest]

... der Tree soll eigentlich nur "virtuelle" Verzeichnisse auswählbar wachen. Die Inhalte dieser Verzeichnisse (Bilder welche in der DB liegen) sollen dann auf der rechten Seite (links ist der Tree) in einer SpliPane angezeigt werden.

gleich noch eine kleine Frage kann man den Tree anweisen das er keine "Blätter" sondern nur Verzeichnisse anlegt?

Danke Rainer

 

[André Uhres]

Ich verstehe dich so, daß du den Tree in der DB gar nicht brauchst,
sondern nur die Bilder. Dann dürfte die einfache Datei aus meinem Beispiel
genügen um den Tree zu speichern.
Um die Icons der Blätter anzupassen brauchst du einen eigenen "TreeCellRenderer":

...
public class Simple_Tree extends JFrame implements WindowListener, ActionListener{
    private static final long serialVersionUID = 7526472295622776147L;
    public Simple_Tree() {
        ...
        myRenderer=new IconRenderer();
        tree.setCellRenderer(myRenderer);
    }
    ...
    private IconRenderer myRenderer;
    ...
}
class IconRenderer extends JLabel implements TreeCellRenderer {
    private static final long serialVersionUID = 7526472295622776147L;
    private static final String folder = "images/folder.gif";
    private static final String folderOpen = "images/folderOpen.gif";
    private DefaultTreeCellRenderer defaultRenderer = new DefaultTreeCellRenderer();
    private Color backgroundSelectionColor = defaultRenderer.getBackgroundSelectionColor();
    private Color backgroundNonSelectionColor = defaultRenderer.getBackgroundNonSelectionColor();
    public Component getTreeCellRendererComponent(JTree tree,
            Object value, boolean selected, boolean expanded, boolean leaf,
            int row, boolean hasFocus) {
        setOpaque(true);
        setText(value.toString());
        if (leaf) {
            if (selected) setIcon(new ImageIcon(folderOpen));
            else setIcon(new ImageIcon(folder));
        } else {
            if (expanded) setIcon(new ImageIcon(folderOpen));
            else  setIcon(new ImageIcon(folder));
        }
        if (selected) setBackground(backgroundSelectionColor);
        else  setBackground(backgroundNonSelectionColor);
        return this;
    }
}

Die Blätter werden hier so dargestellt als wären es Ordner mit nichts drin. Das was eigentlich drin ist (die Bilder) erscheint ja
getrennt auf der anderen Seite vom JSplitPane.
(Natürlich muss in dem Fall jedes Blatt-Objekt eine Bilderliste enthalten.)

Hier noch ein wichtiger Tipp: Die "serialVersionUID" muss als Feld zu allen Klassen hinzugefügt werden, die gespeichert
werden sollen, sonst erscheint bei der geringsten Programmänderung eine Fehlermeldung und das Programm
kann mit dem gespeicherten Objekt nicht mehr gestartet werden! Beispiel:

private static final long serialVersionUID = 7526472295622776147L;

[Edit Andre_Uhres: Geändert am: 30. 10. 2005, 23:27]