An Optimized Approach for Path Searching in Tree Structures Stored in SQL (Draft)

J. L. Villa

Abstract

This article presents an innovative technique for the efficient management of tree structures in relational databases, with specific application to file and directory systems. The proposed approach, called "PathFinder," combines the simplicity of the adjacency list model with an intelligent processing algorithm that enables the location of complete paths in directory trees using a single non-recursive SQL query. Unlike traditional methods that require multiple queries or complex stored procedures, our solution transfers the tree traversal logic to the application layer, resulting in greater flexibility and performance. The article includes a detailed implementation using the DevExpress XPO framework, demonstrating the practical viability of the approach in enterprise applications that need to efficiently manage hierarchical tree structures.

1. Introduction

Representing tree structures in relational databases has been a recurring challenge in software development. Trees, as fundamental data structures, model hierarchical relationships where each node (except the root) has exactly one parent and may have multiple children. File systems are a classic and ubiquitous example of these tree structures, where directories represent internal nodes and files represent leaves of the tree.

Document management systems, file explorers, product catalogs, and numerous enterprise applications require efficiently storing and querying these tree structures, with special emphasis on retrieving complete paths from the root to any node in the tree.

The fundamental problem lies in the tabular nature of relational databases, which does not naturally adapt to hierarchical tree structures. Over the years, various solutions have been proposed, each with its own advantages and limitations. However, many of these approaches sacrifice the simplicity of the data model or the performance of queries, especially when it comes to locating complete paths based on node names at different levels of the tree.

In this article, we present an approach that maintains a simple data schema while providing optimized performance for path searching in trees, with special attention to handling ambiguities when nodes with identical names exist in different branches of the tree.

2. Traditional Approaches to Modeling Trees in Databases and Their Limitations

Before describing our solution, it is important to briefly review the main approaches traditionally used to model tree structures in relational databases:

2.1. Adjacency List Model for Trees

The simplest and most direct way to represent trees, where each node stores a reference to its parent node. Its main advantage is the simplicity of the schema, but queries to retrieve complete paths from the root to any node in the tree often require recursive operations or multiple joins, which affects performance with deep trees.

CREATE TABLE Nodes (
    NodeID INT PRIMARY KEY,
    Name VARCHAR(255) NOT NULL,
    ParentID INT,
    FOREIGN KEY (ParentID) REFERENCES Nodes(NodeID)
);

2.2. Materialized Path Model for Trees

Stores the complete path from the root to each node in the tree, facilitating ancestor searches but complicating modification operations when restructuring the tree and limiting the practical depth of the tree.

CREATE TABLE Nodes (
    NodeID INT PRIMARY KEY,
    Name VARCHAR(255) NOT NULL,
    Path VARCHAR(4000) NOT NULL  -- Ex: "/1/4/7/" to represent the path in the tree
);

2.3. Nested Sets Model for Trees

Uses left and right indices to represent the tree structure, offering efficient queries for traversing complete subtrees but significantly complicating node insertion and update operations in the tree.

CREATE TABLE Nodes (
    NodeID INT PRIMARY KEY,
    Name VARCHAR(255) NOT NULL,
    Left INT NOT NULL,
    Right INT NOT NULL
);

2.4. Closure Table for Trees

Explicitly stores all relationships between ancestors and descendants in the tree, providing good performance for all types of navigation queries at the cost of additional space and greater complexity in tree modification operations.

CREATE TABLE Nodes (
    NodeID INT PRIMARY KEY,
    Name VARCHAR(255) NOT NULL
);

CREATE TABLE TreeRelationships (
    AncestorID INT NOT NULL,
    DescendantID INT NOT NULL,
    Depth INT NOT NULL,
    PRIMARY KEY (AncestorID, DescendantID)
);

2.5. Database-Specific Extensions for Trees

Solutions like LTREE in PostgreSQL offer specialized functionality for tree structures, but limit portability between different database management systems and require engine-specific syntax.

Figure 2: Visual comparison of different models for representing tree structures in relational databases.

3. The PathFinder Approach: Description and Fundamentals

Our approach, called "PathFinder," is based on a fundamental principle: using the simplicity of the adjacency list model in the persistence layer, combined with an intelligent processing algorithm in the application layer to efficiently solve path searching in tree structures.

3.1. Conceptual Fundamentals

The method consists of two main parts:

1. A single non-recursive SQL query: Retrieves all candidate nodes (directories) whose names match the components of the path being searched in the tree.

