General transitive closure of relations containing duplicates

摘要

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.