달력

32024  이전 다음

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
출처 : http://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html


Get It Done With MySQL 5&6, Chapter 20. Copyright © Peter Brawley and Arthur Fuller 2008. All rights reserved.

TOC    Previous    Next

Working with Graphs in MySQL

Graphs and SQL   Edge list   Edge-adjacency list model of a tree
   Nested set model of a tree   Edge-list model of a network   Parts explosions

Most non-trivial data is hierarchical. Customers have orders, which have line items, which refer to products, which have prices. Population samples have subjects, who take tests, which give results, which have sub-results and norms. Web sites have pages, which have links, which collect hits, which distribute across dates and times. With such data, we know the depth of the hierarchy before we sit down to write a query. The fixed depth of the hierarchy logically limits the number of JOINs needed in a query.

But if our data describes a family tree, or a browsing history, or a bill of materials, then hierarchical depth depends on the data. We no longer know how many JOINs our query will require. We need a different data model. 

That model is the graph (Fig 1), which is a set of nodes (vertices) and the edges (lines or arcs) that connect them. This chapter is about how to model and query graphs in a MySQL database.

Graph theory is a branch of topology. It is the study of geometric relations which aren't changed by stretching and compression—rubber sheet geometry, some call it. Graph theory is ideal for modelling hierarchies—like family trees, browsing histories, search trees and bills of materials—whose shape and size we can't know in advance.

Let the set of nodes in Fig 1 be N, the set of edges be L, and the graph be G. Then G is the tuple or ordered pair {N,L}:

    N = {A,B,C,D,E,F}
    L = {AC,CD,CF,BE}
    G = {N,L}

If the edges are directed, the graph is a digraph or directed graph. A mixed graph has both directed and undirected edges.

Examples of graphs are organisational charts; itineraries; route maps; parts explosions; massively multiplayer games; language rules; chat histories; network and link analysis in a wide variety of fields, for example search engines, forensics, epidemiology and telecommunications; data mining; models of chemical structure hierarchies; and biochemical processes.

Graph characteristics and models

Nodes and edges : Two nodes are adjacent if there is an edge between them. Two edges are adjacent if they connect to a common node. In a complete graph, all nodes are adjacent to all other nodes.

In a digraph or directed graph, the number of edges entering a node is its indegree; the number leaving is its outdegree. A node of indegree zero is a root node, a node of outdegree zero is a leaf node.

In a weighted graph, used for example to solve the travelling salesman problem, edges have a weight attribute. A digraph with weighted edges is a network.

Paths and cycles: A connected sequence of edges is a path, its length the number of edges traversed. Two nodes are connected if there is a path between them. If there is a path connecting every pair of nodes, the graph is a connected graph.

A path in which no node repeats is a simple path. A path which returns to its own origin without crossing itself is a cycle or circuit. A graph with multiple paths between at least one pair of nodes is reconvergent. A reconvergent graph may be cyclic or acyclic. A unit length cycle is a loop.

If a graph's edges intersect only at nodes, it is planar. Two paths having no node in common are independent.

Traversing graphs: There are two main approaches, breadth-first and depth-first. Breadth-first traversal visits all a node's siblings before moving on to the next level, and typically uses a queue. Depth-first traversal follows edges down to leaves and back before proceeding to siblings, and typically uses a stack.

Sparsity: A graph where the size of E approaches the maximum N2 is dense. When the multiple is much smaller than N, the graph is considered sparse.

Trees: A tree is a connected graph with no cycles. It is also a graph where the indegree of the root node is 0, and the indegree of every other node is 1. A tree where every node is of outdegree <=2 is a binary tree.  A forest is a graph in which every connected component is a tree.

Euler paths: A path which traverses every edge in a graph exactly once is an Euler path. An Euler path which is a circuit is an Euler circuit.

If and only if every node of a connected graph has even degree, it has an Euler circuit (which is why the good people of Königsberg cannot go for a walk crossing each of their seven bridges exactly once). If and only if a connected graph has exactly 2 nodes with odd degree, it has a non-circuit Euler path. The degree of an endpoint of a non-cycle Euler path is 1 + twice the number of times the path passes through that node, so it is always odd.

Models for computing graphs

Traditionally, computer science textbooks have offered edge lists, adjacency lists and adjacency matrices as data structures for graphs, with algorithms implemented in languages like C, C++ and Java. More recently other models and tools have been suggested, including query languages customised for graphs.

Edge list: The simplest way to represent a graph is to list its edges: for Fig 1, the edge list is {AC,CD,CF,BE}. It is easy to add an edge to the list; deletion is a little harder.

Table 1
Nodes Adjacent nodes
A C
B E
C F,D,A
D C
E B
F C
Adjacency list: An adjacency list is a ragged array: for each node it lists all adjacent nodes. Thus it represents a directed graph of n nodes as a list of n lists where list i contains node j if the graph has an edge from node i to node j.

An undirected graph may be represented by having node j in the list for node i, and node i in the list for node j. Table 1 shows the adjacency list of the graph in Fig 1 interpreted as undirected.

Adjacency matrix: An adjacency matrix represents a graph with n nodes as an n x n matrix, where the entry at (i,j) is 1 if there is an edge from node i to node j, or zero if there is not.

An adjacency matrix can represent a weighted graph using the weight as the entry, and can represent an undirected graph by using the same entry in both (i,j) and (j,i), or by using an upper triangular matrix.

There are useful glossaries here and here.

Graphs and SQL

Often standard SQL has been thought cumbersome for graph problems. Craig Mullins once wrote that "the set-based nature of SQL is not simple to master and is anathema to the OO techniques practiced by Java developers."

A few years after Mullins wrote that, SQL is everywhere, and it is increasingly applied to graph problems. DB2 has a WITH operator for processing recursive sets. Oracle has a CONNECT BY operator for graphs that are trees. SQL Server has recursive unions. MySQL has no such enhancements for graphs, but Joe Celko and Scott Stephens, among others, have published general SQL graph problem solutions that are simpler and smaller than equivalent C++, C# or Java code. Here we implement some of these ideas in MySQL.

Beware that in ports of edge list and adjacency list methods to SQL, there has been name slippage. What's often called the adjacency list model in the SQL world is actually an edge list model. If you follow the now-common practice in the SQL world of referring to edge lists as adjacency lists, don't be surprised to find that the model isn't quite like the adjacency list in Table 1. Here we waffle. We call them edge-adjacency lists.

There are also two newer kinds of models: what Joe Celko called the nested sets modealso known as the interval modelwhich uses greater-than/less-than arithmetic to encode tree relationships and modified preorder tree traversal (MPTT) to query them, and Tropashko's materialised path model, where each node is stored with its path to the root. So we have four main possibilities for modelling graphs in MySQL:

  • edge-adjacency lists: based on an adaptation by EF Codd of the logic of linked lists to table structures and queries,
  • adjacency matrices,
  • nested sets for trees simplify some queries, but insertion and deletion are cumbersome, and
  • materialised paths.

Here we work out how to implement edge-adjacency, nested set and materialised path models— or parts of them—in MySQL 5&6.

The edge list

The edge list is the simplest way to represent a graph: minimally, a one-column table of nodes and a two-column table of edges. The edges table can be thought of as a nodes-nodes bridge table, each row containing pointers to origin and destination nodes. Other details of nodes and edges can be encoded in extra nodes and edges columns, or in child tables.

In the real world, the nodes table might be a table of personnel, or assembly parts, or locations on a map. It might have many other columms of data. The edges table might also have additional columns for edge properties. The key integers of both tables might be BIGINTs.

To model Fig 1, though, we keep things as simple as possible:

Listing 1
CREATE TABLE nodes(
  nodeID CHAR(1) PRIMARY KEY
);
CREATE TABLE edges(
  childID CHAR(1) NOT NULL,
  parentID CHAR(1) NOT NULL,
  PRIMARY KEY(childID,parentID)
);
INSERT INTO nodes VALUES('A'), ('B'), ('C'), ('D'), ('E'), ('F');
INSERT INTO edges VALUES ('A','C'), ('C','D'), ('C','F'), ('B','E');
SELECT * FROM edges;
+---------+----------+
| childID | parentID |
+---------+----------+
| A       | C        |
| B       | E        |
| C       | D        |
| C       | F        |
+---------+----------+

Now, without any assumptions whatever about whether the graph is connected, whether it is directed, whether it is a tree, or whatever, how hard is it to write a reachability procedure, a procedure which tells us where we can get to from here, wherever 'here' is?

A simple approach is a breadth-first search:

  1. Seed the list with the starting node,
  2. Add, but do not duplicate, nodes which are children of nodes in the list,
  3. Add, but do not duplicate, nodes which are parents of nodes in the list,
  4. Repeat steps 2 and 3 until there are no more nodes to add.

Here it is as a MySQL stored procedure. It avoids duplicate nodes by defining reached.nodeID as a primary key and adding reachable nodes with INSERT IGNORE.

If you are running MySQL 5.0.6 through 5.0.15, you will have to make two changes to this and subsequent procedures: move CREATE TABLE statements outside the procedures, and set log_bin_trust_routine_creators=TRUE.

Listing 2
DROP PROCEDURE IF EXISTS ListReached;
DELIMITER |

CREATE PROCEDURE ListReached( IN root CHAR(1) )
BEGIN
  DECLARE rows SMALLINT DEFAULT 0;
  DROP TABLE IF EXISTS reached;
  CREATE TABLE reached (
    nodeID CHAR(1) PRIMARY KEY
  ) ENGINE=HEAP;
  INSERT INTO reached VALUES (root );
  SET rows = ROW_COUNT();
  WHILE rows > 0 DO
    INSERT IGNORE INTO reached
      SELECT DISTINCT childID
      FROM edges AS e
      INNER JOIN reached AS p ON e.parentID = p.nodeID;
    SET rows = ROW_COUNT();
    INSERT IGNORE INTO reached
      SELECT DISTINCT parentID
      FROM edges AS e
      INNER JOIN reached AS p ON e.childID = p.nodeID;
    SET rows = rows + ROW_COUNT();
  END WHILE;
  SELECT * FROM reached;
  DROP TABLE reached;
END;
|
DELIMITER ;
CALL ListReached('A');
+--------+
| nodeID |
+--------+
| A      |
| C      |
| D      |
| F      |
+--------+

To make the procedure more versatile, give it input parameters which tell it whether to list child, parent or all connections, and whether to recognise loops (for example C to C).

To give the model referential integrity, use InnoDB and make edges.childID and edges.parentID foreign keys. To add or delete a node, add or delete desired single rows in nodes and edges. To change an edge, edit it. The model does not require the graph to be connected or treelike, and does not presume direction.

The edge list is basic to what SQLers often call the adjacency list model.

Edge-adjacency list model of a tree

Writers in the SQL graph literature often give solutions using single denormalised tables. Denormalisation can cost, big time. The bigger the table, the bigger the cost. You cannot edit nodes and edges separately. Carrying extra node information during edge computation slows performance. With nodes and edges denormalised to one table, you have to represent the root node with a NULL.

Normalisation banishes these difficulties. For William Shakespeare's family tree (Fig 2) we again use two tables, a family table describing family members (nodes), and a familytree table with a row for each tie that binds (edges). Later, when we use a different tree model, we won't have to mess with the data being modelled.

Listing 3
-- Base data:
CREATE TABLE family (
  ID smallint(6) PRIMARY KEY AUTO_INCREMENT,
  name char(20) default '',
  siborder tinyint(4) default NULL,
  born smallint(4) unsigned default NULL,
  died smallint(4) unsigned default NULL
);
INSERT INTO family VALUES (1, 'Richard Shakespeare', NULL, NULL, 1561);
INSERT INTO family VALUES (2, 'Henry Shakespeare', 1, NULL, 1569);
INSERT INTO family VALUES (3, 'John Shakespeare', 2, 1530, 1601);
INSERT INTO family VALUES (4, 'Joan Shakespeare', 1, 1558, NULL);
INSERT INTO family VALUES (5, 'Margaret Shakespeare', 2, 1562, 1563);
INSERT INTO family VALUES (6, 'William Shakespeare', 3, 1564, 1616);
INSERT INTO family VALUES (7, 'Gilbert Shakespeare', 4, 1566, 1612);
INSERT INTO family VALUES (8, 'Joan Shakespeare', 5, 1568, 1646);
INSERT INTO family VALUES (9, 'Anne Shakespeare', 6, 1571, 1579);
INSERT INTO family VALUES (10, 'Richard Shakespeare', 7, 1574, 1613);
INSERT INTO family VALUES (11, 'Edmond Shakespeare', 8, 1580, 1607);
INSERT INTO family VALUES (12, 'Susana Shakespeare', 1, 1583, 1649);
INSERT INTO family VALUES (13, 'Hamnet Shakespeare', 1, 1585, 1596);
INSERT INTO family VALUES (14, 'Judith Shakespeare', 1, 1585, 1662);
INSERT INTO family VALUES (15, 'William Hart', 1, 1600, 1639);
INSERT INTO family VALUES (16, 'Mary Hart', 2, 1603, 1607);
INSERT INTO family VALUES (17, 'Thomas Hart', 3, 1605, 1670);
INSERT INTO family VALUES (18, 'Michael Hart', 1, 1608, 1618);
INSERT INTO family VALUES (19, 'Elizabeth Hall', 1, 1608, 1670);
INSERT INTO family VALUES (20, 'Shakespeare Quiney', 1, 1616, 1617);
INSERT INTO family VALUES (21, 'Richard Quiney', 2, 1618, 1639);
INSERT INTO family VALUES (22, 'Thomas Quiney', 3, 1620, 1639);
INSERT INTO family VALUES (23, 'John Bernard', 1, NULL, 1674);

-- Table which models the tree:
CREATE TABLE familytree (
  childID smallint NOT NULL,
  parentID smallint NOT NULL,
  PRIMARY KEY (childID, parentID);
);
INSERT INTO familytree VALUES
  (2, 1), (3, 1), (4, 2), (5, 2), (6, 2), (7, 2), (8, 2), (9, 2),
  (10, 2), (11, 2), (12, 6), (13, 6), (14, 6), (15, 8), (16, 8),
  (17, 8), (18, 8), (19, 12), (20, 14), (21, 14), (22, 14), (23, 19);

(The family PK is auto-increment, but the listing is more reader-friendly when the ID values are shown.)

It will be useful to have a function that returns the family.name for a pointer in familytree. Listing 4 shows that function, and simple queries which call it to retrieve child and parent names:

Listing 4
-- 5.0.16 OR LATER:
SET GLOBAL log_bin_trust_function_creators=TRUE;

DROP FUNCTION IF EXISTS PersonName;
DELIMITER |

CREATE FUNCTION PersonName( personID SMALLINT )
RETURNS CHAR(20)
BEGIN
  DECLARE pname CHAR(20) DEFAULT '';
  SELECT name INTO pname FROM family WHERE ID=personID;
  RETURN pname;
END;
|
DELIMITER ;

SELECT PersonName( parentID ) AS 'Parent of William'
FROM familytree
WHERE childID = 6;
+-------------------+
| Parent of William |
+-------------------+
| Henry Shakespeare |
+-------------------+
SELECT PersonName( childID ) AS 'Children of William'
FROM familytree
WHERE parentID = (
  SELECT ID FROM family
  WHERE name = 'William Shakespeare'
);
+---------------------+
| Children of William |
+---------------------+
| Susana Shakespeare  |
| Hamnet Shakespeare  |
| Judith Shakespeare  |
+---------------------+
SELECT
  PersonName(childID) AS child,
  PersonName(parentID) AS parent
FROM familytree;
+----------------------+---------------------+
| child                | parent              |
+----------------------+---------------------+
| Henry Shakespeare    | Richard Shakespeare |
| John Shakespeare     | Richard Shakespeare |
| Joan Shakespeare     | Henry Shakespeare   |
| Margaret Shakespeare | Henry Shakespeare   |
| William Shakespeare  | Henry Shakespeare   |
| Gilbert Shakespeare  | Henry Shakespeare   |
| Joan Shakespeare     | Henry Shakespeare   |
| Anne Shakespeare     | Henry Shakespeare   |
| Richard Shakespeare  | Henry Shakespeare   |
| Edmond Shakespeare   | Henry Shakespeare   |
| Susana Shakespeare   | William Shakespeare |
| Hamnet Shakespeare   | William Shakespeare |
| Judith Shakespeare   | William Shakespeare |
| William Hart         | Joan Shakespeare    |
| Mary Hart            | Joan Shakespeare    |
| Thomas Hart          | Joan Shakespeare    |
| Michael Hart         | Joan Shakespeare    |
| Elizabeth Hall       | Susana Shakespeare  |
| Shakespeare Quiney   | Judith Shakespeare  |
| Richard Quiney       | Judith Shakespeare  |
| Thomas Quiney        | Judith Shakespeare  |
| John Bernard         | Elizabeth Hall      |
+----------------------+---------------------+

GROUP_CONCAT() simplifies grouping parents with their children:

Listing 5
SELECT
  PersonName(parentID) AS Parent,
  GROUP_CONCAT( PersonName(childID) SEPARATOR ', ' ) AS Children
FROM familytree
GROUP BY parentID;
+---------------------+----------------------------------------------------------------------------------+
| Parent              | Children                                                                         |
+---------------------+----------------------------------------------------------------------------------+
| Richard Shakespeare | Henry Shakespeare, John Shakespeare                                              |
| Henry Shakespeare   | Edmond Shakespeare, Richard Shakespeare, Anne Shakespeare, Joan Shakespeare,     |
|                     | Gilbert Shakespeare, William Shakespeare, Margaret Shakespeare, Joan Shakespeare |
| William Shakespeare | Judith Shakespeare, Hamnet Shakespeare, Susana Shakespeare                       |
| Joan Shakespeare    | William Hart, Mary Hart, Thomas Hart, Michael Hart                               |
| Susana Shakespeare  | Elizabeth Hall                                                                   |
| Judith Shakespeare  | Shakespeare Quiney, Richard Quiney, Thomas Quiney                                |
| Elizabeth Hall      | John Bernard                                                                     |
+---------------------+----------------------------------------------------------------------------------+

The paterfamilias is the root node, individuals with no children are the leaf nodes, and queries to retrieve subtree statistics are straightforward:

Listing 6
SELECT
  PersonName(ID) AS Paterfamilias,
  IFNULL(born,'?') AS Born,
  IFNULL(died,'?') AS Died
FROM family AS f
LEFT JOIN familytree AS t ON f.ID=t.childID
WHERE t.childID IS NULL;
+---------------------+------+------+
| Paterfamilias       | Born | Died |
+---------------------+------+------+
| Richard Shakespeare | ?    | 1561 |
+---------------------+------+------+

SELECT
  PersonName(ID) AS Childless,
  IFNULL(born,'?') AS Born,
  IFNULL(died,'?') AS Died
FROM family AS f
LEFT JOIN familytree AS t ON f.ID=t.parentID
WHERE t.parentID IS NULL;
+----------------------+------+------+
| Childless            | Born | Died |
+----------------------+------+------+
| John Shakespeare     | 1530 | 1601 |
| Joan Shakespeare     | 1558 | ?    |
| Margaret Shakespeare | 1562 | 1563 |
| Gilbert Shakespeare  | 1566 | 1612 |
| Anne Shakespeare     | 1571 | 1579 |
| Richard Shakespeare  | 1574 | 1613 |
| Edmond Shakespeare   | 1580 | 1607 |
| Hamnet Shakespeare   | 1585 | 1596 |
| William Hart         | 1600 | 1639 |
| Mary Hart            | 1603 | 1607 |
| Thomas Hart          | 1605 | 1670 |
| Michael Hart         | 1608 | 1618 |
| Shakespeare Quiney   | 1616 | 1617 |
| Richard Quiney       | 1618 | 1639 |
| Thomas Quiney        | 1620 | 1639 |
| John Bernard         | ?    | 1674 |
+----------------------+------+------+

SELECT ROUND(AVG(died-born),2) AS 'Longevity of the childless'
FROM family AS f
LEFT JOIN familytree AS t ON f.ID=t.parentID
WHERE t.parentID IS NULL;
+----------------------------+
| Longevity of the childless |
+----------------------------+
|                      25.86 |
+----------------------------+

In marked contrast with Celko's nested sets model, inserting a new item in this model requires no revision of existing rows. We just add a new family row, then a new familytree row with IDs specifying who is the parent of whom. Deletion is also a two-step: delete the familytree row which documents the child-parent link, then delete the family row for that child.

Retrieving subtrees in the edge-adjacency list model

Retrieving subtrees is what gives the edge-adjacency list model its reputation for difficulty. We can't know in advance, except in the simplest of trees, how many levels of parent and child have to be queried, so we need recursion or a logically equivalent loop.

It's a natural problem for a stored procedure. Here is a breadth-first algorithm that is straightforward, though not optimised:

  1. Create a table for the results, descendants,
  2. Create a HEAP table, nextparents, for the next parents whose children are to be found , and another HEAP table for use as a temp copy,
  3. Seed nextparents with the name of the ancestor whose descendants we wish to list,
  4. Add to descendants all children of rows in nextparents,
  5. Seed nextparents with those children's IDs, and if there are any, loop back to 4.

As a convenience, the procedure accepts either a name or numeric ID argument. (With MySQL 5.0.6 or 5.0.7, you will have to move the CREATE TABLE calls outside the procedure, to step around a MySQL bug that was fixed in 5.0.9.)

Listing 7
DROP PROCEDURE IF EXISTS ListDescendants;
DELIMITER |

