PaperlayerView exact revision on arXiv

Source-linked AI summary

Tree Databases

Nicolas Spyratos

arXiv:2609.03538v1cs.DB

TL;DR

Tree Databases addresses how application data, relationships, access, and analysis can be represented in one model. It proposes labeled, directed trees combined through tree operations and a shared functional algebra for traversal and analytic queries. The paper demonstrates inheritance, consistent relational databases over trees, and relational-data access, while leaving efficient restriction algorithms and fuller inheritance treatment for future work.

  • Problem

    Application data and relationships need a tree-based model that supports both data access and analysis within one formal framework.

  • Method

    The model represents data as a set of labeled, directed trees and defines tree operations plus traversal and analytic queries using restriction, composition, pairing, and Cartesian product.

  • Results

    The model demonstrates inheritance, consistent relational databases defined over tree databases, and a user-friendly interface for accessing and analyzing relational data.

  • Takeaways & Limitations

    Tree databases can serve as an underlying semantic layer and support relational-data access and analysis through the same tree-based framework.

  • Takeaways & Limitations

    Efficient algorithms for tree restriction and a richer treatment of inheritance remain outside the paper’s scope and part of current work.

Abstract

from arXiv · show

We propose a novel database model whose basic structure is a labeled, directed tree with node identities. Intuitively, the root of the tree is seen as an object (or entity), the non-root nodes as attributes of the object and the semantics of each attribute is represented by the unique path leading from the root to the attribute. We define a tree database to be a set of such trees. The trees of the database can be combined to produce new trees using a set of operations on trees that we define in the paper. The query language of our model offers two types of queries, traversal queries and analytic queries. A query (whether traversal or analytic) is always defined over a tree, which is either a tree in the database or a tree derived from other trees using tree operations. The operations on trees and the query language are both defined using a simple functional algebra whose operations are: restriction of a function, composition of functions, pairing of functions and Cartesian product of sets. A distinctive feature of our model is that traversal queries and analytic queries are both defined within the same formal framework; and in fact, traversal queries serve as the building blocks for analytic queries. This is in sharp contrast to the relational model, where analytic queries are defined outside the relational algebra, in the form of SQL Group-by queries. Therefore our model supports data access and data analysis within the same formal framework. We demonstrate the expressive power of our model by showing: (a) how our model can support inheritance in a seamless manner, (b) how one can define consistent relational databases on top of a tree database - with the tree database playing the role of an underlying semantic layer and (c) how a tree database can be used as a user-friendly interface for accessing and analyzing relational data.

1 Introduction

The paper models application data and relationships as labeled, directed trees, then combines trees and uses a shared functional algebra for traversal and analytic queries. It demonstrates inheritance, relational definitions, and relational-data access through this framework.

  • Tree database model: A tree database represents application datasets and relationships as labeled, directed trees with node identities, where paths encode attribute semantics.Roots represent objects or entities; non-root nodes represent attributes, and edges represent total functions between datasets.
  • Tree database model: The example database separates invoice data from auxiliary branch, product, supplier, category, and pricing information across multiple trees.Tree composition combines trees at a unique shared node to create larger trees such as T5.
  • Functional algebra: The model combines sets and functions using Cartesian product, restriction, composition, and pairing to construct tree operations and queries.Pairing acts as a tuple constructor, while composition and pairing represent path and fork combinations.
  • Query language: Traversal queries are path expressions or pairings of same-source paths, returning either one target or a Cartesian product of targets.For example, pairing region and product paths returns a region-product pair for each invoice.
  • Query language: Analytic expressions combine grouping and measuring traversal queries with an aggregate operation, and analytic queries pair expressions sharing a source.Traversal queries therefore provide the building blocks for analytic queries within the same formal framework.
  • Contributions: The paper demonstrates expressive power through inheritance, consistent relational databases defined over trees, and a user-friendly interface for relational data access and analysis.The tree database can serve as an underlying semantic layer for relational databases.
  • Motivation: The model treats graph connections as readily available for navigation, contrasting with relational joins that match primary and foreign keys at query time.The introduction presents relational organization as rigid and graph-style relationships as first-class connections.

2 The Formal Definition of a Tree Database

