Tree Databases

Technical Report

Tree Databases

arXiv:2609.03538v1 [cs.DB] 3 Sep 2026

Nicolas Spyratos

Abstract 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. Keywords Data model. Graph database model. Conceptual modeling. Query language. Data Analysis. Interface LISN Laboratory - University Paris-Saclay, CNRS, INRIA, France Affiliated Scienist, FORTH Institute of Computer Science, Greece nicolas.spyratos@lri.fr Acknowledgment: Work conducted while the author was visiting with the HCI Group at FORTH Institute of Computer Science, Greece (https://www.ics.forth.gr/)

1 Introduction The basic idea underlying this work is that the data sets of an application and their relationships can be modeled as a labeled, directed tree with node identities. Each node of the tree stores a data set of the application and each edge stores a total function (i.e. a set of key-value pairs) from its source node to its target node. A set of such trees is what we call a tree database (or simply database, hereafter). Intuitively, the root of a tree in the database 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. An example of a tree database is shown in Figure 1. It contains four trees, T1 , T2 , T3 , T4 , storing data concerning a distribution center (e.g. Walmart) which delivers products of various types in a number of branches. A delivery invoice contains the following data: the date of delivery, the branch in which the delivery took place, the type of product delivered (e.g. CocaLight) and the quantity (i.e. the number of units delivered of that type of product). There is a separate invoice for each type of product delivered, and the data on all invoices during the year are stored in T1 for yearly analyses and planning purposes. At any given moment during the year, the root Inv of T1 stores the set of all invoice identifiers so far (e.g. a set of integers) and the non-root nodes store the data appearing on the invoices (e.g. the node ‘Date’ stores the delivery dates appearing on the invoices, the node ‘Branch’ stores all identifiers of branches to which deliveries were made, and so on). As for the edges of T1 , each edge e : Inv → X stores a function (i.e. a set of key-value pairs) associating each invoice number i of Inv with the corresponding data e(i) stored in node X (e.g. the edge b : Inv → Branch associates each invoice number i of Inv with the branch identifier b(i) of Branch appearing on invoice i). By the way, to simplify our discussions, we shall use the terms ‘edge’ and ‘function’ interchangeably whenever no ambiguity is possible; and similarly we shall use interchangeably the terms ‘node’ and ‘set’. The remaining trees of our example database store auxiliary information needed for the analysis of the data stored in tree T1 . Thus T2 stores the region in which each branch is located; T3 stores the supplier and the category of each product type; and T4 stores the unit price of a product as a function of its supplier and its category. Now, the trees of a database can be combined to produce new trees using a set of operations on trees that we shall define in the paper. Such operations on trees create new trees and therefore new ways of accessing information. An example of tree operation is ‘tree composition’ defined as follows: a tree T is composable with tree T ′ if the root of T ′ is a node of T , and additionally, this is the only node shared by the two trees (this unique shared node is then called the ‘link’ of the comopsition). If T is composable with tree T ′ then their composition is denoted by T ′ ◦ T and the result is a new ‘larger’ tree. Figure 1 shows three examples of tree composition. First, T1 is composable with T2 (with the node Branch as the link) and the result of their composition is the tree T5 = T2 ◦ T1 as shown in the figure; similarly, T1 is composable with T3 (with the node P rod as the link) and the result of their composition is the tree T6 = T3 ◦T1 ; and finally, T6 is composable with T2 (with the node Branch as the link) and the result of their composition is the tree T7 = T2 ◦ T6 . By the way, we shall use the tree T7 in most of our examples throughout the paper. 2

A tree database with four trees

Branch

Prod

Region

Sup

Cat

b

p

r

s

c

Date

Inv q d

Qty

Branch

SupCat

T2

T3

T4

Region

r Branch

Prod

b

p

Date

Inv q d

Qty

u

Prod

T1

Examples of tree composition

UnitPrice

Sup Cat

Region

c

r Branch

Branch

s Prod

b

p

d

Inv q

Date

T5 =T2 OT1

T6 =T3 O T1

b Qty

Date

Sup

Cat

c s Prod

p

Inv q d

Qty

T7 =T2 O T6

Fig. 1 A tree database and examples of tree composition

Suppose now that T is a tree, which is either in the database or derived from those in the database as explained above. Then the question is: how can one extract information from T ? To this end, we need operations to combine nodes and edges in T so as to formulate queries. In our model we use one operation to combine sets, namely Cartesian product; and three operations on functions, namely restriction of a function to a subset of its domain of definition, composition of two functions, and pairing of two functions with the same source. We shall refer to these operations, collectively, as the functional algebra. Note that these are well known, elementary operations except possibly for pairing which is defined as follows: given two functions f : X → Y and g : X → Z with X as their common source, we call pairing of f and g, denoted as f ∧ g, the function defined by: f ∧ g : X → Y × Z such that (f ∧ g)(x) = (f (x), g(x)) for all x in X Note that pairing works as a tuple constructor. Indeed, if we view the elements of X as identifiers (or ‘keys’), then for each x in X the pairing constructs a tuple (x, f (x), g(x)) of x and the images of x under the input functions. Clearly, the definition of pairing can be extended to more than two functions with the same source in a straightforward manner. Also note that function composition and function pairing express the only two ways edges combine in a graph (i.e. either forming a path or a fork). Our model offers a query language comprising two types of queries, traversal queries and analytic queries. They are both defined using the functional algebra defined above. Given a tree T , a path expression over T is just the composition of the edges of a path of T ; and a traversal query over T is either a single path expression or the pairing of two or more path expressions having the same source. Referring to Figure 1, here are two examples of path expressions over the tree T7 : P E1 : r ◦ b, returning, for each i ∈ Inv, the region associated with i 3

P E2 : s ◦ p, returning, for each i ∈ Inv, the product associated with i By pairing these two path expressions we obtain the following traversal query: Q = ((r ◦b))∧(s◦p), returning for each i ∈ Inv, the region-product pair associated with i Note that the answer of a path expression is a function from the source of the path to its target; and the answer of a traversal query is a function from the common source of its path expressions to the Cartesian product of the targets of its path expressions. In order to simplify our discussions, we will often confuse a traversal query with its answer, which is a function. For example we will say ‘the function r ◦ b’ to mean the answer to query r ◦ b. Similarly, an analytic expression over a tree T is a triple of the form ⟨g, m, op⟩, where g and m are traversal queries over T with the same source (serving for grouping and measuring, respectively) and op is an aggregate operation applicable on the target of m; and an analytic query is either a single analytic expression or the pairing of two or more analytic expressions having the same source. Referring to Figure 1, here are two examples of analytic expressions over the tree T7 : AE1 : (b, q, sum) is an analytic expression returning the total quantity delivered by Branch AE2 : (b, q, avg) is an analytic expression returning the average quantity delivered by Branch To compute the answer to AE1 we proceed as follows: first, given a branch x, we group together all invoices that refer x (actually, this is the set S = b−1 (x)); then we apply the function q to every invoice i in S to find the quantity corresponding to i; and finally, we sum up the quantities for all i ∈ S to find the total quantity for branch x (and similarly for computing the answer of AE2 ). Note that the answer to an analytic expression is a function from the target of the grouping query b to the target of the aggregate operation (and as this target is a node not appearing in the tree, the user is asked to name it (e.g. BranchT ot in our example). The answer to AE2 is computed in a similar manner returning the average quantity delivered by branch, say BranchAvg. Next, by pairing these two analytic expressions we obtain the following analytic query: Q′ = (b, q, sum) ∧ (b, q, avg), returning, for each i ∈ Inv, the pair (BranchT ot, BranchAvg) associated with i Note that the answer of a an analytic expression (g, m, op) is a function from the target of g to the target of op; and the answer of an analytic query is a function from the common source of its analytic expressions to the Cartesian product of the targets of its analytic expressions. Roughly speaking, traversal queries parallel relational algebra queries, whereas analytic queries parallel SQL Group-by queries. 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 4

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. A fundamental aspect of our model is that data is stored in the form of trees that is data is not stored sequentially (i.e., not in a linear order). Instead, data is organized across multiple levels, forming a hierarchical structure. Graph data models in general have gained considerable attention in the last few decades since they use nodes, relationships between nodes and key-value properties instead of tables to represent information [2][6]. Therefore they are typically substantially faster for associative data sets. While other database models compute relationships expensively at query time, a graph database stores connections as first-class citizens, readily available for any ‘join-like’ navigation operation. Any purposeful query over a graph database can be easily answered, as data is easily accessed using traversals. A traversal is how you query a graph, navigating from starting nodes to related nodes according to an algorithm [1]. Graph-based models present a high degree of flexibility and are able to capture complex non-linear relationships. In a graph data model relationships are of equal importance to the data itself. This means you are not required to infer connections between entities using special properties such as foreign keys or out-of-band processing like map-reduce. In contrast, relational databases store highly-structured data in tables with predetermined columns and rows of specific types of information. Due to the rigidity of their organization, relational databases require developers and applications to strictly structure the data used in their applications. In relational databases, references to other rows and tables are indicated by referring to primary key attributes via foreign key columns; joins are computed at query time by matching primary and foreign keys of all rows in the connected tables. These operations are compute-heavy and memory-intensive, and have an exponential cost; and when many-to-many relationships occur in the model, you must introduce a join table (or associative entity table) that holds foreign keys of the participating tables, further increasing join operation costs. Graph databases have become a cornerstone of modern data management, enabling complex queries, pattern discovery, and knowledge inference in highly connected datasets [6]. There is a substantial body of literature around the use of graphs in computer science, including several tools to support graph management by means of digital technology, as well as data models and query languages based on graphs. The reader is referred to [2][3][7][8][23] for a comprehensive analysis of graph-based approaches to data and knowledge management, emphasizing the relation between graph databases and knowledge graphs, and including an extensive bibliography. A rather detailed discussion on the power and limitations of graph databases can be found in [13]. Moreover, several graph database systems have appeared in recent years such as Neo4j Graph Database, ArangoDB, Amazon Neptune, Dgraph and a host of others1 . A comparison of the main graph database models can be found in [5].

1

https://www.g2.com/categories/graph-databases (retrieved on March 4, 2026)

5

2 The Formal Definition of a Tree Database In this section we give formal definitions of the basic concepts seen informally in the introduction, namely ‘tree database’ and ‘functional algebra’; and we also introduce the important concept of integrity constraint over a tree database.

2.1 Tree Database To define formally the concept of tree database we need some auxiliary concepts and notation. First, we call universe any finite abstract set over which we define ‘nodes’. A node over U is either an element of U (simple node) or the Cartesian product of two or more elements of U (composite node or product node). We assume that each simple node A over U is associated with a fixed set of values, called the domain of A and denoted by dom(A). The domain of a node may be a finite or an infinite set of values (e.g. the set of the two boolean values or the set of integers can be node domains). As for a product node, its domain is defined to be the product of the domains of its factors; for example, for A, B in U , dom(A×B) = dom(A)×dom(B). Second, throughout the paper, by ‘tree over U ’ we mean a finite, directed and labeled graph whose nodes are nodes over U such that: (a) there is a distinguished node with no incoming edge called the root, (b) there is exactly one path from the root to every non-root node and (c) all edges and all nodes have distinct labels. Moreover, we call leaf any node with no outgoing edge and we assume that the set of successors of every node is unordered. Definition 1 (Tree Database) Let U be a universe. A tree database over U is a finite set D = {T1 , . . . , Tn } of trees over U such that: 1. in each tree, the root can be a simple or a composite node over U , while each non-root node is a simple node 2. each simple node X over U appears at most once in a given tree Ti (but X may appear in two or more different trees) 3. every simple node over U must appear in at least one tree (therefore all simple nodes of U appear in the database that is U has no superfluous symbols) 4. every tree node X is associated with an edge ιX : X → X from X to X called the identity edge of X Note that, although a node can appear at most once in a given database tree (item 2 of the above definition), a node may appear in two or more database trees. In other words, all nodes of U appear in the database but each node can appear at most once in a given tree (either as a simple node or as a component of a product node); and as a consequence no edge can appear in two different trees. Now, as we explained informally in the introduction, the nodes and edges of a database tree represent the datasets of an application and their relationships; and these datasets and relationships may change with time. The contents of a database tree T , at any given time t, is what we call the instance of T at time t; and the set of all tree instances at time t is what we call the database instance at time t. 6

Definition 2 (Tree Instance) Let U be a universe, D = {T1 , . . . , Tn } a database over U and T a tree in D. An instance of T is a function δT that associates the nodes and edges of T with values such that: – for each node N of T , δT (N ) is a finite nonempty subset of dom(N ) – for each edge f : X → Y of T , δT (f ) is a total function from δT (X) to δT (Y ) – for each node N of T , δT (ιN ) is the identity function on δT (N ) Moreover, an instance of D at time t is defined to be the set δ = {δT1 , . . . , δTn } of instances of all trees of D at time t. An important remark is in order here regarding the above definition. Although the domain of a node can be an infinite set, the instance of a node (whether simple or composite) is always a finite nonempty set of values from its domain; and as a consequence, the instance of an edge f : X → Y is always a finite nonempty function. Moreover, as we assume that δT (f ) is a total function, this means that δT (f ) is defined on every value of δ(X), which means that we assume no nulls. Another important remark is that, as mentioned earlier, a node X may be shared by two or more different trees of the database, say T and T ′ . In this case, X may be associated with different instances in the two trees that is we may have δT (X) ̸= δT ′ (X). For example, in Figure 1, the node Branch is shared by the trees T1 and T2 and we have, in general, δT1 (Branch) ̸= δT2 (Branch). This is natural as δT1 (Branch) is the set of all branches to which products have been delivered, whereas δT2 (Branch) is the set of all branches of the distribution company (i.e. including those branches to which no deliveries have been made). In the rest of the paper, in order to simplify our discussions, we shall not make the distinction between a node and its instance or between an edge and its instance unless necessary. Indeed, more often than not, the intended meaning of terms will be evident from the way these terms are used. For example, if e is an edge of a tree T and we write e−1 this will clearly mean δT (e)−1 ; and similarly, if f : X → Y and g : Y → Z are two edges and we write g ◦ f this will clearly mean the composition f1

f2

δT (g) ◦ δT (f ); or if P : X −→ Y −→ Z is a path and we write P (x), where x in X, this will clearly mean (δT (f2 ) ◦ δT (f1 ))(x)); and similarly for a path of n edges f1 , f2 , . . . , fn , n ≥ 1.

2.2 The functional algebra In order to access the data stored in a tree database users need operations to combine nodes and edges in a tree so as to formulate queries. In our model, as mentioned in the introduction, we use four well known, elementary operations that we call, collectively, the functional algebra. Definition 3 (Functional algebra) Given a tree T , the functional algebra of T consists of the following operations: – Cartesian product of sets (and its accompanying projection functions). – Restriction: Given a function f : X → Y and a subset S of X, the restriction of f to S, denoted by f /S, is the function f /S : S → Y defined by: (f /S)(x) = f (x), for all x in S. 7

– Pairing: Given two functions f : X → Y and g : X → Z with common source, their pairing, denoted by f ∧ g, is the function f ∧ g : X → Y × Z such that: (f ∧ g)(x) = (f (x), g(x)) for all x in X. – Composition: Given two functions f : X → Y and g : Y → Z, their composition, denoted by g ◦ f is the function g ◦ f : X → Z defined by: (g ◦ f )(x) = g(f (x)) for all x in X. Note that the operations of composition and pairing can be defined for more than two functions in the obvious way. An important remark concerning the functional algebra is that its four operations are strongly connected to each other as stated in the following lemma. Its proof is a direct consequence from the definitions of the operations. Lemma 1 Let X, Y, Z be three sets, and let f : X → Y and g : X → Z be two functions with common source. Then the following hold: πY ◦ (f ∧ g) = f and πZ ◦ (f ∧ g) = g (where πY and πZ denote the projections of Y × Z over Y and Z, respectively). There is an interesting ‘derived’ operation, called ‘product of functions’, defined as follows: Definition 4 (Product of functions) Let f : X → Y and g : X ′ → Y ′ be two functions. The product of f and g is the function f × g : X × X ′ → Y × Y ′ defined by: (f × g)(x, x′ ) = (f (x), g(x′ )) for all (x, x′ ) in X × X ′ . Clearly, the above definition of product can be extended to more than two functions in a straightforward manner. The following lemma states how the product can be derived from operations of the functional algebra, namely using projection, composition and pairing. Its proof follows immediately from the definitions. Lemma 2 Let f : X → Y and g : X ′ → Y ′ be two functions. Then we have: f × g = (f ◦ πX ) ∧ (g ◦ πX ′ ). We now introduce the basic concept of ‘expression’ over a database tree and its evaluation in a database instance. Definition 5 (Expression over a Tree) Let D be a database and let T be a tree in D. An expression over T is either an edge of T or a well formed expression E whose operands are edges of T and whose operations are among those of the functional algebra. Moreover, given an instance δT , the value of E in δT , denoted as V alE (δT ), is obtained by (a) replacing the nodes and edges of E with the values assigned to them by δT and (b) performing the operations. Note that this definition is in the spirit of a similar definition in the relational model, namely the definition of relational expression over a database schema [20]. Indeed, if S is a database schema and D a relational database over S then a relational expression over S is a well formed expression E whose operands are relation schemas of S and whose operations are among those of the relational algebra. Moreover, the value of E in D is obtained by replacing the relation schemas of E with the relations assigned to them by D and performing the operations. 8

It is important to note that every expression E has a source and a target that can be defined recursively based on the sources and targets of the edges appearing in E. For example, referring to tree T7 of Figure 1, if E1 = r ◦ b then source(E1 ) = Inv and target(E1 ) = Region; and similarly, if E2 = (r ◦ b) ∧ p then source(E2 ) = Inv and target(E2 ) = Region × P roduct. Clearly, the value of an expression is always a function from the source of the expression to its target. A particular kind of expression over a tree, called ‘path expression’ will be frequently used in the rest of this paper. Intuitively, a path expression is the composition of edges along a path. Definition 6 (Path expression) Let T be a database tree. A path expression over T is a well formed expression P E whose operands are the edges of a path of T and whose only operation is composition. Moreover, given an instance δT , the value of P E is defined to be the composition of the functions assigned to the edges of P E by δT (therefore, a path expression with source S and target A evaluates to a function from S to A). Note that, as there is at most one path between any two nodes of a tree, every path is associated to one and only one path expression, namely the composition of its edges; and conversely, every path expression is associated to one and only one path (namely, the sequence of its operands in reverse order). We end this section with an interesting observation relating the functional algebra with functional dependency theory, and in particular with Armstrong’s axioms for functional dependencies in relational databases [4][10]. Let T be a database tree, δT an instance of T and f : X → Y a function, where X, Y are nodes of T . We shall say that δT implies f if f is the value of an expression over T , for all δT . Then the question is: what is the set of all functions that are ‘implied’ by δT ? The following lemma gives a first answer. Lemma 3 Let δT be an instance of a database tree T . Then the following hold: – If X is a simple node then δT implies the function ιX ; and if X is a product node and Y a sub-product of X then δT implies the function πY : X → Y . – If two functions f : X → Y and g : Y → Z are implied by δT then g◦f : X → Z is also implied by δT . – If the function f : X → Y is implied by δT and Z is a node of T then f × ιZ : X × Z → Y × Z is also implied by δT . Proof The first implication follows from the definition of Cartesian product of sets; the second follows by applying composition of functions; and the third follows by taking the product of f with the identity function of Z. We recall here that the properties expressed in the above lemma correspond to Armstrong’s axioms, or implication rules for functional dependencies in relational databases (namely, reflexivity, transitivity and augmentation, respectively) [4][10]). However, the above lemma shows only the ‘soundness’ of these implication rules, therefore the accompanying question is the following: is there a ‘derivation’ system showing completeness? Answering this kind of questions lies outside the scope of the present paper and it is part of our current work. We end this section by summarizing a few basic properties of the operations of the functional algebra (whose proofs follow easily from the definitions): 9

