SECONDO: an extensible DBMS architecture and prototype
Published 1 January 2004
Ralf Hartmut Güting, Thomas Behr, Victor Almeida, Zhiming Ding, F. Hoffmann, Markus Spiekermann
Citations44
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
A new algor for conjunctive query optimization is described which is remarkably simple, yet performs very well and emphasizes a technique for selectivity estimation suitable for an extensible envi ronment with complex algebras for non-standard data types.
Abstract
We describe SECONDO, an extensible DBMS platform suitable for building research prototypes and for teaching architecture and implementation of database systems. It does not have a fixed data model, but is open for implementation of new models. SECONDO consists of three major components which can be used together or independently: (i) the kernel, which offers query processing over a set of implemented algebras, each offering some type constructors and operators, (ii) the optimizer, which implements the essential part of an SQL-like language, and (iii) the graphical user interface which is extensible by viewers for new data types and which provides a sophisticated viewer for spatial and spatio-temporal (moving) objects. Examples of algebras implemented in SECONDO are relations, spatial data types, R-trees, or midi objects (music files), each with suitable operations. The kernel is extensible by algebras, the optimizer by optimization rules and cost functions, and the GUI by viewers and display functions. A highlight of the description is a new algorithm for conjunctive query optimization which is remarkably simple, yet performs very well. We also emphasize a technique for selectivity estimation suitable for an extensible environment with complex algebras for non-standard data types.
Keywords
Computer Science
Access path selection in a relational database management system
2,153 Citations1979Patricia G. Selinger, M. M. Astrahan +3 more
This paper describes how System R chooses access paths for both simple (single relation) and complex queries (such as joins) given a user specification of desired data as a boolean expression of predicates.
ACM Transactions on Database SystemsA foundation for representing and querying moving objects
756 Citations2000Ralf Hartmut Güting, Michael H. Böhlen +5 more
The paper formally defines the types and operations, offers detailed insight into the considerations that went into the design, and exemplifies the use of the abstract data types using SQL.
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.
IEEE Transactions on Knowledge and Data EngineeringSpatial SQL: a query and presentation language
376 Citations1994Max J. Egenhofer
The spatial query language has been designed as a minimal extension to the interrogative part of SQL and distinguishes from previously designed SQL extensions by: the preservation of SQL concepts; the high-level treatment of spatial objects; and the incorporation of spatial operations and relationships.
Accurate estimation of the number of tuples satisfying a condition
342 Citations1984Gregory Piatetsky-Shapiro, Charles W. Connell
A new method for estimating the number of tuples satisfying a condition of the type attribute rel constant, where rel is one of "=", ">", "<, "≥", "≤" , which gives highly accurate, yet easy to compute, estimates.
Practical selectivity estimation through adaptive sampling
276 Citations1990Richard J. Lipton, Jeffrey F. Naughton +1 more
This paper extends the previous analysis to provide significantly improved bounds on the amount of sampling necessary for a given level of accuracy and provides “sanity bounds” to deal with queries for which the underlying data is extremely skewed or the query result is very small.
Predicate migration
273 Citations1993Joseph M. Hellerstein, Michael Stonebraker
This paper develops a theory for moving expensive predicates in a query plan so that the total cost of the plan — including the costs of both joins and restrictions — is minimal, and presents an algorithm to implement the theory, as well as results of the implementation in POSTGRES.
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.
IEEE Transactions on Software EngineeringGENESIS: an extensible database management system
233 Citations1988D.S. Batoory, Jane Barnett +5 more
The authors are designing an extensible DBMS, called GENESIS, which is based on this theory, and give a detailed description of their first operational prototype.
The VLDB JournalModeling and querying moving objects in networks
232 Citations2005Ralf Hartmut Güting, Victor Teixeira de Almeida +1 more
The ADT approach is extended by modeling networks explicitly and providing data types for static and moving network positions and regions and the new types and operations are integrated seamlessly into the ADT framework to achieve a relatively simple, consistent and powerful overall model and query language for constrained and unconstrained movement.
ACM SIGMOD RecordSelectivity estimation in spatial databases
188 Citations1999Swarup Acharya, Viswanath Poosala +1 more
GeoInformaticaIndexing the Trajectories of Moving Objects in Networks*
183 Citations2005Victor Teixeira de Almeida, Ralf Hartmut G�ting
A new index structure for moving objects on networks, the MON-Tree is proposed in terms of the basic algorithms for insertion and querying and shows good scalabiliy and outperforms the competing index structures in updating (index creation) as well as in querying.
Adaptive selectivity estimation using query feedback
181 Citations1994Chungmin Melvin Chen, Nick Roussopoulos
Experimental results show that the estimation accuracy of this approach for estimating the record selectivities of database queries is comparable to traditional methods based on statistics gathering.
eScholarship (California Digital Library)Simple Random Sampling from Relational Databases
156 Citations1986Frank Olken, Doron Rotem
Sampling as a fundamental operation for the auditing and statistical analysis of large databases is discussed and how samples of relational queries can often be computed for a small fraction of the effort of computing the entire relational query is shown.
Minds at UW (University of Wisconsin)The EXODUS extensible DBMS project: an overview
129 Citations1989Michael J. Carey, David J. DeWitt +6 more
Gral: an extensible relational database system for geometric applications
119 Citations1989Ralf Hartmut Güting
The central concept is to use languages based on many-sorted algebra to represent queries as well as query execution plans that leads to a simple and clean extensible system architecture that eases the task of an application developer by providing a uniform framework, and also simplifies rule-based optimization.
The Computer JournalAlgorithms for Moving Objects Databases
116 Citations2003José Antonio Cotelo Lema
The goal is to develop data models and query languages as well as DBMS implementations supporting such entities, enabling new kinds of database applications.
Information SystemsEstimating record selectivities
111 Citations1983Stavros Christodoulakis
It is shown that certain assumptions-used for modelling data base contents, data placement on devices and user requests often are not satisfied in actual data base environments.
ACM SIGMOD RecordProcessing aggregate relational queries with hard time constraints
107 Citations1989Wen‐Chi Hou, Gültekin Özsoyoğlu +1 more
Rapid bushy join-order optimization with Cartesian products
91 Citations1996Bennet Vance, David Maier
The main contribution of the paper is in fully separating join-order enumeration from predicate analysis, and in showing that the former problem in particular can be solved swiftly by novel implementation techniques.
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.
Practical predicate placement
67 Citations1994Joseph M. Hellerstein
This paper explores the predicate placement options considered in the Montage DBMS, presenting a family of algorithms that form successively more complex and effective optimization solutions.
Second-order signature
65 Citations1993Ralf Hartmut Güting
A framework for the specification of extensible database systems using second-order signature (and algebra), a system of two coupled many-sorted signatures, where the top- level signature offers kinds and type constructors and the bottom-level signature provides polymorphic operations over the types defined as terms of the top level.
Plug and play with query algebras: SECONDO, a generic DBMS development environment
53 Citations2002Stefan Dieker, Ralf Hartmut Güting
This paper presents the system functionality, given by a uniform set of user commands that are valid for all data models, and the extensible system architecture, and describes the key strategies for extensible query processing in the SECONDO environment and explains the structure of the algebra modules.
The VLDB JournalEnhanced abstract data types in object-relational databases
39 Citations1998Praveen Seshadri
This paper argues that the “blackbox” ADTs used in current object-relational systems inhibit their performance, thereby limiting their use in emerging applications and should be based on enhanced abstract data type (E-ADT) technology.
Indexing the trajectories of moving objects in networks
36 Citations2004V. T. Almeida, Ralf Hartmut Güting
Query estimation by adaptive sampling
18 Citations2003Yi-Leh Wu, Divyakant Agrawal +1 more
This paper shows that the traditional estimation techniques with data reduction points of view do not produce satisfiable estimation results if the query patterns are dynamically changing and proposes query estimation techniques that can adapt to user query patterns for more accurate estimates of the size of selection or range queries over databases.
Lecture notes in computer scienceEfficient dynamic programming algorithms for ordering expensive joins and selections
17 Citations1998Wolfgang Scheufele, Guido Moerkotte
This work presents a formally derived and correct dynamic programming algorithm to compute optimal bushy processing trees for queries with expensive predicates and introduces unique solutions for efficiently computing the cost of the intermediate plans and for saving memory space by utilizing bitvector contraction.
Data & Knowledge EngineeringEfficient handling of tuples with embedded large objects
13 Citations2000Stefan Dieker, Ralf Hartmut Güting
A sound and general large object interface extension which automatically switches the representation of large objects according to their actual size is described, based upon a linear cost model.
Lecture notes in computer scienceSECONDO/QP: Implementation of a Generic Query Processor
11 Citations1999Ralf Hartmut Güting, Stefan Dieker +3 more
The solution presented here is particularly simple, elegant, and general, and for example, it is entirely independent from the data model being implemented, admits arbitrary parameter functions, and allows one to mix freely stream operators and other operators.