This section formally defines tree databases, their instances, and a functional algebra for constructing expressions. It also introduces integrity constraints, including refinement constraints over expression information.

  • 2.1 Tree Database: Simple nodes have fixed domains, while composite nodes are Cartesian products of universe elements; every simple universe node appears in at least one database tree.A simple node appears at most once in any individual tree, and every tree node has an identity edge.
  • 2.1 Tree Database: A tree database is a finite set of finite directed labeled trees over a universe of simple and composite nodes.Each tree has one root, exactly one root-to-node path, distinct labels, and unordered successors.
  • 2.1 Tree Database: A database instance assigns each tree its current contents, with every node holding a finite nonempty set and every edge a total function between node instances.Identity edges interpret as identity functions, and the model assumes no nulls because edge functions are total.
  • 2.2 The functional algebra: The functional algebra provides Cartesian products with projections, restriction, pairing, and composition for combining sets and edges.Restriction narrows a function’s domain, pairing maps one source to a product target, and composition chains functions.
  • 2.2 The functional algebra: Function composition and pairing can be extended to multiple functions, while product of functions maps paired inputs to paired outputs.The product operation is derivable from projections, composition, and pairing.
  • 2.2 The functional algebra: Pairing followed by projection recovers either component function, establishing a basic algebraic relationship among the operations.The algebra’s operations are strongly connected and form the foundation for tree operations and the query language.
  • 2.3 Integrity constraints: The paper introduces expressions over trees and defines refinement constraints by comparing the information content of expressions with a common source.A refinement constraint requires one expression to contain finer information than another.

3 Operations on Trees

The paper defines tree operations that restrict, compose, and combine trees while preserving tree structure and total-function semantics. These operations support richer cross-tree queries, decomposition, and user-specific views.

  • Tree restriction: Restriction propagation terminates, is order-independent, and extends from paths and forks to arbitrary trees.For two-edge paths and forks, it reduces to restriction of function composition and function pairing.
  • Tree restriction: Tree restriction propagates a subset through paths and forks so the resulting tree preserves total functions.The propagation rules differ for roots, intermediate nodes, and leaves, using pullback and pushforward operations.
  • Tree composition: Tree composition combines trees sharing exactly one node, provided that node is the root of the second tree.The shared node is the link, and the union becomes a single composed tree.
  • Tree composition: Composition creates paths that traverse multiple trees, enriching the query language with cross-tree expressions.This enables expressions whose meaning exists only in the composed tree rather than either original tree alone.
  • Decomposition and views: Tree operations also support decomposition, allowing large trees to be split into focused subtrees for information-specific views.The algebra combines tree construction with database views tailored to individual users or user groups.
  • Decomposition and views: The algebra increases expressive power by creating larger trees, decomposing databases, and defining sophisticated user-tailored views.These capabilities support both richer traversal across trees and more focused access to database subsets.

4 Traversal Queries

Traversal queries navigate a database tree through composed path expressions and combine their results from a common source. Their answers are functional mappings that can be represented as relation-like tables.

  • Query definition: A traversal query is either one path expression or a pairing of path expressions sharing a source and having distinct targets.The queried tree may be stored directly in the database or derived through a tree expression.
  • Query definition: Path expressions compose the edges along a tree path, while a traversal answer pairs the resulting functions into a mapping from source to target products.For n paths, the answer maps the common source S to A1 × ... × An.
  • Query definition: Identity queries read a node’s contents by returning identity pairs for the values in that node.For example, the identity query on Sup yields supplier identifiers and can expose the current supplier set.
  • Query answers: Traversal-query answers can be displayed as tables whose rows use source values and columns use the query targets.Each cell contains the value produced by the corresponding path function.
  • Query answers: Traversal queries induce relation schemas, while functional dependencies remain the query-building primitives rather than merely relational constraints.The model therefore treats relations as derived from functional paths and pairings.
  • Query evaluation: Traversal queries can be evaluated directly, translated into another query engine, or rewritten through transformations.SQL translation is given as an example of indirect evaluation.

5 Analytic queries