CREATE PROCEDURE ListDescendants( ancestor CHAR(20) )
BEGIN
  DECLARE rows, iLevel, iMode INT DEFAULT 0;
  -- create temp tables
  DROP TEMPORARY TABLE IF EXISTS descendants,nextparents,prevparents;
  CREATE TEMPORARY TABLE descendants( childID INT, parentID INT, level INT );
  CREATE TEMPORARY TABLE IF NOT EXISTS nextparents ( parentID SMALLINT) ENGINE=MEMORY;
  CREATE TEMPORARY TABLE prevparents LIKE nextparents;
  -- seed nextparents
  IF ancestor RLIKE '[:alpha:]+' THEN      -- ancestor passed as a string
    INSERT INTO nextparents SELECT id FROM family WHERE name=ancestor;
  ELSE
    SET iMode = 1;                         -- ancestor passed as a numeric
    INSERT INTO nextparents VALUES( CAST( ancestor AS UNSIGNED ));
  END IF;
  SET rows = ROW_COUNT();
  WHILE rows > 0 DO
    -- add children of nextparents
    SET iLevel = iLevel + 1;
    INSERT INTO descendants
      SELECT t.childID, t.parentID, iLevel
      FROM familytree AS t
      INNER JOIN nextparents USING(parentID);
    SET rows = ROW_COUNT();
    -- save nextparents to prevparents
    TRUNCATE prevparents;
    INSERT INTO prevparents
      SELECT * FROM nextparents;
    -- next parents are children of these parents:
    TRUNCATE nextparents;
    INSERT INTO nextparents
      SELECT childID FROM familytree
      INNER JOIN prevparents USING (parentID);
    SET rows = rows + ROW_COUNT();
  END WHILE;  
  -- result
  IF iMode = 1 THEN
    SELECT CONCAT(REPEAT( ' ', level), parentID ) As Parent, GROUP_CONCAT(childID) AS Child
    FROM descendants GROUP BY parentID ORDER BY level;
  ELSE
    SELECT CONCAT(REPEAT( ' ', level), PersonName(parentID) ) As Parent, PersonName(childID) AS Child
    FROM descendants;
  END IF;
  DROP TEMPORARY TABLE descendants,nextparents,prevparents;
END;
|
DELIMITER ;
CALL ListDescendants( 1 );
+---------+-------------------+
| Parent  | Child             |
+---------+-------------------+
|  1      | 2,3               |
|   2     | 11,10,9,8,7,6,5,4 |
|    6    | 14,13,12          |
|    8    | 15,16,17,18       |
|     12  | 19                |
|     14  | 20,21,22          |
|      19 | 23                |
+---------+-------------------+
CALL ListDescendants( 'Richard Shakespeare' );
+------------------------+----------------------+
| Parent                 | Child                |
+------------------------+----------------------+
|  Richard Shakespeare   | Henry Shakespeare    |
|  Richard Shakespeare   | John Shakespeare     |
|   Henry Shakespeare    | Joan Shakespeare     |
|   Henry Shakespeare    | Margaret Shakespeare |
|   Henry Shakespeare    | William Shakespeare  |
|   Henry Shakespeare    | Gilbert Shakespeare  |
|   Henry Shakespeare    | Joan Shakespeare     |
|   Henry Shakespeare    | Anne Shakespeare     |
|   Henry Shakespeare    | Richard Shakespeare  |
|   Henry Shakespeare    | Edmond Shakespeare   |
|    William Shakespeare | Susana Shakespeare   |
|    William Shakespeare | Hamnet Shakespeare   |
|    William Shakespeare | Judith Shakespeare   |
|    Joan Shakespeare    | William Hart         |
|    Joan Shakespeare    | Mary Hart            |
|    Joan Shakespeare    | Thomas Hart          |
|    Joan Shakespeare    | Michael Hart         |
|     Susana Shakespeare | Elizabeth Hall       |
|     Judith Shakespeare | Shakespeare Quiney   |
|     Judith Shakespeare | Richard Quiney       |
|     Judith Shakespeare | Thomas Quiney        |
|      Elizabeth Hall    | John Bernard         |
+------------------------+----------------------+

Not too bad. Notice how little of the code is specific to the Shakespeare example: the logic will port easily to any other edge list. In fact let's prove that right now by rewriting ListDescendants() for the general case. We need six parameters to drive three PREPAREd queries:

  • the name and key column of the data table (family, ID in the Shakespeare example),
  • the name of the edge table, its ID column and its parentID column (familytree, childID, parentID),
  • a parameter for the ancestorID whose subtree is to be listed:
Listing 7a: General-purpose edge list subtree walker
DROP PROCEDURE IF EXISTS GenericSubtree;
DELIMITER |
CREATE PROCEDURE GenericSubtree( 
  dataTable CHAR(64),
  dataIDcol CHAR(64),
  edgeTable CHAR(64),
  edgeIDcol CHAR(64),
  edgeParentIDcol CHAR(64),
  ancestorID INT
)
BEGIN
  DECLARE rows INT DEFAULT 0;
  -- create temp tables
  DROP TEMPORARY TABLE IF EXISTS descendants,nextparents,prevparents;
  CREATE TEMPORARY TABLE descendants( id INT, parentID INT );
  CREATE TEMPORARY TABLE IF NOT EXISTS nextparents ( parentID INT ) ENGINE=MEMORY;
  CREATE TEMPORARY TABLE prevparents LIKE nextparents;
  -- seed nextparents table with ancestorID
  INSERT INTO nextparents VALUES (ancestorID);
  SET rows = ROW_COUNT();
  WHILE rows > 0 DO
    -- insert children of nextparents into descendants
    SET @sql = CONCAT( 'INSERT INTO descendants SELECT t.', edgeIDcol, ',t.', 
                       edgeParentIDcol, ' FROM ', edgeTable, ' AS t JOIN nextparents n ON t.', 
                       edgeParentIDcol, ' = n.parentID'
                     );
    PREPARE stmt FROM @sql;
    EXECUTE stmt;
    SET rows = ROW_COUNT();
    DROP PREPARE stmt;
    -- save copy of nextparents to prevparents
    TRUNCATE prevparents;
    INSERT INTO prevparents SELECT * FROM nextparents;
    -- insert the children of these parents into nextparents:
    TRUNCATE nextparents;
    SET @sql = CONCAT( 'INSERT INTO nextparents SELECT ', edgeIDcol, ' FROM ', edgeTable,
                       ' t JOIN prevparents p ON t.', edgeParentIDcol, ' = p.parentID'
                     );
    PREPARE stmt FROM @sql;
    EXECUTE stmt;
    SET rows = rows + ROW_COUNT();
    DROP PREPARE stmt;
  END WHILE;
  -- show the result
  SET @sql = CONCAT( 'SELECT t.* FROM descendants d',
                     ' JOIN ', edgeTable, ' e ON d.ID = e.', edgeIDCol,
                     ' JOIN ', dataTable, ' t ON e.', edgeIDcol, '=t.', dataIDcol
                   );
  PREPARE stmt FROM @sql;
  EXECUTE stmt;
  DROP PREPARE stmt;
  -- clean up
  DROP TEMPORARY TABLE descendants,nextparents,prevparents;
END;
|
DELIMITER ;

Does it work? Let's have William's descendants again:

CALL GenericSubtree( 'family', 'ID', 'familytree', 'childID', 'parentID', 
                     (SELECT ID from family where name='William Shakespeare') );
+----+--------------------+----------+------+------+
| ID | name               | siborder | born | died |
+----+--------------------+----------+------+------+
| 12 | Susana Shakespeare |        1 | 1583 | 1649 |
| 13 | Hamnet Shakespeare |        1 | 1585 | 1596 |
| 14 | Judith Shakespeare |        1 | 1585 | 1662 |
| 19 | Elizabeth Hall     |        1 | 1608 | 1670 |
| 20 | Shakespeare Quiney |        1 | 1616 | 1617 |
| 21 | Richard Quiney     |        2 | 1618 | 1639 |
| 22 | Thomas Quiney      |        3 | 1620 | 1639 |
| 23 | John Bernard       |        1 | NULL | 1674 |
+----+--------------------+----------+------+------+

Is it fast? No. But once we have this algorithm, pruning subtrees is no harder than calling GenericSubtree() then deleting the listed rows. Better still, write a generic tree pruner from Listing 7a replacing the final SELECT with a DELETE command. To insert a subtree, prepare a table of new rows, point its top edge at an existing node as parent, and INSERT it. 

For speed, try recursion! Here is a recursive depth-first PHP treewalk for the  familytree and family tables:

Listing 7b: Recursive edge list subtree in PHP
$info = recursivesubtree( 1, $a = array(), 0 );
foreach( $info as $row ) 
  echo str_repeat( "&nbsp;", 2*$row[4] ), ( $row[3] > 0 ) ? "<b>{$row[1]}</b>" : $row[1], "<br/>";

function recursivesubtree( $rootID, $a, $level ) {
  $childcountqry = "(SELECT COUNT(*) FROM familytree WHERE parentID=t.childID) AS childcount";
  $qry = "SELECT t.childid,f.name,t.parentid,$childcountqry,$level " .
         "FROM familytree t JOIN family f ON t.childID=f.ID " .
         "WHERE parentid=$rootID ORDER BY childcount<>0,t.childID";
  $res = mysql_qry( $qry );
  while( $row = mysql_fetch_row( $res )) {
    $a[] = $row;
    if( $row[3] > 0 ) $a = recursivesubtree( $row[0], $a, $level+1 );    // down before right
  }
  return $a;
}

A query with a subquery, a fetch loop, and a recursive call--that's all there is to it. To port this to MySQL, you must have set maximum recursion depth in my.cnf/ini or in your client:

Listing 7c: Recursive edge list subtree in MySQL
SET @@SESSION.max_sp_recursion_depth=25;
DROP PROCEDURE IF EXISTS recursivesubtree;
DELIMITER |
CREATE PROCEDURE recursivesubtree( iroot INT, ilevel INT )
BEGIN
  DECLARE ichildid, iparentid,ichildcount,done INT DEFAULT 0;
  DECLARE cname VARCHAR(64);
  DECLARE cur CURSOR FOR
  SELECT 
    t.childid,t.parentid,f.name,
    (SELECT COUNT(*) FROM familytree WHERE parentID=t.childID) AS childcount
  FROM familytree t JOIN family f ON t.childID=f.ID
  WHERE parentid=iroot ORDER BY childcount<>0,t.childID;
  DECLARE CONTINUE HANDLER FOR SQLSTATE '02000' SET done = 1;
  IF ilevel = 0 THEN
    DROP TEMPORARY TABLE IF EXISTS descendants;
    CREATE TEMPORARY TABLE descendants(
      childID INT,parentID INT,name VARCHAR(64),childcount INT,level INT
    );
  END IF;
  OPEN cur;
  WHILE NOT done DO
    FETCH cur INTO ichildid,iparentid,cname,ichildcount;
    IF NOT done THEN
      INSERT INTO descendants VALUES(ichildid,iparentid,cname,ichildcount,ilevel );
      IF ichildcount > 0 THEN
        CALL recursivesubtree( ichildid, ilevel + 1 );
      END IF;
    END IF;
  END WHILE;
  CLOSE cur;
END;
|
DELIMITER ;
CALL recursivesubtree(1,0);
SELECT CONCAT(REPEAT(' ',2*level),IF(childcount,UPPER(name),name)) AS 'Richard\'s Descendants'
FROM descendants;
+--------------------------+
| Richard's Descendants    |
+--------------------------+
| John Shakespeare         |
| HENRY SHAKESPEARE        |
|   Joan Shakespeare       |
|   Margaret Shakespeare   |
|   Gilbert Shakespeare    |
|   Anne Shakespeare       |
|   Richard Shakespeare    |
|   Edmond Shakespeare     |
|   WILLIAM SHAKESPEARE    |
|     Hamnet Shakespeare   |
|     SUSANA SHAKESPEARE   |
|       ELIZABETH HALL     |
|         John Bernard     |
|     JUDITH SHAKESPEARE   |
|       Shakespeare Quiney |
|       Richard Quiney     |
|       Thomas Quiney      |
|   JOAN SHAKESPEARE       |
|     William Hart         |
|     Mary Hart            |
|     Thomas Hart          |
|     Michael Hart         |
+--------------------------+

The recursive depth-first treewalk is faster than the breadth-first procedures. It is also faster than a MySQL version of Kendall Willet's depth-first edge list subtree algorithm:

Listing 7d: Depth-first edge list subtree 
CREATE PROCEDURE depthfirstsubtree( iroot INT )
BEGIN
  DECLARE ilastvisited, inxt, ilastord INT;
  SET ilastvisited = iroot;
  SET ilastord = 1;
  DROP TABLE IF EXISTS descendants;
  CREATE TABLE descendants SELECT childID,parentID,-1 AS ord FROM familytree;
  UPDATE descendants SET ord=1 WHERE childID=iroot;
  this: LOOP
    SET inxt = NULL;
    SELECT MIN(childID) INTO inxt FROM descendants   -- go down
    WHERE parentID = ilastvisited AND ord = -1 ;
    IF inxt IS NULL THEN                             -- nothing down, so go right   
      SELECT MIN(d2.childID) INTO inxt 
      FROM descendants d1
      JOIN descendants d2 ON d1.parentID = d2.parentID AND d1.childID < d2.childID
      WHERE d1.childID = ilastvisited;
    END IF;
    IF inxt IS NULL THEN                             -- nothing right. so go up        
      SELECT parentID INTO inxt FROM descendants
      WHERE childID = ilastvisited AND parentID IS NOT NULL;
    END IF;
    UPDATE descendants SET ord = ilastord + 1
    WHERE childID = inxt AND ord = -1;
    IF ROW_COUNT() > 0 THEN
      SET ilastord = ilastord + 1;
    END IF;
    IF inxt IS NULL THEN
      LEAVE this;
    END IF;
    SET ilastvisited = inxt;
  END LOOP;
END;

One reason Willet's is slower is that MySQL does not permit use of temporary tables with its queries; when all algorithms are denied temp tables, though, this algorithm is still slower than recursion.

Edge list subtrees are easier to query than their reputation suggests. And edge tables are flexible. For a tree describing a parts explosion rather than a family, just add columns for weight, quantity, assembly time, cost, price and so on. Reports need only aggregate column values and sums. We'll revisit this near the end of the chapter.

Enumerating paths in an edge-adjacency list

Path enumeration in an edge list tree is almost as easy as depth-first subtree traversal:

  • create a table for paths,
  • seed it with paths of unit length from the tree table,
  • iteratively add paths till there are no more to add.

MySQL's INSERT IGNORE command simplifies the code by removing the need for a NOT EXISTS(...) clause in the INSERT ... SELECT statement. Since adjacencies are logically symmetrical, we make path direction the caller's choice, UP or DOWN:

Listing 8
DROP PROCEDURE IF EXISTS ListAdjacencyPaths;
DELIMITER |
CREATE PROCEDURE ListAdjacencyPaths( IN direction CHAR(5) )
BEGIN
  DROP TABLE IF EXISTS paths;
  CREATE TABLE paths(
    start SMALLINT,
    stop SMALLINT,
    len SMALLINT,
    PRIMARY KEY(start,stop)
  ) ENGINE=HEAP;
  IF direction = 'UP' THEN
    INSERT INTO paths
      SELECT childID,parentID,1
      FROM familytree;
  ELSE
    INSERT INTO paths
      SELECT parentID,childID,1
      FROM familytree;
  END IF;
  WHILE ROW_COUNT() > 0 DO
    INSERT IGNORE INTO paths
      SELECT DISTINCT
        p1.start,
        p2.stop,
        p1.len + p2.len
      FROM paths AS p1 INNER JOIN paths AS p2 ON p1.stop = p2.start;
  END WHILE;
  SELECT start, stop, len
  FROM paths
  ORDER BY start, stop;
  DROP TABLE paths;
END;
|
DELIMITER ;

To find the paths from just one node, seed the paths table with paths from the starting node, then iteratively search a JOIN of familytree and paths for edges which will extend existing paths in the user-specified direction:

Listing 9
DROP PROCEDURE IF EXISTS ListAdjacencyPathsOfNode;
DELIMITER |
CREATE PROCEDURE ListAdjacencyPathsOfNode( IN node SMALLINT, IN direction CHAR(5) )
BEGIN
  TRUNCATE paths;
  IF direction = 'UP' THEN
    INSERT INTO paths
      SELECT childID,parentID,1
      FROM familytree
      WHERE childID = node;
  ELSE
    INSERT INTO paths
      SELECT parentID,childID,1
      FROM familytree
      WHERE parentID = node;
  END IF;
  WHILE ROW_COUNT() > 0 DO
    IF direction = 'UP' THEN
      INSERT IGNORE INTO paths
        SELECT DISTINCT
          paths.start,
          familytree.parentID,
          paths.len + 1
        FROM paths
          INNER JOIN familytree ON paths.stop = familytree.childID;
    ELSE
      INSERT IGNORE INTO paths
        SELECT DISTINCT
          paths.start,
          familytree.childID,
          paths.len + 1
        FROM paths
          INNER JOIN familytree ON paths.stop = familytree.parentID;

    END IF;
  END WHILE;
    SELECT start, stop, len
    FROM paths
    ORDER BY start, stop;
END;
|
DELIMITER ;

CALL ListAdjacencyPathsOfNode(1,'DOWN');
+-------+------+------+
| start | stop | len  |
+-------+------+------+
|     1 |    2 |    1 |
|     1 |    3 |    1 |
|     1 |    4 |    2 |
|     1 |    5 |    2 |
|     1 |    6 |    2 |
|     1 |    7 |    2 |
|     1 |    8 |    2 |
|     1 |    9 |    2 |
|     1 |   10 |    2 |
|     1 |   11 |    2 |
|     1 |   12 |    3 |
|     1 |   13 |    3 |
|     1 |   14 |    3 |
|     1 |   15 |    3 |
|     1 |   16 |    3 |
|     1 |   17 |    3 |
|     1 |   18 |    3 |
|     1 |   19 |    4 |
|     1 |   20 |    4 |
|     1 |   21 |    4 |
|     1 |   22 |    4 |
|     1 |   23 |    5 |
+-------+------+------+

These algorithms don't bend the brain. They perform acceptably with large trees. Querying edge-adjacency lists for subtrees and paths is less daunting than their reputation suggests.

Nested sets model of a tree

Imagine an oval drawn round every leaf and every subtree in Fig 2, and a final oval round the entire tree. The tree is a set. Each subtree is a subset. That's the basic idea of the nested sets model.

The advantage of the nested sets model is that root, leaves, subtrees, levels, tree height, ancestors, descendants and paths can be retrieved without recursion or application language code. The disadvantages are:

  • initial setup of the tree table can be difficult,
  • queries for parents (immediate superiors) and children (immediate subordinates) are more complicated than with an edge list model,
  • insertion, updates and deletion are extremely cumbersome since they may require updates to much of the tree.

The nested sets model depends on using a modified preorder tree traversal (MPTT) depth-first algorithm to assign each node left and right integers which define the node's tree position. All nodes of a subtree have

  • left values greater than the subtree parent's left value, and
  • right values smaller than that of the subtree parent's right value.

so queries for subtrees are dead simple. If the numbering scheme is integer-sequential as in Fig 3, the root node receives a left value of 1 and a right value equal to twice the item count.

To see how to code nested sets using MPTT, trace the ascending integers in Fig 3, starting with 1 on the left side of the root node (Richard Shakespeare). Following edges downward and leftward, the left side of each box gets the next integer. When you reach a leaf (Joan, left=3), the right side of that box gets the next integer (4). If there is another node to the right on the same level, continue in that direction; otherwise continue up the right side of the subtree you just descended. When you arrive back at the root on the right side, you're done. Down, right and up.

A serious problem with this scheme jumps out right away: after you've written the Fig 3 tree to a table, what if historians discover an older brother or sister of Henry and John? Every row in the tree table must be updated!

Celko and others have proposed alternative numbering schemes to get round this problem, but the logical difficulty remains: inserts and updates can invalidate many or all rows, and no SQL CHECK or CONSTRAINT can prevent it. The nested sets model is not good for trees which require frequent updates, and is pretty much unsupportable for large updatable trees that will be accessed by many concurrent users. But as we'll see in a moment, it can be very useful indeed for reporting a tree.

How to build a nested set representation from an edge list

Obviously, numbering a tree by hand will be error-prone, and seriously impractical for large trees. It's usually best, therefore, to code the tree initially as an edge-adjacency list, then use a stored procedure to translate the edge list to a nested sets model. We can write a stored procedure that uses Celko's pushdown stack method to translate any edge list into a nested sets tree:

  1. create a table for the tree: node, leftedge, rightedge, and a stack pointer (top),
  2. seed that table, nestedsettree, with the root node of the adjacency tree,
  3. set a counter to 1 plus the left value of the root node, i.e. 2,
  4. while that counter is less than the right value of the root node ...
    • insert rows for children of parent rows into nestedsettree, or
    • update existing right integers in nestedsettree.
