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

Download PDF file (www.vldb.org, Darmstadt, Germany)
Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/vldb8997 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

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 O₂ 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)