Analytic queries extend traversal-based access with grouping, measuring, and aggregation over tree data. The model supports direct and recursive evaluation, richer query composition, and mixed traversal-analytic queries.

  • Analytic expressions: (b, q, sum) computes total delivered quantity by branch by grouping invoices with b and summing their q-values.The example evaluates branch-to-total quantities through grouping, measuring, and aggregation.
  • Analytic expressions: (dd, cc, avg) computes the average tweet character count by date by grouping tweets with dd and averaging cc-values.The same three-stage pattern applies to dates, tweet character counts, and the average aggregate.
  • Analytic expressions: Traversal-query answers can serve as grouping or measuring functions, substantially expanding analytic expressions beyond individual tree edges.This extension also enables combined rewriting rules and allows several analytic expressions with a common source to share partitioning.
  • Analytic expressions: An analytic expression is a triple (g, m, op) that groups with g, measures with m, and aggregates using op.The grouping and measuring queries share a source, while op applies to the target of m.
  • Evaluation and rewriting: Analytic expressions can be evaluated directly, translated to a query engine, optimized through shared computation, or rewritten into equivalent forms.Rewriting can avoid some relational joins; for example, a nested form of the regional total computation avoids joining separate tables during grouping.
  • Analytic queries and mixed queries: Analytic queries may pair analytic expressions with a common source, while mixed queries combine traversal and analytic expressions within the same functional-algebra framework.The query language can therefore combine data traversal with analysis in a principled way.

6 Applications

The paper demonstrates the model’s expressive power through inheritance, relational schemas with explicit attribute semantics, and tree databases as interfaces for relational data.

  • 6.1 Inheritance: The model supports inheritance by composing a child tree with a parent tree through a one-to-one Isa edge.The formal definition requires disjoint trees, matching root domains, attribute inclusion, and an identity-preserving Isa edge.
  • 6.1 Inheritance: Car and Boat can inherit shared attributes from Vehicle, while Amphi illustrates multiple inheritance and the associated diamond problem.The paper describes factoring out common attributes and adding Isa edges from Amphi to Car and Boat.
  • 6.1 Inheritance: Inheritance reduces redundancy by allowing a newly created tree to acquire information from an existing tree, but Isa edges should form one or more trees to avoid problems.The paper also presents update constraints as one way to address multiple-inheritance consistency.
  • 6.2 Defining relations over a tree database: The model can define consistent relational databases over tree databases, with query answers inducing relations that satisfy their dependencies.The tree database serves as an underlying semantic layer for the relational schema.
  • 6.2 Defining relations over a tree database: Each relational attribute is computed by a query expression whose semantics can be inspected, giving table attributes explicit meanings.Users see ordinary relation schemas, while clickable attributes can reveal the underlying expression used to compute their values.
  • 6.3 Tree databases as interfaces: A tree database can also act as a tailored interface to relational data by representing relation instances through node and edge projections.For an instance satisfying functional dependencies, node and edge instances are defined using projections of the relation.

7 Concluding remarks and perspectives

The paper positions tree databases as a functional alternative to graph and relational models, while identifying open work in query optimization, updates, inheritance, design, visualization, and system implementation.

  • Concluding contributions: Traversal and analytic queries share the same functional framework, and the model supports inheritance, relational databases built on tree semantics, and relational-data access and analysis.Queries can operate on database trees or trees derived through tree algebra operations.
  • Concluding contributions: The model extends a prior single-graph approach by using sets of trees and tree operations to provide more flexibility, including inheritance modeling.The paper claims this is a novel use of trees as the basic conceptual database structure.
  • Concluding contributions: Tree databases use functions as first-class elements forming trees, with relations treated as derived concepts.Each tree edge represents a total function and can be viewed as key-value pairs.
  • Open research directions: Complete rewriting systems are still needed to optimize the evaluation of traversal and analytic queries.The paper gives examples based on distributivity of composition over pairing and an analytic composition rule, but describes further work as necessary.
  • Open research directions: Updating tree databases remains an open problem because preserving function totality and integrity constraints may require propagating changes across many edges.The paper identifies constraint-preserving update algorithms as an important theme for further work.
  • Open research directions: Future work includes generalized webs of inherited trees, criteria-based tree database design, visualization, and a full-fledged management system.The proposed system would support storage, access, analysis, inheritance, relational-data interfaces, and visual exploration.
Loading 2609.03538v1…