Now that MySQL 8.0 supports recursive queries, we can say that all popular SQL databases support recursive queries in standard syntax.
WITH RECURSIVE MyTree AS (
SELECT * FROM MyTable WHERE ParentId IS NULL
UNION ALL
SELECT m.* FROM MyTABLE AS m JOIN MyTree AS t ON m.ParentId = t.Id
)
SELECT * FROM MyTree;
I tested recursive queries in MySQL 8.0 in my presentation Recursive Query Throwdown in 2017.
Below is my original answer from 2008:
There are several ways to store tree-structured data in a relational database. What you show in your example uses two methods:
- Adjacency List (the "parent" column) and
- Path Enumeration (the dotted-numbers in your name column).
Another solution is called Nested Sets, and it can be stored in the same table too. Read "Trees and Hierarchies in SQL for Smarties" by Joe Celko for a lot more information on these designs.
I usually prefer a design called Closure Table (aka "Adjacency Relation") for storing tree-structured data. It requires another table, but then querying trees is pretty easy.
I cover Closure Table in my presentation Models for Hierarchical Data with SQL and PHP and in my book SQL Antipatterns: Avoiding the Pitfalls of Database Programming.
CREATE TABLE ClosureTable (
ancestor_id INT NOT NULL REFERENCES FlatTable(id),
descendant_id INT NOT NULL REFERENCES FlatTable(id),
PRIMARY KEY (ancestor_id, descendant_id)
);
Store all paths in the Closure Table, where there is a direct ancestry from one node to another. Include a row for each node to reference itself. For example, using the data set you showed in your question:
INSERT INTO ClosureTable (ancestor_id, descendant_id) VALUES
(1,1), (1,2), (1,4), (1,6),
(2,2), (2,4),
(3,3), (3,5),
(4,4),
(5,5),
(6,6);
Now you can get a tree starting at node 1 like this:
SELECT f.*
FROM FlatTable f
JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1;
The output (in MySQL client) looks like the following:
+----+
| id |
+----+
| 1 |
| 2 |
| 4 |
| 6 |
+----+
In other words, nodes 3 and 5 are excluded, because they're part of a separate hierarchy, not descending from node 1.
Re: comment from e-satis about immediate children (or immediate parent). You can add a "path_length
" column to the ClosureTable
to make it easier to query specifically for an immediate child or parent (or any other distance).
INSERT INTO ClosureTable (ancestor_id, descendant_id, path_length) VALUES
(1,1,0), (1,2,1), (1,4,2), (1,6,1),
(2,2,0), (2,4,1),
(3,3,0), (3,5,1),
(4,4,0),
(5,5,0),
(6,6,0);
Then you can add a term in your search for querying the immediate children of a given node. These are descendants whose path_length
is 1.
SELECT f.*
FROM FlatTable f
JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1
AND path_length = 1;
+----+
| id |
+----+
| 2 |
| 6 |
+----+
Re comment from @ashraf: "How about sorting the whole tree [by name]?"
Here's an example query to return all nodes that are descendants of node 1, join them to the FlatTable that contains other node attributes such as name
, and sort by the name.
SELECT f.name
FROM FlatTable f
JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1
ORDER BY f.name;
Re comment from @Nate:
SELECT f.name, GROUP_CONCAT(b.ancestor_id order by b.path_length desc) AS breadcrumbs
FROM FlatTable f
JOIN ClosureTable a ON (f.id = a.descendant_id)
JOIN ClosureTable b ON (b.descendant_id = a.descendant_id)
WHERE a.ancestor_id = 1
GROUP BY a.descendant_id
ORDER BY f.name
+------------+-------------+
| name | breadcrumbs |
+------------+-------------+
| Node 1 | 1 |
| Node 1.1 | 1,2 |
| Node 1.1.1 | 1,2,4 |
| Node 1.2 | 1,6 |
+------------+-------------+
A user suggested an edit today. SO moderators approved the edit, but I am reversing it.
The edit suggested that the ORDER BY in the last query above should be ORDER BY b.path_length, f.name
, presumably to make sure the ordering matches the hierarchy. But this doesn't work, because it would order "Node 1.1.1" after "Node 1.2".
If you want the ordering to match the hierarchy in a sensible way, that is possible, but not simply by ordering by the path length. For example, see my answer to MySQL Closure Table hierarchical database - How to pull information out in the correct order.
I've tried many different ways to do this, and this is the best solution that I have come up with. AdvancedDataGrid already has logic built in to handle the mouseMove/mouseOver/mouseDown events, so there's no need to recreate it. Simply override the DragEvent handlers.
I have duplicated the code I use in several applications that need similar functionality, included your logic for determining if the item can be dragged, as well as some logic to determine if it can be dropped in a certain location. I have also included extensive commenting to help explain why certain things are done. I hope this helps!
CustomADG.as:
package
{
import mx.controls.AdvancedDataGrid;
import mx.controls.listClasses.IListItemRenderer;
import mx.core.DragSource;
import mx.events.DragEvent;
import mx.managers.DragManager;
import mx.utils.ObjectUtil;
public class DragDropADG extends AdvancedDataGrid
{
private var itemRendererUnderPoint:IListItemRenderer
public function DragDropADG()
{
super();
}
override protected function dragStartHandler(event:DragEvent):void
{
/* Create a new Array from the Array of selectedItems, filtering out items
that are not "branches". */
var selectedBranches:Array /* of Object */ =
selectedItems.filter(hasCategories);
function hasCategories(element:*, index:int, array:Array):Boolean
{
/* Returns true if the item is a Branch (has children in the categories
property). */
return (element.hasOwnProperty("categories") &&
element.categories != null);
}
/* Exit if no Branches are selected. This will stop the drag operation from
starting. */
if (selectedBranches.length == 0)
return;
/* Reset the selectedItems Array to include only selected Branches. This
will deselect any "non-Branch" items. */
selectedItems = selectedBranches;
/* Create a copy of the Array of selected indices to be sorted for
display in the drag proxy. */
var sortedSelectedIndices:Array /* of int */ =
ObjectUtil.copy(selectedIndices) as Array /* of int */;
// Sort the selected indices
sortedSelectedIndices.sort(Array.NUMERIC);
/* Create an new Array to store the selected Branch items sorted in the
order that they are displayed in the AdvancedDataGrid. */
var draggedBranches:Array = [];
var itemRendererAtIndex:IListItemRenderer;
for each (var index:int in sortedSelectedIndices)
{
itemRendererAtIndex = indexToItemRenderer(index);
var branchItem:Object = itemRendererAtIndex.data;
draggedBranches.push(branchItem);
}
// Create a new DragSource Object to store data about the Drag operation.
var dragSource:DragSource = new DragSource();
// Add the Array of Branches to be dragged to the DragSource Object.
dragSource.addData(draggedBranches, "draggedBranches");
// Create a new Container to serve as the Drag Proxy.
var dragProxy:DragProxyContainer = new DragProxyContainer();
/* Update the labels in the Drag Proxy using the "label" field of the items
being dragged. */
dragProxy.setLabelText(draggedBranches);
/* Create a point relative to this component from the mouse
cursor location (for the DragEvent). */
var eventPoint:Point = new Point(event.localX, event.localY);
// Initiate the Drag Event
DragManager.doDrag(this, dragSource, event, dragProxy,
-eventPoint.x, -eventPoint.y, 0.8);
}
/* This function runs when ANY item is dragged over any part of this
AdvancedDataGrid (even if the item is from another component). */
override protected function dragEnterHandler(event:DragEvent):void
{
/* If the item(s) being dragged does/do not contain dragged Branches,
it/they are being dragged from another component; exit the function to
prevent a drop from occurring. */
if (!event.dragSource.hasFormat("draggedBranches"))
return;
var dropIndex:int = calculateDropIndex(event);
/* Get the itemRenderer of the current drag target, to determine if the
drag target can accept a drop. */
var dropTargetItemRenderer:IListItemRenderer =
indexToItemRenderer(dropIndex);
/* If the item is being dragged where there is no itemRenderer, exit the
function, to prevent a drop from occurring. */
if (dropTargetItemRenderer == null)
return;
/* If the item is being dragged onto an itemRenderer with no data, exit the
function, to prevent a drop from occurring. */
if (dropTargetItemRenderer.data == null)
return;
/* Store the underlying item for the itemRenderer being dragged over, to
validate that it can be dropped there. */
var dragEnterItem:Object = dropTargetItemRenderer.data
if (!dragEnterItem.hasOwnProperty("categories")
return;
if (dragEnterItem.categories == null)
return;
var eventDragSource:DragSource = event.dragSource;
eventDragSource.addData(dragEnterItem, "dropTargetItem");
/* Add an dragDrop Event Listener to the itemRenderer so that the
necessary will run when it is dropped.*/
dropTargetItemRenderer.addEventListener(DragEvent.DRAG_DROP,
itemRenderer_dragDropHandler);
// Specify that the itemRenderer being dragged over can accept a drop.
DragManager.acceptDragDrop(dropTargetItemRenderer);
}
/* Perform any logic that you want to occur once the user drops the item. */
private function itemRenderer_dragDropHandler(event:DragEvent):void
{
var eventDragSource:DragSource = event.dragSource;
var dropTargetItem:Object =
eventDragSource.dataForFormat("dropTargetItem");
if (dropTargetItem == null)
return;
var draggedBranchesData:Object =
eventDragSource.dataForFormat("draggedBranches");
var draggedBranches:Array /* of Object */ =
draggedBranchesData as Array /* of Object */;
// Call any other functions to update your underlying data, etc.
}
}
}
DragProxyContainer.as:
package
{
import mx.containers.VBox;
import mx.core.UITextField;
[Bindable]
public class DragProxyContainer extends VBox
{
private var textField:UITextField = new UITextField();
public function DragProxyContainer()
{
super();
minWidth = 150;
addChild(textField);
}
public function setLabelText(items:Array, labelField:String = "label"):void
{
var labelText:String;
var numItems:int = items.length;
if (numItems > 1)
{
labelText = numItems.toString() + " items";
}
else
{
var firstItem:Object = items[0];
labelText = firstItem[labelField];
}
textField.text = labelText;
}
}
}
Best Answer
AdvancedDataGrid has an expandItem() method too:
http://livedocs.adobe.com/flex/3/langref/mx/controls/AdvancedDataGrid.html#expandItem()