A Set-Based Approach to Deal with Hierarchical Structures

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.Le strutture gerarchiche sono largamente utilizzate in informatica in quanto mezzi fondamentali per modellare molti aspetti della realtà e per rappresentare nonché gestire una grande varietà di dati e risorse digitali. Una delle strutture gerarchiche più rilevanti è l'albero, una struttura ampiamente studiata, analizzata e adottata in diversi contesti scientifici. Questo lavoro tiene in grande considerazione il ruolo e l'impatto della struttura ad albero in informatica e ne studia le applicazioni a partire dalla seguente domanda: "La struttura ad albero è sempre il modo più vantaggioso per modellare, rappresentare e gestire le gerarchie?" A tal proposito ci si propone di analizzare la natura e l'uso delle strutture gerarchiche e di determinare il modo più adeguato per impiegarle nei diversi contesti considerati. Il lavoro si focalizza principalmente sul campo scientifico delle biblioteche digitali, ossia su quei sistemi composti e complessi che gestiscono risorse digitali culturali, provenienti da organizzazioni differenti quali biblioteche, archivi e musei e che definiscono servizi avanzati su tali risorse. In particolare, il caso d'uso principale su cui è basato questo lavoro è la modellazione, la rappresentazione, la gestione e la condivisione delle risorse di tipo archivistico in ambiente distribuito. Si considera quindi la struttura gerarchica degli archivi tenendo presente le soluzioni per modellare, rappresentare, gestire e condividere le risorse archivistiche allo stato dell'arte. Gli archivi sono solitamente modellati mediante una struttura ad albero; inoltre, lo standard di fatto per la codifica delle risorse culturali digitali descritte e rappresentate per mezzo di metadati è l'XML che supporta la rappresentazione ad albero.%; tale approccio tuttavia utilizza un modello per rappresentare le gerarchie spesso legato alla specifica tecnologia scelta per la sua istanziazione, ad esempio l'XML. Nel contesto archivistico la struttura ad albero è comunemente istanziata mediante un unico file XML che, per come è definito e comunemente utilizzato, mischia elementi strutturali e di contenuto senza permettere una chiara distinzione tra di loro. Di fatto, non è facilmente definibile l'accesso e lo scambio di sottoinsiemi di dati e risorse senza costringere alla navigazione di tutta la gerarchia o senza perdere le significative relazioni gerarchiche tra le varie componenti. Per affrontare i problemi esemplificati nel precedente scenario si propone il NEsted SeT for Object hieRarchies (NESTOR) Framework composto da due componenti principali: Il NESTOR Model e il NESTOR Prototype. Il NESTOR Model è il nucleo del framework perché definisce i modelli ad insiemi su cui ogni componente del framework si basa. Il NESTOR Model definisce due modelli dati basati su insiemi annidati: il "Nested Set Model (NS-M)" e l' "Inverse Nested Set Model (INS-M)". Questi modelli sono definiti formalmente mostrando come sia possibile modellare e rappresentare gerarchie mediante collezioni di insiemi annidati. Si dimostra come questi modelli aggiungano alcune caratteristiche rispetto alla struttura ad albero, mantenendone il potere espressivo. Si dimostrano formalmente diverse proprietà dei modelli ad insiemi e si mostrano le corrispondenze con la struttura ad albero. Si definiscono inoltre quattro misure di distanza per il NS-M e l'INS-M dimostrando come questi possano essere definiti come spazi metrici. Il NESTOR Model è presentato da un punto di vista formale e successivamente adottato in un concreto contesto applicativo definito dal NESTOR Prototype. Per descrivere il NESTOR Prototype ci si basa sul caso d'uso degli archivi, proponendo un'applicazione per modellare, rappresentare, gestire e scambiare le risorse archivistiche. Il potere espressivo degli archivi modellati mediante l'albero e modellati mediante i modelli dati ad insiemi sono confrontati. Si analizzano i vantaggi e gli svantaggi dell'approccio presentato quando deve essere affrontata la gestione e lo scambio delle risorse in ambiente distribuito. Si fornisce un'implementazione concreta dei modelli descritti nel contesto del sistema informativo chiamato SIAR (Sistema Informativo Archivistico Regionale), progettato e sviluppato per la gestione delle risorse archivistiche della Regione del Veneto. Inoltre, si mostra come il NESTOR Framework possa essere usato congiuntamente alle tecnologie definite e ampiamente utilizzate nel contesto delle biblioteche digitali per superare i problemi evidenziati dalle soluzioni allo stato dell'arte