2. A path reconstruction algorithm: Processes the results to verify the parent-child relationships typical of a tree and builds the correct path from the root to the target node, even in the presence of ambiguities.

This approach adopts the "divide and conquer" principle, separating the task of candidate selection (which is delegated to the database, where it is more efficient) from the task of verifying the hierarchical relationships of the tree (which is performed in the application layer, where it offers greater flexibility).

Figure 1: Conceptual representation of a directory tree where each node has a single parent (except the root) and may have multiple children.

3.2. Description of the Algorithm for Traversing the Tree

The algorithm for traversing the tree and finding the correct path can be summarized in the following steps:

1. Decompose the search path into its individual components (node names at each level of the tree).

2. Execute a single query that retrieves all nodes in the tree whose names match any of the components of the searched path.

3. Organize the candidate nodes by their expected level in the tree structure.

4. Recursively build all possible paths in the tree, verifying the parent-child relationships between nodes at adjacent levels, following the structure typical of a tree where each node has exactly one parent.

5. Select the first valid path that meets all the expected hierarchical relationships in the tree structure.

The key to the approach is step 2, where with a single SQL query we obtain all potential candidates that could form part of the path in the tree, eliminating the need for recursive queries or multiple database accesses to traverse the tree level by level.

4. Implementation with DevExpress XPO

Below, we present a complete implementation of the approach using the XPO (eXpress Persistent Objects) framework from DevExpress, widely used in enterprise applications.

4.1. Data Model

using DevExpress.Xpo;

namespace DirectoryManager
{
    [Persistent("Directories")]
    public class Directory : XPObject
    {
        public Directory(Session session) : base(session) { }
        public Directory() : base() { }

        private string _name;
        [Indexed(Name = "IDX_Name")]
        public string Name
        {
            get { return _name; }
            set { SetPropertyValue(nameof(Name), ref _name, value); }
        }

        private Directory _parent;
        [Association("Parent-Children")]
        public Directory Parent
        {
            get { return _parent; }
            set { SetPropertyValue(nameof(Parent), ref _parent, value); }
        }

        [Association("Parent-Children", typeof(Directory))]
        public XPCollection<Directory> Children
        {
            get { return GetCollection<Directory>(nameof(Children)); }
        }
    }
}

4.2. PathFinder Implementation

The implementation of the PathFinder algorithm is done in a specialized class that uses XPO to interact with the database:

using DevExpress.Data.Filtering;
using DevExpress.Xpo;
using System;
using System.Collections.Generic;
using System.Linq;

namespace DirectoryManager
{
    public class DirectoryPathFinder
    {
        private readonly UnitOfWork _unitOfWork;

        public DirectoryPathFinder(UnitOfWork unitOfWork)
        {
            _unitOfWork = unitOfWork ?? throw new ArgumentNullException(nameof(unitOfWork));
        }

        public string FindPath(string[] pathComponents)
        {
            if (pathComponents == null || pathComponents.Length == 0)
            {
                return "Invalid path";
            }

            // Perform a single query to get all candidate directories
            var candidates = GetDirectoriesByNames(pathComponents);

            if (!candidates.Any())
            {
                return "No path component was found";
            }

            // Organize directories by expected level in the path
            var directoriesByLevel = OrganizeDirectoriesByLevel(candidates, pathComponents);

            // Verify that there are candidates for all levels
            if (directoriesByLevel.Any(level => !level.Any()))
            {
                return $"Component not found: {string.Join(", ", pathComponents.Where((p, i) => !directoriesByLevel[i].Any()))}";
            }

            // Build path from each root candidate
            foreach (var root in directoriesByLevel[0])
            {
                var foundPath = BuildPath(root, pathComponents, directoriesByLevel);
                if (foundPath != null)
                {
                    return "/" + string.Join("/", foundPath.Select(d => d.Name));
                }
            }

            return "Path not found - components do not form a connected chain";
        }

        private IList<Directory> GetDirectoriesByNames(string[] pathComponents)
        {
            // Create criteria to filter by names
            CriteriaOperator criteria = new InOperator("Name", pathComponents);

            // Get all matching directories
            return _unitOfWork.GetObjects<Directory>(criteria, null, true);
        }

        private List<List<Directory>> OrganizeDirectoriesByLevel(
            IList<Directory> candidates, string[] pathComponents)
        {
            var directoriesByLevel = new List<List<Directory>>();

            for (int i = 0; i < pathComponents.Length; i++)
            {
                var directoriesAtLevel = candidates
                    .Where(d => d.Name == pathComponents[i])
                    .ToList();

                directoriesByLevel.Add(directoriesAtLevel);
            }

            return directoriesByLevel;
        }

