page 1  (20 pages)
2to next section

Database Graph Views :

A Practical Model to Manage Persistent Graphs 1

Alejandro Guti?rrez ?? Philippe Pucheral ? Hermann Steffen ? Jean-Marc Th?venin ??

(?) University of Versailles (?) Universidad de la Rep?blica (??) University of Toulouse 1 PRiSM Laboratory 2 Computer Science Department IRIT / SIG Laboratory 78000 Versailles, France 11300 Montevideo, Uruguay 31042 Toulouse, France {gutier, pucheral}@prism.uvsq.fr steffen@fing.edu.uy thevenin@cix.cict.fr

Rapport de Recherche PRiSM n? 94/10, Mars 1994

Abstract
Advanced technical applications like routing systems or electrical network management systems introduce the need for complex manipulations of large size graphs. Efficiently supporting this requirement is now regarded as a key feature of future database systems. This paper proposes an abstraction mechanism, called Database Graph View, to define and manipulate various kinds of graphs stored in either relational, object oriented or file systems. A database graph view provides a functional definition of a graph which allows its manipulation independently of its physical organization. Derivation operators are proposed to define new graph views upon existing ones. These operators permit the composition, in a single graph view, of graphs having different node and edge types and different implementations. The graph view mechanism comes with an execution model where both setoriented and pipelined execution of graph operators can be expressed. The graph view operators form a library which can be integrated in database systems or applications managing persistent data with no repercussion on the data organization.

R?sum?
Des applications techniques avanc?es telles que les syst?mes de navigation routi?re ou les syst?mes d'entretien de r?seaux ?lectriques introduisent des traitements complexes sur des graphes volumineux. Le support efficace de ces traitements est un enjeu important des futurs syst?mes de bases de donn?es. Cet article propose un m?canisme d'abstraction appel? Database Graph View permettant la d?finition et la manipulation de graphes stock?s dans un syst?me relationnel, un syst?me orient? objet ou un syst?me de fichiers. Une vue de graphe offre une d?finition fonctionnelle d'un graphe qui permet sa manipulation ind?pendamment de sa repr?sentation physique. Des op?rateurs de d?rivation sont propos?s pour d?finir de nouvelles vues de graphes ? partir de celles d?j? d?finies. Ces op?rateurs peuvent composer dans un m?me graphe, plusieurs graphes ayant des types de noeuds et d'ar?tes diff?rents ainsi que des implantations diff?rentes. Le mod?le d'ex?cution associ? au m?canisme de vues de graphes supporte aussi bien l'ex?cution ensembliste que pipeline des op?rateurs de graphes. Ces op?rateurs forment une biblioth?que pouvant ?tre int?gr?e dans tout syst?me de bases de donn?es ou dans toute application manipulant des donn?es persistantes sans changement de la repr?sentation des donn?es.

Keywords: persistent graphs, database view definition, graph composition operators, query processing on graphs

1 This work is partially funded by the Esprit project IMPRESS n? 6355.?
2 Phone: +33 (1) 39.25.40.49 Fax: +33 (1) 39.25.40.57