1. Strictly speaking, the Cartesian product is neither associative nor commutative. However, there are always natural bijections between the various forms of a Cartesian product, for example, between A × B × C, (A × B) × C and A × (B × C), or between A × B and B × A, and so on. Therefore, in our setting, we shall assume that the Cartesian product is both associative and commutative. As a consequence of this assumption, pairing is also associative and commutative. 2. Composition is an associative operation, therefore we can group together its component functions as it is more convenient for our purposes. For example, (h ◦ s) ◦ p = h ◦ (s ◦ p). 3. Composition distributes over pairing. For example referring to tree T7 of Figure 1 we have (s ∧ c) ◦ p = (s ◦ p) ∧ (c ◦ p). 4. For any functions f : X → Y and g : Y → Z we have: if S ⊆ X then g ◦ (f /S) = (g ◦ f )/S 5. For any functions f : X → Y and g : X → Z we have: if S ⊆ X then (f ∧ g)/S = (f /S) ∧ (g/S) As a last remark, the functional algebra introduced in this section constitutes the foundation of our model and the basic tool for defining the tree operations and the query language that we shall see in the following sections.

2.3 Integrity constraints Integrity constraints are properties that the database must satisfy so that the quality of information is maintained. Examples of such constraints from relational databases are domain constraints, key constraints, or referential constraints [20]. Integrity constraints ensure that changes in the database are performed in such a way that data integrity is not affected. In our model we distinguish two kinds of constraints, namely those imposed by the definition of database over a universe U , and those that may be imposed by the application. There are two constraints imposed by our definition of database, namely (a) every instance of a database tree T must associate each node X with a finite subset δT (X) of dom(X) and (b) each edge f : X → Y with a total function δT (f ) : δT (X) → δT (Y ) (meaning that no nulls are allowed in the database). Incidentally, the second constraint implies a referential constraint similar to referential constraints in the relational model. Indeed as each edge e : X → Y of a tree is interpreted as a total function, every object of δT (X) must ‘refer’ to an object of δT (Y ) (i.e. no ‘dangling pointers’). As for constraints that may be imposed on a database by the application, we consider two kinds in this paper: (a) an inter-tree constraint that we call inclusion constraint and (b) an intra-tree constraint that we call refinement constraint or dependency constraint. An inclusion constraint applies to two trees, T and T ′ that share a node, say X, and expresses that we must have that δT (X) ⊆ δT ′ (X), in every database instance. We denote this by δT (X) ⊑ δT ′ (X). For example, in the database of Figure 1, where the trees T1 and T2 share the node P rod we may impose the inclusion constraint δT1 (P rod) ⊑ δT2 (P rod) expressing that the set of products delivered are among those available at the company. 10

A refinement constraint on the other hand states that, given a tree T , an expression E must contain finer information than an expression E ′ with the same source as E. It is an information-theoretic constraint referring to the information content of expressions having the same source. To understand the definition of this constraint, recall that the value (instance) of an expression E over a tree is a total function and therefore its information content can be defined as the partition pE that this function induces on its domain of definition. It follows that we can compare two expressions having the same source using the ordering of the partitions they induce on their common source. Definition 7 (Refinement constraint) Let T be a tree and let E, E ′ be expressions over T having the same source. Then E is said to be finer than or equal to E ′ , denoted by E ≤ E ′ , if pE ≤ pE ′ . Moreover, if E ≤ E ′ then we say that E determines E ′ , denoted by E → E ′ . The following lemma states an interesting property of refinement constraints also showing their relationship to functional dependencies of the relational model. Lemma 4 Let T be a tree and let f : X → Y and g : X → Z be two edges of T having the same source. Then f ≤ g if and only if there is a function h : Y → Z such that h ◦ f = g. Moreover, the function h is unique. Proof Suppose that pf ≤ pg , and define h(y) = g(f −1 (y)) for every y in the range of f (i.e. in the set of values of f ). Then h is a well defined function from Y to Z. Indeed, as pf ≤ pg , every block of pf is contained in a block of pg and therefore g(f −1 (y)) is a single value in the range of g. It follows that h : range(f ) → Z is a well defined function and that h ◦ f = g. In the opposite direction, suppose that h ◦ f = g. It follows that ph◦f = pg and as pf ≤ ph◦f we have that pf ≤ pg . Now, suppose that there is a function h′ : Y → Z such that h ◦ f = g ′ . If h′ ̸= h then there is y ∈ range(f ) such that h′ (y) ̸= h(y). It follows that there is x ∈ X such that f (x) = y, therefore h′ (f (x)) ̸= h(f (x)), that is g(x) ̸= g(x) which is impossible as g is a function. Clearly the proof remains the same if f, g and h in the above lemma are values of expressions over T (since the value of an expression over T is a function). 2 To see an example of refinement constraint refer to Figure 1 and consider the edges c and s of tree T3 that associates each product with a category and a supplier. If we declare the refinement constraint c ≤ s this means that each product category must be provided by one and only one supplier. In other words, a refinement constraint works in much the same way as a functional dependency in the relational model. Let’s see a simple example illustrating this point. Consider the following tree relating employees, departments and managers in some enterprise: g

f

T : M gr ← − Emp − → Dep If we impose the refinement constraint f ≤ g then the above lemma implies that there must be a function h : Dep → M gr which means that a department must have one and only one manager. We shall not discuss constraints any further in this paper. Our intention in this section was to give a brief account of the kind of constraints that we can use in our model. A detailed discussion of constraints and their inference mechanism lies 11