        private List<Directory> BuildPath(
            Directory currentNode,
            string[] pathNames,
            List<List<Directory>> directoriesByLevel,
            int currentLevel = 0,
            List<Directory> partialPath = null)
        {
            partialPath = partialPath ?? new List<Directory>();
            partialPath.Add(currentNode);

            // If we've reached the last level, we've found the complete path
            if (currentLevel == pathNames.Length - 1)
            {
                return partialPath;
            }

            // Candidates for the next level
            var nextCandidates = directoriesByLevel[currentLevel + 1];

            // Filter candidates that have the current node as parent
            var childCandidates = nextCandidates
                .Where(d => d.Parent != null && d.Parent.Oid == currentNode.Oid)
                .ToList();

            // Try to build the path with each child candidate
            foreach (var child in childCandidates)
            {
                var newPartialPath = new List<Directory>(partialPath);
                var result = BuildPath(
                    child,
                    pathNames,
                    directoriesByLevel,
                    currentLevel + 1,
                    newPartialPath
                );

                if (result != null)
                {
                    return result;
                }
            }

            // We couldn't build a complete path from this node
            return null;
        }
    }
}

4.3. Optimized Version for High Performance

For scenarios with large volumes of data, we have developed an optimized implementation that minimizes memory load and ORM overhead:

public class OptimizedDirectoryPathFinder
{
    private readonly Session _session;

    public OptimizedDirectoryPathFinder(Session session)
    {
        _session = session ?? throw new ArgumentNullException(nameof(session));
    }

    public string FindPathOptimized(string[] pathComponents)
    {
        // Create a temporary table of directories by component
        Dictionary<string, List<DirectoryInfo>> directoriesByName = new Dictionary<string, List<DirectoryInfo>>();

        // Initialize the dictionary
        foreach (var component in pathComponents)
        {
            directoriesByName[component] = new List<DirectoryInfo>();
        }

        // Perform a single optimized SQL query
        var customSelectStatements = new SelectStatement[]
        {
            new SelectStatement(
                _session.GetClassInfo(typeof(Directory)).TableName,
                new SelectedProperty[]
                {
                    new SelectedProperty("Oid"),
                    new SelectedProperty("Name"),
                    new SelectedProperty("GCRecord"),
                    new SelectedProperty("Parent.Oid")
                },
                new InOperator("Name", pathComponents),
                null
            )
        };

        // Execute the query and process the results directly
        using (var result = _session.DataLayer.SelectData(customSelectStatements))
        {
            while (result.Read())
            {
                if (result.GetValue(2) != null) // Ignore deleted records
                    continue;

                int id = Convert.ToInt32(result.GetValue(0));
                string name = result.GetValue(1) as string;
                object parentOid = result.GetValue(3);
                int? parentId = parentOid != null ? Convert.ToInt32(parentOid) : (int?)null;

                if (directoriesByName.ContainsKey(name))
                {
                    directoriesByName[name].Add(new DirectoryInfo
                    {
                        Id = id,
                        Name = name,
                        ParentId = parentId
                    });
                }
            }
        }

        // Search for all possible paths starting from the first component
        var candidatePaths = new List<List<DirectoryInfo>>();
        var firstComponent = pathComponents[0];

        foreach (var dirRoot in directoriesByName[firstComponent])
        {
            if (dirRoot.ParentId == null) // Verify it's a root
            {
                FindPathsRecursively(
                    dirRoot,
                    pathComponents,
                    directoriesByName,
                    new List<DirectoryInfo> { dirRoot },
                    1,
                    candidatePaths
                );
            }
        }

        // Return the first valid path found
        if (candidatePaths.Count > 0)
        {
            var validPath = candidatePaths[0];
            return "/" + string.Join("/", validPath.Select(d => d.Name));
        }

        return "Path not found";
    }

    private class DirectoryInfo
    {
        public int Id { get; set; }
        public string Name { get; set; }
        public int? ParentId { get; set; }
    }
}

This optimized version works directly with low-level SQL queries, avoiding the overhead associated with the ORM when loading complete objects, which results in better performance for large datasets.

5. Performance Analysis and Use Cases

5.1. Advantages of the PathFinder Approach for Trees

The PathFinder approach offers several significant advantages for handling tree structures:

1. Query efficiency: A single non-recursive SQL query, regardless of the tree depth, avoiding the classic problem of recursive queries that can degrade performance in deep trees.