Listing 10
DROP PROCEDURE IF EXISTS EdgeListToNestedSet;
DELIMITER |
CREATE PROCEDURE EdgeListToNestedSet( edgeTable CHAR(64), idCol CHAR(64), parentCol CHAR(64) )
BEGIN
  DECLARE maxrightedge, rows SMALLINT DEFAULT 0;
  DECLARE current SMALLINT DEFAULT 1;
  DECLARE nextedge SMALLINT DEFAULT 2;
  -- create working tree table as a copy of edgeTable
  DROP TEMPORARY TABLE IF EXISTS tree;
  CREATE TEMPORARY TABLE tree( childID INT, parentID INT );
  SET @sql = CONCAT( 'INSERT INTO tree SELECT ', idCol, ',', parentCol, ' FROM ', edgeTable );
  PREPARE stmt FROM @sql;
  EXECUTE stmt;
  DROP PREPARE stmt;
  -- initialise result table
  DROP TABLE IF EXISTS nestedsettree;
  CREATE TABLE nestedsettree (
    top SMALLINT, nodeID SMALLINT, leftedge SMALLINT, rightedge SMALLINT
  ) ENGINE=HEAP;
  -- find root of tree (or: add an sproc param for the desired root value)
  SET @sql = CONCAT( 'SELECT DISTINCT f.', parentCol, ' INTO @root FROM ',
                     edgeTable, ' AS f LEFT JOIN ', edgeTable, ' AS t ON f.',
                     parentCol, '=', 't.', idCol, ' WHERE t.', idCol, ' IS NULL'
                   );
  -- For the familytree table, the above query parses to:
  -- SELECT DISTINCT f.parentid INTO @root 
  -- FROM familytree AS f LEFT JOIN familytree AS t ON f.parentid=t.childid 
  -- WHERE t.childid IS NULL |
  PREPARE stmt FROM @sql;
  EXECUTE stmt;
  DROP PREPARE stmt;
  -- build nested sets tree
  SET maxrightedge = 2 * (1 + (SELECT + COUNT(*) FROM tree));
  INSERT INTO nestedsettree VALUES( 1, @root, 1, maxrightedge );
  WHILE nextedge < maxrightedge DO
    SELECT *
    FROM nestedsettree AS s
    JOIN tree AS t ON s.nodeID=t.parentID AND s.top=current;
    SET rows = FOUND_ROWS();
    IF rows > 0 THEN
      BEGIN
        INSERT INTO nestedsettree
          SELECT current+1, MIN(t.childID), nextedge, NULL
          FROM nestedsettree AS s
          JOIN tree AS t ON s.nodeID = t.parentID AND s.top = current;
        DELETE FROM tree
        WHERE childID = (SELECT nodeID FROM nestedsettree WHERE top=(current+1));
        SET nextedge = nextedge + 1;
        SET current = current + 1;
       END;
     ELSE
       BEGIN
         UPDATE nestedsettree
         SET rightedge=nextedge, top = -top
         WHERE top=current;
         SET nextedge=nextedge+1;
         SET current=current-1;
       END;
    END IF;
  END WHILE;
  SET rows := ( SELECT COUNT(*) FROM tree );
  DROP TEMPORARY TABLE tree;
  -- show result
  IF rows > 0 THEN
    SELECT 'Orphaned rows remain';
  ELSE
    SELECT nodeID, leftedge AS 'Left', rightedge AS 'Right'
    FROM nestedsettree ORDER BY nodeID;
  END IF;
END |
DELIMITER ;
CALL EdgeListToNestedSet( 'familytree', 'childID', 'parentID' );
+--------+------+-------+
| nodeID | Left | Right |
+--------+------+-------+
|      1 |    1 |    46 |
|      2 |    2 |    43 |
|      3 |   44 |    45 |
|      4 |    3 |     4 |
|      5 |    5 |     6 |
|      6 |    7 |    24 |
|      7 |   25 |    26 |
|      8 |   27 |    36 |
|      9 |   37 |    38 |
|     10 |   39 |    40 |
|     11 |   41 |    42 |
|     12 |    8 |    13 |
|     13 |   14 |    15 |
|     14 |   16 |    23 |
|     15 |   28 |    29 |
|     16 |   30 |    31 |
|     17 |   32 |    33 |
|     18 |   34 |    35 |
|     19 |    9 |    12 |
|     20 |   17 |    18 |
|     21 |   19 |    20 |
|     22 |   21 |    22 |
|     23 |   10 |    11 |
+--------+------+-------+
Finding a node's parent and children

A nested sets tree can be queried without recursion, but using the model's arithmetic in a query requires a bit of thought. For example, if we INNER JOIN the tree table AS t1 to itself AS t2 ON t2.leftedge BETWEEN t1.leftedge AND t1.rightedge, and if we scope the query to the descendants of a particular node, we get a list of t2.nodeID values in which the children (one level down) occur once, the grandkids (two levels down) occur twice, and so on:

Listing 11a
SELECT GROUP_CONCAT(t2.nodeID ORDER BY t2.nodeID) AS 'Descendants of William'
FROM nestedsettree AS t1
INNER JOIN nestedsettree AS t2
  ON t2.leftedge BETWEEN t1.leftedge AND t1.rightedge
WHERE t1.leftedge > 7 AND t1.rightedge < 24;
+-------------------------------------------+
| Descendants of William                    |
+-------------------------------------------+
| 12,13,14,19,19,20,20,21,21,22,22,23,23,23 |
+-------------------------------------------+

Therefore HAVING COUNT(t2.nodeID)=1 will scope listed descendants to those who are one level down:

Listing 11b
DROP PROCEDURE IF EXISTS ListNestedSetChildNodes;
DELIMITER |
CREATE PROCEDURE ListNestedSetChildNodes( node SMALLINT )
BEGIN
  DECLARE thisleft, thisright SMALLINT DEFAULT 0;
  SELECT leftedge, rightedge
    INTO thisleft, thisright
  FROM nestedsettree
  WHERE nodeID = node;
  SELECT
    PersonName(t2.nodeid) AS Children
  FROM nestedsettree AS t1
    INNER JOIN nestedsettree AS t2
    ON t2.leftedge BETWEEN t1.leftedge AND t1.rightedge
  WHERE t1.leftedge > thisleft AND t1.rightedge < thisright
  GROUP BY t2.nodeid
  HAVING COUNT(t2.nodeid) = 1
  ORDER BY t2.leftedge;
END;
|
DELIMITER ;

CALL ListNestedSetChildNodes(6);
+--------------------+
| Children           |
+--------------------+
| Susana Shakespeare |
| Hamnet Shakespeare |
| Judith Shakespeare |
+--------------------+

Similar logic gets us the parent of a node:

  1. retrieve its leftedge and rightedge values,
  2. compute its level,
  3. find the node which is one level up and which has edge values outside the node's leftedge and rightedge values.
Listing 12
DROP PROCEDURE IF EXISTS ShowNestedSetParent;
DELIMITER |
CREATE PROCEDURE ShowNestedSetParent( node SMALLINT )
BEGIN
  DECLARE level, thisleft, thisright SMALLINT DEFAULT 0;
  -- find node edges
  SELECT leftedge, rightedge
    INTO thisleft, thisright
  FROM nestedsettree
  WHERE nodeID = node;
  -- find node level
  SELECT COUNT(n1.nodeid)
    INTO level
  FROM nestedsettree AS n1
    INNER JOIN nestedsettree AS n2
    ON n2.leftedge BETWEEN n1.leftedge AND n1.rightedge
  WHERE n2.nodeid = node
  GROUP BY n2.nodeid;
  -- find parent
  SELECT
    PersonName(n2.nodeid) AS Parent
  FROM nestedsettree AS n1
    INNER JOIN nestedsettree AS n2
    ON n2.leftedge BETWEEN n1.leftedge AND n1.rightedge
  WHERE n2.leftedge < thisleft AND n2.rightedge > thisright
  GROUP BY n2.nodeid
  HAVING COUNT(n1.nodeid)=level-1;
END;
|
DELIMITER ;
CALL ShowNestedSetParent(6);
+-------------------+
| Child             |
+-------------------+
| Henry Shakespeare |
+-------------------+
Other queries

For some queries, adjacency list and nested sets queries are equivalently simple. For example to find the tree root and leaves, compare Listing 6 with:

Listing 13
SELECT
  name AS Paterfamilias,
  IFNULL(born,'?') AS Born,
  IFNULL(died,'?') AS Died
FROM nestedsettree AS t
INNER JOIN family AS f ON t.nodeID=f.ID
WHERE leftedge = 1;
+---------------------+------+------+
| Paterfamilias       | Born | Died |
+---------------------+------+------+
| Richard Shakespeare | ?    | 1561 |
+---------------------+------+------+

SELECT
  name AS 'Childless Shakespeares',
  IFNULL(born,'?') AS Born,
  IFNULL(died,'?') AS Died
FROM nestedsettree AS t
INNER JOIN family AS f ON t.nodeID=f.ID
WHERE rightedge = leftedge + 1;
+------------------------+------+------+
| Childless Shakespeares | Born | Died |
+------------------------+------+------+
| Joan Shakespeare       | 1558 | ?    |
| Margaret Shakespeare   | 1562 | 1563 |
| John Bernard           | ?    | 1674 |
| Hamnet Shakespeare     | 1585 | 1596 |
| Shakespeare Quiney     | 1616 | 1617 |
| Richard Quiney         | 1618 | 1639 |
| Thomas Quiney          | 1620 | 1639 |
| Gilbert Shakespeare    | 1566 | 1612 |
| William Hart           | 1600 | 1639 |
| Mary Hart              | 1603 | 1607 |
| Thomas Hart            | 1605 | 1670 |
| Michael Hart           | 1608 | 1618 |
| Anne Shakespeare       | 1571 | 1579 |
| Richard Shakespeare    | 1574 | 1613 |
| Edmond Shakespeare     | 1580 | 1607 |
| John Shakespeare       | 1530 | 1601 |
+------------------------+------+------+

But in contrast to edge list models, finding subtrees in a nested sets model requires no twisted code, no stored procedure. To retrieve the nestedsettree nodes in William's subtree, simply ask for the nodes whose leftedge values are greater, and whose rightedge values are smaller than William's:

Listing 14
SELECT
  PersonName(t.nodeID) AS Descendant
FROM nestedsettree AS s
  INNER JOIN nestedsettree AS t
  ON s.leftedge < t.leftedge AND s.rightedge > t.rightedge
WHERE s.nodeID = (
  SELECT ID FROM family
  WHERE name='William Shakespeare'
);

Finding a single path in the nested sets model is about as complicated as path enumeration (Listings 8, 9) with edge-adjacency lists:

Listing 15
SELECT
  t2.nodeID AS Node,
  PersonName(t2.nodeID) AS Person,
  (SELECT COUNT(*)
   FROM nestedsettree AS t4
   WHERE t4.leftedge BETWEEN t1.leftedge AND t1.rightedge
     AND t2.leftedge BETWEEN t4.leftedge AND t4.rightedge
   ) AS Path
FROM nestedsettree AS t1
  INNER JOIN nestedsettree AS t2 ON t2.leftedge BETWEEN t1.leftedge AND t1.rightedge
  INNER JOIN nestedsettree AS t3 ON t3.leftedge BETWEEN t2.leftedge AND t2.rightedge
WHERE t1.nodeID=(SELECT ID FROM family WHERE name='William Shakespeare')
  AND t3.nodeID=(SELECT ID FROM family WHERE name='John Bernard');
+------+---------------------+------+
| Node | Person              | Path |
+------+---------------------+------+
|    6 | William Shakespeare |    1 |
|   12 | Susana Shakespeare  |    2 |
|   19 | Elizabeth Hall      |    3 |
|   23 | John Bernard        |    4 |
+------+---------------------+------+
Displaying the tree

Here the nested sets model shines. The arithmetic that was used to build the tree makes short work of summary queries. For example to retrieve a node list which preserves all parent-child relations, we need just two facts:

  • listing order is the order taken in the node walk that created the tree, i.e. leftedge,
  • a node's indentation depth is simply the JOIN (edge) count from root to node:
Listing 16
SELECT
  CONCAT( SPACE(2*COUNT(n1.nodeid)-2), PersonName(n2.nodeid) )
  AS 'The Shakespeare Family Tree'
FROM nestedsettree AS n1
  INNER JOIN nestedsettree n2
  ON n2.leftedge BETWEEN n1.leftedge AND n1.rightedge
GROUP BY n2.nodeid
ORDER BY n2.leftedge;
+-----------------------------+
| The Shakespeare Family Tree |
+-----------------------------+
| Richard Shakespeare         |
|   Henry Shakespeare         |
|     Joan Shakespeare        |
|     Margaret Shakespeare    |
|     William Shakespeare     |
|       Susana Shakespeare    |
|         Elizabeth Hall      |
|           John Bernard      |
|       Hamnet Shakespeare    |
|       Judith Shakespeare    |
|         Shakespeare Quiney  |
|         Richard Quiney      |
|         Thomas Quiney       |
|     Gilbert Shakespeare     |
|     Joan Shakespeare        |
|       William Hart          |
|       Mary Hart             |
|       Thomas Hart           |
|       Michael Hart          |
|     Anne Shakespeare        |
|     Richard Shakespeare     |
|     Edmond Shakespeare      |
|   John Shakespeare          |
+-----------------------------+

To retrieve only a subtree, add a query clause which restricts nodes to those whose edges are within the range of the parent node's left and right edge values, for example for William and his descendants...

WHERE n1.leftedge >= 7 AND n1.rightedge <=24

Node insertions, updates and deletions

Nested set arithmetic also helps with insertions, updates and deletions, but the problem remains that changing just one node can require changing much of the tree.

Inserting a node in the tree requires at least two pieces of information: the nodeID to insert, and the nodeID of its parent. The model is normalised so the nodeID first must have been added to the parent (family) table. The algorithm for adding the node to the tree is:

  1. increment leftedge by 2 in nodes where the rightedge value is greater than the parent's rightedge,
  2. increment rightedge by 2 in nodes where the leftedge value is greater than the parent's leftedge,
  3. insert a row with the given nodeID, leftedge = 1 + parent's leftedge, rightedge = 2 + parent's leftedge.

That's not difficult, but all rows will have to be updated!

Listing 17
DROP PROCEDURE IF EXISTS InsertNestedSetNode;
DELIMITER |
CREATE PROCEDURE InsertNestedSetNode( IN node SMALLINT, IN parent SMALLINT )
BEGIN
  DECLARE parentleft, parentright SMALLINT DEFAULT 0;
  SELECT leftedge, rightedge
    INTO parentleft, parentright
  FROM nestedsettree
  WHERE nodeID = parent;
  IF FOUND_ROWS() = 1 THEN
    BEGIN
      UPDATE nestedsettree
        SET rightedge = rightedge + 2
      WHERE rightedge > parentleft;
      UPDATE nestedsettree
        SET leftedge = leftedge + 2
      WHERE leftedge > parentleft;
      INSERT INTO nestedsettree
        VALUES ( 0, node, parentleft + 1, parentleft + 2 );
    END;
  END IF;
END;
|
DELIMITER ;

"Sibline" or horizontal order is obviously significant in family trees, but may not be significant in other trees. Listing 17 adds the new node at the left edge of the sibline. To specify another position, modify the procedure to accept a third parameter for the nodeID which is to be to the left or right of the insertion point.

Updating a node in place requires nothing more than editing nodeID to point at a different parent row.

Deleting a node raises the problem of how to repair links severed by the deletion. In tree models of parts explosions, the item to be deleted is often replaced by a new item, so it can be treated like a simple nodeID update. In organisational boss-employee charts, though, does a colleague move over, does a subordinate get promoted, does everybody in the subtree move up a level, or does something else happen? No formula can catch all the possibilities. Listing 18 illustrates how to handle two common scenarios, move everyone up, and move someone over. All possibilities except simple replacement of the nodeID involve changes elsewhere in the tree.

Listing 18
DROP PROCEDURE IF EXISTS DeleteNestedSetNode;
DELIMITER |
CREATE PROCEDURE DeleteNestedSetNode( IN mode CHAR(7), IN node SMALLINT )
BEGIN
  DECLARE thisleft, thisright SMALLINT DEFAULT 0;
  SELECT leftedge, rightedge
    INTO thisleft, thisright
  FROM nestedsettree
  WHERE nodeID = node;
  IF mode = 'PROMOTE' THEN
    BEGIN                                                         -- Ian Holsman found these two bugs
      DELETE FROM nestedsettree
      WHERE nodeID = node;
      UPDATE nestedsettree
        SET leftedge = leftedge - 1, rightedge = rightedge - 1    -- rather than = thisleft
      WHERE leftedge BETWEEN thisleft AND thisright;
      UPDATE nestedsettree
        SET rightedge = rightedge - 2
      WHERE rightedge > thisright;
      UPDATE nestedsettree
        SET leftedge = leftedge - 2
      WHERE leftedge > thisright;                                 -- rather than > thisleft
    END;
  ELSEIF mode = 'REPLACE' THEN
    BEGIN
      UPDATE nestedsettree
        SET leftedge = thisleft - 1, rightedge = thisright
      WHERE leftedge = thisleft + 1;
      UPDATE nestedsettree
        SET rightedge = rightedge - 2
      WHERE rightedge > thisleft;
      UPDATE nestedsettree
        SET leftedge = leftedge - 2
      WHERE leftedge > thisleft;
      DELETE FROM nestedsettree
      WHERE nodeID = node;
    END;
  END IF;
END;
|
DELIMITER ;
Nested set model summary

Given the concurrency nightmare which nested sets impose for inserts and deletions, it is reasonable to reserve the nested set model for fairly static trees whose users are mostly interested in querying subtrees. You could think of the nested set model as an OLAP tool: maintain an OLTP tree in an edge-adjacency list representation, and build a nested sets OLAP table when the report is needed.

If you will be using the nested sets model, you may be converting back and forth with edge list models, so here is a simple query which generates an edge list from a nested set tree:

Listing 19
SELECT
  p.nodeID AS parentID,
  c.nodeID AS childID
FROM nestedsettree AS p
  INNER JOIN nestedsettree AS c
  ON p.leftedge = (SELECT MAX(s.leftedge)
                   FROM nestedsettree AS s
                   WHERE c.leftedge > s.leftedge
                     AND c.leftedge < s.rightedge)
ORDER BY p.nodeID;

Edge list model of a non-tree graph

Many graphs are not trees. Imagine a small airline which has just acquired licences for flights no longer than 6,000 km between Los Angeles (LAX), New York (JFK), Heathrow in London, Charles de Gaulle in Paris, Amsterdam-Schiphol, Arlanda in Sweden, and Helsinki-Vantaa. You have been asked to compute the shortest possible one-way routes that do not deviate more than 90° from the direction of the first hop—roughly, one-way routes and no circuits.

Airports are nodes, flights are edges, routes are paths. We will need three tables.

Airports (nodes)

To identify an airport we need its code, location name, latitude and longitude. Latitude and longitude are usually given as degrees, minutes and seconds, north or south of the equator, east or west of Greenwich. To hide details that aren't directly relevant to nodes and edges, code latitude and longitude as simple reals where longitudes west of Greenwich and latitudes south of the equator are negative, whilst longitudes east of Greenwich and latitudes north of the equator are positive:

Listing 20
CREATE TABLE airports (
  code char(3) NOT NULL,
  city char(100) default NULL,
  latitude float NOT NULL,
  longitude float NOT NULL,
  PRIMARY KEY (code)
) ENGINE=MyISAM;

INSERT INTO airports VALUES ('JFK', 'New York, NY', 40.75, -73.97);
INSERT INTO airports VALUES ('LAX', 'Los Angeles, CA', 34.05, -118.22);
INSERT INTO airports VALUES ('LHR', 'London, England', 51.5, -0.45);
INSERT INTO airports VALUES ('HEL', 'Helsinki, Finland', 60.17, 24.97);
INSERT INTO airports VALUES ('CDG', 'Paris, France', 48.86, 2.33);
INSERT INTO airports VALUES ('STL', 'St Louis, MO', 38.63, -90.2);
INSERT INTO airports VALUES ('ARN', 'Stockholm, Sweden', 59.33, 18.05);
Flights (edges)

The model attaches two weights to flights: distance and direction.

We need a method of calculating the Great Circle Distance—the geographical distance between any two cities - another natural job for a stored function. The distance calculation

  • converts to radians the degree coordinates of any two points on the earth's surface,
  • calculates the angle of the arc subtended by the two points, and
  • converts the result, also in radians, to surface (circumferential) kilometres (1 radian=6,378.388 km).
Listing 21
SET GLOBAL log_bin_trust_function_creators=TRUE;   -- since 5.0.16
DROP FUNCTION IF EXISTS GeoDistKM;
DELIMITER |
CREATE FUNCTION GeoDistKM( lat1 FLOAT, lon1 FLOAT, lat2 FLOAT, lon2 FLOAT ) RETURNS float
BEGIN
  DECLARE pi, q1, q2, q3 FLOAT;
  SET pi = PI();
  SET lat1 = lat1 * pi / 180;
  SET lon1 = lon1 * pi / 180;
  SET lat2 = lat2 * pi / 180;
  SET lon2 = lon2 * pi / 180;
  SET q1 = COS(lon1-lon2);
  SET q2 = COS(lat1-lat2);
  SET q3 = COS(lat1+lat2);
  SET rads = ACOS( 0.5*((1.0+q1)*q2 - (1.0-q1)*q3) );
  RETURN 6378.388 * rads;
END;
|
DELIMITER ;

That takes care of flight distances. Flight direction is, approximately, the arctangent (ATAN) of the difference between flights.depart and flights.arrive latitudes and longitudes. Now we can seed the airline's flights table with one-hop flights up to 6,000 km long:

Listing 22
CREATE TABLE flights (
  id INT PRIMARY KEY AUTO_INCREMENT,
  depart CHAR(3),
  arrive CHAR(3),
  distance DECIMAL(10,2),
  direction DECIMAL(10,2)
) ENGINE=MYISAM;

INSERT INTO flights
  SELECT
  NULL,
  depart.code,
  arrive.code,
  ROUND(GeoDistKM(depart.latitude,depart.longitude,arrive.latitude,arrive.longitude),2),
  ROUND(DEGREES(ATAN(arrive.latitude-depart.latitude,arrive.longitude-depart.longitude)),2)
  FROM airports AS depart
  INNER JOIN airports AS arrive ON depart.code <> arrive.code
  HAVING Km <= 6000;