outside the scope of the present paper and it is part of our current work. We have seen so far the basic concepts of our model, namely the concepts of tree database, functional algebra and the basic constraints that can be imposed on a tree database. In the following two sections we define the two kinds of queries offered by the query language of our model, namely traversal queries and analytic queries. We end this section by reminding the reader that, in order to simplify our discussions, we often confuse syntax and semantics, when no ambiguity is possible. Here are some examples, referring to tree T7 of Figure 1: if we say ‘the function b’ this means the function δT7 (b); if we say ‘the function r ◦ b’ this will mean the function δT7 (r) ◦ δT7 (b); if we write b−1 this will mean (δT7 (b))−1 and so on. 3 Operations on Trees In this section, we introduce operations for defining new trees from old. To do so, we ‘upgrade’ the operations of the functional algebra to similar operations on trees. Before defining our operations on trees, we recall a few facts about graphs which also apply to trees. In particular, we recall the definition of a directed labeled graph as a set of triples. Seen as syntactic objects, the edges of a directed labeled graph are triples of the form ⟨source, label, target⟩, therefore two edges are different if they differ in at least one component of this triple. This implies, in particular, that two edges can have the same label if they have different sources and/or different targets. Moreover, two different edges can have the same source and the same target provided that they have different labels; we call such edges parallel edges and this definition extends to paths, which we call parallel paths. Following this abstract view, a set of triples can be a disconnected graph, with or without isolated nodes, with or without cycles, with or without parallel paths; and it can be a tree, a path, a fork and so on. Moreover a singleton {⟨X, ιX , X⟩} is a graph called a trivial graph and the empty set of triples is also a graph called the empty graph. Finally, the result of any set theoretic operation on graphs (seen as sets of triples) is also a graph. Motivated by these remarks, given two graphs G and G ′ , we shall denote by G ⊔ G ′ the union of their sets of triples that is: G ⊔ G ′ = T riples(G) ∪ T riples(G ′ ).

3.1 Tree restriction Before we define the operation of tree restriction we recall that, in our model, the nodes of a database tree represent datasets and the edges represent total functions; and that the edges in a tree are arranged either in a path or in a fork of paths (i.e. a set of paths having the same source). Now, the question is: if a node in a path or in a fork is restricted to one of its subsets, how can the restriction be ‘propagated’ to the remaining nodes and edges such as function totality is maintained? To answer this question, let T be a tree, P a path in T and F a fork of two paths in T defined as follows: f g P :X− →Y − →Z 12

g1

f1

f2

g2

F : Z1 ←− Y1 ←− X −→ Y2 −→ Z2 We shall answer the question separately, first for P and then for F . Regarding P , we distinguish three cases of restriction propagation as follows: 1. Restriction of the root If V ⊆ X then replace X by V , Y by f (V ), f by f /V and g by g/f (V ) We refer to this action as pushing V to Z along P 2. Restriction of the target If V ⊆ Z then replace Z by V , Y by g −1 (V ), X by f −1 (g −1 (V )), f by f /f −1 (g −1 (V )) and g by g/g −1 (V ) We refer to this action as pulling V back to X along P 3. Restriction of an intermediate node If V ⊆ Y then replace Y by V , X by f −1 (V ), Z by g(V ), f by f /f −1 (V ) and g by g/V Note that, in this case, the result of restriction is independent of the order in which pulling back and pushing forward are performed. Regarding F , let’s call P1 the path from X to Z1 and P2 the path from X to Z2 . We distinguish four cases as follows: 1. Restriction of the source If V ⊆ X then replace X by V , push V to Z1 along P1 and to Z2 along P2 2. Restriction of a target (say Z1 ) If V ⊆ Z1 then replace Z1 by V , pull V back to X along P1 , push f1−1 (g1−1 (V )) to Z2 along P2 3. Restriction of an intermediate node (say Y1 ) If V1 ⊆ Y1 then replace Y1 by V1 ; replace g1 by g1 /V1 ; pull V1 to X along f1 ; push f1−1 (V1 )) to Z2 along P2 4. Restriction of both targets If V1 ⊆ Z1 and V2 ⊆ Y2 then (a) pull V1 back to X along P1 and let H1 ⊆ X be the result of this pullback (b) pull V2 back to X along P2 and let H2 ⊆ X be the result of this pullback (c) push H1 ∩ H2 to Z1 along P1 and push H1 ∩ H2 to Z2 along P2 Note that, in this case, as set intersection is commutative, the result of restriction is independent of the order in which the pullbacks in (a) and (b) above are performed. A few remarks are in order here: (a) restriction propagation as described above can be extended in a straightforward manner to a path with more than two edges and to a fork with more than two paths - and this means that it can be extended to a tree; (b) restriction propagation always terminates and the result is independent of the order in which the actions of pulling and pushing are performed; (c) the functions represented by the edges remain total in the result of restriction propagation; (d) if the path P consists of only two edges and we restrict the source then restriction propagation reduces to restriction of function composition; and if a fork F consists of only two edges and we restrict the source then restriction propagation reduces to the restriction of a function pairing. Definition 8 (Tree restriction) Let T be a database tree with root ρ, let X be a node of T and let V be a subset of X. Then the restriction of T to V , denoted by TV ⊆X is the tree defined as follows: 13

1. if X is the root of T (i.e. if X = ρ) then for every leaf L of T , push V to L along the unique path from ρ to L 2. if X is an intermediate node of T , P the unique path from ρ to X and W the result of pulling V back to ρ along P then push W to every leaf L along the unique path from ρ to L 3. if X is a leaf of T , say L, and P the unique path from ρ to L then pull V back to ρ along P and if W is the result of this pulling back then push W to every leaf L Clearly when applying the above definition there are redundant occurrences of pulling back and pushing forward. For example, suppose X is an intermediate node (item 2 in the above definition) and let P be the unique path from ρ to X. Suppose now that X is the common source of two paths P1 and P2 leading from X to leaves L1 and L2 , respectively. Then pushing W from ρ to leaves L1 and L2 actually pushes W to X along P twice (in general, as many times as there are leaves that are descendants of X). Hence the need for efficient algorithms for performing tree restriction. However, designing such algorithms lies outside the scope of the present paper and it is part of our current research.

3.2 Tree composition Intuitively, given two database trees T and T ′ , we would like to ‘combine’ them so as to create a ‘larger’ tree thus enabling the extraction of more complex information from the database. In view of our previous discussion, the obvious candidate for doing so is the union T ⊔ T ′ . Unfortunately this union is not always a tree, as it may create cycles and/or parallel paths, disconnected components and so on. Therefore we must impose conditions to ensure that this union is indeed a tree. Definition 9 (Composability) T is called composable with T ′ if T and T ′ share only one node, and moreover this node is the root of T ′ . We call this unique shared node the link (of T to T ′ ). It is important to note that the link can be any node of T that is, it can be a leaf, the root or an intermediate node of T . The following lemma states how two trees that are composable can be combined so as to return a single tree. Lemma 5 Let T , T ′ be two trees in a database. If T is composable with T ′ then T ⊔ T ′ is a tree called the composition of T with T ′ , denoted by T ′ ◦ T . Proof Let ρ be the root of T . As T is a tree, there is a unique path from ρ to every node of T , and in particular to the link node, say X. Now, as X is the root of T ′ , there is a unique path from X to every node of T ′ , and as X is the only node shared by T and T ′ , it follows that there is a unique path from ρ to every node of T ′ . More precisely, let P be the unique path in T from ρ to X, let N be a node of T ′ and let P ′ be the unique path in T ′ from X to N . Then the ‘concatenation’ of P and P ′ is the unique path from ρ to N . It follows that there is a unique path from ρ to every node of T and to every node of T ′ , therefore T ′ ◦ T is a tree whose root is that of T .

14

Hereafter, motivated by the proof of the above lemma, if T is composable with T ′ , we shall call composition path the unique path that exists from the root ρ of T to the link X (i.e. to the root ρ′ of T ′ ). Note that the composition of two functions, f

g

seen as separate one-edge trees, T : X − → Y and T ′ : Y − → Z, is a special case of tree composition with the link being the node Y and f being the composition path. Therefore the use of the symbol ‘◦’ to denote the composition of two trees should create no confusion. Similarly, the pairing of two functions with the same f

g

source, seen as separate trees, T : Y ← − X and T ′ : X − → Z is a special case of tree composition with the link being the node X and the identity path ιX being the composition path. Now, if two trees T and T ′ are in the same database and T is composable with T ′ then the question is: how to define the instance of T ◦ T ′ in terms of the instances of T and T ′ (so as to be able to answer queries against their composition). Our approach to answer this question is motivated by the example of composition of f

g

two total functions seen as two separate trees, T : X − → Y and T ′ : Y − → Z, and residing in the same database. Then T is composable with T ′ and the link is Y . Now, in general, we have δT (Y ) ̸= δT ′ (Y ), therefore we can distinguish three possible cases for performing the composition T ′ ◦ T (i.e. g ◦ f in our example), while maintaining the totality of the functions f and g: – The two instances, δT (Y ) and δT ′ (Y ) have an empty intersection, in which case the result of the composition g ◦ f is the empty tree – The two instances are equal, in which case we have the usual composition of two total functions – The two instances are neither disjoint nor equal. In this case, objects lying outside the intersection I = δT (Y ) ∩ δT ′ (Y ) are not ‘useful’ (as they don’t participate in the composition) so we can ‘forget’ them. Therefore, we can restrict our attention to I, and as I is a restriction of Y , we can pull it back to X along f and push it forward to Z along g to obtain the ‘useful part’ of the composition that is g ′ ◦ f ′ , where f ′ = f /f −1 (I) and g ′ = g/I are total functions. The important thing to note here is that if the database contains only the two trees T and T ′ of our previous example then the path expression g ◦ f has a meaning only if expressed against the tree T ′ ◦ T (and its value will be g ′ ◦ f ′ ). In other words, as we mentioned earlier, composition of trees creates paths that traverse two or more trees, thus enriching the query language that we shall see in the following sections. Let us now add one more edge to the tree T of our example that is let us consider h

f

g

the following two trees: T : W ← − X − → Y and T ′ : Y − → Z. Clearly the two trees remain composable, and in order to find the instance δT ◦T ′ in terms of the instances of T and T ′ , we can follow the same reasoning as above, adding one more step to restriction propagation, namely: replace h by h′ = h/f −1 (I). We summarize our discussion so far in the following definition of instance of tree composition. Definition 10 (Instance of Tree Composition) Let T , T ′ be two trees residing in the same database with roots ρ and ρ′ , and instances δT and δT ′ , respec15

tively. If T is composable with T ′ with link X then the instance δT ◦T ′ is defined as follows: Step 1 If I = δT (X) ∩ δT ′ (ρ′ ) = ∅ then δT ◦T ′ = ∅ else Step 2 Pull I backwards from X to ρ along the composition path and let V be the resulting restriction of δT (ρ). Then Step 2.1 Push δT (ρ) from ρ to each leaf L of T along the unique path from ρ to L Step 2.2 Push I from ρ′ to each leaf L′ of T ′ along the unique path from ρ′ to L′ What this definition actually says is the following: to find the instance δT ◦T ′ , first restrict δT with I ⊆ δT (X) (this is step 2.1) then restrict δT ′ with I ⊆ δT ′ (ρ′ ) (this is step 2.2). Clearly, if in step 1 I = δT (X) = δT ′ (X) then no restriction propagation is needed that is the nodes and edges of δT ◦T ′ keep the values they have in δT and δT′ . Note that pulling back and pushing forward in the above definition maintains the constraint of function totality for each edge of T ′ ◦ T as required by our definition of tree instance (see Definition 2). As a last remark regarding tree composition, this operation is clearly non-commutative and non-associative, in general. However, in particular cases, composition can be commutative and/or associative. For example, when T , T ′ share only their root then tree composition is commutative; and if moreover we have three trees, T , T ′ , T ′′ sharing only their root, then composition is also associative.

3.3 Cartesian product of trees We have seen that tree composition combines two trees that share a unique node (the link) so as to create a larger tree. On the other hand, in a tree database, we may be interested in a collection of trees which, although pairwise disjoint (i.e. no node in common) they contain related information. For instance, a tree database may contain a tree TEmp describing characteristics of employees and a tree TT rans describing characteristics of the company’s transportation means. Although these two trees may share no node, we might want to be able to refer to their pair as subtrees of a larger tree, say TAdmin , whose root serves as the entry point for the pair of trees. The Cartesian product serves precisely this purpose. This operation ‘puts together’ two disjoint trees and returns a tree having the input trees as subtrees. It is a derived operation defined in terms of tree composition and Cartesian product of sets. Definition 11 Let T and T ′ be two disjoint trees with roots X and Y , respecπ πY tively. Let TX : X × Y −−X → X and TY : X × Y −−→ Y be the projections of X × Y over X and Y , respectively, seen as separate trees (with one edge each). Then the product of T and T ′ is a tree denoted by T × T ′ and defined by: T × T ′ = (TX ◦ T ) ◦ (TY ◦ T ′ ). The current instance of T × T ′ is computed from the current instances of X × Y , πX , πY , TX and TY , by applying the operations used in the definition of T × T ′ . To see that T × T ′ is well defined, observe that TX is composable with T (with link X), TY is composable with T ′ (with link Y ) and (TX ◦ T ) is composable with (TY ◦ T ′ ) (with link X × Y ). The definition of T × T ′ is depicted in Figure 2. Note that the Cartesian product of trees is a commutative and transitive operation over mutually disjoint trees. Also note that the Cartesian product of trees can be 16

extended to non-disjoint trees if we prefix each node shared by the two trees by f

