Skip Navigation

The Computer Journal 1994 37(3):164-176; doi:10.1093/comjnl/37.3.164
© 1994 by British Computer Society
This Article
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in ISI Web of Science
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrow Search for citing articles in:
ISI Web of Science (1)
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Lorentzos, N. A.
Right arrow Articles by Poulovassilis, c.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

Implementation of Update Operations for Interval Relations

N. A. Lorentzos1 * {ddagger}, A. Poulovassilis2 § and c. Poulovassilis3 ¶

1 Informatics Laboratory, Agricultural University of Athens, Iera Odas 75, 118 55 Athens, Greece, 2 Department of Computer Science, King's College London, Strand, London WC2R 2LS, UK, 3 Department of Computer Science, Birkbeck College, Malet Street, London WC1E 7HX, UK

The concept of an interval has application in diverse areas, including temporal and spatial databases. However, the semantics of set-union and set-difference are inappropriate for the update of interval relations (i.e. of relations with interval attributes). In particular, we discuss how set-union can yield relations in which data is duplicated over several tuples and how set-difference does not implement the desired deletion semantics. This leads us to the definition of a normalized representation for interval relations in which there is no duplication of data over several tuples: we call such relations canonical ones. We define a pair of update operations which complement set-union and set-difference, give the desired update semantics, and maintain the property of canonicity. We give algorithms for these update operations. An examination of the efficiency of these operations leads us to propose two pairs of successively more optimized operations and we give algorithms for these also. The contribution of this paper is the development of efficient algorithms for updating interval relations while maintaining the desired update semantics and preserving the non-redundancy of the data.

Received August 1993. revised January 1994.

* Informatics Laboratory, Agricultural University of Athens, Iera Odas 75, 118 55 Athens, Greece

§ Department of Computer Science, King's College London, Strand, London WC2R 2LS, UK

Department of Computer Science, Birkbeck College, Malet Street, London WC1E 7HX, UK

{ddagger} Correspondence to N. A. Lorentzos.


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.