SELECT * FROM flights;
+----+--------+--------+----------+-----------+
| id | depart | arrive | distance | direction |
+----+--------+--------+----------+-----------+
|  1 | LAX    | JFK    | 3941.18  | 8.61      |
|  2 | LHR    | JFK    | 5550.77  | -171.68   |
|  3 | CDG    | JFK    | 5837.46  | -173.93   |
|  4 | STL    | JFK    | 1408.11  | 7.44      |
|  5 | JFK    | LAX    | 3941.18  | -171.39   |
|  6 | STL    | LAX    | 2553.37  | -170.72   |
|  7 | JFK    | LHR    | 5550.77  | 8.32      |
|  8 | HEL    | LHR    | 1841.91  | -161.17   |
|  9 | CDG    | LHR    | 354.41   | 136.48    |
| 10 | ARN    | LHR    | 1450.12  | -157.06   |
| 11 | LHR    | HEL    | 1841.91  | 18.83     |
| 12 | CDG    | HEL    | 1912.96  | 26.54     |
| 13 | ARN    | HEL    | 398.99   | 6.92      |
| 14 | JFK    | CDG    | 5837.46  | 6.07      |
| 15 | LHR    | CDG    | 354.41   | -43.52    |
| 16 | HEL    | CDG    | 1912.96  | -153.46   |
| 17 | ARN    | CDG    | 1545.23  | -146.34   |
| 18 | JFK    | STL    | 1408.11  | -172.56   |
| 19 | LAX    | STL    | 2553.37  | 9.28      |
| 20 | LHR    | ARN    | 1450.12  | 22.94     |
| 21 | HEL    | ARN    | 398.99   | -173.08   |
| 22 | CDG    | ARN    | 1545.23  | 33.66     |
+----+--------+--------+----------+-----------+

The distances agree approximately with public information sources for flight lengths. For a pair of airports A and B not very near the poles, the error in calculating direction using ATAN(), is small. To remove that error, instead of ATAN() use a formula from spherical trigonometry (for example one of the formulas at http://www.dynagen.co.za/eugene/where/formula.html).

Routes (paths)

A route is a path along one or more of these edges, so flights:routes is a 1:many relationship. For simplicity, though, we denormalise our representation of routes with a variation of the materialised path model to store all the hops of one route as a list of flights in one routes column. The column routes.route is the sequence of airports, from first departure to final arrival, the column routes.hops is the number of hops in that route, and the column routes.direction is the direction:

Listing 23
CREATE TABLE routes (
  id INT PRIMARY KEY AUTO_INCREMENT,
  depart CHAR(3),
  arrive CHAR(3),
  hops SMALLINT,
  route CHAR(50),
  distance DECIMAL(10,2),
  direction DECIMAL(10,2)
) ENGINE=MYISAM;

Starting with an empty routes table, how do we populate it with the shortest routes between all ordered pairs of airports?

  1. Insert all 1-hop flights from the flights table.
  2. Add in the set of shortest multi-hop routes for all pairs of airports which don't have rows in the flights table.

For 1-hop flights we just write

Listing 24
INSERT INTO routes
  SELECT
    NULL,
    depart,
    arrive,
    1,
    CONCAT(depart,',',arrive),
    distance,
    direction
  FROM flights;

NULL being the placeholder for the auto-incrementing id column.

For multi-hop routes, we iteratively add in sets of all allowed 2-hop, 3-hop, ... n-hop routes, replacing longer routes by shorter routes as we find them, until there is nothing more to add or replace. That also breaks down to two logical steps: add hops to build the set of next allowed routes, and update longer routes with shorter ones.

Next allowed routes

The set of next allowed routes is the set of shortest routes that can be built by adding, to existing routes, flights which leave from the last arrival airport of an existing route, which arrive at an airport which is not yet in the given route, and which stay within ± 90° of the route's initial compass direction. That is, every new route is a JOIN between routes and flights in which

  • depart = routes.depart,
  • arrive = flights.arrive,
  • flights.depart = routes.arrive,
  • distance = MIN(routes.distance + flights.distance),
  • LOCATE( flights.arrive,routes.route) = 0,
  • flights.direction+360 > routes.direction+270 AND flights.direction+360 < routes.direction+450

This is a natural logical unit of work for a VIEW:

Listing 25
CREATE OR REPLACE VIEW nextroutes AS
  SELECT
    routes.depart,
    flights.arrive,
    routes.hops+1 AS hops,
    CONCAT(routes.route, ',', flights.arrive) AS route,
    MIN(routes.distance + flights.distance) AS distance,
    routes.direction
  FROM routes INNER JOIN flights
    ON routes.arrive = flights.depart
    AND LOCATE(flights.arrive,routes.route) = 0
  WHERE flights.direction+360>routes.direction+270 
    AND flights.direction+360<routes.direction+450
  GROUP BY depart,arrive;

How to add these new hops to routes? In standard SQL, this variant on a query by Scott Stephens should do it...

Listing 26
INSERT INTO routes
  SELECT NULL,depart,arrive,hops,route,distance,direction FROM nextroutes
  WHERE (nextroutes.depart,nextroutes.arrive) NOT IN (
    SELECT depart,arrive FROM routes
  );

but MySQL does not yet support subqueries on the table being updated. We have to use a subquery-less (and faster) version of that logic:

Listing 27
INSERT INTO routes
  SELECT
    NULL,
    nextroutes.depart,
    nextroutes.arrive,
    nextroutes.hops,
    nextroutes.route,
    nextroutes.distance,
    nextroutes.direction
  FROM nextroutes
  LEFT JOIN routes ON nextroutes.depart = routes.depart
        AND nextroutes.arrive = routes.arrive
  WHERE routes.depart IS NULL AND routes.arrive IS NULL;

Running that code right after the initial seeding from flights gives ...

SELECT * FROM routes;
+----+--------+--------+------+-------------+----------+-----------+
| id | depart | arrive | hops | route       | distance | direction |
+----+--------+--------+------+-------------+----------+-----------+
|  1 | LAX    | JFK    |    1 | LAX,JFK     | 3941.18  | 8.61      |
|  2 | LHR    | JFK    |    1 | LHR,JFK     | 5550.77  | -171.68   |
|  3 | CDG    | JFK    |    1 | CDG,JFK     | 5837.46  | -173.93   |
|  4 | STL    | JFK    |    1 | STL,JFK     | 1408.11  | 7.44      |
|  5 | JFK    | LAX    |    1 | JFK,LAX     | 3941.18  | -171.39   |
|  6 | STL    | LAX    |    1 | STL,LAX     | 2553.37  | -170.72   |
|  7 | JFK    | LHR    |    1 | JFK,LHR     | 5550.77  | 8.32      |
|  8 | HEL    | LHR    |    1 | HEL,LHR     | 1841.91  | -161.17   |
|  9 | CDG    | LHR    |    1 | CDG,LHR     | 354.41   | 136.48    |
| 10 | ARN    | LHR    |    1 | ARN,LHR     | 1450.12  | -157.06   |
| 11 | LHR    | HEL    |    1 | LHR,HEL     | 1841.91  | 18.83     |
| 12 | CDG    | HEL    |    1 | CDG,HEL     | 1912.96  | 26.54     |
| 13 | ARN    | HEL    |    1 | ARN,HEL     | 398.99   | 6.92      |
| 14 | JFK    | CDG    |    1 | JFK,CDG     | 5837.46  | 6.07      |
| 15 | LHR    | CDG    |    1 | LHR,CDG     | 354.41   | -43.52    |
| 16 | HEL    | CDG    |    1 | HEL,CDG     | 1912.96  | -153.46   |
| 17 | ARN    | CDG    |    1 | ARN,CDG     | 1545.23  | -146.34   |
| 18 | JFK    | STL    |    1 | JFK,STL     | 1408.11  | -172.56   |
| 19 | LAX    | STL    |    1 | LAX,STL     | 2553.37  | 9.28      |
| 20 | LHR    | ARN    |    1 | LHR,ARN     | 1450.12  | 22.94     |
| 21 | HEL    | ARN    |    1 | HEL,ARN     | 398.99   | -173.08   |
| 22 | CDG    | ARN    |    1 | CDG,ARN     | 1545.23  | 33.66     |
| 23 | ARN    | JFK    |    2 | ARN,LHR,JFK | 7000.89  | -157.06   |
| 24 | CDG    | LAX    |    2 | CDG,JFK,LAX | 9778.64  | -173.93   |
| 25 | CDG    | STL    |    2 | CDG,JFK,STL | 7245.57  | -173.93   |
| 26 | HEL    | JFK    |    2 | HEL,LHR,JFK | 7392.68  | -161.17   |
| 27 | JFK    | ARN    |    2 | JFK,LHR,ARN | 7000.89  | 8.32      |
| 28 | JFK    | HEL    |    2 | JFK,LHR,HEL | 7392.68  | 8.32      |
| 29 | LAX    | CDG    |    2 | LAX,JFK,CDG | 9778.64  | 8.61      |
| 30 | LAX    | LHR    |    2 | LAX,JFK,LHR | 9491.95  | 8.61      |
| 31 | LHR    | LAX    |    2 | LHR,JFK,LAX | 9491.95  | -171.68   |
| 32 | LHR    | STL    |    2 | LHR,JFK,STL | 6958.88  | -171.68   |
| 33 | STL    | CDG    |    2 | STL,JFK,CDG | 7245.57  | 7.44      |
| 34 | STL    | LHR    |    2 | STL,JFK,LHR | 6958.88  | 7.44      |
+----+--------+--------+------+-------------+----------+-----------+

... adding 12 two-hop rows.

Replace longer routes with shorter ones

As we build routes with more hops, it is logically possible that the nextroutes view will find shorter routes for an existing routes pair of depart and arrive. Standard SQL for replacing existing routes rows with nextroutes rows which match (depart, arrive) and have shorter distance values would be:

Listing 28
UPDATE routes SET (hops,route,distance,direction) = (
  SELECT hops, route, distance, direction
  FROM nextroutes
  WHERE nextroutes.depart = routes.depart AND nextroutes.arrive = routes.arrive
)
WHERE (depart,arrive) IN (
  SELECT depart,arrive FROM nextroutes
  WHERE nextroutes.distance < routes.distance
);

but MySQL does not support SET(col1,...) syntax, and as with Listing 7, MySQL does not yet accept subqueries referencing the table being updated, so we have to write more literal SQL:

Listing 29
UPDATE routes, nextroutes
SET
  routes.hops=nextroutes.hops,
  routes.route=nextroutes.route,
  routes.distance=nextroutes.distance,
  routes.direction=nextroutes.direction
WHERE routes.arrive=nextroutes.arrive
  AND routes.depart=nextroutes.depart
  AND nextroutes.distance < routes.distance;

Running this code right after the first run of Listing 27 updates no rows. To test the logic of iteration, continue running Listings 27 and 29 until no rows are being added or changed. The final result is:

SELECT * FROM ROUTES;
+----+--------+--------+------+-----------------+----------+-----------+
| id | depart | arrive | hops | route           | distance | direction |
+----+--------+--------+------+-----------------+----------+-----------+
|  1 | LAX    | JFK    |    1 | LAX,JFK         | 3941.18  | 8.61      |
|  2 | LHR    | JFK    |    1 | LHR,JFK         | 5550.77  | -171.68   |
|  3 | CDG    | JFK    |    1 | CDG,JFK         | 5837.46  | -173.93   |
|  4 | STL    | JFK    |    1 | STL,JFK         | 1408.11  | 7.44      |
|  5 | JFK    | LAX    |    1 | JFK,LAX         | 3941.18  | -171.39   |
|  6 | STL    | LAX    |    1 | STL,LAX         | 2553.37  | -170.72   |
|  7 | JFK    | LHR    |    1 | JFK,LHR         | 5550.77  | 8.32      |
|  8 | HEL    | LHR    |    1 | HEL,LHR         | 1841.91  | -161.17   |
|  9 | CDG    | LHR    |    1 | CDG,LHR         | 354.41   | 136.48    |
| 10 | ARN    | LHR    |    1 | ARN,LHR         | 1450.12  | -157.06   |
| 11 | LHR    | HEL    |    1 | LHR,HEL         | 1841.91  | 18.83     |
| 12 | CDG    | HEL    |    1 | CDG,HEL         | 1912.96  | 26.54     |
| 13 | ARN    | HEL    |    1 | ARN,HEL         | 398.99   | 6.92      |
| 14 | JFK    | CDG    |    1 | JFK,CDG         | 5837.46  | 6.07      |
| 15 | LHR    | CDG    |    1 | LHR,CDG         | 354.41   | -43.52    |
| 16 | HEL    | CDG    |    1 | HEL,CDG         | 1912.96  | -153.46   |
| 17 | ARN    | CDG    |    1 | ARN,CDG         | 1545.23  | -146.34   |
| 18 | JFK    | STL    |    1 | JFK,STL         | 1408.11  | -172.56   |
| 19 | LAX    | STL    |    1 | LAX,STL         | 2553.37  | 9.28      |
| 20 | LHR    | ARN    |    1 | LHR,ARN         | 1450.12  | 22.94     |
| 21 | HEL    | ARN    |    1 | HEL,ARN         | 398.99   | -173.08   |
| 22 | CDG    | ARN    |    1 | CDG,ARN         | 1545.23  | 33.66     |
| 23 | ARN    | JFK    |    2 | ARN,LHR,JFK     | 7000.89  | -157.06   |
| 24 | CDG    | LAX    |    2 | CDG,JFK,LAX     | 9778.64  | -173.93   |
| 25 | CDG    | STL    |    2 | CDG,JFK,STL     | 7245.57  | -173.93   |
| 26 | HEL    | JFK    |    2 | HEL,LHR,JFK     | 7392.68  | -161.17   |
| 27 | JFK    | ARN    |    2 | JFK,LHR,ARN     | 7000.89  | 8.32      |
| 28 | JFK    | HEL    |    2 | JFK,LHR,HEL     | 7392.68  | 8.32      |
| 29 | LAX    | CDG    |    2 | LAX,JFK,CDG     | 9778.64  | 8.61      |
| 30 | LAX    | LHR    |    2 | LAX,JFK,LHR     | 9491.95  | 8.61      |
| 31 | LHR    | LAX    |    2 | LHR,JFK,LAX     | 9491.95  | -171.68   |
| 32 | LHR    | STL    |    2 | LHR,JFK,STL     | 6958.88  | -171.68   |
| 33 | STL    | CDG    |    2 | STL,JFK,CDG     | 7245.57  | 7.44      |
| 34 | STL    | LHR    |    2 | STL,JFK,LHR     | 6958.88  | 7.44      |
| 35 | ARN    | LAX    |    3 | ARN,LHR,JFK,LAX | 10942.07 | -157.06   |
| 36 | ARN    | STL    |    3 | ARN,LHR,JFK,STL | 8409.00  | -157.06   |
| 37 | HEL    | LAX    |    3 | HEL,LHR,JFK,LAX | 11333.86 | -161.17   |
| 38 | HEL    | STL    |    3 | HEL,LHR,JFK,STL | 8800.79  | -161.17   |
| 39 | LAX    | ARN    |    3 | LAX,JFK,CDG,ARN | 10942.07 | 8.61      |
| 40 | LAX    | HEL    |    3 | LAX,JFK,CDG,HEL | 11333.86 | 8.61      |
| 41 | STL    | ARN    |    3 | STL,JFK,CDG,ARN | 8409.00  | 7.44      |
| 42 | STL    | HEL    |    3 | STL,JFK,CDG,HEL | 8800.79  | 7.44      |
+----+--------+--------+------+-----------------+----------+-----------+

All that's left to do is to assemble the code in a stored procedure:

Listing 30
DROP PROCEDURE IF EXISTS BuildRoutes;
DELIMITER |
CREATE PROCEDURE BuildRoutes()
BEGIN
  DECLARE rows INT DEFAULT 0;
  TRUNCATE routes;

  -- STEP 1, LISTING 24: SEED ROUTES WITH 1-HOP FLIGHTS
  INSERT INTO routes
    SELECT
      NULL,
      depart,
      arrive,
      1,
      CONCAT(depart,',',arrive),
      distance,
      direction
  FROM flights;
  SET rows = ROW_COUNT();

  WHILE (rows > 0) DO

    -- STEP 2, LISTINGS 25, 27: ADD NEXT SET OF ROUTES
    INSERT INTO routes
      SELECT
        NULL,
        nextroutes.depart,
        nextroutes.arrive,
        nextroutes.hops,
        nextroutes.route,
        nextroutes.distance,
        nextroutes.direction
      FROM nextroutes
      LEFT JOIN routes ON nextroutes.depart = routes.depart
            AND nextroutes.arrive = routes.arrive
      WHERE routes.depart IS NULL AND routes.arrive IS NULL;
    SET rows = ROW_COUNT();

    -- STEP 3, LISTING 29: UPDATE WITH SHORTER nextroutes ROUTES IF ANY
    UPDATE routes,nextroutes SET
      routes.hops=nextroutes.hops,
      routes.route=nextroutes.route,
      routes.distance=nextroutes.distance,
      routes.direction=nextroutes.direction
    WHERE routes.arrive=nextroutes.arrive
      AND routes.depart=nextroutes.depart
      AND nextroutes.distance < routes.distance;
    SET rows = rows + ROW_COUNT();

  END WHILE;

END;
|
DELIMITER ;

If you are running MySQL 5.0.6 or 5.0.7, BuildRoutes() fails to insert four rows:

+--------+--------+-----------------+------+----------+-----------+
| depart | arrive | route           | hops | distance | direction |
+--------+--------+-----------------+------+----------+-----------+
| ARN    | LAX    | ARN,LHR,JFK,LAX |    3 | 10942.07 | -157.06   |
| ARN    | STL    | ARN,LHR,JFK,STL |    3 | 8409.00  | -157.06   |
| HEL    | LAX    | HEL,LHR,JFK,LAX |    3 | 11333.86 | -161.17   |
| HEL    | STL    | HEL,LHR,JFK,STL |    3 | 8800.79  | -161.17   |
+--------+--------+-----------------+------+----------+-----------+

That MySQL bug (#11302) was corrected in 5.0.9.

Route queries

Route queries are straightforward. How do we check that the algorithm produced no duplicate depart-arrive pairs? The following query should yield zero rows,

Listing 31
SELECT depart, arrive, COUNT(*)
FROM routes
GROUP BY depart,arrive
HAVING COUNT(*) > 1;

and does. Reachability queries are just as simple, for example where can we fly to from Helsinki?

Listing 32
SELECT *
FROM routes
WHERE depart='HEL'
ORDER BY distance;
+----+--------+--------+------+-----------------+----------+-----------+
| id | depart | arrive | hops | route           | distance | direction |
+----+--------+--------+------+-----------------+----------+-----------+
| 21 | HEL    | ARN    |    1 | HEL,ARN         | 398.99   | -173.08   |
|  8 | HEL    | LHR    |    1 | HEL,LHR         | 1841.91  | -161.17   |
| 16 | HEL    | CDG    |    1 | HEL,CDG         | 1912.96  | -153.46   |
| 26 | HEL    | JFK    |    2 | HEL,LHR,JFK     | 7392.68  | -161.17   |
| 38 | HEL    | STL    |    3 | HEL,LHR,JFK,STL | 8800.79  | -161.17   |
| 37 | HEL    | LAX    |    3 | HEL,LHR,JFK,LAX | 11333.86 | -161.17   |
+----+--------+--------+------+-----------------+----------+-----------+

An extended edge list model is simple to implement, gracefully accepts extended attributes for nodes, edge and paths, does not unduly penalise updates, and responds to queries with reasonable speed.

Parts explosions

A bill of materials for a house would include the cement block, lumber, shingles, doors, wallboard, windows, plumbing, electrical system, heating system, and so on. Each subassembly also has a bill of materials; the heating system has a furnace, ducts, and so on. A bill of materials implosion links component pieces to a major assembly. A bill of materials explosion breaks apart assemblies and subassemblies into their component parts.

Which graph model best handles a parts explosion? Combining edge list and "nested sets" algorithms provides a clean solution.

Imagine a new company that plans to make variously sized bookcases, either packaged as do-it-yourself kits of, or assembled from sides, shelves, shelf brackets, backboards, feet and screws. Shelves and sides are cut from planks. Backboards are trimmed from laminated sheeting. Feet are machine-carved from readycut blocks. Screws and shelf brackets are purchased in bulk. Here are the elements of one bookcase:

  1 backboard, 2 x 1 m
    1 laminate
    8 screws
  2 sides 2m x 30 cm
    1 plank length 4m
    12 screws
  8 shelves 1 m x 30 cm (incl. top and bottom)
    2 planks
    24 shelf brackets
  4 feet 4cm x 4cm
    4 cubes
    16 screws

which may be packaged in a box for sale at one price, or assembled as a finished product at a different price. At any time we need to be able to answer questions like

  • Do we have enough parts to make the bookcases on order?
  • What assemblies or packages would be most profitable to make given the current inventory?

There is no reason to break the normalising rule that item detail belongs in a nodes table, and graph logic belongs in an edges table. Edges also require a quantity attribute, for example a shelf includes four shelf brackets. Nodes and edges may also have costs and prices:

  • item purchase cost,
  • item assembly cost,
  • assembly cost,
  • assembly selling price.

In many parts problems like this one, items occur in multiple assemblies and subassemblies. The graph is not a tree. Also, it is often desirable to model multiple graphs without the table glut that would arise from giving each graph its own edges table. A simple way to solve this problem is to represent multiple graphs (assemblies) in the edges table by giving every row not only childID and parentID pointers, but a pointer which identifies the root itemID of the graph to which the row belongs.

So the data model is just two tables, for items (nodes) and for product graphs or assemblies (edges). Assume that the company begins with a plan to sell the 2m x 1m bookcase in two forms, assembled and kit, and that the purchasing department has bought quantities of raw materials (laminate, planks, shelf supports, screws, wood cubes, boxes). Here are the nodes (items) and edges (assemblies):

Listing 33
CREATE TABLE items (
  itemID INT PRIMARY KEY AUTO_INCREMENT,
  name CHAR(20) NOT NULL,
  onhand INT NOT NULL DEFAULT 0,
  reserved INT NOT NULL DEFAULT 0,
  purchasecost DECIMAL(10,2) NOT NULL DEFAULT 0,
  assemblycost DECIMAL(10,2) NOT NULL DEFAULT 0,
  price DECIMAL(10,2) NOT NULL DEFAULT 0
);
CREATE TABLE assemblies (
  assemblyID INT NOT NULL,
  assemblyroot INT NOT NULL,
  childID INT NOT NULL,
  parentID INT NOT NULL,
  quantity DECIMAL(10,2) NOT NULL,
  assemblycost DECIMAL(10,2) NOT NULL,
  PRIMARY KEY(assemblyID,childID,parentID)
);
INSERT INTO items VALUES    -- inventory
  (1,'laminate',40,0,4,0,8),
  (2,'screw',1000,0,0.1,0,.2),
  (3,'plank',200,0,10,0,20),
  (4,'shelf bracket',400,0,0.20,0,.4),
  (5,'wood cube',100,0,0.5,0,1),
  (6,'box',40,0,1,0,2),
  (7,'backboard',0,0,0,3,0),
  (8,'side',0,0,0,8,0),
  (9,'shelf',0,0,0,4,0),
  (10,'foot',0,0,0,1,0),
  (11,'bookcase2x30',0,0,0,10,0),
  (12,'bookcase2x30 kit',0,0,0,2,0);
INSERT INTO assemblies VALUES
  (1,11,1,7,1,0),      -- laminate to backboard
  (2,11,2,7,8,0),      -- screws to backboard
  (3,11,3,8,.5,0),     -- planks to side
  (4,11,2,8,6,0),      -- screws to side
  (5,11,3,9,0.25,0),   -- planks to shelf
  (6,11,4,9,4,0),      -- shelf brackets to shelf
  (7,11,5,10,1,0),     -- wood cubes to foot
  (8,11,2,10,1,0),     -- screws to foot
  (9,11,7,11,1,0),     -- backboard to bookcase
  (10,11,8,11,2,0),    -- sides to bookcase
  (11,11,9,11,8,0),    -- shelves to bookcase
  (12,11,10,11,4,0),   -- feet to bookcase
  (13,12,1,7,1,0),     -- laminate to backboard
  (14,12,2,7,8,0),     -- screws to backboard
  (15,12,3,8,0.5,0),   -- planks to side
  (16,12,2,8,6,0),     -- screws to sides
  (17,12,3,9,0.25,0),  -- planks to shelf
  (18,12,4,9,4,0),     -- shelf brackets to shelves
  (19,12,5,10,1,0),    -- wood cubes to foot
  (20,12,2,10,1,0),    -- screws to foot
  (21,12,7,12,1,0),    -- backboard to bookcase kit
  (22,12,8,12,2,0),    -- sides to bookcase kit
  (23,12,9,12,8,0),    -- shelves to bookcase kit
  (24,12,10,12,4,0),   -- feet to bookcase kit
  (25,12,6,12,1,0);    -- container box to bookcase kit

Now, we want a parts list, a bill of materials, which will list show parent-child relationships and quantities, and sum the costs. Could we adapt the depth-first "nested sets" treewalk algorithm (Listing 10) to this problem even though our graph is not a tree and our sets are not properly nested? Yes indeed. We just have to modify the treewalk to handle multiple parent nodes for any child node, and add code to percolate costs and quantities up the graph. Navigation remains simple using leftedge and rightedge values. This is just the sort of problem the Celko algorithm is good for: reporting!

Listing 34
DROP PROCEDURE IF EXISTS ShowBOM;
DELIMITER |
CREATE PROCEDURE ShowBOM( IN root INT )
BEGIN
  DECLARE thischild, thisparent, rows, maxrightedge INT DEFAULT 0;
  DECLARE thislevel, nextedgenum INT DEFAULT 1;
  DECLARE thisqty, thiscost DECIMAL(10,2);

  -- Create and seed intermediate table:
  DROP TABLE IF EXISTS edges;
  CREATE TABLE edges (
    childID smallint NOT NULL,
    parentID smallint NOT NULL,
    PRIMARY KEY (childID, parentID)
  ) ENGINE=HEAP;
  INSERT INTO edges
    SELECT childID,parentID
    FROM assemblies
    WHERE assemblyRoot = root;
  SET maxrightedge = 2 * (1 + (SELECT COUNT(*) FROM edges));
  -- Create and seed result table:
  DROP TABLE IF EXISTS bom;
  CREATE TABLE bom (
    level SMALLINT,
    nodeID SMALLINT,
    parentID SMALLINT,
    qty DECIMAL(10,2),
    cost DECIMAL(10,2),
    leftedge SMALLINT,
    rightedge SMALLINT
  ) ENGINE=HEAP;
  INSERT INTO bom
    VALUES( thislevel, root, 0, 0, 0, nextedgenum, maxrightedge );
  SET nextedgenum = nextedgenum + 1;
  WHILE nextedgenum < maxrightedge DO
    -- How many children of this node remain in the edges table?
    SET rows = (
      SELECT COUNT(*)
      FROM bom AS s
      INNER JOIN edges AS t ON s.nodeID=t.parentID AND s.level=thislevel
    );
    IF rows > 0 THEN
      -- There is at least one child edge.
      -- Compute qty and cost, insert into bom, delete from edges.
      BEGIN
        -- Alas MySQL nulls MIN(t.childid) when we combine the next two queries
        SET thischild = (
          SELECT MIN(t.childID)
          FROM bom AS s
          INNER JOIN edges AS t ON s.nodeID=t.parentID AND s.level=thislevel
        );
        SET thisparent = (
          SELECT DISTINCT t.parentID
          FROM bom AS s
          INNER JOIN edges AS t ON s.nodeID=t.parentID AND s.level=thislevel
        );
        SET thisqty = (
          SELECT quantity FROM assemblies
          WHERE assemblyroot = root
            AND childID = thischild
            AND parentID = thisparent
        );
        SET thiscost = (
          SELECT a.assemblycost + (thisqty * (i.purchasecost + i.assemblycost ))
          FROM assemblies AS a
          INNER JOIN items AS i ON a.childID = i.itemID
          WHERE assemblyroot = root
            AND a.parentID = thisparent
            AND a.childID = thischild
        );
        INSERT INTO bom
          VALUES(thislevel+1, thischild, thisparent, thisqty, thiscost, nextedgenum, NULL);
        DELETE FROM edges
        WHERE childID = thischild AND parentID=thisparent;
        SET thislevel = thislevel + 1;
        SET nextedgenum = nextedgenum + 1;
      END;
    ELSE
      BEGIN
        -- Set rightedge, remove item from edges
        UPDATE bom
        SET rightedge=nextedgenum, level = -level
        WHERE level = thislevel;
        SET thislevel = thislevel - 1;
        SET nextedgenum = nextedgenum + 1;
      END;
    END IF;
  END WHILE;
  SET rows := ( SELECT COUNT(*) FROM edges );
  IF rows > 0 THEN
    SELECT 'Orphaned rows remain';
  ELSE
    -- Total
    SET thiscost = (SELECT SUM(qty*cost) FROM bom);
    UPDATE bom
    SET qty = 1, cost = thiscost
    WHERE nodeID = root;
    -- Show the result
    SELECT
      CONCAT(Space(Abs(level)*2), ItemName(nodeid,root)) AS Item,
      ROUND(qty,2) AS Qty,
      ROUND(cost, 2) AS Cost
    FROM bom
    ORDER BY leftedge;
  END IF;
END;
|
DELIMITER ;

-- Function used by ShowBOM() to retrieve bom item names:
DROP FUNCTION IF EXISTS ItemName;
SET GLOBAL log_bin_trust_function_creators=TRUE;
DELIMITER |
CREATE FUNCTION ItemName( id INT, root INT ) RETURNS CHAR(20)
BEGIN
  DECLARE s CHAR(20) DEFAULT '';
  SELECT name INTO s FROM items WHERE itemid=id;
  RETURN IF( id = root, UCASE(s), s );
END;
|
DELIMITER ;
CALL ShowBOM(11);
+---------------------+------+--------+

| Item                | Qty  | Cost   |

+---------------------+------+--------+

|   BOOKCASE2X30      |  1.0 | 327.93 |

|     backboard       |  1.0 |   3.00 |

|       laminate      |  1.0 |   4.00 |

|       screw         |  8.0 |   0.80 |

|     side            |  2.0 |  16.00 |

|       screw         |  6.0 |   0.60 |

|       plank         |  0.5 |   5.00 |

|     shelf           |  8.0 |  32.00 |

|       plank         |  0.3 |   2.50 |

|       shelf bracket |  4.0 |   0.80 |

|     foot            |  4.0 |   4.00 |

|       screw         |  1.0 |   0.10 |

|       wood cube     |  1.0 |   0.50 |

+---------------------+------+--------+


With ShowBOM() in hand, it's easy to compare costs of assemblies and subassemblies. By adding price columns, we can do the same for prices and profit margins. And now that MySQL has re-enabled prepared statements in stored procedures, it will be relatively easy to write a more general version of ShowBOM(). We leave that to you.

Shorter and sweeter

But ShowBOM() is not the small, efficient bit of nested sets reporting code we were hoping for. There is a simpler solution: hide graph cycles from the edges table by making them references to rows in a nodes table, so we can treat the edges table like a tree; then apply a breadth-first edge-list subtree algorithm to generate the Bill of Materials. Again assume a cabinetmaking company making bookcases (with a different costing model). For clarity, skip inventory tracking for now. An items table ww_nodes tracks purchased and assembled bookcase elements with their individual costs, and an assemblies/edges ww_edges table tracks sets of edges that combine to make products.

Listing 35: DDL for a simpler parts explosion
DROP TABLE IF EXISTS ww_nodes;
CREATE TABLE ww_nodes (
  nodeID int,
  description CHAR(50),
  cost decimal(10,2)
);
INSERT INTO ww_nodes VALUES (1,'finished bookcase',10);
INSERT INTO ww_nodes VALUES (2,'backboard2x1',1);
INSERT INTO ww_nodes VALUES (3,'laminate2x1',8);
INSERT INTO ww_nodes VALUES (4,'screw',.10);
INSERT INTO ww_nodes VALUES (5,'side',4);
INSERT INTO ww_nodes VALUES (6,'plank',20);
INSERT INTO ww_nodes VALUES (7,'shelf',4);
INSERT INTO ww_nodes VALUES (8,'shelf bracket',.5);
INSERT INTO ww_nodes VALUES (9,'feet',1);
INSERT INTO ww_nodes VALUES (10,'cube4cmx4cm',1);
INSERT INTO ww_nodes VALUES (11,'bookcase kit',2);
INSERT INTO ww_nodes VALUES (12,'carton',1);
 
DROP TABLE IF EXISTS ww_edges;
CREATE TABLE ww_edges (
  rootID INT,
  nodeID int,
  parentnodeID int,
  qty decimal(10,2)
);
INSERT INTO ww_edges VALUES (1,1,null,1);
INSERT INTO ww_edges VALUES (1,2,1,1);
INSERT INTO ww_edges VALUES (1,3,2,1);
INSERT INTO ww_edges VALUES (1,4,2,8);
INSERT INTO ww_edges VALUES (1,5,1,2);
INSERT INTO ww_edges VALUES (1,6,5,1);
INSERT INTO ww_edges VALUES (1,4,5,12);
INSERT INTO ww_edges VALUES (1,7,1,8);
INSERT INTO ww_edges VALUES (1,6,7,.5);
INSERT INTO ww_edges VALUES (1,8,7,4);
INSERT INTO ww_edges VALUES (1,9,1,4);
INSERT INTO ww_edges VALUES (1,10,9,1);
INSERT INTO ww_edges VALUES (1,4,9,1);
 
INSERT INTO ww_edges VALUES (11,11,null,1);
INSERT INTO ww_edges VALUES (11,2,11,1);
INSERT INTO ww_edges VALUES (11,3,2,1);
INSERT INTO ww_edges VALUES (11,4,2,8);
INSERT INTO ww_edges VALUES (11,5,11,2);
INSERT INTO ww_edges VALUES (11,6,5,1);
INSERT INTO ww_edges VALUES (11,4,5,12);
INSERT INTO ww_edges VALUES (11,7,11,8);
INSERT INTO ww_edges VALUES (11,6,7,.5);
INSERT INTO ww_edges VALUES (11,8,7,4);
INSERT INTO ww_edges VALUES (11,9,11,4);
INSERT INTO ww_edges VALUES (11,10,9,1);
INSERT INTO ww_edges VALUES (11,4,9,11);
INSERT INTO ww_edges VALUES (11,12,11,1);

Here is an adaptation of the breadth-first edge list algorithm to retrieve a Bill of Materials for a product identified by a rootID:

·  Initialise a level-tracking variable to zero.

·  Seed a temp reporting table with the rootID of the desired product.

·  While rows are being retrieved, increment the level tracking variable and add rows to the temp table whose parentnodeIDs are nodes at the current level.

·   Print the BOM ordered by path with indentation proportional to tree level.

Listing 36: A simpler parts explosion
DROP PROCEDURE IF EXISTS ww_bom;
DELIMITER |
CREATE PROCEDURE ww_bom( root INT )
BEGIN
  DECLARE lev INT DEFAULT 0;
  DECLARE totalcost DECIMAL( 10,2);
  DROP TABLE IF EXISTS temp;
  CREATE TABLE temp                                 -- initialise temp table with root node
  SELECT
    e.nodeID AS nodeID,
    n.description AS Item,
    e.parentnodeID,
    e.qty,
    n.cost AS nodecost,
    e.qty * n.cost AS cost,
    0 as level,                                     -- tree level
    CONCAT(e.nodeID,'') AS path                     -- path to this node as a string
  FROM ww_nodes n
  JOIN ww_edges e USING(nodeID)                     -- root node
  WHERE e.nodeID = root AND e.parentnodeID IS NULL;
  WHILE FOUND_ROWS() > 0 DO 
    BEGIN
      SET lev = lev+1;                              -- increment level
      INSERT INTO temp                              -- add children of this level
      SELECT 
        e.nodeID,
        n.description AS Item,
        e.parentnodeID,
        e.qty,
        n.cost AS nodecost,
        e.qty * n.cost AS cost,
        lev,                                
        CONCAT(t.path,',',e.nodeID)
      FROM ww_nodes n
      JOIN ww_edges e USING(nodeID)
      JOIN temp t ON e.parentnodeID = t.nodeID
      WHERE e.rootID = root AND t.level = lev-1;
    END;
  END WHILE;
  WHILE lev > 0 DO                                  -- percolate costs up the graph
    BEGIN
      SET lev = lev - 1;
      DROP TABLE IF EXISTS tempcost;
      CREATE TABLE tempcost                         -- compute child cost
      SELECT p.nodeID, SUM(c.nodecost*c.qty) AS childcost
      FROM temp p 
      JOIN temp c ON p.nodeid=c.parentnodeid
      WHERE c.level=lev
      GROUP by p.nodeid;
      UPDATE temp JOIN tempcost USING(nodeID)       -- update parent item cost
      SET nodecost = nodecost + tempcost.childcost;
      UPDATE temp SET cost = qty * nodecost         -- update parent cost
      WHERE level=lev-1;
    END;
  END WHILE;
  SELECT                                            -- list BoM
    CONCAT(SPACE(level*2),Item) AS Item,
    ROUND(nodecost,2) AS 'Unit Cost',
    ROUND(Qty,0) AS Qty,ROUND(cost,2) AS Cost FROM temp
  ORDER by path;  
END |
DELIMITER ;
CALL ww_bom( 1 );
+-------------------+-----------+------+--------+
| Item              | Unit Cost | Qty  | Cost   |
+-------------------+-----------+------+--------+
| finished bookcase |    206.60 |  1.0 | 206.60 |
|   backboard2x1    |      9.80 |  1.0 |   9.80 |
|     laminate2x1   |      8.00 |  1.0 |   8.00 |
|     screw         |      0.10 |  8.0 |   0.80 |
|   side            |     25.20 |  2.0 |  50.40 |
|     screw         |      0.10 | 12.0 |   1.20 |
|     plank         |     20.00 |  1.0 |  20.00 |
|   shelf           |     16.00 |  8.0 | 128.00 |
|     plank         |     20.00 |  0.5 |  10.00 |
|     shelf bracket |      0.50 |  4.0 |   2.00 |
|   foot            |      2.10 |  4.0 |   8.40 |
|     cube4cmx4cm   |      1.00 |  1.0 |   1.00 |
|     screw         |      0.10 |  1.0 |   0.10 |
+-------------------+-----------+------+--------+

Summary

Stored procedures, stored functions and Views make it possible to implement edge list graph models, nested sets graph models, and breadth-first and depth-first graph search algorithms in MySQL 5&6.

Further Reading

Celko J, "Trees and Hierarchies in SQL For Smarties", Morgan Kaufman, San Francisco, 2004.

Codersource.net, "Branch and Bound Algorithm in C#", http://www.codersource.net/csharp_branch_and_bound_algorithm_implementation.aspx.

Math Forum, "Euler's Solution: The Degree of a Vertex", http://mathforum.org/isaac/problems/bridges2.html

Muhammad RB, "Trees", http://www.personal.kent.edu/~rmuhamma/GraphTheory/MyGraphTheory/trees.htm.

Mullins C, "The Future of SQL", http://www.craigsmullins.com/idug_sql.htm.

Rodrigue J-P, "Graph Theory: Definition and Properties", http://people.hofstra.edu/geotrans/eng/ch2en/meth2en/ch2m1en.html.

Santry P, "Recursive SQL User Defined Functions", http://www.wwwcoder.com/main/parentid/191/site/1857/68/default.aspx.

Shasha D, Wang JTL, and Giugno R, "Algorithmics and applications of tree and graph searching", In Symposium on Principles of Database Systems, 2002, p 39--52.

Stephens S, "Solving directed graph problems with SQL, Part I", http://builder.com.com/5100-6388_14-5245017.html.

Stephens, S, "Solving directed graph problems with SQL, Part II", http://builder.com.com/5100-6388_14-5253701.html.

Steinbach T, "Migrating Recursive SQL from Oracle to DB2 UDB", http://www-106.ibm.com/developerworks/db2/library/techarticle/0307steinbach/0307steinbach.html.

Tropashko V, "Nested Intervals Tree Encoding in SQL, http://www.sigmod.org/sigmod/record/issues/0506/p47-article-tropashko.pdf

Van Tulder G, "Storing Hierarchical Data in a Database", http://www.sitepoint.com/print/hierarchical-data-database.

Venagalla S, "Expanding Recursive Opportunities with SQL UDFs in DB2 v7.2", http://www-106.ibm.com/developerworks/db2/library/techarticle/0203venigalla/0203venigalla.html.

Wikipedia, "Graph Theory", http://en.wikipedia.org/wiki/Graph_theory.

Willets K, "SQL Graph Algorithms", http://willets.org/sqlgraphs.html.



Last updated 20 Aug 2007

Posted by tornado
|
[MySQL] mysqld_multi 사용법

- 작성자 : 김칠봉 <san2(at)linuxchannel.net>
- 작성일 : 2002.02.09(오타수정, 보완)
         : 2003.01.29
- 분 류  : mysql
- 수 준  : 초중급이상
- 내 용  : 하나의 서버에서 여러개의 mysqld 데몬을 띄우는 방법
- 키워드 : mysql, mysqld, mysqld_multi, safe_mysqld, mysqld_safe

*주1)
이 문서에 대한 최신 내용은 아래 URL에서 확인할 수 있습니다.

http://www.linuxchannel.net/docs/mysqld_multi.txt

*주2)
이 문서의 내용은 같은 하나의 MySQL 서버에서 여러개의 mysqld 데몬을
띄우는 방법에 대해서 설명합니다.
mysql 설치나 실제 실무에서 다루는 고차원적이고 상세한 기술적인
부분은 다루지 않습니다.