the name of the tree to which it belongs. For example, the trees T : X − → Y and g T′ :Y − → Z are not disjoint as they share the node Y . However, if we replace Y by two nodes, T .Y and T ′ .Y such that dom(T .Y ) = dom(T ′ .Y ) then the two trees become disjoint and we can take their Cartesian product whose root is (X × T ′ .Y ) with X → T .Y and T ′ .Y → Z as its sub-trees. This ‘renaming’ technique is wellknown in relational databases, where it is used for renaming attributes which are shared by two relation schemas (in particular, when defining ‘joins’ [19]). As a last remark, the product f × g of two functions f : X → Y and g : X ′ → Y ′ that we have seen earlier (see Section 2.2, Lemma 2) is a special case of the Cartesian product of trees, as stated in the following lemma. f

Lemma 6 Let f : X → Y and g : X ′ → Y ′ be two functions and let T : X − →Y g π and T ′ : X ′ − → Y ′ be the functions f and g seen as trees. Let TX : X × X ′ −−X → X, πX ′ TX ′ : X × X ′ −− → X ′ be the projections of X × X ′ also seen as trees. Then we have: (T ◦ TX ) ◦ (T ′ ◦ TX ′ ) is the product function f × g seen as a tree. Proof First observe that TX is composable with T (with link X) and TX ′ is composable with T ′ (with link X ′ ). Moreover, T ◦ TX is composable with T ′ ◦ TX ′ (with link X × X ′ ). As X × X ′ is the common root of T ◦ TX and T ′ ◦ TX ′ , it follows that (T ◦ TX ) ◦ (T ′ ◦ TX ′ ) = (T ◦ TX ) ∧ (T ′ ◦ TX ′ ) which is the product function f × g seen as a tree.

3.4 Tree projection Restriction, composition and Cartesian product are tree operations each taking as input one or more trees and creating a new tree. In the opposite direction, it is sometimes desirable to be able to ‘decompose’ a given tree into two composable subtrees such that their composition reconstructs the original tree. For example when designing a tree database one may want to ‘experiment’ different ways of configuring the information by either composing two or more trees in order to create a larger tree or by decomposing a tree into smaller subtrees so that the information in the database is more focused and easier to grasp. To this end we need an operation that takes as input a tree T and a node X of T and returns a subtree of T rooted at X. Hence the following definition of ‘projection’ of a tree onto one of its nodes. Definition 12 (Tree projection) Let T be a tree and X a node of T . Then the projection of T on X, denoted by πX (T ), is the subtree of T defined as follows: – the set of nodes consists of X and all descendants of X in T – the set of edges consists of all edges of T connecting nodes in the following set: {X} ∪ {Y /Y is a descendant of X in T } To see that πX (T ) is indeed a subtree of T it is sufficient to note that (a) there is a unique path from the root of T to every node of πX (T ) (because of item 1 above), (b) there is a unique path from the root of T to X and (c) every node of X is a descendant of X in T . Therefore there is a unique path from X to every node of πX (T ). Note that if X is the root of TX then πX (T ) = T and if X is 17

T

(a)

X

Y

…

…

Y

X T’

Z

T

Y

X

Y

…

…

Y

TT’

complement of X(T)

Z

S

S

(b)

XY

V

X

W

X

X

V

W

X(T) U

U

Fig. 2 (a) Product of trees (b) Projection of a tree on a node X

a leaf of T then πX (T ) is a trivial subtree (i.e. it consists of the node X and its identity edge ιX ). Now, it is not difficult to see that what remains of T if we remove from it all edges of πX (T ) is also a subtree of T . To see this, note that there is a unique path from the root of T to X and also from the root of T to every node not in πX (T ). We shall refer to this subtree as the complement of πX (T ) and if we set TX = πX (T ) then we shall denote its complement by T X . Therefore we have: T X = triples(T ) \ triples(TX ) It is important to note that (a) TX and T X are composable (with the node X as the link) and (b) they ‘make up’ the whole tree T in the sense that. T X ◦ TX = T . Therefore, using tree projection, we can decompose a tree T into two composable subtrees as stated formally in the following definition. Definition 13 (Tree decomposition) Let T be a tree and X a node of T . The pair (TX , T X ) is called the decomposition of T on X. The simplest example to illustrate tree decomposition is to consider the composif

g

tion of two functions f : X → Y and g : Y → Z seen as the tree T : X − →Y − → Z. Then TY is g and T Y is f . Using decomposition it is possible to decompose a tree into two or more subtrees and, as we shall see later, this possibility is quite welcome when designing a view of a tree database. Indeed, using decomposition when defining a view, a view user may wish to focus on smaller trees serving specific information needs. Now, given an instance δT of T , the question is what are the instances of the components in a decomposition of T in terms of δT . Roughly speaking, the instances of the components are the components of δT . More formally we have: 18

Definition 14 Let (TX , T X ) be a decomposition of a tree T and let δT be an instance of T . Then we have: - for each node N of TX , δTX (N ) = δT (N ) and for each edge e of TX , δTX (e) = δT (e) - for each node N of T X , δT X (N ) = δT (N ) and for each edge e of T X , δT X (e) = δT (e) Suppose now that, in a database, we have a tree T with instance δT and we want to replace it by the two trees of the decomposition (TX , T X ), where X is a node of T . Then we have two cases: - if we want to let the two trees evolve independently during database updates then we may have δTX (X) ̸= δT X (X) - if we want to be able to ‘recover’ δT (by composition) in every database instance then we must maintain the set-theoretic constraint: δTX (X) = δT X (X) In the rest of the paper, we shall refer to the set of all operations on trees that we have seen in this section as the tree algebra and to a well formed expression using the operations of this algebra as a tree expression. Definition 15 (Tree algebra and tree expression) Let D be a tree database. – The tree algebra of D is defined to be the set of the following operations on trees: restriction, composition and projection (the Cartesian product of trees being a derived operation). – A tree expression over D is either a tree of D or a well formed expression T E whose operands are trees of D and whose operations are among those of the tree algebra. The value of a tree expression T E, denoted by V alT E , is the tree obtained by performing the operations in T E; and given the current instance of D, the current instance of V alT E is obtained in the way that we have seen earlier in this section. To illustrate the concept of tree expression refer to Figure 1 and consider the tree expression T2 ◦ T1 . Its value is the tree T5 and the (current) instance of T5 is computed from the instances of T1 and T2 as explained for tree composition earlier in this section. Now, a tree expression T E over a tree database D can be seen as a query over D, whose answer is the value V alT E of T E. Therefore, in our approach, the user interacts with the tree database at two levels: (a) querying the database to extract a desired tree and (b) querying the extracted tree using one of two kinds of queries, traversal queries or analytic queries that we shall see in the following sections. As a last remark, the operations of the tree algebra contribute to increase the expressive power of our model in at least three significant ways: First, as we shall see in the following sections, by creating larger trees, the operations of composition and Cartesian product enrich the query language by offering the possibility of expressing new queries traversing two or more trees. Second, by decomposing a large tree into smaller trees, tree decomposition allows to focus on smaller parts of the database. Third, as we shall see in the following subsection, using these operations we can define quite sophisticated views of a tree database tailored to the needs of individual users or user groups. 19

Branch Database: D = {T1, T2, T3}

T1

Date

Prod

d

Inv

q

Qty

Region View:

(v, Prod(T3 )o(T2oT1) )

r

p

Branch

Inv

T2

p

b

Region

Prod

r

Branch

Prod

b

p

V

Date

d

Inv q

s

Sup

c

Cat

s

Sup

c

Cat

T3

Qty

Fig. 3 Example of view

3.5 Views The concept of view was introduced in the early days of relational databases [19] and originated from the need of individual users or groups of users wanting to use only part of the information contained in the database, and moreover tailored to their specific needs. Formally, a view of a relational database is a pair (V, RE), where V is the view name and RE is a relational algebra expression called the ‘view definition’. Such a view actually defines a relational table whose name is V and whose content is the value of RE [19]. Motivated by the concept of relational view, we introduce the following definition of view of a tree database.

Definition 16 (View of a Tree Database) Let D be a tree database. A view of D is defined to be a pair (V, T E), where V is the view name and T E is a tree expression over D, called the view definition. To illustrate this definition, consider the tree database D of Figure 3. The pair (V, πP rod (T3 ) ◦ (T2 ◦ T1 )) is a view of D whose name is V and whose definition is the expression T2 ◦ T1 . Incidentally, as the trees T2 and T3 are disjoint, we have: πP rod (T3 ) ◦ (T2 ◦ T1 ) = T2 ◦ (πP rod (T3 ) ◦ T1 ); and in fact this property holds in general, as stated formally in the following lemma, whose proof follows immediately from the definition of composition. Lemma 7 Let D be a tree database and T1 , T2 , T3 three trees of D such that (a) T1 is composable with T2 and with T3 and (b) T2 and T3 are disjoint. Then we have: T3 ◦ (T2 ◦ T1 ) = T2 ◦ (T3 ◦ T1 ). 20

4 Traversal Queries As explained informally in the introduction, our model offers two kinds of queries, traversal queries and analytic queries; and these queries are always expressed over a tree, which is either a tree present in the database or a tree derived from other trees using a tree expression. In this section, given a tree T , we present the definition of traversal query over T , and in the following section we present the definition of analytic query over T . A traversal query is a type of query used to explore and navigate a tree by traversing its nodes and edges, starting from a specific node or a set of nodes and following the connections between nodes based on defined criteria. The definition of a traversal query is based on that of path expression over a tree, a concept that we have seen in section 2.2. We recall that a path expression is the composition of all edges along a path; and that there is a one-one correspondence between paths in a tree and path expressions: given a path, the corresponding path expression is the composition of its edges, and conversely, given a path expression the corresponding path is the sequence of edges in the expression in reverse order. Therefore we can use a path to specify a path expression, unambiguously; and we can use a path expression to specify a path, unambiguously. Clearly, the source and target of a path expression are the source and target of the corresponding path. Definition 17 (Traversal query over a tree) Let D be a tree database and T a tree, which is either in D or derived from D using a tree expression. A traversal query Q over T is defined to be either a single path expression over T or the pairing of two or more path expressions having the same source S and distinct targets A1 , . . . , An , that is: Q = P E1 ∧ . . . ∧ P En , where target(P E1 ) = A1 , . . . , target(P En ) = An , n ≥ 1 The answer of Q in an instance δT of T is denoted by AnsQ (δT ) and it is defined to be the pairing of the values of P E1 , . . . , P En in δT that is: AnsQ (δT ) = V alP E1 (δT ) ∧ . . . ∧ V alP En (δT ) We shall denote a traversal query also by Q(S, P E1 , . . . , P En ) when we want to state explicitly that the common source of its expressions is S; and we shall refer to S as the source of the query. Moreover, we shall denote the answer simply by AnsQ when δT is understood. Clearly, as the value of each P Ei is a function from S to Ai , say fi : S → Ai , the answer of Q is the pairing f1 ∧ . . . ∧ fn (i.e. a function from S to A1 × . . . × An ). For example, referring to tree T7 of Figure 1, if Q = (s ◦ p) ∧ (c ◦ p) then AnsQ is a function from Inv to Sup × Cat. We shall refer to A1 × . . . × An as ‘the target’ of the query and to each Ai as ‘a target’ of the query. Note that the identity edge of each node is a traversal query (also called the identity query of the node). Typically, identity queries are used when we want to ‘read’ the content of a node X. For example, the identity query Q = ιSup will return the set {(x, x)/x ∈ δT (Sup)} from which we can ‘extract’ the (current) set of suppliers. Traversal queries have a number of important features that we summarize below: 1. The answer to a traversal query can be represented as an easy-to-read table. Indeed, if A1 , . . . , An are the targets of the query, then the answer can be represented in a table such that: the rows are indexed by the values of S, the 21

