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)
- [Bancilhon 87]
- François Bancilhon, Ted Briggs, Setrag Khoshafian, Patrick Valduriez:
FAD, a Powerful and Simple Database Language.
VLDB 1987: 97-105
- [Bancilhon 89]
- François Bancilhon, Sophie Cluet, Claude Delobel:
A Query Language for the O2 Object-Oriented Database System.
DBPL 1989: 122-138
- [Borodin 77]
- Allan Borodin:
On Relating Time and Space to Size and Depth.
SIAM J. Comput. 6(4): 733-744(1977)
- [Carey 88]
- Michael J. Carey, David J. DeWitt, Scott L. Vandenberg:
A Data Model and Query Language for EXODUS.
SIGMOD Conference 1988: 413-423
- [Ceri 90]
- ...
- [DBPL 89]
- ...
- [DBPL 91]
- ...
- [Fegaras 89]
- Leonidas Fegaras, Tim Sheard, David W. Stemple:
The ADABTPL Type System.
DBPL 1989: 207-218
- [Ginsburg 92]
- Seymour Ginsburg, Xiaoyang Sean Wang:
Pattern Matching by Rs-Operations: Toward a Unified Approach to Querying Sequenced Data.
PODS 1992: 293-300
- [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)
- [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
- [Koshafian 86]
- Setrag Khoshafian, George P. Copeland:
Object Identity.
OOPSLA 1986: 406-416
- [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)
- [Richardson 91a]
- Joel E. Richardson, Peter M. Schwarz:
Aspects: Extending Objects to Support Multiple, Independent Roles.
SIGMOD Conference 1991: 298-307
- [Richardson 91b]
- Joel E. Richardson, Peter M. Schwarz:
MDM: An Object-Oriented Data Model.
DBPL 1991: 86-95
- [Segev 87]
- Arie Segev, Arie Shoshani:
Logical Modeling of Temporal Data.
SIGMOD Conference 1987: 454-466
- [Shaw 91]
- Gail M. Shaw, Stanley B. Zdonik:
A Query Algebra for Object-Oriented Databases.
ICDE 1990: 154-162
- [Sistla 85]
- A. Prasad Sistla, Edmund M. Clarke:
The Complexity of Propositional Linear Temporal Logics.
J. ACM 32(3): 733-749(1985)
- [Snodgrass 87]
- Richard T. Snodgrass:
The Temporal Query Language TQuel.
ACM Trans. Database Syst. 12(2): 247-298(1987)
- [Snyder 86]
- Alan Snyder:
Encapsulation and Inheritance in Object-Oriented Programming Languages.
OOPSLA 1986: 38-45
- [Tuzhilin 90]
- Alexander Tuzhilin, James Clifford:
A Temporal Relational Algebra as Basis for Temporal Relational Completeness.
VLDB 1990: 13-23
- [Vandenberg 91]
- Scott L. Vandenberg, David J. DeWitt:
Algebraic Support for Complex Objects with Arrays, Identity, and Inheritance.
SIGMOD Conference 1991: 158-167
- [Vandenberg 92]
- ...
- [Wolper 83]
- Pierre Wolper:
Temporal Logic Can Be More Expressive.
Information and Control 56(1/2): 72-99(1983)
Referenced by
- Ke Wang, Beng Chin Ooi, Sam Yuan Sung:
P-Tree: A B-Tree Index for Lists.
DASFAA 1999: 221-228
- Wesley W. Chu, Chih-Cheng Hsu, Alfonso F. Cardenas, Ricky K. Taira:
Knowledge-Based Image Retrieval with Spatial and Temporal Constructs.
IEEE Trans. Knowl. Data Eng. 10(6): 872-888(1998)
- Gösta Grahne, Matti Nykänen:
Safety, Translation and Evaluation of Alignment Calculus.
ADBIS 1997: 295-304
- Praveen Seshadri, Miron Livny, Raghu Ramakrishnan:
The Design and Implementation of a Sequence Database System.
VLDB 1996: 99-110
- Hagit Shatkay, Stanley B. Zdonik:
Approximate Queries and Representations for Large Data Sequences.
ICDE 1996: 536-545
- Giansalvatore Mecca, Anthony J. Bonner:
Sequences, Datalog and Transducers.
PODS 1995: 23-35
- H. V. Jagadish, Alberto O. Mendelzon, Tova Milo:
Similarity-Based Queries.
PODS 1995: 36-45
- Stéphane Grumbach, Tova Milo:
An Algebra for Pomsets.
ICDT 1995: 191-207
- Bharathi Subramanian, Theodore W. Leung, Scott L. Vandenberg, Stanley B. Zdonik:
The AQUA Approach to Querying Lists and Trees in Object-Oriented Databases.
ICDE 1995: 80-89
- Praveen Seshadri, Miron Livny, Raghu Ramakrishnan:
SEQ: A Model for Sequence Databases.
ICDE 1995: 232-239
- Giansalvatore Mecca, Anthony J. Bonner:
Finite Query Languages for Sequence Databases.
DBPL 1995: 12
- Gultekin Özsoyoglu, Z. Meral Özsoyoglu, Kumar V. Vadaparty:
A Scientific Database System for Polymers and Materials Engineering Needs.
SSDBM 1994: 138-148
- Praveen Seshadri, Miron Livny, Raghu Ramakrishnan:
Sequence Query Processing.
SIGMOD Conference 1994: 430-441
- Divesh Srivastava, Raghu Ramakrishnan, Praveen Seshadri, S. Sudarshan:
Coral++: Adding Object-Orientation to a Logic Database Language.
VLDB 1993: 158-170
- Bharathi Subramanian, Stanley B. Zdonik, Theodore W. Leung, Scott L. Vandenberg:
Ordered Types in the AQUA Data Model.
DBPL 1993: 115-135
Last update Fri May 25 08:45:23 2012
CET by the DBLP Team — 
Data released under the ODC-BY 1.0 license — See also our legal information page