*주3)
`mysqld_multi` 프로그램은 MySQL 3.23.29 이상 버전용입니다.

reference :
- http://www.mysql.com/doc/en/mysqld_multi.html
- http://www.mysql.com/doc/en/Multiple_servers.html

---------------------------------------------------------
목차
1. mysqld multi 란?
2. 서로 다른 여러개의 mysqld를 띄우는 방법(기본)
3. mysqld_multi 을 이용하여 여러개의 mysqld 띄우는 방법
4. MySQL 3.23.x와 MySQL 4.0.x 을 동시에 구동하는 방법
5. 공유한 하나의 DB에 랜덤하게 접속하는 방법
6. 후기
---------------------------------------------------------

1. mysqld multi 란?

`mysqld_multi'라는 PERL 스크립트(3.23.29 이상)를 이용하여
같은 서버에서 여러개의 독자적인 mysqld를 운영하는 방법을 말합니다.

정확히 말해서, mysql 포트나 소켓을 서로 달리하여 여러개의 mysqld
프로세스를 띄워 운영하는 방법을 말합니다.

httpd에서 80, 8080 포트로 운영하는 것이나 또는 sendmail에서
daemonport를 서로 달리하여 운영하는 방법과 비슷한 원리입니다.


2. 서로 다른 여러개의 mysqld를 띄우는 방법(기본)

<주의>
이 절의 내용은 여러개의 mysqld 데몬을 띄우는 기본 사항에 대해서
다룹니다. 실제로 이렇게 운영할 수도 있지만 약간 불편하기 때문에
권장방법은 아닙니다.
</주의>

따로 mysql을 추가로 컴파일할 필요는 없습니다. 기존의 safe_mysqld
스크립트를 이용하면 됩니다.

이때 중요한 점은 반드시 최소한 pid-file, socket 위치를 서로 다르게
지정해야 합니다.

*반드시 다르게 설정해야할 옵션)

--pid-file=
--socket=
--port= or --skip-network

나머지 옵션은 mysql을 컴파일할때 기본값으로 사용하는 값을 따르거나
my.cnf 파일의 [mysqld] 섹션에 설정한 옵션을 따릅니다.

<팁> 외부 MySQL client에서 접속을 원천 봉쇄하려면?
mysql.host 테이블과 상관없이 아예 mysql 포트를 열지않도록
--skip-network 옵션을 주고 mysqld를 시작하면 됩니다.
(`netstat -atnp`로 확인).
</팁>

이하 설명은 외부 mysql client에서 접속해 오는 경우가 아닌 내부 client
에서 접속하는 경우로 가정하겠습니다.

만약 외부 mysql client(대부분 웹서버)에서 접속해야만 하는 경우라면
--skip-network 대신 --port=# 옵션으로 바꾸어야 합니다.


[첫번째 mysqld 구동]

shell> safe_mysqld &
or
shell> safe_mysqld --defaults-file=/root/.my.cnf &

[두번째 추가적인 mysqld 구동]

shell> safe_mysqld \
  --pid-file=/usr/local/mysql/var/`hostname`.pid2 \
  --socket=/tmp/mysql.sock2 \
  --skip-network & /*** or --port=3307 ***/
or
shell> safe_mysqld \
  --defaults-file=/root/.my.cnf \
  --pid-file=/usr/local/mysql/var/`hostname`.pid2 \
  --socket=/tmp/mysql.sock2 \
  --skip-network & /*** or --port=3307 ***/

두번째 mysqld에서 사용되는 나머지 옵션은 첫번째 mysqld의 기본 옵션을
그대로 따릅니다. 즉 basedir, datadir 와 같은 옵션을 따로 지정하지
않았기 때문에 어떤 값을 사용하는지를 알아보려면 다음과 같이 확인해
봅니다.

[기본적으로 사용되는 값 알아보기]

shell> /usr/local/mysql/libexec/mysqld --help
...
basedir:     /usr/local/mysql/
datadir:     /usr/local/mysql/var/
tmpdir:      /tmp/
language:    /usr/local/mysql/share/mysql/english/
pid file:    /usr/local/mysql/var/home.pid
TCP port:    3306
Unix socket: /tmp/mysql.sock
...
Possible variables for option --set-variable (-O) are:
back_log              current value: 50
binlog_cache_size     current value: 32768
connect_timeout       current value: 5
...


[두번째 mysqld에 접속해 보기]

현재 두번째 mysqld의 datadir 옵션이 없기 때문에 첫번째 mysqld의 datadir
와 같습니다. 즉 하나의 datadir를 공유한 셈이 됩니다.

*프로세스 확인)
shell> ps -ef --cols 400 | grep mysqld

*소켓 확인)
shell> ls /tmp/mysql.sock*
/tmp/mysql.sock  /tmp/mysql.sock2

*접속해 보기)
shell> mysql -u username -p -S /tmp/mysql.sock2 db_name

'-S'(또는 --socket) 옵션으로 두번째 mysqld의 소켓 위치를 입력해 주면
됩니다.


[두번째 mysqld 종료하기]

이와 같이 두번째, 세번째 mysqld를 구동하는 방법은 매번 옵션을 적어줘야
하는 불편함이 있습니다(또한 관리도 썩 매끄럽지 못하고).

일단 두번째 mysqld 구동에 성공하고 접속 테스트까지 끝냈다면 이제는
필요없으니 두번째 mysqld를 종료해 봅시다.

종료도 간단합니다. 단지 소켓 위치만 추가 옵션을 주면 됩니다.

shell> mysqladmin -u root -p -S /tmp/mysql.sock2 shutdown


3. mysqld_multi 을 이용하여 여러개의 mysqld 띄우는 방법

mysqld_multi 프로그램은 PERL로 짜여져 있으며, PREFIX/bin/mysqld_multi에
위치합니다. (MySQL 3.23.29 버전부터 추가되었군요.)

mysql.server 또는 safe_mysqld 스크립트는 기본적으로 /etc/my.cnf 또는
~/.my.cnf 또는 PREFIX/var/my.cnf 설정 파일에서 [mysqld] 섹션의 옵션 내용
을 읽어들여 mysqld 를 구동합니다.

<주의>
MySQL 4.0.x 버전은 safe_mysqld가 아니라 mysqld_safe으로 스크립트 이름이
변경되었습니다.
</주의>

이하 mysql 설정파일(my.cnf)은 /root/.my.cnf으로 통일합니다.

반면 mysqld_multi 스크립트는 [mysqld_multi], [mysqld1], [mysqld2], ...,
[mysqld] 의 섹션을 참고합니다.

정리하면,

  `safe_mysqld'  <-- [mysqld] <-- defaults options

  `mysqld_multi' <-- [mysqld_multi]
                       |-- [mysqld1] <-- ([mysqld]) <-- defaults options
                       |-- [mysqld2] <-- ([mysqld]) <-- defaults options
                       |-- [mysqld3] <-- ([mysqld]) <-- defaults options
                       `-- [mysqld#] <-- ([mysqld]) <-- defaults options

이와 같은 위계로 각 섹션을 참고하여 mysqld를 구동합니다.
(괄호안의 섹션은 그 섹션이 있다면 참고한다는 옵션입니다.)

mysqld_multi 를 사용하기 위해서 /root/.my.cnf 파일에 다음과 같이
추가해야 합니다(없다면 파일 생성).

shell> /usr/local/mysql/bin/mysqld_multi --example

하면 그 예제가 출력됩니다.

-- /root/.my.cnf 또는 /etc/my.cnf (수정전) ----------
[client]
password	= 안 갈쳐조오..
host		= localhost

[mysql]
ignore-spaces

[mysqld]
default-character-set = euc_kr
safe-show-database
skip-name-resolve
#port		= 3306
skip-network
log
#log-update
user		= mysql
set-variable 	= key_buffer=256M
set-variable 	= thread_cache_size=8
set-variable 	= table_cache=256

[myisamchk]
set-variable 	= key_buffer=100M
set-variable 	= sort_buffer=100M
set-variable 	= read_buffer=3M
set-variable 	= write_buffer=3M
#set-variable 	= sort_key_blocks=20
#set-variable 	= decode_bits=10

[mysqladmin]
#set-variable 	= connect_timeout=100
#set-variable 	= shutdown_timeout=1

[mysqldump]
user		= root
-----------------------------------------------------

-- /root/.my.cnf 또는 /etc/my.cnf (수정후) ----------
[client]
(생략)...

[mysql]
(생략)...

[mysqld]
default-character-set = euc_kr
skip-name-resolve
skip-network	## only localhost access
language	= /usr/local/mysql/share/mysql/english
(생략)...

[mysqld_multi]
mysqld		= /usr/local/mysql/bin/safe_mysqld
mysqladmin	= /usr/local/mysql/bin/mysqladmin
#user		= root

[mysqld1]
socket		= /tmp/mysql.sock1
#port		= 3307
pid-file	= /usr/local/mysql/var/mysqld1.pid
datadir		= /usr/local/mysql/var
log		= /usr/local/mysql/var/mysqld1.log
user		= mysql

[mysqld2]
socket		= /tmp/mysql.sock2
#port		= 3308
pid-file	= /usr/local/mysql/var2/mysqld2.pid
datadir		= /usr/local/mysql/var2
log		= /usr/local/mysql/var2/mysqld2.log
user		= mysql

[myisamchk]
(생략)...

[mysqladmin]
(생략)...

[mysqldump]
(생략)...
-----------------------------------------------------

앞의 설정에서 [mysqld1]은 datadir이 기존의 [mysqld] 섹션과 동일하므로
하나의 datadir을 공유하겠다는 의미입니다.

[mysqld2]의 datadir은 서로 다르므로 아주 독자적인 데이터베이스를 운영
하겠다는 의미입니다.

예) [mysqld2]용 datadir 만들기
shell> mkdir /usr/local/mysql/var2
shell> /usr/local/mysql/bin/mysql_install_db \
  --datadir=/usr/local/mysql/var2