2. Data schema simplicity: Maintains the basic adjacency list model to represent the tree, making it easy to understand and implement.

3. Ambiguity resolution: Correctly handles nodes with identical names in different branches of the tree, a common problem in real file systems where directories with the same name can exist in different locations of the tree.

4. DBMS independence: Works with any relational database, without depending on specific features for handling hierarchical structures.

5. Flexibility: Easily adaptable to different types of tree structures (binary trees, n-ary trees, etc.) and use cases where tree path navigation is required.

5.2. Complexity Analysis

• Time complexity:

  • SQL query: O(n), where n is the total number of directories in the database.
  • Reconstruction algorithm: O(m²), where m is the number of directories with names matching path components.
  • In practice, m << n, which makes the approach very efficient.

• Space complexity:

  • Storage: O(n) for the adjacency list model.
  • Runtime memory: O(m) for candidate directories.

5.3. Ideal Use Cases

The PathFinder approach is particularly suitable for:

1. Document management systems: Where it is common to search for documents by their complete path.
2. File explorers: That need to efficiently navigate hierarchical structures.
3. Product catalogs: With deeply nested categories and subcategories.
4. Content management systems: Where pages are organized hierarchically.
5. Taxonomies and classifications: In systems that require flexible hierarchical structures.

6. Comparison with Other Approaches

To provide context, we compare the performance and features of the PathFinder approach with traditional methods:

Feature	PathFinder	Adjacency List + CTEs	Materialized Path	Nested Sets	Closure Table
Schema complexity	Low	Low	Low	Medium	High
Path search efficiency	High	Medium	High	Medium	High
Modification efficiency	High	High	Low	Low	Medium
Ambiguity handling	Yes	Depends	No	No	Yes
Ascending queries (ancestors)	Requires processing	Requires recursion	O(1) with LIKE	O(1)	O(1)
Descending queries (children)	O(1)	O(1)	Requires LIKE	O(1)	O(1)
Portability between DBMSs	High	Medium	High	High	High
Scalability	High	Medium	High	Medium	Medium
Memory usage	Low-Medium	Medium	Low	Low	High

7. Limitations and Considerations

Despite its advantages, the PathFinder approach presents some limitations that should be considered:

1. Processing load: Transfers part of the processing load to the application, which may not be ideal in environments with limited resources.

2. Query optimization: Depends on adequate indexes on the Name and ParentID columns for optimal performance.

3. Synchronization: In multi-user environments, appropriate locking mechanisms must be implemented to avoid inconsistencies during modification operations.

4. Horizontal scalability: For distributed systems, additional adaptations may be necessary.

8. Conclusions and Future Work

The PathFinder approach represents an innovative and efficient solution to the problem of path searching in tree structures stored in relational databases. Combining the simplicity of the adjacency list model with an intelligent processing algorithm, it offers an optimal balance between performance, flexibility, and ease of implementation for traversing and querying trees.

The implementation with DevExpress XPO demonstrates the practical viability of the approach in enterprise applications that need to manage tree structures, with optimization options for different use cases and tree sizes.

For future work in the field of tree structures, we identify:

1. Extension to directed acyclic graph (DAG) structures: Adapt the algorithm to support nodes with multiple parents, thus extending the tree concept to directed acyclic graphs.

2. Tree traversal parallelization: Explore parallelization strategies to improve performance in systems with large trees, dividing the processing of different branches of the tree.

3. Intelligent caching of tree paths: Develop caching mechanisms for frequently used paths, especially for the upper parts of the tree that are accessed more frequently.

4. Integration with tree search systems: Combine with full-text search technologies to implement hybrid searches that leverage both the tree structure and the content of the nodes.

5. Optimization for balanced trees: Develop variants of the algorithm that take advantage of the special properties of balanced trees to further improve performance.

References

1. Celko, J. (2012). Joe Celko's Trees and Hierarchies in SQL for Smarties. Morgan Kaufmann.

2. Date, C. J. (2015). SQL and Relational Theory: How to Write Accurate SQL Code. O'Reilly Media.

3. DevExpress Documentation. "XPO - eXpress Persistent Objects". https://docs.devexpress.com/XPO/

4. Karwin, B. (2010). SQL Antipatterns: Avoiding the Pitfalls of Database Programming. Pragmatic Bookshelf.

5. Tropashko, V. (2005). SQL Design Patterns: Expert Guide to SQL Programming. Rampant Techpress.

Acknowledgments

[Acknowledgments to collaborators, reviewers, etc.]