columns are indexed by A1 , . . . , An , and for each s in S, the value fi (s) is entered in the cell (s, Ai ). We recall that, in the relational model [20], a table where the entries are atomic values and in which the values in each column are functionally dependent on the key-values is said to be in ‘First Normal Form’. Moreover, if we view each expression P Ei of a traversal query as a functional dependency (from the source S of the query to the target Ai of P Ei ) then the table just defined satisfies all dependencies fi : S → Ai . Therefore, the answer of a traversal query can be seen as a relation whose key is S (the source of the query) and whose attributes are the targets A1 , . . . , An of the path expressions defining the query. 2. Each path expression P Ei of a traversal query over a tree T corresponds to the unique path from the source S to the target Ai of the query. Therefore a traversal query Q over T can be specified as follows: (a) choose a node S of T as the source of Q, (b) choose n distinct descendants A1 , . . . , An of S in T as the targets of Q, and (c) give restrictions (optionally) for S and for each Ai . Then the query Q will be the pairing of the (possibly restricted) path expressions thus defined. This implies that one can use the following SQL-like statement to define a traversal query Q: select ⟨S, A1 , . . . , An ⟩ from ⟨tree − expression⟩ where ⟨conditions⟩ Here the nodes in the select clause must be nodes of the tree, say T , defined by the tree expression in the from clause; and ‘conditions’ in the where clause must (optionally) define restrictions of the nodes given in the select clause. Put differently, the select and where clauses define a traversal query over the tree defined by the from clause. Clearly, the system will have to first verify whether the nodes A1 , . . . , An given in the select clause are distinct descendants of node S in T ). 3. As a traversal query Q over a tree T is the pairing of n path expressions P E1 , . . . , P En with a common source S and targets A1 , . . . , An , its answer, AnsQ , can be seen as a set of tuples over ‘attributes’ S, A1 , . . . , An , where A1 = target(P E1 ), . . . , An = target(P En ). For example, consider the query Q = (r ◦ b) ∧ (s ◦ p) over the tree T7 of Figure 1. The source of Q is Inv, the expression r ◦b has Region as target, and the expression s◦p has Sup as target. The answer to this query can be seen as a set of tuples over the ‘attributes’ Inv, Region, Sup. In other words, each traversal query Q(S, P E1 , . . . , P En ) induces a relation schema RQ (S, A1 , . . . , An ), and for every instance δT of T , the answer AnsQ (δT ) induces a relation rQ over RQ . Moreover, as πAi ◦ AnsQ (δT ) = fi is a function from S to Ai , i = 1, . . . , n, the relation rQ satisfies the functional dependencies f1 , . . . , fn (thus making the source S of Q the key of RQ ). It follows that there is a mapping from traversal queries Q over T to relation schemas RQ such that: (a) for each instance δT , the answer AnsQ (δT ) induces a relation rQ over RQ satisfying the functional dependencies f1 , . . . , fn , and (b) the values of each non-key attribute Ai of RQ are computed by the expression P Ei having Ai as its target. In other words, each expression P Ei of Q provides the semantics of attribute Ai of RQ , i = 1, . . . , n; and the pairing of the path expressions in the query provides the semantics of the induced relation schema RQ . Moreover, this semantics is unique as there is one and only one path from the source of the query to each of its targets (put differently, there can’t be two parallel paths between the 22

source and a target of the query). We shall come back to this point in section 6.3, where we discuss the definition of a relational database as a set of traversal queries over a tree database. 4. In view of our discussion in the previous item, in our model, we consider functional dependencies as ‘first class citizens’ for building queries, while relations are derived concepts. This is in sharp contrast with the relational model, in which relations are considered as ‘first class citizens’ and functional dependencies are considered as ‘constraints’ that the relations must satisfy. Put differently, in the relational model, functional dependencies play a static role, whereas in our model they play a dynamic role in the sense that it is the functional dependencies that actually build-up consistent relations. Before ending this section, a word on query evaluation. The evaluation of a traversal query can be done directly, based on the definitions of the operations of the functional algebra that appear in the query; or indirectly, either by translating the query as an equivalent query in some query engine (e.g. by translating it as an SQL query) or by rewriting the query. The kind of rewriting that we envisage in our model is the process of applying a number of transformations to the original query in order to produce an equivalent optimized one (‘optimized’ in the sense that the equivalent query allows to reuse previously obtained query results). Such transformations do not depend on the physical state of the system (such as the size of physical structures, the system workload, etc). They are just well-defined rules that specify how to transform a query expression into a logically equivalent one [12]. Here, by ‘equivalence’ between two queries we mean the following: two traversal queries Q and Q′ over a tree T are equivalent, denoted as Q ≡ Q′ , if they return the same answer in every database instance. For example, referring to the tree T7 of Figure 1, the queries Q = (s ◦ p) ∧ (c ◦ p) and Q′ = (s ∧ c) ◦ p are equivalent (as composition distributes over pairing). Yet, the first needs two compositions and one pairing for its evaluation whereas the second needs one composition and one pairing. Such rewriting is obviously based on properties of the functional algebra. However, a complete account of traversal query rewriting lies outside the scope of the present paper and it is part of our current research.

5 Analytic queries In order to give a general definition of analytic query over a tree we proceed as for traversal queries that is: we first define what an analytic expression is and then we define an analytic query to be either an analytic expression or the pairing of two or more analytic expressions with the same source. In doing so we build upon our previous work on data analytics [15][14]. First, let us see how an analytic expression is defined and evaluated using the tree T1 of Figure 1 as an example. Suppose that we want to know the total quantity delivered to each branch. This computation needs the following items: - the edges (functions) b and q of T1 that return the branch and the quantity appearing on each invoice, respectively; - and the aggregate operation sum (to sum-up the quantities delivered in each branch). 23

The triple AE = (b, q, sum) is an example of what we call an ‘analytic expression’ and ‘the total quantity delivered by branch’ is what we call the ‘value’ of AE in T1 , denoted by V alAE (T1 ). Figure 4(a) shows a toy example, where the data set Inv consists of seven invoices, numbered 1 to 7, with each invoice associated with a branch and a quantity by the functions b and q, respectively. In order to find the value of AE we proceed in three steps as follows: Grouping: During this step we group together all invoices referring to the same branch (i.e. we invert the function b). The results of grouping are shown in Figure 4(a) (e.g. invoices 1, 2 refer to branch Br1 ). Measuring: In each group of the previous step, we find the quantity corresponding to each invoice in the group, using the function q (e.g. the quantities corresponding to Br1 are 200 and 100). Aggregation: In each group of the previous step, we sum up the quantities found (e.g. for branch Br1 we find 200 + 100= 300). Then the association of each branch to the corresponding total quantity is the desired result (and this result is the function V alAE (T1 ) shown in Figure 4(a)): Br1 → 300, Br2 → 600, Br3 → 600 We view the ordered triple AE = (b, q, sum) shown in Figure 4(a) as an analytic expression over T1 , the function V alAE : Branch → T otQty in that same figure as the value of AE, and the computations shown in the figure as the expression evaluation process. Note though that what makes the association of branches to total quantities possible is (1) the fact that the functions b and q have the same source (namely, Inv in this example) and (2) that ‘sum’ is an operation applicable on q-values. Also note that TotQty is a new symbol (i.e. not appearing in the analytic expression) which is necessary for naming the target of the computed function V alAE (T1 ). The function b that appears first in the triple (b, q, sum) and used in the grouping step is called the grouping function; the function q that appears second in the triple is called the measuring function, or the measure; and the function sum that appears third in the triple is called the aggregate operation. Actually, the triple (b, q, sum) should be regarded as the specification of a data analysis task to be carried out over the data set Inv. Note that exchanging the two first components of this triple we obtain the triple (q, b, sum) which is not a well formed analytic expression as, although b and q have the same source, the aggregate operation is not applicable on b-values (as we can’t sum up branches). However if instead of ‘sum’ we put ‘count’ as the aggregate operation then we obtain the analytic expression (q, b, count) which is a well formed analytic expression, as ‘count’ is an aggregate operation applicable on b-values. By the way, what this analytic expression returns is the number of branches per delivered quantity. To see another example of analytic expression, suppose that W is the set of tweets accumulated over a year; dd is the function associating each tweet t in W with the date dd(t) in which the tweet was published; and cc is the function associating each tweet t in W with its character count, cc(t). To find the average number of characters in a tweet by date, we follow the same steps as in our previous example: first, group the tweets by date (using function dd); then find the number of characters per tweet (using function cc); and finally take the average of the 24

Branch Br1 Br2 Br3

b

Inv

q

1 2 3 4 5 6 7

Qty 200 100 200 400 100 400 100

sum

TotQty

AE= (b, q, sum)

300 600

unfolding the expression

recursive evaluation

AE= (rob, q, sum)

ValAE

(r, (b, q, sum), sum)

(r, ValAE1 , sum)= ValAE2

Evaluation of AE

600

AE1 Branch

ValAE

TotQty

Br1

300

Br2

600

Br3

600

ValAE

(b, (iInv, q, sum), sum) Extension of ValAE

ValAE1= (b, ValAE0 , sum)

AE0 ValAE0= q

(a)

base of recursion

(b)

Fig. 4 (a) Evaluation of an analytic expression (b) Recursive evaluation of analytic expression

character counts in each group (using ‘average’ as the aggregate operation). The appropriate analytic expression formulation in this case is the triple (dd, cc, avg). Now, the concept of analytic expression as defined in the previous examples was first introduced in [15][14] (although it is called ‘analytic query’ in those works). In the present work, we extend the concept of analytic expression in several ways: (a) we introduce the use of traversal queries for performing grouping and measuring, (b) we define an analytic query to be either an analytic expression or the pairing of two or more analytic expressions with the same source, (c) we introduce a two-level rewriting for analytic queries, and (d) we introduce the concept of ‘mixed query’ as the pairing of path expressions and analytic expressions having the same source. To begin with, in an analytic expression (g, m, op), as defined in the previous examples, the grouping and measuring functions are seen as abstract functions (or as edges of a database tree). On the other hand, as we have seen in the previous section, the answer to a traversal query is a function, therefore the (answers of) traversal queries can be used in the definition of an analytic query either as grouping or as measuring functions. This simple observation allows for a significant extension of the concept of analytic expression compared to the one introduced in [15][14]. Indeed, by using traversal queries to define the grouping and measuring functions, a user has the possibility to define analytic expressions representing specific user needs. These observations motivate a semantically richer definition of analytic expression. Definition 18 (Analytic expression) An analytic expression over a tree T is a triple AE = (g, m, op), where g and m are traversal queries over T having the same source, and op is an aggregate operation applicable on the target of m. Given an instance δT of T , the value of AE, denoted V alAE (δT ), or simply V alAE when δT is understood, is the following function: 25

V alAE : range(g) → target(op) such that: V alAE (i) = op(m/(g −1 (i))), for all i ∈ range(g) where m/(g −1 (i)) denotes the restriction of m to the subset g −1 (i) of its source The traversal queries g and m are called grouping query and measuring query, respectively, and they can be any traversal queries over T . As in the case of a path expression, an analytic expression AE = (g, m, op) has a source and a target. The source of AE is the source of the grouping query g and the target of AE is the target of the aggregate operation op. A few remarks are in order here explaining in what ways the above definition of analytic expression generalizes significantly the one given in [15][14]. First, by allowing grouping and measuring to be done by the results of traversal queries, we gain access to a much larger set of meaningful functions for grouping and measuring (‘meaningful’ in the sense that they are defined through queries expressing user needs). Second, we can benefit from the combination of rewriting rules for traversal queries with rewriting rules for analytic expressions (as we shall see shortly) so as to obtain a richer rewriting system for analytic queries. Third, by pairing analytic expressions into a single analytic query, we need to partition the common source of the grouping queries only once and then apply the measuring query of each analytic expression separately. It is important to note that, in an analytic expression, the common source of the grouping and measuring queries can be any node - not necessarily the root of the tree. For example, consider the tree T7 of Figure 1 and the following two analytic expressions over T7 : (s, c, count) returning the number of product categories supplied by each supplier (c, s, count) returning the number of suppliers supplying each product category The common source of the grouping and measuring queries in these analytic expressions is the node P rod (and not Inv as in the previous examples). Also note that, given a database tree T , we can use the identity query ιX of any node X as the grouping or measuring query in an analytic expression over T . Here is an example, referring to tree T7 of Figure 1: AE = (ιInv , q, sum) During the evaluation of AE, in the grouping step, the function ιInv puts each invoice of Inv in a singleton block. Therefore summing up the values of q in a group simply finds the value of q on the single invoice in that group; then the measuring step simply returns this value of q. It follows that, for each invoice i, V alAE (i) returns q(i). Therefore V alAE = q. As another example over the same tree consider the following: AE = (q, ιInv , count) During the evaluation of AE, in the grouping step, the traversal query q groups together in a single group all invoices having the same delivered quantity; then, during the measuring step, the traversal query ιInv makes no changes in the group; and finally, during the aggregation step, the aggregate function count counts the invoices in each group. It follows that, for each value x of Qty, the value V alAE (x) is the number of invoices having x as the delivered quantity (i.e. the answer is the number of invoices by quantity delivered). In fact, we can enrich the class of analytic expressions if we ‘augment’ the notion of tree as follows: 26

