Supporting Lists in a Data Model (A Timely Approach).
Joel E. Richardson:
Supporting Lists in a Data Model (A Timely Approach).
VLDB 1992: 127-138@inproceedings{DBLP:conf/vldb/Richardson92,
author = {Joel E. Richardson},
editor = {Li-Yan Yuan},
title = {Supporting Lists in a Data Model (A Timely Approach)},
booktitle = {18th International Conference on Very Large Data Bases, August
23-27, 1992, Vancouver, Canada, Proceedings},
publisher = {Morgan Kaufmann},
year = {1992},
isbn = {1-55860-151-1},
pages = {127-138},
ee = {db/conf/vldb/Richardson92.html},
crossref = {DBLP:conf/vldb/92},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
Abstract
This paper considers the problem of adding list as a type constructor toan object-oriented data model.
In particular, we are concerned with how lists in a database can be constructedand how they can be queried.
We propose that operators from a discrete, linear-time temporal logic provide anatural basis for making assertions about the ordering of elements in a list.
We then show how such assertions may be incorporated into a query algebra by extending the Melampus Data Model (MDM) with a list type constructor and by allowing temporal assertions as predicates on lists.
The extended algebra allows the expression of a significantly larger class of queries than previously possible.
Furthermore, temporal operators provide a basis for creating new lists that satisfy desired ordering properties.
For example, sorting is shown to fall out as a special case.
This paper also describes a new framework based on Boolean circuits for evaluating the truth of an assertion on a given list.
This framework provides many opportunities for optimization and parallelism, and it lends insight to the meaning and complexity of a temporal formula.
Copyright © 1992 by the VLDB Endowment.
Permission to copy without fee all or part of this material is granted provided that the copies are not made or
distributed for direct commercial advantage, the VLDB
copyright notice and the title of the publication and
its date appear, and notice is given that copying
is by the permission of the Very Large Data Base
Endowment. To copy otherwise, or to republish, requires
a fee and/or special permission from the Endowment.
Online Paper
CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ...
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
Printed Edition
Li-Yan Yuan (Ed.):
18th International Conference on Very Large Data Bases, August 23-27, 1992, Vancouver, Canada, Proceedings.
Morgan Kaufmann 1992, ISBN 1-55860-151-1
Contents
References
- [Albano 85]
- Antonio Albano, Luca Cardelli, Renzo Orsini:
Galileo: A Strongly-Typed, Interactive Conceptual Language.
ACM Trans. Database Syst. 10(2): 230-260(1985)
![bibliographical record in XML](../../xml.gif)
- [Bancilhon 87]
- François Bancilhon, Ted Briggs, Setrag Khoshafian, Patrick Valduriez:
FAD, a Powerful and Simple Database Language.
VLDB 1987: 97-105
![bibliographical record in XML](../../xml.gif)
- [Bancilhon 89]
- François Bancilhon, Sophie Cluet, Claude Delobel:
A Query Language for the O2 Object-Oriented Database System.
DBPL 1989: 122-138
![bibliographical record in XML](../../xml.gif)
- [Borodin 77]
- Allan Borodin:
On Relating Time and Space to Size and Depth.
SIAM J. Comput. 6(4): 733-744(1977)
![bibliographical record in XML](../../xml.gif)
- [Carey 88]
- Michael J. Carey, David J. DeWitt, Scott L. Vandenberg:
A Data Model and Query Language for EXODUS.
SIGMOD Conference 1988: 413-423
![bibliographical record in XML](../../xml.gif)
- [Ceri 90]
- ...
- [DBPL 89]
- ...
- [DBPL 91]
- ...
- [Fegaras 89]
- Leonidas Fegaras, Tim Sheard, David W. Stemple:
The ADABTPL Type System.
DBPL 1989: 207-218
![bibliographical record in XML](../../xml.gif)
- [Ginsburg 92]
- Seymour Ginsburg, Xiaoyang Sean Wang:
Pattern Matching by Rs-Operations: Toward a Unified Approach to Querying Sequenced Data.
PODS 1992: 293-300
![bibliographical record in XML](../../xml.gif)
- [Güting 89]
- Ralf Hartmut Güting, Roberto Zicari, David M. Choy:
An Algebra for Structured Office Documents.
ACM Trans. Inf. Syst. 7(2): 123-157(1989)
![bibliographical record in XML](../../xml.gif)
- [Gyssens 88]
- Marc Gyssens, Dirk Van Gucht:
The Powerset Algebra as a Result of Adding Programming Constructs to the Nested Relational Algebra.
SIGMOD Conference 1988: 225-232
![bibliographical record in XML](../../xml.gif)
- [Koshafian 86]
- Setrag Khoshafian, George P. Copeland:
Object Identity.
OOPSLA 1986: 406-416
![bibliographical record in XML](../../xml.gif)
- [Lichtenstein 85]
- ...
- [McKenzie 91]
- L. Edwin McKenzie, Richard T. Snodgrass:
Evaluation of Relational Algebras Incorporating the Time Dimension in Databases.
ACM Comput. Surv. 23(4): 501-543(1991)
![bibliographical record in XML](../../xml.gif)
- [Richardson 91a]
- Joel E. Richardson, Peter M. Schwarz:
Aspects: Extending Objects to Support Multiple, Independent Roles.
SIGMOD Conference 1991: 298-307
![bibliographical record in XML](../../xml.gif)
- [Richardson 91b]
- Joel E. Richardson, Peter M. Schwarz:
MDM: An Object-Oriented Data Model.
DBPL 1991: 86-95
![bibliographical record in XML](../../xml.gif)
- [Segev 87]
- Arie Segev, Arie Shoshani:
Logical Modeling of Temporal Data.
SIGMOD Conference 1987: 454-466
![bibliographical record in XML](../../xml.gif)
- [Shaw 91]
- Gail M. Shaw, Stanley B. Zdonik:
A Query Algebra for Object-Oriented Databases.
ICDE 1990: 154-162
![bibliographical record in XML](../../xml.gif)
- [Sistla 85]
- A. Prasad Sistla, Edmund M. Clarke:
The Complexity of Propositional Linear Temporal Logics.
J. ACM 32(3): 733-749(1985)
![bibliographical record in XML](../../xml.gif)
- [Snodgrass 87]
- Richard T. Snodgrass:
The Temporal Query Language TQuel.
ACM Trans. Database Syst. 12(2): 247-298(1987)
![bibliographical record in XML](../../xml.gif)
- [Snyder 86]
- Alan Snyder:
Encapsulation and Inheritance in Object-Oriented Programming Languages.
OOPSLA 1986: 38-45
![bibliographical record in XML](../../xml.gif)
- [Tuzhilin 90]
- Alexander Tuzhilin, James Clifford:
A Temporal Relational Algebra as Basis for Temporal Relational Completeness.
VLDB 1990: 13-23
![bibliographical record in XML](../../xml.gif)
- [Vandenberg 91]
- Scott L. Vandenberg, David J. DeWitt:
Algebraic Support for Complex Objects with Arrays, Identity, and Inheritance.
SIGMOD Conference 1991: 158-167
![bibliographical record in XML](../../xml.gif)
- [Vandenberg 92]
- ...
- [Wolper 83]
- Pierre Wolper:
Temporal Logic Can Be More Expressive.
Information and Control 56(1/2): 72-99(1983)
![bibliographical record in XML](../../xml.gif)
Copyright © Tue Mar 16 02:22:02 2010
by Michael Ley (ley@uni-trier.de)