General transitive closure of relations containing duplicates

作者:

Highlights:

摘要

General transitive closures are introduced to process recursive structures of data stored in relations. General transitive closures allow a broad range of practical applications to be supported, and yet have the property of being efficiently implementable and easy to use.We extend general transitive closures to relations containing duplicates, so-called multiset-relations, to increase the expressiveness, and because database management systems usually permit the appearance of duplicates in tables. In particular, we show that complicated surrogate generation is no longer necessary for the processing of reconvergent structures.General transitive closures can easily be integrated into the view definition of SQL, requiring a minimum of new concepts and constructs. Recursively defined views can be used in queries like other relations. Due to the formal declarative definition of the semantics of general transitive closure, query optimization and reasoning about effective computation can be left with the query processing system.

论文关键词:relational database,SQL,recursive query processing,multiset-relations,algebra of multiset-relations,general transitive closure

论文评审过程:Received 16 May 1989, Revised 13 October 1989, Available online 17 June 2003.

论文官网地址:https://doi.org/10.1016/0306-4379(90)90005-A