– every tree is equipped with a ‘terminal node’ or ‘sink’ Σ such that dom(Σ) is a singleton – every node X of a tree is equipped with a ‘terminal edge’ σX : X → Σ, representing the constant function δT (σX ) : X → δT (Σ), for every node X (i.e. the function mapping every element of δT (σX ) to the singe value of dom(Σ)). Note that by doing so we maintain the basic property of a tree: there still is a unique path from the root to every non-root node different than Σ. Clearly, given a tree T , we can use the terminal edge σX of each node X in the same way as any other edge of T . In particular, we can use it in defining analytic expressions. Referring to the tree T7 of Figure 1, here is an example: AE = (σP rod , c, count) During the evaluation of AE, in the grouping step, the grouping query σP rod groups all products in a single group; then the measuring query c associates each product with a category; and finally, during the aggregation step, the aggregate operation count finds the number of categories of all products delivered. Here are two more examples involving the identity query and the constant query: – (σInv , ιInv , count) returns the number of all invoices of node Inv Note that the analytic expression (σX , ιX , count) is typically used for finding the cardinality of a node X. – (σInv , q, sum) returns the total of all quantities delivered Note that the analytic expression (σX , m, op) is typically used for reducing the whole of X under some measuring query m and operation op. It is important to note that combinations of analytic expressions such as the above can be used in several special cases such as when we want to compute percentages. For example, in the tree T1 of Figure 1, suppose we want to compute, for each branch, the percentage of the total quantity of products delivered. In this case, we use the following two analytic expressions: – AEBr = (b, q, sum), returning the total quantity delivered by branch – AET ot = (σInv , q, sum), returning the total of all quantities delivered By dividing now the value of AEBr on a specific branch Bri by the value returned by AET ot we find the percentage for each branch Bri (and the set of percentages for all branches can be visualized for example in the form of a pie). Regarding the use of both ιX and σX in analytic expressions, we note that, for any nodes A and B, and any analytic expression e : A → B, we have: – ιB ◦ e = e ◦ ιA = e – σB ◦ e = σA An interesting remark regarding an analytic expression is that there are several possibilities of restriction. Here are a few examples: 1. We can restrict the grouping and/or the measuring query to a subset of the source and/or to a subset of a target of the query. 2. We can restrict the analytic expression itself. Indeed, as the value of an analytic expression AE is a function, we can restrict it to a subset D of its source (or to a subset of its target and then ‘pull’ the restriction to its source). 27

For example, consider the analytic expression AE = (p, q, sum) over the tree T1 of Figure 1, which returns the totals by product. Its value is a function from P rod to T otals, and if we define D = {x ∈ P rod/V alAE (x) ≤ 1000} then the restricted value, V alAE /D, will contain only products for which the total is less than or equal to 1000. 3. We can use any function which is applicable on the source of V alAE to define quite complex restrictions of V alAE . For example, consider the analytic expression: AE = (s, c, count) over the tree T3 of Figure 1, which returns the number of categories supplied by each supplier. Its value is a function from Sup to a set CountCat of integers, and if we define D = {x ∈ Sup/V alAE (x) > Avg(AnsQ (Sup))} then the restricted value V al(AE)/D will contain only suppliers supplying more categories than the average of categories supplied by a supplier. We note that the kinds of restriction described in items 2 and 3 above are not possible to implement in relational algebra queries (although some might be possible to implement as SQL group-by queries through the ‘Having’ clause). So a relevant question here is: how the possibilities of restriction offered by our model compare with those offered by the ‘Having’ clause of SQL? However interesting, the answer to this question lies outside the scope of the present paper.

5.1 Evaluation of analytic expressions In principle, the evaluation of an analytic expression can be done in four different ways: 1. Directly, as described in Figure 4(a); 2. By translating the analytic expression and evaluating it by some query engine; 3. By sharing computations when evaluating a set of queries with the same grouping query; 4. By rewriting the analytic expression so as to put it in some desired form. Direct evaluation consists essentially in programming the steps described in Figure 4(a). Clearly, direct evaluation is inefficient for analyzing big data sets. A better option is translating the analytic expression and evaluating it by some query engine thus taking advantage of optimization techniques implemented in the query engine. An analytic expression as defined here can be translated as an SQL group-by query, when processing relational data [15]; as a MapReduce job, when processing data residing in a file system [15, 25]; and as a SPARQL query when processing RDF data [11]. Moreover, the possibility of translating an analytic expression as a query in three different kinds of query engines makes it possible to use the tree database model as a ‘mediator’ [24]. This means that a user formulates an analytic expression over the tree database; the expression is then translated to a query over the underlying query engine; and finally the user receives the answer ‘transparently’, that is, as if the analytic expression were processed by the tree database. Sharing computations when evaluating two or more analytic expressions is a third option. Consider the following set of analytic expressions: AE = {(g, m1 , op1 ), . . . , (g, mn , opn )} 28

The expressions in this set share the same grouping query g. Clearly, in this case, the result of the grouping step will be the same for each analytic expression AEi , i = 1, . . . , n. Therefore the set of analytic expressions can be rewritten using the ‘optimized’ form AE ′ = {(g, {(m1 , op1 ), . . . , (mn opn ))}, meaning that the grouping step is performed only once and then the measuring and aggregation steps for each analytic expression is performed to obtain the results of the analytic expressions in AE. Moreover, if the analytic expressions in the set share both, the grouping and the measuring query then the set AE can be rewritten using the ‘optimized’ form: AE ′ = (g, m, {op1 , . . . , opn }) This time, the grouping and measuring steps are performed only once and then the aggregation step for each analytic expression is performed to obtain the results of the analytic expressions in AE. To illustrate these optimizations, refer to the tree T7 of Figure 1 and consider the following set of two analytic expressions: AE = {(b, q, sum), (b, s ◦ p, count)}. The first asks for the total quantity delivered by branch and the second asks for the number of suppliers by branch. Then the optimized form for the set AE is the following: AE ′ = (b, {(q, sum), (s ◦ p, count)}). Next, consider the following set of two analytic expressions: AE = {(b, q, sum), (b, q, avg)}. The first asks for the total quantity delivered by branch and the second for the average quantity delivered by branch. Then the optimized form is: AE ′ = (b, q, {sum, avg}).

5.2 Rewriting an Analytic Expression In this section we discuss the last option for evaluating an analytic expression that is by rewriting the expression. Rewriting an analytic expression AE = (g, m, op) can be done at two orthogonal levels: (a) rewriting the grouping query g and/or the measuring query m, and (b) rewriting the analytic expression itself in terms of other analytic expressions. Rewriting the grouping or the measuring query can be done as outlined in section 4. Rewriting the analytic expression in terms of other analytic expressions depends on the form of the grouping and measuring queries as well as on the kind of aggregate operation used in the analytic expression. More precisely, if the aggregate operation is associative [9], then the following is the basic rule for rewriting an analytic expression [15]: Composition Rule : (g ′ ◦ g, m, op) = (g ′ , (g, m, op), op) What this rule says is that if the grouping query is the composition of two other queries then the analytic expression can be rewritten as a nested analytic expression. To understand this nesting, consider the following analytic expression over the tree T7 of Figure 1: AE = (r ◦ b, q, sum), asking for the totals by region Here is why the composition rule works: the edge r tells us in which region each branch is located, therefore, if we have the totals for each branch in a region then we can sum them up to find the total for that region. Now, to find the totals by branch 29

we can use the analytic expression AE ′ = (b, q, sum); and as the answer to AE ′ has the same source as r we can use the analytic expression AE ′′ = (r, V alAE ′ , sum) to compute the totals by region. In other words, the expression AE for computing the totals by region can be rewritten as AE = (r, V alAE ′ , sum). By replacing now V alAE ′ by (b, m, sum) we obtain that AE = (r, (b, q, sum), q), which should be read as follows: first evaluate the inner or nested expression (b, m, sum) to obtain the totals by branch; and then use its value as the measure to evaluate the outer expression thus obtaining the totals by region. It is important to note that the composition rule works only if the aggregate operation op is associative [9]. Most common operations such as ‘sum’, ‘min’, ‘max’ etc. are associative, for example, sum(1, 2, 3, 4, 5) = sum(sum(1, 2), sum(3, 4, 5)). In contrast, ‘avg’ is not associative, for example: avg(1, 2, 3, 4, 5) ̸= avg(avg(1, 2), avg(3, 4, 5))) Although there are ‘corrective’ algorithms allowing the use of many non-associative operations such as average, median, etc. (see for example [25][9]), we shall not pursue this subject any further here. Rather, in order to simplify the discussion, we shall assume that all aggregate operations are associative. The composition rule allows for the recursive evaluation of analytic expressions as shown in Figure 3(b), where the expression AE = (r ◦ b, q, sum), asks for totals by region. We first unfold AE using the composition rule until we reach the base expression AE0 ; then we evaluate the base expression and use its value to compute the value of the expression AE1 = (b, q, sum); and finally we use the value of AE1 to compute the value of AE. Note how the identity query ιInv is indispensable in defining the base expression AE0 , based on the equality: b = b ◦ ιInv . Indeed, it follows from this equality that: AE1 = (b, q, sum) = (b ◦ ιInv , q, sum) = (b, (ιInv , q, sum), sum) Therefore we have: AE0 = (ιInv , q, sum) and V al(AE0 ) = q Using the composition rule we can sometimes avoid making (relational) joins during the evaluation of an analytic expression. To see how, consider again the expression AE = (r ◦b, q, sum) and suppose that the answers of r and b are stored on separate tables, say R and B, respectively. The direct evaluation of AE requires a join between R and B in order to find the answer to the grouping query, whereas if we use the rewritten form AE ′ = (r, (b, q, sum), sum), no join is needed since the grouping functions for the inner and outer expressions are stored separately, in R and B, respectively. Another advantage of using the composition rule is the possibility of incremental evaluation of analytic expressions when processing big data sets [15][25]. Now, the composition rule says how to rewrite an analytic expression in terms of other analytic expressions, no matter whether we rewrite or not its grouping and measuring queries. Let’s now see an example of rewriting an analytic query at both levels: first rewriting its grouping and/or measuring query to obtain some desired (equivalent) form; then rewriting the resulting analytic expression using the composition rule. For example, consider the following analytic expression: ((p ◦ s) ∧ (p ◦ c), q, sum) asking for the totals by supplier and category Here, by applying lemma 1 to the grouping query (p ◦ s) ∧ (p ◦ c) we can rewrite it as (s ∧ c) ◦ p, so we can now rewrite the analytic expression as follows: ((s ∧ c) ◦ p, q, sum) Next, we apply the composition rule to obtain the final, rewritten expression: 30

((s ∧ c), (p, q, sum), sum) As this example shows, using the composition rule together with rewriting of the grouping and/or measuring query, we can derive a variety of rewriting rules. A most notable example is what we call the ‘pairing rule’. Consider an analytic expression of the form AE = (g1 ∧ g2 , m, op), where the grouping query is the pairing of two queries, g1 and g2 . Suppose now that we want to evaluate the expression AE1 = (g1 , m, op). It follows from Lemma 1 that g1 = πtarget(g1 ) ◦ (g1 ∧ g2 ), therefore AE1 can be rewritten as follows: AE1 = (πtarget(g1 ) ◦ (g1 ∧ g2 ), m, op) Applying now the composition rule, we can further rewrite AE1 as follows: AE1 = (πtarget(g1 ) ◦ (g1 ∧ g2 ), (g1 ∧ g2 , m, op), op) Following the same reasoning for the expression AE2 = (g2 , m, op) we have: AE2 = (g2 , m, op) = (πtarget(g2 ) ◦ (g1 ∧ g2 ), (g1 ∧ g2 , m, op), op) Hence the following rule for rewriting an expression AEi = (gi , m, op) in terms of the expression AE = (g1 ∧ . . . ∧ gn , m, op), n ≥ 2 : Pairing Rule: AEi = (gi , m, op) = (πtarget(gi ) ◦ (g1 ∧ . . . ∧ gn ), (g1 ∧ . . . ∧ gn , m, op), op) To see how the pairing rule works, refer to the tree T7 of Figure 1 and suppose that we have computed the totals by branch and product. Then we can re-use this result to compute the totals by branch and the totals by product in terms of the totals by branch and product. Indeed, applying the pairing rule we have: (b, q, sum) = (πBranch ◦ (b ∧ p), (b ∧ p, q, sum), sum) (p, q, sum) = (πP roduct ◦ (b ∧ p), (b ∧ p, q, sum), sum).

5.3 Analytic queries In the previous subsection we defined and discussed analytic expressions and their evaluation. In this subsection we define analytic queries by proceeding in a similar manner as for traversal queries that is we define an analytic query to be either a single analytic expression or the pairing of two or more analytic expressions with the same source. As we already mentioned, in our model, these two types of queries are defined using the same formal framework, namely the functional algebra. In contrast, in the relational model, it is not possible to define analytic queries in the relational algebra; they are defined outside the relational algebra, in the form of SQL group-by queries. Definition 19 (Analytic query) Let D be a tree database and T a tree in D. An analytic query Q over T is defined to be either a single analytic expression AE over T or the pairing of two or more analytic expressions with the same source S and distinct targets that is: Q = AE1 ∧ AE2 ∧ . . . ∧ AEn , n ≥ 1 Given an instance δT , the answer to Q is denoted by AnsQ (δT ) and it is defined as the pairing of the values of the analytic expressions AE1 , AE2 , . . . AEn that is: AnsQ (δT ) = V alAE1 (δT ) ∧ . . . ∧ V alAEn (δT ) We shall also denote this answer by AnsQ whenever δT is understood from context. 31