shell> chown mysql.mysql -R /usr/local/mysql/var2

이와 같이 기본 mysql 데이터베이스를 만들어 주면 됩니다.

MySQL 영문 매뉴얼에 의하면 [mysqld_multi] 섹션에 multi_admin 유저를
다음과 같이 기존의 MySQL에 추가하여 관리하도록 하는 예제가 있습니다.

shell> mysql -u root -S /tmp/mysql.sock -proot_password -e \
  "GRANT SHUTDOWN ON *.* TO multi_admin@localhost \
  IDENTIFIED BY 'multipass'"

그러나 반드시 이와 같이 multi_admin 유저를 추가할 필요는 없고
기존의 root 유저를 이용하면 그만입니다.

<참고>
[mysqld1] 섹션에서 user는 해당 mysqld의 프로세스 유저를
의미합니다. /etc/passwd 파일에 존재한 다른 유저로도 설정가능합니다.
만약 하나의 유저에 대한 어떤 제한(ulimt)이 있다면 mysql 유저 대신
다른 유저를 /etc/passwd 파일에 추가하고 해당 유저를 사용하면 됩니다.
</참고>

그럼 두번째 [mysqld1], 세번째 [mysqld2] mysqld를 구동해 봅시다.

shell> /usr/local/mysql/bin/mysqld_multi --help
...
Usage: mysqld_multi [OPTIONS] {start|stop|report} [GNR,GNR,GNR...]
or     mysqld_multi [OPTIONS] {start|stop|report} [GNR-GNR,GNR,GNR-GNR,...]
..

GNR은 'Group NumbeR'를 의미하며 [mysqld#]에서 # 부분을 말합니다.
즉 정수 단위로 1부터 가능하며 GNR 옵션이 없다면 모든 GNR을 기본값으로
사용합니다.

*mysqld 구동하기)
shell> /usr/local/mysql/bin/mysqld_multi start
or
shell> /usr/local/mysql/bin/mysqld_multi start 1,2

*구동확인)
shell> /usr/local/mysql/bin/mysqld_multi report
Reporting MySQL servers
MySQL server from group: mysqld1 is running
MySQL server from group: mysqld2 is running

*두번째 mysqld에 접속하기
shell> mysql [OPTIONS] -S /tmp/mysql.sock1 db_name

*세번째 mysqld에 접속하기
shell> mysql [OPTIONS] -S /tmp/mysql.sock2 db_name

*두번째 mysqld 종료하기)
shell> /usr/local/mysql/bin/mysqld_multi stop 1

*두번째, 세번째 mysqld 종료하기)
shell> /usr/local/mysql/bin/mysqld_multi stop 1,2

*모든 mysqld multi 종료하기)
shell> /usr/local/mysql/bin/mysqld_multi stop
or
shell> /usr/local/mysql/bin/mysqld_multi stop 1,2

mysqld_multi는 safe_mysqld와 별개입니다. 어떤 옵션을 주고 구동하느냐에
따라서 두개가 서로 연계를 갖을 수 있지만 정확히 말하면 두개의 독립된 별개의
mysqld 입니다.

즉,

shell> safe_mysqld &
shell> mysqld_multi start
shell> mysqladmin shutdown
shell> mysqld_multi stop

이와 같이 별도로 각각 구별하여 시작/종료할 수 있습니다.

만약 이와 같이 각각 서로 구별하여 운영하고 싶지 않다면
기존의 safe_mysql의 [mysqld] 섹션을 mysqld_multi 용의 [mysqld1]으로
수정하여 기본 mysqld로 운영할 수 있습니다.

<참고> 부팅시 자동 시작하기(/etc/rc.d/rc.local)
/usr/local/mysql/bin/mysqld_multi \
  --defaults-file=/root/.my.cnf start
</참고>


4. MySQL 3.23.x와 MySQL 4.0.x 을 동시에 구동하는 방법

지금까지의 내용을 이해했다면 두개의 서로 다른 MySQL 버전을 구동하는
방법은 아주 쉽습니다.

  MySQL 3.23.x : /usr/local/mysql
  MySQL 4.0.x  : /usr/local/mysql4

에 각각 설치했다는 가정입니다.

<주의>
MySQL 4.0.x 버전은 safe_mysqld가 아니라 mysqld_safe으로 스크립트 이름이
변경되었습니다.
</주의>

-- /root/.my.cnf 또는 /etc/my.cnf ----------------
[client]
(생략)...

[mysql]
(생략)...

[mysqld]
(생략)...

[mysqld_multi]
mysqld		= /usr/local/mysql4/bin/mysqld_safe ## <-- 주의
mysqladmin	= /usr/local/mysql4/bin/mysqladmin
#user		= root

[mysqld1]
socket		= /tmp/mysql4.sock1
#port		= 3307
skip-name-resolve
skip-network	## only localhost access
default-character-set = euc_kr
pid-file	= /usr/local/mysql4/var/mysqld1.pid
datadir		= /usr/local/mysql4/var
language	= /usr/local/mysql4/share/mysql/english
log		= /usr/local/mysql4/var/mysqld1.log
user		= mysql

[myisamchk]
(생략)...

[mysqladmin]
(생략)...

[mysqldump]
(생략)...
-----------------------------------------------------

*MySQL 3.23.x 구동
shell> safe_mysqld &

*MySQL 4.0.x 구동
shell> mysqld_multi start

필자가 이 방법을 소개한 이유는 MySQL 4.0.x 버전으로 업그레이드할 경우
관리자가 조용하게(?) 테스트해 보아, 이상이 없다면 아무도 모르게(?)
조용하게 업그레이드할 수 있다는 점입니다.

물론 다음의 URL을 먼저 알아두어야 합니다.

  - http://www.mysql.com/doc/en/Upgrading-from-3.23.html


5. 공유한 하나의 DB에 랜덤하게 접속하는 방법

이 방법의 서로 다른 여러개의 mysqld 데몬의 datadir을 모두 동일하게
설정하여 운영하는 방법입니다.

여러개의 mysqld 데몬을 띄어야 하므로 시스템에 충분한 메모리가 있어야
합니다(512M 이상).

*권장 하는 경우)
1. 시스템 부하가 극도로 높지 않는 경우.
2. 하나(socket)의 mysqld로 시스템을 운영하기에는 자원이 남는 경우
3. 하나의 mysqld로 서비스가 포화 상태인 경우
4. 기타 테스트로 전보다 낫은 성능을 낼 경우


<주의>
필자가 테스트해 본 바로는 시스템 부하(CPU 사용량 95%이상)가 심한
경우, 좋은 대안이 될 수 없습니다(큰 효과가 없음).
(여러개의 mysqld 데몬을 띄우지 않아도 얼마든지 높은 퍼포먼스를
낼 수 있습니다)
다만, 이 방법은 여러가지 더 많은 테스트를 해보아, 전보다 좀더 낫은
성능을 낼 경우에만 사용하도록 하세요.
</주의>

-- /root/.my.cnf 또는 /etc/my.cnf ----------------
[client]
(생략)...

[mysql]
(생략)...

[mysqld]
default-character-set = euc_kr
skip-name-resolve
skip-network	## only localhost access
datadir		= /usr/local/mysql/var
language	= /usr/local/mysql/share/mysql/english
user		= mysql
(생략)...

[mysqld_multi]
mysqld		= /usr/local/mysql/bin/safe_mysqld
mysqladmin	= /usr/local/mysql/bin/mysqladmin
#user		= root

[mysqld1]
socket		= /tmp/mysql.sock1
#port		= 3307
pid-file	= /usr/local/mysql/var/mysqld1.pid
log		= /usr/local/mysql/var/mysqld1.log

[mysqld2]
socket		= /tmp/mysql.sock2
#port		= 3308
pid-file	= /usr/local/mysql/var/mysqld2.pid
log		= /usr/local/mysql/var/mysqld2.log

[mysqld3]
socket		= /tmp/mysql.sock3
#port		= 3309
pid-file	= /usr/local/mysql/var/mysqld3.pid
log		= /usr/local/mysql/var/mysqld3.log

[myisamchk]
(생략)...

[mysqladmin]
(생략)...

[mysqldump]
(생략)...
-----------------------------------------------------

