Powerdomain of Paths for Representing Object Structures

A new method for viewing and manipulating identity-based object structures is proposed. The method is founded on the viewing the object structure as an object graph which in turn is represented as a set of paths. Over a power set of paths we construct a powerdomain which forms a lattice with well-defined meet and join operations. In our construction of the powerdomain of paths we combine the Hoare ordering (appropriate for ordering of tuple objects) with the Smyth ordering (appropriate for ordering of set objects) into a new ordering appropriate for set of paths capturing information conveyed by both tuple and set objects. The approach allows to deal with incomplete tuple objects as well as with partially described sets. The goal of the powerdomain construction is to provide a semantic domain for a path calculus language [20], where path calculus variables range over paths and path calculus queries give sets of paths as their answers.