5.4 Mixed queries We have seen that a traversal query over a tree T is either a single path expression over T or the pairing of two or more path expressions over T having the same source; and that an analytic query is either a single analytic expression over T or the pairing of two or more analytic expression over T having the same source. Hence we can unify the two types of expression over T in the following definition of ‘mixed query’ over T . Definition 20 (Mixed query) Let D be a tree database and let T be a tree in D. A mixed query Q over T (or simply query over T ) is defined to be the pairing of two or more expressions over T having the same source and distinct targets: Q = E1 ∧ . . . ∧ En , n ≥ 1 where each Ei is either a path expression or an analytic expression over T . Given an instance δT of T , let f1 , . . . , fn be the functions to which E1 , . . . , En evaluate in δT , respectively. Then the answer to Q is denoted by AnsQ (T ) (or simply by AnsQ whenever T is understood) and it is defined as follows: AnsQ = f1 ∧ . . . ∧ fn For example, referring to Figure 1, the following is a mixed query over the tree T7 : Q = r ∧ (b, q, sum) This query returns, for each branch x ∈ Branch, the pair (r(x), BrT ot(x)) that is the region to which the branch x is located and the total quantity, BrT ot(x), delivered to branch x. Note that, as in the case of traversal queries, a mixed query Q induces a relation schema RQ , and for every instance δT , a relation rQ over RQ . In our previous example RQ has three attributes, Region, Branch and BrT ot) and two functional dependencies, Branch → Region and Branch → BrT ot. Moreover, for every instance of T , the relation rQ is the answer to Q in that instance and satisfies the two dependencies. Also note that in a mixed query we can apply the evaluation techniques that we have seen earlier by grouping together path expressions or by grouping together analytic expressions in the query. For example, consider the following mixed query over the tree T7 of Figure 1, which consists of one path expression and two analytic expressions: Q = r ∧ (b, q, sum) ∧ (b, q, avg) This query asks, for each branch, the region in which the branch is located together with the total and the average for the branch. If we group together the analytic expressions then we can replace their pairing by the following expression: (b, q, {sum, avg}); and then we can replace the query Q with the following query (which is less expensive to evaluate): Q′ = r ∧ (b, q, {sum, avg}) We end this section by noting that (a) traversal queries and analytic queries have similar syntax although they have different semantics and (b) mixed queries offer the possibility to use combinations of traversal and analytic queries in a principled way. In a sense, we can say that the query language of a tree database is actually the set of all mixed queries. 32

6 Applications In this section we discuss the expressive power of our model by outlining three possible applications, namely (a) how attribute inheritance can be defined seamlessly in our model using one-to-one edges and tree composition (b) how one can define a consistent relational database as a set of mixed queries over 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.

