The use of deleted tuples in database querying and updating

• Published in: Acta informatica 1997, Vol.34 (12), p.905-925
• Main Authors: Laurent, D., Phan Luong, V., Spyratos, N.
• Format: Article
• Language: English
• ISSN: 0001-5903; 1432-0525
• DOI: 10.1007/s002360050111

The traditional approach to database querying and updating treats insertions and deletions of tuples in an asymmetric manner: if a tuple t is inserted then, intuitively, we think of t as being true and we use this knowledge in query and update processing; in contrast, if a tuple t is deleted then we think of t as being false but we do not use this knowledge at all! In this paper, we present a new approach to database querying and updating in which insertions and deletions of tuples are treated in a symmetric manner. Contrary to the traditional approach, we use both inserted and deleted tuples in our derivation algorithms. Our approach works as follows: if the deletion of a tuple t is requested, then we mark t as being deleted without removing it from the database; if the insertion of a tuple t is requested, then we simply place t in the database and remove all its marked subtuples. Derivation of tuples is done using two derivation rules under one constraint: a tuple t is derived only if t has no marked subtuples in the database. The derivation rules reflect relational projection and relational join. The main contribution of our work is to provide a method which allows insertion or deletion of a tuple over any relation scheme in a deterministic way.