The GraphDB Algebra: Specification of Advanced Data Models with Second-Order Signature
Published 1 January 1995
Ludger Becker, Ralf Hartmut Güting
Citations9
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
An algebraic description for the querying facilities of GraphDB is developed and second-order signature is used to specify the GraphDB data model and its algebra.
Abstract
A framework using so called second-order signature for the specification of database models has been presented in earlier work. The goal of this approach is to provide generic tools for the implementation of database systems, in particular for parsing and rule-based optimization and for execution of query plans, that can be used with widely varying data models and query languages. In this paper we apply this specification technique to the graph based data model GraphDB. We develop an algebraic description for the querying facilities of GraphDB and use second-order signature to specify the GraphDB data model and its algebra.
Keywords
Computer Science
ACM Computing SurveysOn understanding types, data abstraction, and polymorphism
1,675 Citations1985Luca Cardelli, Peter Wegner
A λ-calculus-based model for type systems that allows us to explore the interaction among the concepts of type, data abstraction, and polymorphism in a simple setting, unencumbered by complexities of production programming languages is developed.
IEEE Transactions on Knowledge and Data EngineeringThe implementation of POSTGRES
412 Citations1990Michael Stonebraker, Lawrence A. Rowe +1 more
The design and implementation decisions made for the three-dimensional data manager POSTGRES are discussed, and attention is restricted to the DBMS backend functions.
IEEE Transactions on Knowledge and Data EngineeringVolcano-an extensible and parallel query evaluation system
391 Citations1994Goetz Graefe
Volcano is the first implemented query execution engine that effectively combines extensibility and parallelism, and is extensible with new operators, algorithms, data types, and type-specific methods.
The Volcano optimizer generator: extensibility and efficient search
373 Citations2002Goetz Graefe, William J. McKenna
The Volcano project, which provides efficient, extensible tools for query and request processing, particularly for object-oriented and scientific database systems, is reviewed, and it is shown that the search engine of the Volcano optimizer generator is more extensible and powerful.
A graphical query language supporting recursion
255 Citations1987Isabel F. Cruz, Alberto O. Mendelzon +1 more
G is proposed as a complementary language in which recursive queries are simple to formulate, and it is hoped that this graphical query language can be able to exploit well-known graph algorithms in evaluating recursive queries efficiently, a topic which has received widespread attention recently.
IEEE Transactions on Knowledge and Data EngineeringStarburst mid-flight: as the dust clears (database project)
247 Citations1990Laura M. Haas, Wan Chang +8 more
The purpose of the Starburst project is to improve the design of relational database management systems and enhance their performance, while building an extensible system to better support nontraditional applications and to serve as a testbed for future improvements in database technology.
A query algebra for object-oriented databases
189 Citations2002Gail M. Shaw, Stanley B. Zdonik
An algebra that synthesizes relational query concepts with object-oriented databases is defined and support for object identity leads to new definitions for equality of results and operators that can manipulate the identities of objects.
GraphDB: Modeling and Querying Graphs in Databases
180 Citations1994Ralf Hartmut Güting
A data model and query language that integrates an explicit modeling and querying of graphs smoothly into a standard database environment and permits a natural representation and sophisticated querying of networks, in particular of spatially embedded networks like highways, public transport, etc.
IEEE Transactions on Knowledge and Data EngineeringA graph-oriented object database model
157 Citations1994Marc Gyssens, Jan Paredaens +2 more
ACM SIGMOD RecordDatabase programming in Machiavelli—a polymorphic language with static type inference
139 Citations1989Atsushi Ohori, Peter Buneman +1 more
ACM Transactions on Information SystemsQueries and query processing in object-oriented database systems
136 Citations1990David D. Straube, M. TAMER ÖZSU
A query processing methodology complete with an object calculus to object algebra translation are discussed in detail and an equivalence-preserving transformation rules for object algebra expressions are discussed.
IEEE Transactions on Knowledge and Data EngineeringThe DASDBS project: objectives, experiences, and future prospects
124 Citations1990Hans‐Jörg Schek, H.-B. Paul +2 more
A retrospective of the Darmstadt database system project, also known as DASDBS, is presented, aimed at providing data management support for advanced applications, such as geo-scientific information systems and office automation.
Algebraic support for complex objects with arrays, identity, and inheritance
94 Citations1991Scott Vandenberg, David J. DeWitt
Object identity is incorporated into the algebraic domains, giving an original, intuitive set-theoretic semantics for the domains of object identifiers in the presence of multiple inheritance.
Lecture notes in computer scienceA relational object model
91 Citations1990Marc H. Scholl, Hans‐Jörg Schek
This paper presents a powerful view definition facility that basically allows object views as well as relational views to be defined in the authors' object algebra, and shows an evolutionary path from relational, essentially nested relational, to object-oriented data models and query languages.
Journal of Functional ProgrammingA semantic basis for Quest
81 Citations1991Luca Cardelli, G. Longo
The type inference rules for Quest are described in detail, and the meaning of these rules are given using a partial equivalence relation model of types.
Information SystemsGras, a graph-oriented (software) engineering database system
74 Citations1995N. Kiesel, Andy Schuerr +1 more
The underlying data model and the functionality of GRAS, a database system which has been designed according to the requirements of software engineering, CAD, or office automation, are described.
ACM Transactions on Database SystemsRule-based optimization and query processing in an extensible geometric database system
70 Citations1992Ludger Becker, Ralf Hartmut Güting
This paper shows in particular how the special processing techniques of a geometric database systems, such as spatial join methods and geometric index structures, can be integrated into query processing and optimization of a relational database system.
Lecture notes in computer scienceExceeding the limits of polymorphism in database programming languages
46 Citations2005David Stemple, Leo Fegaras +2 more
The difficulty in achieving such power parsimoniously in polymorphism and reflection in database query languages is examined in this paper.
IEEE Transactions on Knowledge and Data EngineeringExplicit graphs in a functional model for spatial databases
43 Citations1994Martin Erwig, Ralf Hartmut Güting
A new data model and query language that especially supports graph structures is defined, which leads to powerful modeling and querying capabilities for spatial databases, in particular for spatially embedded networks such as highways, rivers, public transport, and so forth.
Lecture notes in computer scienceTypes for data-oriented languages
41 Citations1988Luca Cardelli
It is shown that kinds can provides a framework for relational and database-wide operations, for subtype relations, for schema computations, and perhaps even for schema evolution.
GRAS: a graph-oriented software engineering database system
21 Citations1996N. Kiesel, Andy Schürr +1 more
Computer LanguagesAn extension of SQL for querying graph relations
12 Citations1990Joachim Biskup, Uwe Räsch +1 more
A graph manipulation kernel is defined as an extension of SQL that has features to generate a basic set of paths, to select the relevant paths from it by some conditions, and to produce the desired output.
A type system that reconciles classes and extents
12 Citations1992Peter Buneman, Atsushi Ohori
A type system that naturally couples two different, and apparently contradictory, notions of inheritance that occur in object-oriented databases is presented and it offers a technique for dealing with external databases in a statically typed language.