6.1 Inheritance One of the most intriguing - and at the same time most problematic - notions in object-oriented programming is inheritance [18]. Inheritance is commonly regarded as the feature that distinguishes object-oriented programming from other modern programming paradigms, but researchers rarely agree on its meaning and usage. Yet inheritance is often hailed as a solution to many problems hampering software development, and moreover, many of the alleged benefits of object-oriented programming, such as improved conceptual modeling and re-usability, are largely credited to it. Inheritance is the fundamental reuse mechanism in object-oriented programming languages. In our model, inheritance is the process that allows an entity (i.e. the root of a tree) to acquire or inherit the attributes of another entity (i.e. of the root of another tree) - in much the same way as in traditional databases, where inheritance allows a table to acquire the properties of another table. The tree that inherits is called the child tree and the tree whose attributes are inherited is called the parent tree. Definition 21 (Inheritance) Let D be a tree database and T , T ′ two disjoint trees of D (i.e. no node in common) with roots ρ and ρ′ , respectively. We say that ρ inherits from ρ′ if the following hold: 1. dom(ρ)= dom(ρ′ ) 2. δT (ρ) ⊆ δT ′ (ρ′ ), in every database instance 3. there is an edge Isa : ρ → ρ′ such that, in every database instance, we have: Isa(x) = x for all x ∈ ρ (i.e. Isa is a 1-1 edge) Under the above assumptions, the composition tree T ′ ◦T provides the inheritance of all properties of ρ′ by ρ. Indeed, there is a unique path from ρ to every attribute (i.e. non-root node) of T ′ . More precisely, by adding the Isa edge from ρ to ρ′ , we can consider T together with the Isa edge as a single tree, say T + . In this way, ρ′ becomes a leaf of T + , and therefore, T + becomes composable with T ′ . It follows that, in the tree T ′ ◦ T + , there is a unique path from ρ to every attribute A of T ′ . Therefore ρ inherits every attribute A of ρ′ through the unique path from ρ to A. We note in passing that performing the composition T ′ ◦ T + requires restriction propagation only in T ′ (but not in T because of item 2 in the above definition. Note however that maintaining the equality expressed by item 3 above is a constraint that the database must satisfy in order to support the inheritance represented by the Isa edge. Finally note that, as a consequence of item 3 above, the composition of Isa edges is also an Isa edge. 33

Country

Manuf.

c m

m

Manuf.

Car

Manuf.

Price

m

p

p

Vehicle

Vehicle p

Price

Price Country

Masts

ISABV ISACV

c Car

m m

Manuf.

p

Price

Masts m

Boat

Boat

Country

ISABV

ISACV

c

Masts m

Car

Boat

ISAAC

ISAAB Amphi

(a)

(c)

(b)

Fig. 5 (a) The Car tree and the Boat tree (b) Inheritance by Car and Boat from the Vehicle tree (c) Multiple inheritance by the Amphi tree and the diamond problem

To illustrate how inheritance can be supported by our model, suppose that we have two trees in the database, the Car tree and the Boat tree each with their attributes, as shown in Figure 5(a). The Car attributes are Country, M anuf, P rice, and the Boat attributes are M asts, M anuf, P rice (‘Masts’ meaning ‘number of masts’ in the boat). As the two entities Car and Boat have the attributes M anuf and P rice in common, the idea is to (a) ‘factor out’ (i.e. remove) the common attributes M anuf and P rice from the Car tree and from the Boat tree, (b) create a third entity, V ehicle, having M anuf and P rice as its attributes and (c) place two Isa edges, IsaCV : Car → V ehicle and IsBV : Boat → V ehicle so as Car and Boat each inherit the attributes M anuf and P rice of V ehicle (in the way described above). This process is depicted in Figure 5(b). Note that a tree can inherit from one or more disjoint trees and can be inherited by one or more disjoint trees (using tree composition). Going one step further, suppose now that we want to create an entity Amphi (short for ‘Amphibious’) that inherits the attributes of Car and Boat. To do so we can create a new tree, the Amphi tree (with only one node, Amphi) and add to it two Isa edges: IsaAC : Amphi → Car and IsaAB : Amphi → Boat, as shown in Figure 5(c). Then Amphi inherits the attributes Country from Car and M asts from Boat (this kind of inheritance from two or more other trees is called ‘multiple inheritance’). Now however, we have a problem as Amphi inherits M ake and P rice by composing the Amphi tree with the V ehicle tree (based on the Isa edge IsaCV ◦ IsaAC ), and at the same time Amphi inherits the same attributes M ake and P rice by composing the Amphi tree with the Boat tree (based on the Isa edge IsaBV ◦ IsaAB ). However, nothing guarantees that these two ways of inheriting will return the same values for M ake and P rice! This problem, known as the Diamond Problem drew much controversy in the object-oriented programming 34

community as to whether we should use multiple inheritance [22]. In our context, we can envisage two solutions to the problem: - maintain the constraint IsaCV ◦IsaAC = IsaAB ◦IsaBV during database updates - or require that the set of Isa edges in the database form one or more trees (i.e. no parallel paths formed by Isa edges - as is the case in Figure 5) The main advantage of using inheritance in a tree database is the same as in a classical database that is: inheritance allows a newly created tree to acquire the information contained in an existing tree, thus lowering redundancy by creating a hierarchical structure of trees expressed by the Isa edges present in the database. Inheritance hierarchies are crucial to building a structured and well-organized tree database. However, in such a database, the Isa edges should form one or more trees otherwise we may run into problems (such as the diamond problem). As a last remark, in presence of multiple inheritance, as in the example of Figure 5 we can (a) express semantic constraints and (b) use a set-theoretic language to extract additional, useful information from the database. For example, the following set-theoretic expressions might be imposed as a constraint in our example database: δT (V ehicle) = IsaCV (Car) ∪ IsaAB (Boat) expressing the fact that there can’t be vehicles in the database other than cars and boats. Clearly, as usual, such a constraint will have to be maintained during database updates. As an example of semantic query involving Isa edges consider the following: are there vehicles in the database which are neither cars nor boats? This query can be answered by computing the following set-theoretic expression: E = δT (V ehicle) ⊆ (IsaCV (Car) ∪ IsaAB (Boat)) If the value of E is ‘true’ then there is no vehicle in the database which is neither a car nor a boat; and if the answer is ‘false’ then there is vehicle in the database which is neither a car nor a boat. As a last remark, it is clear that the subject of inheritance in tree databases offers a rich ground for research, and in fact this is a main subject of our current work (see also the following Section 7).

6.2 Defining relations over a tree database We have seen that, in a tree database D, a mixed query over a tree T (hereafter called simply ‘query’) is of the form Q = E1 ∧ E2 ∧ . . . ∧ En , where each Ei denotes either a path expression or an analytic expression from a common source node S to a target node Ai , i = 1, 2, . . . , n. We have also seen that, given an instance of T , each Ei evaluates to a function fi : S → Ai , so the answer to Q is the pairing f1 ∧ . . . ∧ fn (i.e. a function from S to A1 × . . . × An ). Finally, we have also seen that each query Q induces a relation schema RQ (S, A1 , A2 , . . . , An ); and that, for every instance δT of T , the answer of Q in δT induces a relation rQ over RQ which satisfies the functional dependencies f1 , f2 , . . . , fn (see Section 5.4). In other words, each query Q over D induces a relation schema RQ and a relation rQ over RQ which is consistent with the functions defining the answer of Q. For example, consider the following queries: 35

Q1 = s ∧ c, a traversal query returning, the supplier and category of each product Q2 = (p, q, sum), an analytic query returning the total quantity by product (call it P rodT ot). These queries induce each a relation schema as follows: RQ1 (P rod, Sup, Cat) with dependencies: P rod → Sup and P rod → Cat RQ2 (P rod, P rodT ot) with dependency P rod → P rodT ot The above two relation schemas define a relational database schema RDB = {RQ1 , RQ2 }; and, for each instance of D, the answers of RQ1 and RQ2 in that instance induce the relations rQ1 and rQ2 , respectively. Moreover, rQ1 and rQ2 are consistent each with respect to their dependencies. The important thing to note here is that the values of each non-key attribute Ai of rQ are computed by evaluating the expression Ei of Q of which Ai is the target. Therefore the expression Ei provides the semantics of attribute Ai of RQ , i = 1, . . . , m. As a consequence, when defining a relational database over a tree database we have a significant semantic gain: the relation schema RQ (S, A1 , . . . , An ) comes with a clear semantics for its attributes, this semantics being the expression defining each attribute. In contrast, in a traditional database, the attributes of a relation schema have only the intuitive semantics conveyed by their names. Therefore when a relational database is defined as a set of queries over a tree database, the tree database works as the underlying ‘semantic layer’ of the relational database thus defined. We end this subsection by two remarks concerning the use of relational databases defined over of a tree database: 1. The user of a relational database defined over a tree database actually ‘sees’ a set of relation schemas (i.e. a set of tables), exactly as when interacting with a traditional relational database. Here, however, in contrast to a traditional relational database, each table is associated with clear semantics that the user can inspect assuming that (a) the expression computing the values of each attribute Ai is associated with Ai (but stays invisible to the user) and (b) all attributes of a table are made clickable so as the interested user can click an attribute of a table and ‘see’ the expression used to compute the values of that attribute. This expression says how the functions of the underlying tree database are combined in order to compute the values of that attribute. 2. It is natural that the user of relational database defined by a set of queries over a tree database should be able to ask relational algebra queries, as usual (or SQL queries in general). Therefore the system will have to translate each user query as a query over the underlying tree database and return the answer of the user query in the form of a relation. Designing and implementing such translation algorithms is part of our current research.

6.3 A tree database as an interface The idea to use a tree database as an interface to a relational database requires to answer a larger question, namely: under what conditions can we transform a relational database to an ‘equivalent’ tree database? To answer this question, we proceed in two steps as follows: 36

– Step 1: Transform the relational database schema S to a set of trees. – Step 2: For each (consistent) instance of a relational database over S define an ‘equivalent’ instance of the tree database of the previous step. Implementing the above steps is a long term project and here we only outline some first ideas and results. First, we recall a few basic facts from relational database theory [19]. A minimal cover of a set F of (functional) dependencies is a set F ′ of dependencies which is equivalent to F and such that: 1. The right-hand side of each dependency in F ′ is a singleton. 2. The left-hand side of each dependency in F ′ is minimal that is there is no redundant (or extraneous) attribute. 3. F ′ is minimal that is it contains no redundant dependency f (f is redundant if implied by the set of dependencies F ′ \ {f }). We also recall that F is equivalent to F ′ if F implies every dependency of F ′ and conversely, F ′ implies every dependency of F . It can be shown that the minimal cover of a set of dependencies always exists but is not necessarily unique [19]. Now, to implement the first step above, let (R(A), F ) be a relation schema, where R is the name of the schema, A the set of attributes and F the set of dependencies that each relation over A must satisfy in order to be consistent. Moreover, we assume that F is ‘minimized’ that is F is equal to one of its minimal covers. Now, a relation r over R is consistent only if the following hold: – For every dependency f : X → A in F, the projection πXA (r) is a function from πX (r) to πA (r) – There are no two different dependency paths with the same source and the same target (because then no relation over R with more than one tuple can be consistent - see previous item) – There cannot be a cycle of functional dependencies over an attribute A of A (or over a set of attributes of A) other than the identity cycle on A. Indeed, attribute domains are abstract sets of values that is the values of an attribute domain are pairwise independent; therefore, if such a cycle existed on A and we denoted by C the composition of its functions, then for every a ∈ dom(A) we must have C(a) = a otherwise, if C(a) = a′ and a′ ̸= a this would mean that a′ depends on a, a contradiction. It follows that each key K of F, together with all dependency paths having K as source form a tree with root K. As a consequence, the set of trees induced by all relation schemas in RDB forms a tree database, say T DB. Now, to implement the second step above, given a relation schema (R(A), F ) in RDB, an instance r of R and a tree T of T DB induced by F, we can define the instance of each node N and each edge e : X → Y of T as follows: δT (N ) = πN (r) and δT (e) = πXY (r) (which is a total function from X to Y since r satisfies the dependency X → Y ). The tree database T DB defined in this way can then act as an interface to RDB. Moreover, this interface can be tailored to the needs of specific users or groups of users by creating tree views of T DB as defined earlier (see Section 3.5). 37

Using the view mechanism the interface administrator can define a set of tree views tailored to the needs of a user or a group of users. We have already done some preliminary work along these lines as reported in [21].

7 Concluding remarks and perspectives We have seen a novel database model in which the database is seen as a set of trees, where the nodes of each tree represent the data sets of an application and the edges represent total functions between datasets. The query language of our model offers two kinds of queries, traversal queries and analytic queries A traversal query over a tree is the pairing of path expressions with the same source, whereas an analytic query over a tree is the pairing of analytic expressions with the same source. Whether traversal or analytic, a query is always defined over a tree which can be either a tree in the database or a tree defined from other trees using operations of the tree algebra. We have also outlined how our model can support inheritance; how a consistent relational database can be defined on top of a tree database (with the tree database providing the underlying semantics for attributes and relations); and how a tree database can be used as a user friendly interface for accessing and analyzing relational data. This work follows our previous work on graph database modeling in which the whole database is represented as a single graph, namely as a labeled directed acyclic graph with a single root called a ‘context’[14]. However, we believe that, using a set of trees together with a set of tree operations, instead of a single graph, provides more flexibility and opens the way for modeling such important concepts as inheritance - to mention just one. To the best of our knowledge, no other model uses the concept of tree as the basic database structure at the conceptual level. Our model considers functions as ‘first class citizens’ forming trees, while relations are derived concepts. This is in sharp contrast with the relational model, in which it is the relations that are considered as ‘first class citizens’ and functional dependencies are simply ‘constraints’ that the relations must satisfy. Put differently, in the relational model, functional dependencies play a static role, whereas in our model they play a dynamic role in the sense that they express key-value properties between nodes to represent information. In this sense, our model is closer to NoSQL databases[17] and in particular to key-value databases [5]. Indeed, each edge f : X → Y of a tree in our model represents a total function from node X to node Y ; and as such, each edge f can be seen as a set of key-value pairs (x, f (x)) where x is the key and f (x) is the value. Therefore, in principle, it should be possible to store the key-value pairs of a tree database using a key-value store. We envisage this as a long term perspective of our present work. Our current work develops along a number of research lines that we describe succinctly below: Query rewriting: Since our model is purely functional, the functional algebra provides the appropriate framework for studying query rewriting. We have given two examples of such rewriting, namely traversal query rewriting based on the fact that composition distributes over pairing (Section 4) and analytic query rewriting based on the composition rule (Section 5.2). However, more work is needed in order 38

to develop a complete rewriting system for optimizing the evaluation of traversal and analytic queries. Updating: Adding or removing a key-value pair (x, f (x)) in an edge f while preserving function totality may provoke updates in other edges of a tree (and eventually in all edges). Hence the need for efficient algorithms for the propagation of updates throughout the database. Additionally, such algorithms will have to take into account the eventual presence of the two types of integrity constraints that we have seen, namely refinement constraints and set theoretic constraints (see Section 2.3) - as well as constraints due to the presence of Isa edges in the database. Designing algorithms that allow updating a tree database while satisfying all database constraints is an important theme that needs further work. Inheritance: Our intention in this paper was to simply show that our model can support classical inheritance in a seamless manner. We did so by considering trees that are disjoint. However, the concept of inheritance can be generalized to trees that are not disjoint. Indeed, even if two trees T and T ′ share one or more nodes they might have subtrees which are disjoint. For example, a subtree of T might be disjoint with T ′ (or vice versa); or there might be pairs of subtrees (one in each tree) that are disjoint. Such subtrees can be obtained by projections and/or decompositions (see Section 3.4). So the problem here can be stated as follows: given a set of trees (e.g. those in a tree database) use projection and or decomposition to find a (new) set of trees of interest connected through Isa edges and offering to the user a ‘web of trees’ in which each Isa edge from a tree τ to a tree τ ′ ‘imports’ or ‘adds’ in τ the information contained in τ ′ . In such a web of trees the Isa edges act as ‘hyperlinks’ similar to those in the World Wide Web. Our current work aims at defining such webs of trees having specified properties and serving specific application environments (e.g. organized online collections of documents, books, audio, video, and other multimedia files that users can access electronically). Tree database design We have seen that a tree database is a set of trees representing the datasets of an application and their relationships. Clearly there might be several choices of trees to put in the database - following a set of criteria (e.g. small trees with an easy to grasp structure versus larger trees expressing the structure of the application). Hence the question: given a set of trees representing an application how can one find an ’equivalent’ set of trees satisfying a set criteria? To this end one would obviously need to use the tree algebra which allows to decompose large trees to smaller trees or to compose small trees to create larger ones. Of equal importance is the question: what criteria should one use? (e.g. one criterion used in the relational database design is that of ‘lossless decomposition’). Revisiting relational model theory: In the previous section, we have seen how a consistent relational database can be defined on top of a tree database. We have also seen how we can use the functional algebra to ‘simulate’ Armstrong’s axioms (Section 2.2, Lemma 3). In view of these results it is natural to revisit relational database theory and get new insights into functional dependency theory as well as into schema design theory for relational databases.

39

Data visualization: We are currently investigating the development of a visualization model, proper to tree databases, following the concepts introduced in previous work[16]. Such a model should allow the visualization and visual exploration of query results. As a longer term project, we envisage the design and implementation of a fullfledged tree-database management system in which storing, accessing and analyzing data is based on the concept of tree as the basic data structure. Such a system should also provide support for inheritance through tree composition, for interfacing relational data warehouses and for the visualization and visual exploration of query results.

Acknowledgements The author would like to thank Professor Dominique Laurent for his comments that helped improve the content of this paper.

References 1. Renzo Angles, Marcelo Arenas, Pablo Barceló, Aidan Hogan, Juan L. Reutter, and Domagoj Vrgoc. Foundations of modern graph query languages. CoRR, abs/1610.06264, 2016. 2. Sydney Anuyah, Victor Bolade, and Oluwatosin Agbaakin. Understanding graph databases: A comprehensive tutorial and survey, 2024. 3. Marcelo Arenas, Claudio Gutierrez, and Juan F. Sequeda. Querying in the age of graph databases and knowledge graphs. In Guoliang Li, Zhanhuai Li, Stratos Idreos, and Divesh Srivastava, editors, SIGMOD ’21: International Conference on Management of Data, Virtual Event, China, June 20-25, 2021, pages 2821–2828. ACM, 2021. 4. William Ward Armstrong. Dependency structures of data base relationships. In Jack L. Rosenfeld, editor, Information Processing, Proceedings of the 6th IFIP Congress 1974, Stockholm, Sweden, August 5-10, 1974, pages 580–583. North-Holland, 1974. 5. Diogo Fernandes and Jorge Bernardino. Graph databases comparison: Allegrograph, arangodb, infinitegraph, neo4j, and orientdb. In Jorge Bernardino and Christoph Quix, editors, Proceedings of the 7th International Conference on Data Science, Technology and Applications, DATA 2018, Porto, Portugal, July 26-28, 2018, pages 373–380. SciTePress, 2018. 6. Claudio Gutierrez, Jan Hidders, and Peter T. Wood. Graph data models. In Sherif Sakr and Albert Y. Zomaya, editors, Encyclopedia of Big Data Technologies. Springer, 2019. 7. Aidan Hogan. Knowledge graphs: A guided tour (invited paper). In Camille Bourgaux, Ana Ozaki, and Rafael Peñaloza, editors, International Research School in Artificial Intelligence in Bergen, AIB 2022, June 7-11, 2022, University of Bergen, Norway, volume 99 of OASIcs, pages 1:1–1:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. 8. Aidan Hogan, Eva Blomqvist, Michael Cochez, Claudia d’Amato, Gerard de Melo, Claudio Gutierrez, Sabrina Kirrane, José Emilio Labra Gayo, Roberto Navigli, Sebastian Neumaier, Axel-Cyrille Ngonga Ngomo, Axel Polleres, Sabbir M. Rashid, Anisa Rula, Lukas Schmelzeisen, Juan F. Sequeda, Steffen Staab, and Antoine Zimmermann. Knowledge graphs. ACM Comput. Surv., 54(4):71:1–71:37, 2022. 9. Dominique Laurent and Nicolas Spyratos. Rewriting aggregate queries using functional dependencies. In William I. Grosky, Youakim Badr, and Richard Chbeir, editors, MEDES ’11: International ACM Conference on Management of Emergent Digital EcoSystems, San Francisco, CA, USA, November 21-24, 2011, pages 40–47. ACM, 2011. 10. David Maier. The Theory of Relational Databases. Computer Science Press, 1983. 11. Maria-Evangelia Papadaki, Nicolas Spyratos, and Yannis Tzitzikas. Towards interactive analytics over RDF graphs. Algorithms, 14(2):34, 2021.

40

12. Evaggelia Pitoura. Query optimization. In Ling Liu and M. Tamer Özsu, editors, Encyclopedia of Database Systems, Second Edition. Springer, 2018. 13. Jaroslav Pokorný. Graph databases: Their power and limitations. In Khalid Saeed and Wladyslaw Homenda, editors, Computer Information Systems and Industrial Management - 14th IFIP TC 8 International Conference, CISIM 2015, Warsaw, Poland, September 24-26, 2015. Proceedings, volume 9339 of Lecture Notes in Computer Science, pages 58–69. Springer, 2015. 14. Nicolas Spyratos. The context model: A graph database model. CoRR, abs/2305.13895, 2023. 15. Nicolas Spyratos and Tsuyoshi Sugibuchi. HIFUN - a high level functional query language for big data analytics. J. Intell. Inf. Syst., 51(3):529–555, 2018. 16. Nicolas Spyratos and Tsuyoshi Sugibuchi. Data exploration in the HIFUN language. In Alfredo Cuzzocrea, Sergio Greco, Henrik Legind Larsen, Domenico Saccà, Troels Andreasen, and Henning Christiansen, editors, Flexible Query Answering Systems - 13th International Conference, FQAS 2019, Amantea, Italy, July 2-5, 2019, Proceedings, volume 11529 of Lecture Notes in Computer Science, pages 176–187. Springer, 2019. 17. Michael Stonebraker. SQL databases v. nosql databases. Commun. ACM, 53(4):10–11, 2010. 18. Antero Taivalsaari. On the notion of inheritance. ACM Comput. Surv., 28(3):438–479, 1996. 19. Jeffrey D. Ullman. Universal relation interfaces for database systems. In R. E. A. Mason, editor, Information Processing 83, Proceedings of the IFIP 9th World Computer Congress, Paris, France, September 19-23, 1983, pages 243–252. North-Holland/IFIP, 1983. 20. Jeffrey D. Ullman. Principles of Databases and Knowledge-Base Systems, volume 1-2. Computer Science Press, 1988. 21. Katerina Vitsaxaki, Stavroula Ntoa, George Margetis, and Nicolas Spyratos. Interactive visual exploration of big relational datasets. International Journal of Human–Computer Interaction, 2022. 22. Jim Waldo. Controversy: The case for multiple inheritance in C++. Comput. Syst., 4(2):157–171, 1991. 23. Yanhao Wang, Yuchen Li, Ju Fan, Chang Ye, and Mingke Chai. A survey of typical attributed graph queries. World Wide Web (New York), 24:297–346, January 2021. 24. Gio Wiederhold. Mediation in information systems. ACM Comput. Surv., 27(2):265–267, 1995. 25. Petros Zervoudakis, Haridimos Kondylakis, Nicolas Spyratos, and Dimitris Plexousakis. Query rewriting for incremental continuous query evaluation in HIFUN. Algorithms, 14(5):149, 2021.

41

Related documents

• Introduction: Tree#623310
• Database trap trees#1016778
• Prescriptive analytics in operations problems : a tree ensemble approach#284695
• M 1.6 - 16 km E of Seven Trees, CA#782256
• Your Family Tree: How to Begin#641792