Normal view MARC view ISBD view

A graph based data structure for efficient implementation of main memory DBMS's / Philippe Pucheral, Jean-Marc Thevenin

Auteur principal : Pucheral, PhilippeCo-auteur : Thevenin, Jean-Marc, 1958-...., AuteurPublication : Le Chesnay, France : Institut National de Recherche en Informatique et en Automatique, 1989Description : 22 p. : ill. ; 30 cmDewey: 004Résumé : Abstract: "Considering that in future DBMS's it will be possible to hold the active database in main memory, a new physical database organization is proposed. This organization aims two objectives: be compact and decomposable such as the active database always fits in main memory and speed up extended relational algebra in term of CPU time. Tuples, indices and temporary results are integrated in a unique data structre called DBGraph. Tuples and values are stored separately and constitute the vertices of the DBGraph. Edges between tuples and values are maintained using OID's in order to constitute a bipartite graph. This graph precompiles selection, join and transitive closure operations; Set oriented execution of relational algebra is generated using a breadth first traversal of this graph while pipeline execution is produced using a depth first traversal. The two strategies lead to the same temporal complexity. Storage cost evaluations demonstrate the compactness of DBGraph. Peroformance evaluations show that in a main memory context transitive closure on DBGraph outperforms transitive closure on join indices, still considered as one of the best algorithm.Bibliographie: Includes bibliographical references..Sujet - Nom d'actualité : Bases de données -- Gestion ;Structures de données (informatique) Sujet : Base de données ;STRUCTURE DE DONNEES Sujet Catégorie : H-LOGICIEL
Current location Call number Status Date due Barcode
Centre de recherche en informatique
EM AI CI6160 Sur demande

Includes bibliographical references.

Abstract: "Considering that in future DBMS's it will be possible to hold the active database in main memory, a new physical database organization is proposed. This organization aims two objectives: be compact and decomposable such as the active database always fits in main memory and speed up extended relational algebra in term of CPU time. Tuples, indices and temporary results are integrated in a unique data structre called DBGraph. Tuples and values are stored separately and constitute the vertices of the DBGraph. Edges between tuples and values are maintained using OID's in order to constitute a bipartite graph. This graph precompiles selection, join and transitive closure operations

Set oriented execution of relational algebra is generated using a breadth first traversal of this graph while pipeline execution is produced using a depth first traversal. The two strategies lead to the same temporal complexity. Storage cost evaluations demonstrate the compactness of DBGraph. Peroformance evaluations show that in a main memory context transitive closure on DBGraph outperforms transitive closure on join indices, still considered as one of the best algorithm

Powered by Koha