앞의 설정을 요약하면 각 그룹 [mysqld#]는 datadir 옵션이 없으므로
[mysqld] 섹션의 datadir를 그대로 따릅니다.
즉 모두 같은 하나의 datadir을 공유하는 결과가 됩니다.

또한 log 옵션을 생략하면 기본 [mysqld] 섹션의 log 옵션을 따릅니다.
앞의 예제는 접속 확인을 알아보기 위해서 각각 다른 log 파일에 기록
하도록 했을 뿐입니다.

만약 하나의 유저로 모두 구동하고 싶지 않다면 각 [mysqld#] 섹션에
해당 user 옵션을 설정해 주면 됩니다.
(하나의 유저당 파일 제한수가 적을 경우)

shell> mysqld_multi start

이렇게 명령어를 내리면 추가로 3개의 각각 독립된 mysqld가 구동되며,
모두 동일한 하나의 datadir를 공유합니다.

만약 1, 2번 mysqld만 시작하도록 하고 싶다면

shell> mysqld_multi start 1,2

이렇게 추가 옵션을 주면 됩니다.

shell> mysqld_multi report

앞의 명령어로 3개 모두 구동하는지 확인해 보도록 하세요.

이제는 랜덤하게 1, 2, 3번에 접속하도록 socket 파일만 랜덤하게 선택해
주면 됩니다.

만약 PHP로 접근한다면(검색에만 적용),

----------------------------------------------------
<?php
##
## 검색모드에만 적용
if('검색모드인경우') {
  $sock = '/tmp/mysql.sock' . rand(1,3);
  ini_set('mysql.default_socket',$sock);
}

(생략: 나머지는 기존과 동일)

?>
----------------------------------------------------

이렇게 접속하는 기본 socket 파일 위치를 랜덤하게 만들어 주면 됩니다.

만약 각각 datadir이 서로 다르고 독자적으로 모두 별개의 MySQL 서비스를
한다면, 관리자 측면에서 다음과 같이 설정할 수 있습니다.

-- httpd.conf --------------------------------------
...
<VirtualHost xxxx>
  ...
  php_value mysql.default_socket "/tmp/mysql.sock1"
</VirtualHost>

<VirtualHost xxxx>
  ...
  php_value mysql.default_socket "/tmp/mysql.sock2"
</VirtualHost>

<VirtualHost xxxx>
  ...
  php_value mysql.default_socket "/tmp/mysql.sock3"
</VirtualHost>
----------------------------------------------------

or

-- DOCUMENT_ROOT/.htaccess -------------------------
...
php_value mysql.default_socket "/tmp/mysql.sock2"
----------------------------------------------------


6. 후기

(생략)


EOF

'SQL > MySQL' 카테고리의 다른 글

[MySQL] hierarchical Data 표현...  (0) 2009.02.11
[MySQL] Got error 28 from storage engine  (0) 2008.03.03
mysql 관리 툴 EMS  (0) 2006.09.30
[Mysql] GRANT로 사용자 추가하기  (0) 2006.08.28
replication 사용하기.. version - 4.0.17  (0) 2004.07.06
Posted by tornado
|

mysql 관리 툴 EMS

SQL/MySQL 2006. 9. 30. 11:22

mysql mysqladmin 관리 하기 잘되있음

http://www.snapfiles.com/get/emsmysqllite.html

프리웨어라

기간도 없고 넘좋아~~~~


Posted by tornado
|

#mysql -u root -p


mysql>GRANT ALL PRIVILEGESE ON 데이타베이스명.테이블명 TO '아이디'@'호스트'

->IDENTIFIED BY '패스워드' ;



※ DB 생성

mysql> create database test_db;


※ 사용자 생성

1. 외부에서 접근할수 있게 하는 경우

mysql> GRANT ALL PRIVILEGES ON test_db.* TO test_id@'%'              <======== %는 모든 호스트를 의미함

-> IDENTIFIED BY 'test_passwd';

2. 내부에서 접속할수 있게 하는 경우

mysql> GRANT ALL PRIVILEGES ON test_db.* TO test_id@localhost      <======== *는 모든 테이블을 의미함
-> IDENTIFIED BY 'test_passwd';                                                      <======== localhost는 내부

3. 확인

mysql> select user from user;


mysql 재시작

[root@/root]mysqladmin -uroot -ptest_passwd reload

Posted by tornado
|

mysql replication 사용....


데이터 복제는 두가지 설정으로 나누어 진다.

* master 설정
* slave 설정

mysql 은 이미 설치되어 있다는 전제하에 설명하며,

두대의 서버에 각각 설치되었다고 가정한다.

master 서버의 ip 는 111.111.111.111  로 가정하고
slave 서버의 ip 는 222.222.222.222 로 가정한다.


먼저 master 설정...


1. Master Server 에 새로운 사용자 등록...(권한은 all 로 했지만 Repl_slave_priv 만 준다고 함).
    (전체 데이터베이스 복제를 위해 *.* 로 한다..... 디비는 딱 세개 있음 ㅡㅡ)
 grant all on *.* to 'tornado'@'%' identified by '패스워드' with grant option;


 2. 권한을 줬으면 mysql 데이터베이스에 user 테이블에 현재 생성한 유져가 잘 들어있는지 체크한다.


 3. my.cnf 파일을 고쳐주어야 한다. 보통 mysql 설치후 /etc/ 디렉토리에 복사해 놓고 사용하는데
 없다면 MYSQL_HOME/support-files 디렉토리에 보면

-rw-r--r--    1 root     mysql        2686  6¿u  3 10:04 MySQL-shared-compat.spec
-rw-r--r--    1 root     mysql         773  6¿u  3 10:04 magic
-rw-r--r--    1 root     mysql        4874  6¿u  3 10:04 my-huge.cnf
-rw-r--r--    1 root     mysql        4850  6¿u  3 10:04 my-large.cnf
-rw-r--r--    1 root     mysql        4833  6¿u  3 10:04 my-medium.cnf
-rw-r--r--    1 root     mysql        2418  6¿u  3 10:04 my-small.cnf
-rwxr-xr-x    1 root     mysql       24917  6¿u  3 10:04 mysql-4.0.17.spec
-rwxr-xr-x    1 root     mysql         676  6¿u  3 10:04 mysql-log-rotate
-rwxr-xr-x    1 root     mysql        5432  6¿u  3 10:04 mysql.server
-rw-r--r--    1 root     mysql       24917  6¿u  3 10:04 mysql.spec


이렇게 파일이 존재한다.

이중에... my-small.cnf 를 /etc/my.cnf 로 복사한다.

cp my-small.cnf /etc/my.cnf

4. vi 로 /etc/my.cnf 를 열어본다...

# vi /etc/my.cnf    로 보면 아래와 같은 부분이 있다.

log-bin
server-id     = 1


이 부분이 주석처리 되면 안되며, server-id 는 master 서버와 slave 서버 사이에서 유일한 값이어야 한다.


6. Database 및 Table 생성

mysql 에는 test 디비가 있는데 그곳에 아래와 같이 테이블을 만든다.

create table a ( name varchar(50) );


7. Database 복사.

위에처럼 생성했다면 mysql/data/test 디렉토리에 a 테이블에 관련된 세개의 파일이 생성된다.

그럼 해당 Table 을 무식하게(?) 압축해서 slave 의 test 디렉토리로 이동한다.

[root@localhost data]# tar cvzf test.tar.gz ./test
./test/
./test/a.frm
./test/a.MYI
./test/a.MYD
You have new mail in /var/spool/mail/root
[root@localhost data]#


압축된 파일을 slave 서버의 mysql/data/ 디렉토리에 옮긴후 압축을 푼다.

# tar xvzf test.tar.gz


이제 Slave 서버 셋팅이다.



1.  my.cnf 파일 수정하기..

master 서버의 my.cnf 를 복사한 것과 같은 방법으로 /etc/my.cnf 를 만들어 준다.

# vi /etc/my.cnf

파일을 보다가 server-id = 1 이라고 되어있는 부분이 있으면
server-id = 2 로 바꾸어 준다.

아래와 같이 master 서버의 주소와 사용자를 적어준다.

# Replication Configure
master-host=111.111.111.111
master-user=tornado
master-password=패스워드
master-port=3306


2. mysql 데몬 다시 시작하기.

master 서버 및 slave 서버의 데몬을 다시 시작한다.


./bin/safe_mysqld --user=mysql &


3. master 서버에서의 상태 보기.

show master status;

위 명령을 치면 master 서버의 상태를 보여준다.
그곳에 보이는 파일과 slave 에서 보이는 파일이 동일해야 한다.


4. slave 서버에서의 상태보기.

show slave status;

위 명령을 치면 master 와는 틀리게 컬럼이 좀 여러개가 보인다.

그중에 master 에 적혀 있는 파일이 정확하게 있는지 확인한다.

만약 없다면 slave 의 data/ 디렉토리에 있는 모든 파일(디렉토리는 빼고!!!) 을 싹 지운다.
보통 xxx-bin 과 같은 파일일 것임..


만약 컬럼 중간에 에러 비스무리한 것이 있다면... 잘 읽어보라.


5. slave 서버 시작/중지하기.

slave start ;  <-- 슬레이브 시작하기
slave stop ;  <-- 슬레이브 중지하기..


이렇게 중지해도 양쪽의 로그파일이 있기 때문에 
중간에 중단되었다 해도 중단된 시점부터 다시 백업해준다.


6. 테스트


master 서버의 test 디비에서 아까 만들었던 a 테이블에 쿼리를 날려본다.

insert into a values('tornado');


마스터/슬레이브 서버에서 각각 select * from a; 를 해보고

데이터가 동일한지 확인해서 같으면 끝...



7. 문제점???

pk 컬럼의 중복 및 짜잘한 오류가 생겼을 경우 slave 가 죽는 현상이 벌어짐 ㅡㅡ
해결책 ... 모름.. 아시는 분 덧글 부탁 ^^




Posted by tornado
|

4장 데이터베이스 관리

전체적으로 볼 때 MySQL은 그다지 관리할 것이 많지 않은 편이다. 일단 설치하고 나면 관리자가 할 일이 별로 없다. 그렇다고 해도 MySQL 관리자는 다음과 같은 임무를 맡고 있다.

  • 설치
  • 설정 및 튜닝
  • 액세스 제어
  • 로깅
  • 백업 및 복구
  • 테이블 관리

위에 열거한 주제 중 몇 가지는 다른 자에서 다룬다(설치는 2장에서, 퍼포먼스 튜닝은 5장에서, 액세스 제어는 6장에서).

MySQL 서버 관리를 할 필요가 없는 사람이라도 이 장에 있는 내용을 알아두면 도움이 된다. 데이터베이스 관리에 대한 내용을 알고 있으면 데이터베이스 관리자에게 문의하기 전에 어떤 문제가 있는지 확인해 볼 수 있기 때문이다.

여러 가지 관리 작업을 처리하려면 MySQL의 관리자 액세스가 필요하다(액세스 권한과 MySQL 데이터베이스 관리자 설정에 관한 내용은 6장에서 자세히 다룬다). 작업에 따라 운영 체제의 관리자 권한(유닉스에서는 root, 윈도우 NT/2000/XP에서는 Administrator)이 필요할 수도 있다.

설정

우선 MySQL 서버 프로세스인 mysqld 및 mysql 명령행 유틸리티를 비롯한 여러 클라이언트 프로세스에 대한 설정을 해야 한다. MySQL 설정은 유닉스에서 흔히 사용하는 방법으로 이루어진다. 즉 명령행 옵션, 설정 파일 그리고 환경 변수를 이용하여 설정할 수 있다. 이러한 세 가지 방법을 통해 모든 설정 가능한 내역을 관리할 수 있다.

옵션을 정의하는 방법이 다양하기 때문에 위의 세 가지 옵션들이 서로 충돌할 때에는 다음과 같은 우선순위를 기준으로 삼는다.

  1. 명령행 옵션
  2. 설정 파일 옵션
  3. 환경 변수 옵션

예를 들어, 패스워드 옵션이 명령행, 설정 파일, 환경 변수에서 제각기 다르게 정의되어 있다면 MySQL 클라이언트 도구에서는 명령행에서 지정한 옵션을 사용한다.

MySQL 옵션을 다루는 방법 중에서는 설정 파일을 이용하는 방법이 가장 쉽고 많이 쓰인다. 설정 파일을 이용하면 모든 옵션을 파일 하나에 넣을 수 있기 때문에 명령을 실행시키거나 컴퓨터에 로그인할 때마다 옵션을 지정하지 않아도 된다.

파일 위치

유닉스 시스템에서는 MySQL 설정 파일을 다음과 같은 위치에서 순서대로 검색한다.

  1. /etc/my.cnf 파일. MySQL에서는 가장 먼저 전역 옵션 파일을 검색한다. 일반적으로 모든 사용자와 서버에서 사용하는 기본 옵션은 이 파일에 저장해 두는 편이 좋다.
  2. DATADIR/my.cnf 파일. DATADIR은 MySQL 서버 인스턴스의 데이터파일을 저장하는 디렉토리이다. 이 설정 파일에는 주어진 서버 인스턴스에만 적용되는 설정 인자를 저장한다.
  3. --default-extra-file=filename 명령행 옵션을 통해 지정한 위치. 이 명령행 옵션을 이용하면 MySQL 서버나 클라이언트 유틸리티에서 임의의 위치에 있는 설정 파일을 이용할 수 있다.
  4. $HOME/.my.cnf 파일. $HOME은 현재 사용자의 홈 디렉토리를 나타내는 유닉스 환경 변수이다. 이 설정 파일은 사용자의 홈 디렉토리에 저장되며 여기에는 사용자들이 개인적으로 사용하는 옵션을 저장해둘 수 있다. 클라이언트 옵션은 대부분 여기에 저장된다.

윈도우에는 전역 설정 파일이 추가로 있으며, 사용자별 개인 설정 파일은 없다.

  1. 윈도우 시스템 폴더(보통 C:\WINNT\System32)에 들어가는 My.ini 파일
  2. C:\my.cnf
  3. C:\mysql/data/my.cnf
  4. --default-extra-file=filename

만약 어떤 옵션이 여러 파일에서 서로 다르게 정의되었다면 가장 나중에 읽어들인 내용이 적용된다. 즉 C:\my.cnf 파일에 저장된 사용자 정의 옵션이 My.ini 파일에 있는 옵션보다 더 우선시된다. 이렇게 하면 데이터베이스 관리자는 클라이언트 도구의 기본값을 My.ini를 통해 설정하고 사용자는 필요에 따라 다른 옵션을 사용할 수 있다.

파일 내용

모든 설정 파일의 형식은 같다. 설정 파일의 예가 [예제 4-1]에 나와 있다. 설정 파일이 그다지 어렵진 않지만, 일단 이 파일을 꼼꼼하게 살펴보자:

 [예제 4-1] MySQL 설정 파일 샘플 # MySQL 설정파일 예제 # # 클라이언트 옵션 [client] password = my_password port     = 3306 socket   = /var/lib/mysql/mysql.sock # mysqld 서버 옵션 [mysqld] port   = 3306 socket = /var/lib/mysql/mysql.sock skip-locking set-variable   = max_allowed_packet=1M

#으로 시작하는 맨 처음 세 줄은 주석이다. MySQL 설정 파일 형식에서는 #와 ; 기호로 주석을 표시할 수 있다. 샵(#)이나 세미콜론(;)이 나타나면 주석 기호 뒤에 나오는 그 줄의 나머지 부분은 모두 무시된다.

다음 줄에는 한 섹션이 시작하는 것을 나타내는 다음과 같은 코드가 있다:

 [client]

삼바(samba)나 윈도우 INI 설정을 건드려본 경험이 있다면 위와 같은 형식이 그다지 낯설지 않을 것이다. 설정 파일은 몇 개의 섹션으로 나위고, 각 옵션은 그 섹션에만 적용된다. MySQL 설정 파일에는 client와 mysqld의 두 가지 섹션이 있다.

섹션을 표시하는 부분 다음 줄부터는 파일이 끝나기 전까지, 또는 다른 그룹이 시작되기 전까지 그 섹션에만 해당되는 옵션이 들어간다. client 섹션에는 클라이언트 도구에 필요한 세 가지 설정 내역이 들어있다. 첫 번째 옵션은 기본 패스워드를 지정하는 부분이다:

 password       = my_password

이 옵션은 --password=my_password 명령행 옵션과 같은 역할을 한다. 일반적으로 명령행 옵션에서 --option=value 형태로 지정하는 것은 MySQL 설정 파일에서 option=value 형태로 지정하는 것과 똑같다.

설정 파일에 패스워드를 넣어 두면 MySQL에 연결할 때마다 매번 패스워드를 입력할 필요가 없기 때문에 편리하다. 하지만 패스워드를 설정 파일이나 명령행에 직접 입력하는 것은 그다지 권장할 만한 방법이 아니다. 클라이언트 유틸리티에서 패스워드를 입력할 수 있는 프롬프트가 나오게 하는 것이 좋다. 설정 파일에 패스워드를 입력해 놓았을 때에는 다른 사람이 절대 그 파일을 열어볼 수 없도록 주의해야 한다.

패스워드 옵션 아래에는 있는 두 줄에서는 클라이언트 도구에서 서버에 연결할 때 사용할 포트 및 소켓 파일을 설정한다. 그 뒤에는 다음과 같은 행이 있어서 새로운 섹션이 시작된다:

 [mysqld]

이 섹션에서는 MySQL 서버 프로세스를 설정하는 옵션이 들어간다. 여기에서는 클라이언트 섹션에서 사용하는 것과 비슷한 형태 외에 두 가지 새로운 옵션 설정 방식이 등장한다. 다음과 같은 옵션에서는 값을 입력할 필요가 없다:

 skip-locking

위의 옵션은 MySQL 서버에서 시스템 잠금을 사용하지 않는다는 것을 의미하는 부울 옵션이다. 위의 옵션을 지정하지 않으면 시스템 잠금이 작동한다. 명령행에서는 --skip-locking 옵션을 사용하면 된다.

MySQL에서 옵션을 지정하는 또 다른 방법은 mysqld 변수를 직접 지정하는 방법이다:

 set-variable = max_allowed_packet=1M

명령행에서는 --set-variable max_allowed_packet=1M라고 적으면 된다. 변수는 서버와 클라이언트의 런타임 환경을 제어하는 설정값이다.

서버 시작 및 종료

MySQL 서버는 서버 프로세스 형태로 동작하므로 컴퓨터를 켤 때마다 자동으로 시작해야 한다. 또한 컴퓨터를 종료할 때 서버도 종료시켜야 한다. MySQL 서버를 자동으로 시작하고 종료시키는 방법은 운영 체제에 따라 다르다.

mysqld 명령으로 명령행에서 직접 서버를 시작하게 만들 수도 있다. 하지만 어떤 운영 체제에서든지 MySQL을 시작할 때에은 safe_mysqld를 사용하는 것이 좋다.

유닉스/리눅스

유닉스 및 리눅스와 같은 유닉스 계열 운영 체제(Mac OS X는 제외)에서 MySQL을 시작하고 끝내는 방법은 SVR4 시스템인지 아닌지에 따라 달라진다. SVR4 시스템에서는 mysql.server 스크립트를 사용하면 되고 다른 유닉스 시스템에서는 safe_mysqld를 사용하면 된다. 여기에서는 이러한 스크립트를 사용하는 대략적인 방법에 대해 설명하겠다(유닉스 시스템을 관리할 때 힘든 부분 중 하나가 바로 시스템별로 서비스를 시작하고 종료하는 방법이 조금씩 다르다는 점이다).

SVR4

SVR4 시스템에서 MySQL을 시작하고 종료할 때에는 mysql.server 스크립트를 사용한다. 이 스크립트는 보통 MySQL을 설치하고 나면 만들어지는 support.files라는 디렉토리(보통 /usr/local/mysql/support-files)에 저장된다. SVR4의 시작/종료 메커니즘은 시스템이 다른 런레벨(run level)에 들어갈 때 서비스를 시작하고, 종료하기 위한 스크립트(/etc 폴더 아래에 들어가는 몇 개의 폴더에 들어감)에 의해 운영된다.

리눅스 시스템에서 RPM 패키지로 설치했다면 mysql.server가 자동으로 설치된다. RPM 설치기에서 mysql.server 파일을 /etc/rc.d/init.d에 복사할 때 그 파일명을 mysql로 바꾼다. /etc/rc.d/init.d/mysql 파일이 있으면 MySQL이 자동으로 시작되고 종료될 것이다.

레드헷 리눅스 시스템에서 mysql.server를 설치하는 방법은 다음과 같다:

 $ cp mysql.server /etc/rc.d/init.d $ ln -s /etc/rc.d/init.d/mysql.server /etc/rc.d/rc3.d/S99mysql $ ln -s /etc/rc.d/init.d/mysql.server /etc/rc.d/rc0.d/S01mysql

첫 번째 줄에서는 mysql.server 스크립트를 초기화 스크립트가 들어가는 /etc/rc.d/init.d 디렉토리에 설치한다. 두 번째 명령에서는 시스템이 3번 런 레벨에 들어갈 때 리눅스에서 자동으로 스크립트를 실행시킬 수 있도록 링크를 만든다. 리눅스에서는 시스템이 3번 런 레벨로 들어가면 /etc/rc.d/rc3.d 디렉토리에 있는 스크립트를 실행시킨다. 3번 런 레벨은 보통 SVR4 시스템이 다중 사용자 모드로 들어간다는 것을 의미한다. 다중 사용자 모드의 런 레벨이 3번이 아니라면 그에 맞는 디렉토리에 링크를 설치해야 한다.

마지막 줄에서는 0번 런 레벨에 mysql.server 스크립트에 대한 링크를 만든다. 0번 런 레벨은 시스템을 종료시키는 런 레벨이다. 따라서 /etc/rc.d/rc0.d에 있는 스크립트는 시스템이 종료될 때 실행된다.

다른 유닉스 시스템

SVR4를 기반으로 하지 않는 유닉스 시스템에서는 safe_mysqld라는 스크립트로 MySQL을 시작한다. 이 스크립트는 MySQL 설치 디렉토리 밑에 있는 /bin 디렉토리(보통 /usr/local/mysql/bin)에서 찾을 수 있다.

safe_mysqld를 사용하고 싶다면 해당 유닉스 시스템이 시작할 때와 종료할 때 서비스를 시작하고 종료하는 방법을 알아야 한다. BSD 시스템 중에는 safe_mysqld를 호출할 수 있도록 /etc/rc.local이라는 파일을 수정해야 하는 것도 있다. 하지만 FreeBSD와 같이 최근에 나온 BSD 시스템에서는 rc.local 파일을 수정하면 안되는 경우도 있다. 예를 틀어, FreeBSD에서는 mysql.server와 같은 스크립트를 /usr/local/etc/rc.d 디렉토리에 저장하면 된다.

Mac OS X

Mac OS X에서는 유닉스 시스템에서 자동으로 서비스를 시작하는 새로운 방법을 도입하였다. 여기에서는 세 가지 서로 다른 시작 디렉토리를 사용한다.

  • /System/Library/StartupItems
  • /Library/StartupItems
  • $HOME/Library/StartupItems

./System/Library/StartupItems 디렉토리는 운영 체제 서비스를 위한 디레토리이고, $HOME/Library/StartupItems 디렉토리는 사용자 소유의 서비스를 위한 디렉토리이다. MySQL은 시스템이 부팅될 때 시작되어야 하는 일반 서비스 디렉토리인 /Library/StartupItems 디렉토리에서 시작해야 한다.

StartupItems 디렉토리에서는 각 서비스별로 디렉토리가 하나씩 있어야 하기 때문에 MySQL을 설치할 때에는 우선 /Library/StartupItems/MySQL 디렉토리를 만들어야 한다. 사실 디렉토리의 이름은 그다지 중요하지 않다. 어쨌든 그 디렉토리에는 다음과 같은 파일이 있어야 한다.

  • MySQL을 시작할 때 쓰는 유닉스 스크립트
  • StartupParameters.plist라는 이름의 시작 매개 변수 파일

유닉스 스크립트는 MySQL을 시작할 때 safe_mysqld 명령어를 호출하기 위한 간단한 스크립트이다. 이 파일명은 디렉토리의 이름과 같아야 한다(여기에는 MySQL). 스크립트는 다음과 같이 만들면 된다:

 #!/bin/sh ./etc/rc.common if ["${MYSQLSERVER:=-NO-}" = "-YES-"]; then        cd /usr/local/mysql        bin/mysqld_safe --user=mysql & fi

$MYSQLSERVER의 값을 확인하는 부분을 넣어 두면 MySQL을 사용하고 싶지 않을 때, StartupItems에서 MySQL 디렉토리를 지울 필요 없이 Mac OS X hostconfig 파일의 내용만 수정하면 된다. MySQL을 사용할 때에는 /etc/hostconfig 파일에 다음과 같은 내용을 추가하면 된다:

 MYSQLSERVER=-YES-

MySQL을 사용하지 않을 때에는 위에 있는 -YES-를 -NO-로 바꾸면 된다.

스크립트 설치를 끝내고 나면 StartupParameters.plist 파일을 만들어야 한다:

 {  Description = "MySQL Database Server";  Provides = ("MySQL");  Requires = ("Resolver");  OrderPreference = "None";  Message =  {   start = "Starting MySQL Server";   stop = "Stopping MySQL Server";  }; }

이 파일은 Mac OS X에 이 디렉토리에 있는 서비스에 대한 설명을 해 주고 다른 서비스에 대한 의존성을 알려주는 역할을 한다. 시스템을 재부팅하면 서비스 시작 메시지가 나올 때 "Starting MySQL Server"라는 메시지가 나오는 것을 볼 수 있다.

윈도우 NT/2000

윈도우 NT 시스템에서는 NT 서비스 형태로 설치된 모든 애플리케이션을 자동으로 시작하고 종료시킨다. 윈도우 시스템에서 MySQL을 서비스로 설치하는 방법은 2장에서 나와 있다.

로그

MySQL 서버에서는 다음과 같은 로그를 만들 수 있다.

  • 에러 로그
  • 질의 로그
  • 이진 로그
  • 느린 질의 로그

mysql.server 또는 safe_mysqld를 이용하여 MySQL을 시작하면 에러 로그가 만들어진다. 원한다면 위에 있는 모든 로그를 기록할 수도 있고, 로그를 전혀 기록하지 않도록 할 수도 있다. 따로 실정해주지 않으면 로그 파일은 데이터 디렉토리에 저장된다.

에러 로그

에러 로그에는 safe_mysqld 스크립트에서 디다이렉트된 출력이 기록된다. 유닉스에서는 hostname.err(hostname 자리에는 호스트명이 들어감)이라는 파일로 저장된다. 윈도우에서는 mysql.err이라는 파일로 저장된다. 이 파일에는 서버가 죽어서 재시작한 경우를 포함하여 매번 서버가 시작할 때와 종료할 때 내용이 기록된다. 테이블의 치명적인 에러 또는 경고 메시지도 이 로그에 기록된다(나중에 확인해야 하거나 고칠 때에는 이 로그를 참조하면 된다).

이진 로그

이진 로그에는 데이터를 갱신하는 모든 SQL 명령어가 기록된다. MySQL에서는 데이터베이스에 있는 데이터를 실제로 바꾼 선언문만을 로그에 남긴다. 예를 들어, 삭제 명령을 내렸는데 전혀 삭제된 행이 없다면 로그에 아무런 기록도 남지 않는다. 도한 어떤 열에 원래 들어있던 것과 같은 값을 다시 대입하면 그 내용도 로그에 기록되지 않는다. 업데이트 내역은 실행된 순서대로 기록된다.

마지막으로 백업한 이후에 일어난 모든 업데이트 내역을 보관할 때에는 이진 로그가 좋다. 예를 들어, 데이터베이스를 매일 한 번씩 백업하는데 데이터베이스가 깨져버렸다면 다음과 같은 방법으로 마지막으로 완료된 트랜잭션까지의 데이터베이스 내용을 그래도 살려낼 수 있다.

  1. 데이터베이스를 복구한다(복구 작업과 관련된 내용은 잠시 후에 나오는 "백업"과 "복구"절을 참고하기 바란다).
  2. 마지막으로 백업한 이후에 이진 로그에 저장된 트랜잭션을 적용한다.

이진 로그를 활성화시킬 때에는 --log-bin=file 옵션을 사용한다. 파일명을 지정해주지 않으면 hostname-bin이라는 파일에 로그가 저장된다. 상대 경로를 사용하면 데이터 디렉토리를 기준으로 한 상대 경로로 간주된다. 그리고 파일명에 숫사 인덱스를 붙이기 때문에 파일명은 filename.number와 같은 형태가 된다(예를 틀어, hostname-bin.2). 이 인덱스는 파일을 순환(rotate)시키기 위한 용도로 쓰이는데, 다음과 같은 경우에 파일이 순환된다.

  • 서버를 다시 시작했을 때
  • 서버를 갱신(refresh)했을 때
  • 로그 크기가 최대 크기에 다다랐을 때
  • 로그를 밀어낼 때(flush할 때)

또한 사용중인 모든 이진 로그 파일의 목록이 저장된 인덱스 파일도 생성된다. 따로 설정해주지 않으면 파일명은 hostname-bin.index가 된다. 이 인덱스의 이름과 위치는 --log-bin-index=file 옵션으로 바꿀 수 있다.

이진 로그의 내용을 볼 때에는 mysqlbinlog 유틸리티를 사용한다. 다음 예에서 이진 로그가 어떤 식으로 작동하는지 알아보자. 이 예에서는 odin이라는 호스트에서 MySQL을 시작했고 log-bin 옵션을 전체 설정 파일인 /etc/my.cnf 파일에서 설정했다고 가정하자. 이 경우에 데이터 디렉토리에 다음과 같은 파일이 만들어진다:

 $ cd /usr/local/mysql/data $ ls -l . . -rw-rw----   1  mysql    mysql     73 Aug   5  17:06 odin-bin.001 -rw-rw----   1  mysql    mysql     15 Aug   5  17:06 odin-bin.index . .

odin-bin.index 파일의 내용은 다음과 같다:

 $ cat odin-bin.index ./odin-bin.001 $

위와 같은 인덱스 내용으로부터 인덱스와 같은 디렉토리에 odin-bin.001이라는 이진 로그파일이 있다는 것을 알 수 있다. mysqlbinlog 유틸리티를 이용하면 로그를 읽을 수 있다:

 $ mysqlbinlog odin-bin.001 # at 4 #010805 17:06:00 server id 1    Start: binlog v 1, server 3.23.40-log created 010805 17:06:00 $

클라이언트에서 데이터베이스를 갱신할 때마다 이진 로그의 내용은 점점 불어난다. 예를 들어, mysql 명령 프롬프트에서 다음과 같은 명령을 내리는 경우를 생각해 보자:

 $ mysql mysql> USE test; mysql> INSERT INTO test (object_id, object_title) VALUES (1, 'test'); Query OK, 1 row affected (0.02 sec) mysql> QUIT; Bye $

위와 같이 하고 나면 이진 로그의 내용이 다음과 같이 바뀐다:

 $ mysqlbinlog odin-bin.001 # at 4 #010805 17:06:00 server id 1    Start: binlog v 1, server 3.23.40-log created 010805 17:06:00 # at 73 #010805 17:39:38 server id 1    Query   thread_id=2    exec_time=0 error_code=0 USE test; SET TIMESTAMP=997058378; INSERT INTO test (object_id, object_title) VALUES (1, 'test'); $

즉 SQL 구문으로 데이터베이스를 갱신하면 이진 로그도 갱신된다. 로그를 밀어내고(flush) 새로운 이진 로그를 시작할 때에는 다음과 같이 하면 된다:

 $ mysqladmin -u root -ppassword flush-logs

이렇게 하면 모든 새로운 갱신 내용이 odin-bin.002라는 파일에 저장된다. 또한 odin-bin.index 파일에도 odin-bin.002 파일이 추가되었음이 기록된다.

이진 로그에 있는 명령을 다시 실행시킬 때에는 mysqlbinlog의 결과를 파이프를 통해 mysql 클라이언트 도구로 보내면 된다:

 $ mysqlbinlog odin-bin.001 | mysql

MySQL에서는 이진 로그를 제어하기 위한 몇 가지 옵션을 제공한다. --binlog-do-db=dbname 옵션을 지정하면 특정 데이터베이스를 갱신했을 때에만 로그를 기록한다. 특정 데이터베이스에 대해서 이진 로그를 기록하지 않을 경우에는 --binlog-ignore-db=dbname 옵션을 사용하면 된다.

느린 질의 로그

느린 질의 로그에는 long_query_time이라는 시스템 변수에 주어진 시간보다 더 오랜 시간이 걸린 모든 명령이 기록된다. 이 로그는 문제가 있는 질의를 찾아서 데이터베이스나 애플리케이션에서 튜닝이 필요한 부분을 밝혀낼 때 많은 도움이 된다.

느린 질의 로그를 사용하고 싶다면 --log-slow-queries=filename 옵션을 사용하면 된다. 파일 이름을 지정하지 않으면 자동으로 hostname-slow.log라는 파일에 저장되고, 디렉토리 이름을 지정하지 않으면 데이터 디렉토리에 저장된다. long_query_time 변수를 설정하고 싶다면 --set-variable long_query_time=time 옵션을 사용하면 된다(이때 time 자리에 초 단위로 시간을 지정하면 된다).

로그 순환

로그를 사용할 때에는 로그 파일이 너무 커지지 않도록 적당히 관리해애 한다. 잘못하면 파일 시스템에서 처리할 수 없을 만큼 로그 파일이 커질 수도 있기 때문이다.

하지만 여기에서 다루는 내용은 에러 로그에는 적용되지 않는다. 에러 로그는 safe_mysqld 스크립트에서 만들기 때문에 MySQL 서버에선 제어할 수 없고, flush-logs 명령어로 밀어낼 수도 없기 때문이다. 게다가 safe_mysqld에서는 매번 새로 시작할 때 새로운 로그를 만들지 않고 같은 로그에 내용을 덧붙인다. 에러 로그를 제대로 제대로 관리하려면 MySQL 서버의 시작 및 종료 스크립트를 수정해야 한다.

레드헷 리눅스를 사용한다면 mysql-log-rotate를 이용하여 로그를 순환시킬 수 있다. 이 프로그램은 MySQL을 설치했을 때 생기는 support-files 디렉토리에 들어 있다. 이 프로그램은 logrotate 유틸리티를 이용하여 자동으로 에러 로그를 순환시켜준다. 레드헷 리눅스에서 mysql-log-rotate를 설치할 때에는 그 파일을 /etc/logrotate.d 디렉토리에 복사하기만 하면 된다. 이 스크립트를 편집하려면 다른 로그도 순환시킬 수 있다. 기본적으로 이 스크립트에서는 질의 로그만 순환시킨다. logrotate에 대한 자센한 내용은 man 페이지나 레드헷 문서에서 찾을 수 있다.

리눅스에서 MySQL을 RPM 패키지로 설치하면 mysql-log-rotata가 자동으로 설치된다. RPM 설치기에서는 mysql-log-rotata를 /etc/logrotate.d에 복사할 대 그 이름을 mysql로 바꾼다. /etc/logrotate.d/mysql 파일이 있다면 로그 순환용 프로그램이 설치되어 있다고 보면된다.

레드헷 기반이 아닌 시스템에서는 로그 순환용 스크립트를 직접 만들어야 되는데, 사용하는 로그의 종류와 로그 저장 위치에 따라 스크립트의 내용이 달라진다. 하지만 로그파일을 복사한 다음 mysqladmin flush-logs 명령으로 로그를 다시 초기화하는 작업을 처리한다는 점은 같다.

백업

관리자가 해야 할 일 중 가장 중요한 것이 바로 백업 계획을 잡는 것이다. 특히 시스템이 다운되었을 때 데이터를 최대한 원래대로 복구해내는 것이 중요하다. 그리고 실수로 테이블을 지우거나 데이터베이스를 손상시킨 경우에도 백업해 둔 데이터가 있다면 문제를 쉽게 해결할 수 있다.

하지만 각 사이트마다 차이점이 있기 때문에 백업 문제에 있어서 어떤 방법이 딱 맞다고 할 수는 없다. 자신이 어떤 식으로 설치했는지, 어떤 기능이 필요한지에 따라 방법이 달라진다. 이 절에서는 백업을 할 때 지켜야 하는 일반적인 규칙과 백업 방법 등에 대해 설명할 것이다. 이 절에 나와 있는 내용을 바탕으로 자신의 상황에 맞는 적당한 백업 방식을 만들면 한다.

일반적으로 백업을 할 때 다음과 같은 점을 고려해야 한다.

  • 가능하다면 데이터베이스와 다른 기기(다른 디스크나 데이프 드라이브 등)에 백업하는 것이 좋다. 디스크가 망거졌더라도 다른 장소에 백업해 두었다면 데이터는 살릴 수 있다. 이진 로그를 사용한다면 이진 로그도 백업하는 기기에 저장하도록 하자.
  • 백업을 하기 전에 디스크 공간이 충분히 남아 있는지 확인한다.
  • 될 수 있으면 백업과 함께 이진 로그를 활용하자. 그러면 데이터 손실을 최소로 줄일 수 있다. 이진 로그를 사용하지 않으면 마지막으로 백업할 시점까지의 데이터만 살릴 수 있다. 백업을 해 두었더라도 이진 로그가 없으면 별 도움이 안되는 경우도 있다.
  • 백업 아카이브의 개수를 적절하게 유지하는 것이 좋다.
  • 위급 상황이 일어나기 전에 백업을 테스트해보는 것이 좋다.

이제 백업할 때 쓸 수 있는 두 가지 MySQL 유틸리티에 대해 알아보자.

mysqldump

mysqldump는 데이터베이스를 덤프해주는 MySQL 유틸리티이다. 이 프로그램에서는 기본적으로는 그 데이터베이스를 다시 만들 때 필요한 모든 명령어(CREATE TABLE, INSERT 등)가 들어 있는 SQL스크립트를 만든다. 이렇게 하면 mysqlhotcopy로 직접 복사하는 경우에 비해 다른 하드웨어나 운영 체제에서 같은 데이터베이스를 새로 만들기에 좋은(즉 이식성이 좋은) ASCII 형식으로 출력된다는 점이다. 그리고 출력 결과가 SQL 스크립트이므로 원하는 테이블만 골라서 복구할 수도 있다.

mysqldump로 데이터베이스를 백업할 때에는 -opt 옵션을 사용하는 것이 좋다. 이 옵션을 사용하면 -quick, --add-drop-table, --add-locks, --extended-insert, --lock-tables 옵션이 모두 선택되며 데이터베이스를 가장 빠르게 덤프할 수 있다. --lock-tables 옵션은 데이터베이스를 사용할 수 없다.

실제 명령은 다음과 같은 식으로 입력하면 된다:

 $ mysqldump --opt test > /usr/backups/testdb

이렇게 하면 test 데이터베이스가 /usr/backups/testdb라는 파일로 덤프된다. 이진 로그를 사용한다면 --flush-logs 옵션을 사용하여 백업할 때 이진 로그를 새로 시작하도록 하는 것이 좋다:

 $ mysqldump --flush-logs --opt test > /usr/backups/testdb

mysqldump에서는 백업할 때 사용할 수 있는 몇 가지 다른 옵션도 제공한다. mysqldump에서 사용할 수 있는 모든 옵션의 목록을 보고 싶다면 mysqldump --help라는 명령을 사용하면 된다.

mysqlhotcopy

mysqlhotcopy는 LOCK TABLES, FLUSH TABLES, 유닉스 cp 명령어 등을 조합하여 데이터베이스를 빠르게 백업하는 펄 스크립트이다. 이 스크립트에서는 데이터베이스 파일을 그대로 다른 곳으로 복사한다. 파일을 복사하기 때문에 mysqldump에 비해 훨씬 더 빠르지만 원래 이식 가능한 형태로 만들어지는 MyISAM 테이블을 제외하면 다른 하드웨어 또는 운영 체제에서 사용하기가 힘들다. 또한 mysqldump는 외부에서도 실행시킬 수 있지만, mysqlhotcopy는 데이터베이스와 같은 호스트에서만 실행시킬 수 있다.

mysqlhotcopy를 실행시킬 때에는 다음과 같은 명령을 사용한다:

 $ mysqlhotcopy test /usr/backups

이렇게 하면 /usr/backups 디렉토리에 test 데이터베이스에 있는 모든 데이터 파일이 복사된다.

이진 로그를 사용한다면 --flushlog 옵션을 사용하면 백업을 마치고 나서 이진 로그를 새로 시작하는 것이 좋다.

복구

디스크에 하드웨어적인 문제가 있는 경우, 데이터 파일이 망가진 경우, 실수로 테이블을 지워버린 경우와 같이 데이터를 복구해야 하는 상황은 정말 다양한다. 이 절에서는 복구 절차에 관한 전반적인 내용을 다뤄보기로 한다.

일반적인 데이터베이스를 복구할 때에는 백업 파일과 이진 로그, 이렇게 두 가지가 필요하다. 복구 절차는 크게 다음과 같이 나눌 수 있다.

  • 마지막으로 백업한 내용으로부터 데이터베이스를 복구한다.
  • 이진 로그를 적용해서 시스템을 완전하게 예전 상태로 되돌린다.

이진 로그 기능을 사용하지 않았다면 마지막으로 백업한 부분까지만 복구할 수 있다.

mysqldump 복구

여기에서는 앞에서 덤프한 test라는 데이터베이스를 북구한다고 가정하겠다.

다음과 같은 명령을 실행하면 데이터베이스를 다시 볼러올 수 있다:

 $ cat test.dump | mysql

이 명령을 실행시키면 mysqldump에서 만들어낸 SQL 명령을 모수 실행시키게 되므로 마지막으로 데이터베이스를 백업할 시점의 상태 그대로 돌아갈 수 있다.

시스템을 마지막으로 백업할 상태로 돌로놓고 나면 이진 로그를 이용해서 마지막 백업 이후에 처리된 트랜잭션을 다시 실행시키면 된다. 로그에 여러 개의 데이터베이스에 대한 내용이 들어 있는데 그 중 하나만 복구하고 싶다면 --one-database 옵션을 사용해서 다른 데이터베이스에 적용되는 SQL 명령을 걸러낼 수 있다. 또한 이진 로그 중에서 마지막 백업 이후에 기록된 부분만 다시 실행시켜야 한다. 각 이진 로그 파일에 대해 다음과 같은 명령을 입력하자:

 $ mysqlbinlog host-bin.xxx | mysql --one-database=testdb

경우에 따라 mysqlbinlog 프로그램에서 출력된 결과를 조금 수정해야 할 수도 있따. 예를 들어, DROP TABLE 명령을 잘못 내려서 지워진 테이블을 복구한다면 mysqlbinlog에서 출력된 내용 중 DROP TABLE 선언문 부분을 지워야 한다. 그렇게 하지 않으면 열심히 복구한 테이블이 다시 삭제된다. 따라서 이런 경우에는 mysqlbinlog에서 출력된 내용을 텍스트 파일에 저장해서 편집하고, 그 텍스트 파일을 이용하여 데이터베이스를 복구해야 한다.

mysqlhotcopy 복구

mysqlhotcopy 백업 데이터로부터 복구할 때에는 서버가 멈춰 있는 상태에서 데이터베이스 파일을 백업 디렉토리에서 mysql 데이터 디렉토리로 복사하면 된다. 데이터베이스를 /var/backup/test에 백업했다고 가정하고, MySQL 데이터 디렉토리가 /usr/local/mysql/data 라면 다음과 같은 명령을 실행시켜서 마지막에 백업한 시점으로 데이터베이스를 되돌릴 수 있다:

 $ cp -R /var/backup/test /usr/lcoal/mysql/data

이제 mysql 서버를 다시 시작시키고 앞에서 설명한 것처럼 이진 로그를 적용시키면 시스템을 완전히 복구할 수 있다.

테이블 관리 및 복구

데이터 파일에 대한 쓰기 작업이 제대로 처리되지 않았을 때 데이터베이스 파일이 망가질 수도 있다. 전원이 나가거나 MySQL 서버를 정상적으로 종료시키지 않으면 이런 일이 일어날 수 있다.

MySQL에서는 myisamchk/ismchk와 mysqlcheck라는 두 가지 방법으로 테이블 에러를 알아내고 수리할 수 있다. 웬만하면 정기적으로 테이블에 문제가 있는지 검사하는 것이 좋다. 데이터베이스에 문제가 있다는 것을 일찍 발견할수록 테이블을 성공적으로 복구할 수 있는 가능성이 높아지게 마련이다.

mysqlcheck는 MySQL 3.23.38부터 새로 등장한 프로그램이다. myisamchk/isamchk와 mysqlcheck의 가장 큰 차이점은 mysqlcheck에서는 서버가 돌아가고 있을 때에도 테이블을 검사하거나 수리할 수 있다는 점이다.

myisamchk와 isamchk는 서로 상당히 유사하다. 이 둘의 기능은 같지만 myisamchk는 MyISAM 테이블에서 isamchk는 ISAM 테이블서 사용한다. mysqlcheck는 MyISAM 테이블에서만 사용할 수 있다.

테이블 검사

테이블에 어떤 문제가 있는 것 같다면 우선 테이블 검사용 유틸리티를 이용하여 테이블을 검사해야 한다. 데이터 파일의 확장자를 보면 테이블의 종류를 알 수 있다. 파일 확장자가 .MYI라면 MyISAM 테이블이고 .ISM이면 ISAM 테이블이다. 따라서 .MYI 파일에 대해서는 myismchk와 mysqlcheck를, .ISM 파일에 대해서는 isamchk를 사용하면 된다.

table1(ISAM 테이블)과 table2(MyISAM 테이블)라는 두 개의 테이블이 있는 test라는 테이터베이스가 있다고 가정하자. 우선 적절한 유틸리티로 테이블을 검사해야 한다. myisamchk와 isamchk를 사용할 때에는 파일을 읽는 도중에 서버에서 파일에 쓰기 작업을 하는 것을 방지하기 위해 MySQL 서버를 종료시켜야 한다:

 $ myisamchk table2.MYI Data records:      0    Deleted blocks:      0 - check file-size - check key delete-chain - check record delete-chain - check index reference $ isamchek table1.ISM Checking ISAM file: table1.ISM Data record:       0   Deleted blocks:       0 - check file-size - check delete-chain - check index reference $ mysqlcheck test table2 test.table2                                  OK

위와 같은 결과가 나오면 두 테이블 모두 에러가 없음을 알 수 있다.

간단한 에러를 찾아낼 때에는 위와 같은 기본적인 검사만으로도 충분하다. 에러는 없지만 테이블이 손상된 것 같다면 myisamchek/isamchk의 --extend-check 옵션이나 mysqlcheck의 --extend 옵션으로 확장 검사를 할 수 있다. 확장 검사를 하면 시간은 조금 오래 걸리지만 매우 자세히 검사할 수 있다. 확장 검사에서도 아무로 에러가 없다면 테이블에 문제가 없음을 알 수 있다.

테이블 복구

검사 결과 테이블에 에러가 있다면 그 에러를 고쳐야 한다.

myisamchk나 isamchk를 사용하는 경우에는 테이블을 복구할 때 MySQL 서버를 종료해야 한다. 그리고 만약에 대비해서 테이블을 복구하기 전에 데이터 파일을 백업해 두는 것이 좋다.

우선 --recover 옵션을 주고, myisamchk/isamchk를 실행해 보자:

 $ isamchk --recover table1.ISM - recovering ISAM-table 'table1.ISM' Data records: 3 $ myisamchk --recover table2.MYI - recovering (with keycache) MyISAM-table 'table2.MYI' Data records: 2

위와 같이 해도 문제가 해결되지 않는다면 느리긴 하지만 --recover로는 수정할 수 없는 에러도 고칠 수 있는 --safe-recover 옵션을 사용해 보자:

 $ isamchk --safe-recover table1.ISM - recovering ISAM-table 'table1.ISM' Data records: 3 $ myisamchk --safe-recover table2.MYI - recovering (with keycache) MyISAM-table 'table2.MYI' Data records: 2

mysqlcheck에서느 복구 옵션이 --repair밖에 없다:

 $mysqlcheck -repair test table2 test.table2                                  OK

이렇게 해도 안 된다면 백업 자료와 이진 로그를 이용해서 테이블을 복구하는 수밖에 없다. 자세한 내용은 "백업" 절과 "복구" 절에 나와 있다.

테이블 정기 검사

테이터베이스 파일에 대해서 정기적으로 테이블 검사를 해 주는 것이 좋다. isamchk/myisamchk/mysqlcheck 명령을 처리하는 스크립트를 만들어서 cron과 같은 스케쥴링 소프트웨어에서 정기적으로 실행하도록 만들면 된다.

또한 시스템이 부팅될 때 테이블을 검사할 수 있도록 시스템 부팅 절차를 조금 고치는 것도 괜찮은 생각이다. 이렇게 하면 특히 시스템이 다운된 후에 재부팅할 때 여려 모로 도움이 된다.


한빛미디어 "MySQL 시스템 관리와 프로그래밍"

Posted by tornado
|