Contents in Current Page:

1. Nested Graph Model - Introduction (P0043)
2. Nested Graph Model - data model, general.
3. Nested Graph Model - data model, Hypernodes and Hypernode Repositories.
4. Nested Graph Model - data model, Types and Typed repositories.

Nested Graph Model - Introduction (P0043)

Three recent trends in database research are object-oriented and deductive databases and graph-based user interfaces. We draw these trends together in a data model we call the Hypernode Model. The single data structure of this model is  the hypernode, a graph whose nodes can themselves be graphs. Hypernodes are typed, and types, too, are nested graphs. We give the theoretical foundations of  hypernodes and types, and we 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 query language called Hyperlog, which is complete with respect to computation  and update. We define the operational semantics of Hyperlog and show that the evaluation of Hyperlog programs is intractable in the general case-we identify cases when evaluation can be performed efficiently. We discuss also the use of Hyperlog for supporting database browsing, an essential feature of Hypertext databases. We compare our work with 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. (36 Refs.).

Nested Graph Model - data model, general.

The Nested Graph model is called Hypernode model, supports object identity and arbitrary complex objects and which is well-suited to the implementation of Hypertext databases. In contrast to other graph based data models Hypernode  uses nested possibly recursively defined , graphs termed hypernodes. A hypernode is a pair (N.E) of Nodes and directed edges such that the nodes themselves can be  hypernodes.Hypernode Model provides inherent support for the nesting of information. the labels of hypernodes are unique and serve as object identifiers. Hypernodes are superscripted with tags indicate the types of the Hypernodes.  Types gives us a means of defining database schemas and of enforcing constarints on the structure and content of hypernodes. Types asre represented , too, by  nested graphs and can be queried and updated using the same formalism as the hypernodes. The Hypernode model comes equipped with a computationally powerfull declarative language called Hyperlog. Hypernode model supports arbitrarily complex objects and the data abstraction concepts of classification (via types), identification (via unique labels), and encapsulation (via the nesting of graphs).

Nested Graph Model - data model, Hypernodes and Hypernode Repositories.

- A directed graph is an ordered pair (N,E), where N is a finite set of Nodes and E  subset of (N x N is a finite set of directed edges. - we define a finite set of primitive nodes P . We assume that P includes alphanumeric strings. Other elements of P are  denoted by identifiers which start with a lower-case letter. - and a countably infinite set of labels L . Elements of L are denoted by identifiers which start with an Upper-case letter. P and L are disjoint sets. Graphs of the Hypernode model are defined be equqtions of the form G = (N,E) where G ε L and where (N,E) is  agraph such that N subset (P U L) . We term thast equationshypernode equations. A hypernode repository is a finite set of hypernode equations satisfying the following two conditions: (Con1) No two conditions have the same left-hand side. (Con2) for any label appearing in the right -hand side of an equation , there exists  an equation with that label on its left hand side. these two conditions corresponds to the entity integrity and referential integrity requirement of Codd. A hypernode repository has a unique solution in the universe of non-well defined sets. This olution assigns to each label G on the left side of an equation a non-well defined set. We term such a set a hypernode and denote it by HYP(G). The hypernode HYP(G) is an ordered pair (N,E) where N is a set of primitive nodes and further hypernodes and E subset (N x N)

Nested Graph Model - data model, Types and Typed repositories.

- We define a finite set of primitive types TP such that every primitive node n ε P is of some unique primitive type T ε TP. - and a countably infinite set of type labels TL such that every label in hypernode repository is tagged by a unique type label T ε TL