A NESTED-GRAPH MODEL FOR THE REPRESENTATION AND MANIPULATION OF COMPLEX OBJECTS

Three recent trends in database research are object-oriented and deduc tive databases and graph-based user interfaces. We draw these trends t ogether in a data model we call the Hypernode Model. The single data s tructure of this model is the hypernode, a graph whose nodes can thems elves be graphs. Hypernodes are typed, and types, too, are nested grap hs. We give the theoretical foundations of hypernodes and types, and w e show that type checking is tractable. We show also how conventional type-forming operators can be simulated by our graph types, including cyclic types. The Hypernode Model comes equipped with a rule-based que ry language called Hyperlog, which is complete with respect to computa tion and update. We define the operational semantics of Hyperlog and s how that the evaluation of Hyperlog programs is intractable in the gen eral case-we identify cases when evaluation can be performed efficient ly. We discuss also the use of Hyperlog for supporting database browsi ng, an essential feature of Hypertext databases. We compare our work w ith other graph-based data models-unlike previous graph-based models, the Hypernode Model provides inherent support for data abstraction via its nesting of graphs. Finally, we briefly discuss the implementation of a DBMS based on the Hypernode Model.