The Experts below are selected from a list of 10509 Experts worldwide ranked by ideXlab platform
Joe Celko - One of the best experts on this subject based on the ideXlab platform.
-
Chapter 28 – Trees and Hierarchies in SQL
Joe Celko's SQL for Smarties, 2015Co-Authors: Joe CelkoAbstract:A tree is a special kind of directed graph. Graphs are data structures that are made up of nodes connected by edges. There are several ways to define a tree: it is a graph with no cycles and it is a graph where all nodes except the root have indegree one and the root has indegree zero. Another defining property is that a path can be found from the root to any other node in the tree by following the edges in their natural direction. Most Structured Query Language (SQL) databases use the adjacency list Model for two reasons. The first reason is that Dr. Codd came up with it in the early days of the relational Model, and nobody thought about it after that. The second reason is that the adjacency list is a way of “faking” pointer chains—the traditional programming method in procedural languages for handling trees. Because SQL is a Set-oriented language, the Nested Set Model is a better Model for the approach discussed in this chapter.
-
Other Models for Trees
Joe Celko's Trees and Hierarchies in SQL for Smarties, 2012Co-Authors: Joe CelkoAbstract:The chapter discusses the Models that use different approaches and properties of trees, some of which are hybrids of other Models. These Models include Models such as adjacency list with self-references and subordinate adjacency list. Subordinate adjacency list is a modification of the usual adjacency list Model and shows the edges of a graph as oriented from the superior to the subordinate. Nodes without a subordinate are leaf nodes, and they have a null value. Adjacency list with self-references are also slight modification of the usual adjacency list Model and include an edge that loops back to the same node. The chapter also discusses hybrid moles, such as adjacency and Nested Sets Model, Nested Set with depth Model, adjacency and depth Model, and computed hybrid Models. The chapter also discusses the problem of inability of the Nested Set Model to represent more a general graph in SQL.
-
37 – Graphs in SQL
Joe Celko's SQL for Smarties, 2011Co-Authors: Joe CelkoAbstract:Publisher Summary This chapter focuses on the use of graphs in SQL. Graphs are a general way to represent various types of data and their relationships and they are made up of nodes connected by edges, which can be directed or undirected. The most common way to Model a graph in SQL is with an adjacency list Model where each edge of the graph is shown as a pair of nodes in which the ordering matters, and then any values associated with that edge is shown in another column. Many graph algorithms are based on the adjacency matrix Model and can be translated into SQL. The Split Node Nested Set Models for Graphs is a specialized trick for a certain class of graphs where an acyclic directed graph is loaded into a Nested Set Model by splitting the nodes. The acyclic graph becomes a tree, but with duplicated node values, and it is mainly useful when one wants to avoid recursion.
-
Trees and Hierarchies in SQL
Joe Celko's SQL for Smarties, 2011Co-Authors: Joe CelkoAbstract:This chapter focuses on the three major approaches used for Modeling trees and hierarchies in SQL. A tree is a special kind of directed graph where the top of the tree is called the root. It is a graph with no cycles and where all nodes except the root have indegree 1 and the root has indegree zero. Another defining property is that a path can be found from the root to any other node in the tree by following the edges in their natural direction. The adjacency list Model is both the most common and the worst possible tree Model, which is the best way to Model any general graph. The Path Enumeration Model stores the path from the root to each node as a string at that node. In the Nested Set Model of Hierarchies, the left and right columns are the count of the “tags” in an XML representation of a tree and they have a definite meaning and carry information about the location and nature of each subtree.
-
Chapter 28 – Trees and Hierarchies in SQL
Joe Celko's SQL for Smarties, 2005Co-Authors: Joe CelkoAbstract:Publisher Summary A tree is a special kind of directed graph. Graphs are data structures that are made up of nodes connected by edges. There are several ways to define a tree: it is a graph with no cycles and it is a graph where all nodes except the root have indegree one and the root has indegree zero. Another defining property is that a path can be found from the root to any other node in the tree by following the edges in their natural direction. Most Structured Query Language (SQL) databases use the adjacency list Model for two reasons. The first reason is that Dr. Codd came up with it in the early days of the relational Model, and nobody thought about it after that. The second reason is that the adjacency list is a way of “faking” pointer chains—the traditional programming method in procedural languages for handling trees. Because SQL is a Set-oriented language, the Nested Set Model is a better Model for the approach discussed in this chapter.
Gianmaria Silvello - One of the best experts on this subject based on the ideXlab platform.
-
A Set-Based Approach to Deal with Hierarchical Structures
2011Co-Authors: Gianmaria SilvelloAbstract:Hierarchical structures are pervasive in computer science because they are a fundamental means for Modeling many aspects of reality and for representing and managing a wide corpus of data and digital resources. One of the most important hierarchical structures is the tree, which has been widely studied, analyzed and adopted in several contexts and scientific fields over time. Our work takes into major consideration the role and impact of the tree in computer science and investigates its applications starting from the following pivotal question: "Is the tree always the most advantageous choice for Modeling, representing and managing hierarchies?" Our aim is to analyze the nature and use of hierarchical structures and determine the most suitable way of employing them in different contexts of interests. We concentrate our work mainly on the scientific field of Digital Libraries. Digital Libraries are the compound and complex systems which manage digital resources from our cultural heritage – belonging to different cultural organizations such as libraries, archives and museums – and which provide advanced services over these digital resources. In particular, we point out a focal use case within this scientific field based on the Modeling, representation, management and exchange of archival resources in a distributed environment. We take into consideration the hierarchical inner structure of archives by considering the solutions proposed in the literature for Modeling, representing, managing and sharing the archival resources. Archives are usually Modeled by means of a tree structure; furthermore, the standard de facto for digital encoding of digital cultural resources – described and represented by means of metadata – is the eXtensible Markup Language (XML) that supports a tree representation. The problem often affecting this approach is that the Model used to represent the hierarchies is bounded by the specific technology of choice adopted for its instantiation – e.g. the XML. In the archival context the tree structure is commonly instantiated by means of a unique XML file which mixes up the hierarchical structure elements with the content elements, without a clear distinction between the two; it is then not straightforward to determine how to access and exchange a specific subSet of data without navigating the whole hierarchy or without losing meaningful hierarchical relationships. To address the problems exemplified in the previous scenario we propose the Nested Set for Object hieRarchies (NESTOR) Framework which is composed of two main components: the NESTOR Model and the NESTOR Prototype. The NESTOR Model is the core of the NESTOR Framework because it defines the Set data Models on which every component of the framework relies. It defines two Set data Models that we have called the "Nested Set Model (NS-M)" and the "Inverse Nested Set Model (INS-M)". We formally define these two Set data Models by showing how we can Model and represent hierarchies throughout collections of Nested Sets. We show how these Models add some features with respect to the tree while maintaining its full expressive power. We formally prove several properties of these Models and show the correspondences with the tree. Furthermore, we define four distance measures for the the NS-M and the INS-M and we prove them to be metric spaces. The NESTOR Model is presented from a formal point-of-view and then envisioned in a practical application context defined by the NESTOR Prototype. In order to describe the prototype we rely on the archive use case, and propose an application for Modeling, representing, managing and sharing of archival resources. The expressive power of the archive Modeled by means of a tree and the Set data Models are compared. We analyze the advantages and disadvantages of our approach when data management and exchange in distributed environments have to be faced. We provide a concrete implementation of the described Models in the context of the informative system called SIAR (Sistema Informativo Archivistico Regionale) that we designed and developed for the management of the archival resources of the Italian Veneto Region. Furthermore, we show how the NESTOR Framework can be used in conjunction with well-established and widely-used Digital Libraries technological advances.
-
the nestor framework manage access and exchange hierarchical datastructures
SEBD, 2010Co-Authors: Maristella Agosti, Nicola Ferro, Gianmaria SilvelloAbstract:In this paper we study the problem of representing, managing and exchanging hierarchically structured data in the context of a Digital Library (DL). We present the Nested Sets for Object hieRarchies (NESTOR) framework defining two Set data Models that we call: the “Nested Set Model (NS-M)” and the “Inverse Nested Set Model (INSM)” based on the organization of Nested Sets which enable the representation of hierarchical data structures. We present the mapping between the tree data structure to NS-M and to INS-M. Furthermore, we shall show how these Set data Models can be used in conjunction with Open Archives Initiative Protocol for Metadata Harvesting (OAI-PMH) adding new functionalities to the protocol without any change to its basic functioning. At the end we shall present how the couple OAI-PMH and the Set data Models can be used to represent and exchange archival metadata in a distributed environment.
-
SEBD - The NESTOR Framework: Manage, Access and Exchange Hierarchical DataStructures.
2010Co-Authors: Maristella Agosti, Nicola Ferro, Gianmaria SilvelloAbstract:In this paper we study the problem of representing, managing and exchanging hierarchically structured data in the context of a Digital Library (DL). We present the Nested Sets for Object hieRarchies (NESTOR) framework defining two Set data Models that we call: the “Nested Set Model (NS-M)” and the “Inverse Nested Set Model (INSM)” based on the organization of Nested Sets which enable the representation of hierarchical data structures. We present the mapping between the tree data structure to NS-M and to INS-M. Furthermore, we shall show how these Set data Models can be used in conjunction with Open Archives Initiative Protocol for Metadata Harvesting (OAI-PMH) adding new functionalities to the protocol without any change to its basic functioning. At the end we shall present how the couple OAI-PMH and the Set data Models can be used to represent and exchange archival metadata in a distributed environment.
-
the nestor framework how to handle hierarchical data structures
European Conference on Research and Advanced Technology for Digital Libraries, 2009Co-Authors: Nicola Ferro, Gianmaria SilvelloAbstract:In this paper we study the problem of representing, managing and exchanging hierarchically structured data in the context of a Digital Library (DL). We present the Nested Sets for Object hieRarchies (NESTOR) framework defining two Set data Models that we call: the "Nested Set Model (NS-M)" and the "Inverse Nested Set Model (INSM)" based on the organization of Nested Sets which enable the representation of hierarchical data structures. We present the mapping between the tree data structure to NS-M and to INS-M. Furthermore, we shall show how these Set data Models can be used in conjunction with Open Archives Initiative Protocol for Metadata Harvesting (OAI-PMH) adding new functionalities to the protocol without any change to its basic functioning. At the end we shall present how the couple OAI-PMH and the Set data Models can be used to represent and exchange archival metadata in a distributed environment.
-
Web Intelligence - Access and Exchange of Hierarchically Structured Resources on the Web with the NESTOR Framework
2009 IEEE WIC ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology, 2009Co-Authors: Maristella Agosti, Nicola Ferro, Gianmaria SilvelloAbstract:The paper addresses the problem of representing, managing and exchanging hierarchically structured data in the context of Digital Library (DL) systems in order to enhance the access and exchange DL resources on the Web. We propose the Nested Sets for Object hieRarchies (NESTOR) framework, which relies on two Set data Models — the “Nested Set Model (NS-M)” and the “Inverse Nested Set Model (INS-M)” — to enable the representation of hierarchical data structures by means of a proper organization of Nested Sets. In particular, we show how NESTOR can be effectively exploited to enhance Open Archives Initiative Protocol for Metadata Harvesting (OAI-PMH) for better access and exchange of hierarchical resources on the Web.
Ali Shokoufandeh - One of the best experts on this subject based on the ideXlab platform.
-
A new rapid watershed delineation algorithm for 2D flow direction grids
Environmental Modelling & Software, 2018Co-Authors: Scott Haag, Bahareh Shakibajahromi, Ali ShokoufandehAbstract:Abstract In this paper we propose an algorithm for retrieving an arbitrary watershed boundary from a 2D Flow Direction Grid. The proposed algorithm and associated data Model provides geometric speed increases in watershed boundary retrieval while keeping storage constraints linear in comparison to existing techniques. The algorithm called Watershed Marching Algorithm (WMA) relies on an existing data structure, the modified Nested Set Model, originally described by Celko and applied to hydrodynamic Models by Haag and Shokoufandeh in 2017. In contrast to existing algorithms that scale proportionally to the area of the underlying region, the complexity of the WMA algorithm is proportional to the boundary length. Results for a group of tested watersheds (n = 14,718) in the ≈ 36,000 km2 Delaware River Watershed show a reduction of between 0 and 99% in computational complexity using a 30 m DEM vs. existing techniques.
-
A Watershed Delineation Algorithm for 2D Flow Direction Grids.
arXiv: Data Structures and Algorithms, 2017Co-Authors: Scott Haag, Ali ShokoufandehAbstract:In this paper we propose an algorithm and associated data Model for creating a watershed boundary using a 2D Flow Direction Grid. Flow Direction Grids (FDGs) are common abstractions for hydrodynamic Models and are utilized for delineating physical systems (e.g. watersheds, fluvial, and non-fluvial flow paths). The proposed algorithm and associated data Model provides geometric speed increases in watershed boundary retrieval while keeping storage constraints linear in comparison to existing techniques. The algorithm called Haag Shokoufandehs' March (HSM) relies on an existing data structure, the modified Nested Set Model, originally described by Celko and applied to hydrodynamic Models by Haag and Shokoufandeh in 2017. The proposed algorithm creates watershed boundaries by marching around the edges of its' corresponding region, never entering the internal area. In contrast to existing algorithms that scales in proportional to the area of the underlying region, the complexity of the HSM algorithm is proportional to the boundary length. Results for a group of tested watersheds (n = 14,718) in the approximately 36,000 km^2 Delaware River Watershed show a reduction of between 0 and 99% in computational complexity using a 30 m DEM vs. existing techniques. Larger watersheds have a consistent reduction in the number of (read) operation complexity, with the largest watershed resulting in approximately 35 million reads using traditional techniques compared to approximately 45 thousand using the HSM algorithm, respectively. Modelled estimates of the complexity for the approximately 6.1 million km^2 Amazon River basin show a reduction from 6.7 billion to 1.4 million reads.
Scott Haag - One of the best experts on this subject based on the ideXlab platform.
-
A new rapid watershed delineation algorithm for 2D flow direction grids
Environmental Modelling & Software, 2018Co-Authors: Scott Haag, Bahareh Shakibajahromi, Ali ShokoufandehAbstract:Abstract In this paper we propose an algorithm for retrieving an arbitrary watershed boundary from a 2D Flow Direction Grid. The proposed algorithm and associated data Model provides geometric speed increases in watershed boundary retrieval while keeping storage constraints linear in comparison to existing techniques. The algorithm called Watershed Marching Algorithm (WMA) relies on an existing data structure, the modified Nested Set Model, originally described by Celko and applied to hydrodynamic Models by Haag and Shokoufandeh in 2017. In contrast to existing algorithms that scale proportionally to the area of the underlying region, the complexity of the WMA algorithm is proportional to the boundary length. Results for a group of tested watersheds (n = 14,718) in the ≈ 36,000 km2 Delaware River Watershed show a reduction of between 0 and 99% in computational complexity using a 30 m DEM vs. existing techniques.
-
A Watershed Delineation Algorithm for 2D Flow Direction Grids.
arXiv: Data Structures and Algorithms, 2017Co-Authors: Scott Haag, Ali ShokoufandehAbstract:In this paper we propose an algorithm and associated data Model for creating a watershed boundary using a 2D Flow Direction Grid. Flow Direction Grids (FDGs) are common abstractions for hydrodynamic Models and are utilized for delineating physical systems (e.g. watersheds, fluvial, and non-fluvial flow paths). The proposed algorithm and associated data Model provides geometric speed increases in watershed boundary retrieval while keeping storage constraints linear in comparison to existing techniques. The algorithm called Haag Shokoufandehs' March (HSM) relies on an existing data structure, the modified Nested Set Model, originally described by Celko and applied to hydrodynamic Models by Haag and Shokoufandeh in 2017. The proposed algorithm creates watershed boundaries by marching around the edges of its' corresponding region, never entering the internal area. In contrast to existing algorithms that scales in proportional to the area of the underlying region, the complexity of the HSM algorithm is proportional to the boundary length. Results for a group of tested watersheds (n = 14,718) in the approximately 36,000 km^2 Delaware River Watershed show a reduction of between 0 and 99% in computational complexity using a 30 m DEM vs. existing techniques. Larger watersheds have a consistent reduction in the number of (read) operation complexity, with the largest watershed resulting in approximately 35 million reads using traditional techniques compared to approximately 45 thousand using the HSM algorithm, respectively. Modelled estimates of the complexity for the approximately 6.1 million km^2 Amazon River basin show a reduction from 6.7 billion to 1.4 million reads.
Nicola Ferro - One of the best experts on this subject based on the ideXlab platform.
-
the nestor framework manage access and exchange hierarchical datastructures
SEBD, 2010Co-Authors: Maristella Agosti, Nicola Ferro, Gianmaria SilvelloAbstract:In this paper we study the problem of representing, managing and exchanging hierarchically structured data in the context of a Digital Library (DL). We present the Nested Sets for Object hieRarchies (NESTOR) framework defining two Set data Models that we call: the “Nested Set Model (NS-M)” and the “Inverse Nested Set Model (INSM)” based on the organization of Nested Sets which enable the representation of hierarchical data structures. We present the mapping between the tree data structure to NS-M and to INS-M. Furthermore, we shall show how these Set data Models can be used in conjunction with Open Archives Initiative Protocol for Metadata Harvesting (OAI-PMH) adding new functionalities to the protocol without any change to its basic functioning. At the end we shall present how the couple OAI-PMH and the Set data Models can be used to represent and exchange archival metadata in a distributed environment.
-
SEBD - The NESTOR Framework: Manage, Access and Exchange Hierarchical DataStructures.
2010Co-Authors: Maristella Agosti, Nicola Ferro, Gianmaria SilvelloAbstract:In this paper we study the problem of representing, managing and exchanging hierarchically structured data in the context of a Digital Library (DL). We present the Nested Sets for Object hieRarchies (NESTOR) framework defining two Set data Models that we call: the “Nested Set Model (NS-M)” and the “Inverse Nested Set Model (INSM)” based on the organization of Nested Sets which enable the representation of hierarchical data structures. We present the mapping between the tree data structure to NS-M and to INS-M. Furthermore, we shall show how these Set data Models can be used in conjunction with Open Archives Initiative Protocol for Metadata Harvesting (OAI-PMH) adding new functionalities to the protocol without any change to its basic functioning. At the end we shall present how the couple OAI-PMH and the Set data Models can be used to represent and exchange archival metadata in a distributed environment.
-
the nestor framework how to handle hierarchical data structures
European Conference on Research and Advanced Technology for Digital Libraries, 2009Co-Authors: Nicola Ferro, Gianmaria SilvelloAbstract:In this paper we study the problem of representing, managing and exchanging hierarchically structured data in the context of a Digital Library (DL). We present the Nested Sets for Object hieRarchies (NESTOR) framework defining two Set data Models that we call: the "Nested Set Model (NS-M)" and the "Inverse Nested Set Model (INSM)" based on the organization of Nested Sets which enable the representation of hierarchical data structures. We present the mapping between the tree data structure to NS-M and to INS-M. Furthermore, we shall show how these Set data Models can be used in conjunction with Open Archives Initiative Protocol for Metadata Harvesting (OAI-PMH) adding new functionalities to the protocol without any change to its basic functioning. At the end we shall present how the couple OAI-PMH and the Set data Models can be used to represent and exchange archival metadata in a distributed environment.
-
Web Intelligence - Access and Exchange of Hierarchically Structured Resources on the Web with the NESTOR Framework
2009 IEEE WIC ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology, 2009Co-Authors: Maristella Agosti, Nicola Ferro, Gianmaria SilvelloAbstract:The paper addresses the problem of representing, managing and exchanging hierarchically structured data in the context of Digital Library (DL) systems in order to enhance the access and exchange DL resources on the Web. We propose the Nested Sets for Object hieRarchies (NESTOR) framework, which relies on two Set data Models — the “Nested Set Model (NS-M)” and the “Inverse Nested Set Model (INS-M)” — to enable the representation of hierarchical data structures by means of a proper organization of Nested Sets. In particular, we show how NESTOR can be effectively exploited to enhance Open Archives Initiative Protocol for Metadata Harvesting (OAI-PMH) for better access and exchange of hierarchical resources on the Web.
-
ECDL - The NESTOR framework: how to handle hierarchical data structures
Research and Advanced Technology for Digital Libraries, 2009Co-Authors: Nicola Ferro, Gianmaria SilvelloAbstract:In this paper we study the problem of representing, managing and exchanging hierarchically structured data in the context of a Digital Library (DL). We present the Nested Sets for Object hieRarchies (NESTOR) framework defining two Set data Models that we call: the "Nested Set Model (NS-M)" and the "Inverse Nested Set Model (INSM)" based on the organization of Nested Sets which enable the representation of hierarchical data structures. We present the mapping between the tree data structure to NS-M and to INS-M. Furthermore, we shall show how these Set data Models can be used in conjunction with Open Archives Initiative Protocol for Metadata Harvesting (OAI-PMH) adding new functionalities to the protocol without any change to its basic functioning. At the end we shall present how the couple OAI-PMH and the Set data Models can be used to represent and exchange archival metadata in a distributed environment.