A nested-graph model for the representation and manipulation of complex objects.
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 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 modelsunlike 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.
INTRODUCTION
Recent database research has focussed on deductive [7, 14, 26] and object-oriented [5, 22] databases. Deductive
databases extend the relational data model with rule-based computation. Rules enable the derivation of further,
intentional, tuples from the stored, extensional, tuples. These derived tuples can be used purely for querying purposes
or can be inserted into the database. Conversely, object-oriented databases start off with a semantic data model [16, 20,
31], which typically supports object identity, inheritance and complex objects, and extend it with features such as
methods and encapsulation from object-oriented programming [32, 37].
Thus, deductive and object-oriented database are largely complementary. The former support extensionally and intentionally
defined relations, but not fundamental data abstraction concepts such as classification, identification, inheritance
and encapsulation. Conversely, the latter do support these abstraction concepts but do not support relations natur-
ally. Hence, recent research has aimed at integrating the two paradigms. The integration has generally taken the route
of extending logic-based deductive database languages with features such as object identity, sets, functions, methods
and inheritance [1, 2, 3, 14]. In contrast, in this paper we report upon a graph-based approach to such an integration.
Our use of graphs has two firstly, graphs are formally defined, well-understood structures; secondly, it
is widely accepted that graph-based formalisms considerably enhance the usability of complex systems [19]. Graphs
have been used in conjunction with a number of conventional data models, for example the hierarchical and network
models [35], the entity-relationship model [9] and a recent extension thereof for complex objects [27], and various
semantic data models [16, 20, 31]. Graphs or hypergraphs [6] have also been used more recently in [12, 17, 23, 25, 33,
36] as a data modelling tool in their own right. We give a comparison between this recent work and our own approach
in Section 4 of the paper.
Directed graphs have also been the foundation of Hypertext databases [11, 33]. Such databases are graphs consisting of
nodes which refer to units of stored information (typically text) and of named links. Each link connects two nodes, the
"source" and the "destination". Links are traversed either forwards (from source to destination) or backwards (from
destination to source). The process of traversing named links and examining the text associated with nodes is called
browsing. Typically, a simple query facility consisting of string-based search is provided which can be used to identify
an initial set of nodes prior to browsing. A further feature of Hypertext is the dynamic creation of new nodes and links.
Motivated by the previous research outlined above, we have developed a graph-based data model called the Hypernode
Model which supports object identity and arbitrarily complex objects, and which is well-suited to the implementation of
Hypertext databases. In contrast to other graph-based models, we use nested, possibly recursively defined, graphs
termed hypernodes. A hypernode is a pair (N,E) of nodes and directed edges such that the nodes can themselves be
hypernodes. Thus, unlike other graph-based models, the Hypernode Model provides inherent support for the nesting of
information. The labels of hypernodes are unique and serve as object identifiers. We illustrate a hypernode in Figure 1.
It represents a couple, C, consisting of two people, PER1 and PER2, whose children are nested within further hyper-
nodes. In Figure 2 we show the children of person PER1, which would become visible if we "exposed" the hypernodes
labelled PER3 and PER4. We observe from these figures that hypernodes differ from hypergraphs in that they
generalise nodes to hypernodes as opposed to generalising edges to hyperedges.
name "Bob"
surname "Smith"
child PER3 PERSON
name "Mary"
surname "Jones"
child PER3 PERSON
Fig. 1. An example hypernode.
name "Jill"
surname "Smith"
child none PERSON
PER3 PERSON
name "Jack"
surname "Jones"
child none PERSON
Fig. 2. Further hypernodes.
We note that the labels C and PER1-PER4 in Figure 1 are superscripted with the tags COUPLE and PERSON, respec-
tively. As we explain in the sequel, these tags indicate the types of their associated hypernodes. Types give us a means
of defining database schemas and of enforcing constraints on the structure and content of hypernodes. Types, too, are
represented by nested graphs and can be queried and updated using the same formalism as for hypernodes. We also
note the use of the node none PERSON in Figure 2 - it denotes "not present".
The Hypernode Model comes equipped with a computationally powerful declarative language called Hyperlog. The
model and language share features with both deductive and object-oriented databases. In common with other deductive
database languages, Hyperlog is rule-based and supports derivations and database updates. In common with object-oriented
databases the 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). In [25] we
showed how structural inheritance is also supported naturally by nested graph structures (in that paper, we used nested
hypergraphs but our treatment is equally applicable to the simpler nested graphs of the Hypernode Model). In [24] we
also showed how methods can be supported as parametrised Hyperlog programs.
The Hypernode Model supports the main features of Hypertext databases : Strings of arbitrary length are supported as
a primitive type and so unstructured text can be represented. Such text can be a node of a hypernode which is itself
encapsulated within a number of further hypernodes - hence text can be shared. Sets of text fragments are easily
represented - as the nodes of a hypernode. Annotated links can be represented by a hypernode with a single incoming
edge from the source node and a single outgoing edge to the destination node; this hypernode can encapsulate the annotation
information, for example, the actual link label, a description of the semantics of the link, the creator of the link
and its date of creation. The nesting of hypernodes is an abstraction tool which greatly facilitates the design and browsing
of densely connected database graphs and which is unique to our model. Finally, Hyperlog can support both
database browsing and general-purpose declarative querying. The latter facility can be used to create contexts for
browsing.
We first introduced the Hypernode Model in [24]. In the present paper we expand upon that work in several directions,
including expressiveness of representation and computation, efficiency of inference, support of Hypertext, and implementation
issues. We also describe recent work in extending the model to include types and extending Hyperlog to perform
deletions as well as insertions. The outline of this paper is as follows. In Section 2 we discuss the fundamentals
of the Hypernode Model, namely hypernodes and types. We also discuss representational expressiveness and type
checking complexity. In Section 3 we give the syntax and semantics of Hyperlog. We discuss the complexity of
evaluating Hyperlog programs, and their computational and update expressiveness. We also show how Hyperlog can
be used for database browsing. In Section 4 we compare our work with other graph-based languages and models. In
Section 5 we briefly describe a prototype implementation. We conclude in Section 6 with a summary of our results.
2. THE HYPERNODE MODEL
In this section we discuss the fundamentals of our model, namely hypernodes and types. We define hypernodes and
repositories for them in Section 2.1. We define types and type repositories in Section 2.2, where we also examine the
efficiency of type checking. In Section 2.3 we illustrate the use of types via an extended example based upon a flights
bookings database. Finally, in Section 2.4 we discuss the representational expressiveness of our model.
2.1 Hypernodes and Hypernode Repositories
In this section we introduce the underlying data structure of the hypernode model, namely the hypernode. We define a
hypernode repository to be a set of graph-defining equations. We then define hypernodes to be the values assigned to
the indeterminates when such a set of equations is solved.
We begin by recalling the definition of a directed graph - a directed graph is an ordered pair (N, E), where N is a finite
set of nodes and E - (N - N) is a finite set of directed edges. For simplicity, we use the terms "graph" and "directed
interchangeably. Similarly for the terms "edge" and "directed edge". We also use the notation n 1 -n 2 interchangeably
with (n 1 , edges. For the purposes of the Hypernode Model we need two disjoint sets of constants, a
finite set of primitive nodes, P, and a countably infinite set of labels, L. We assume that the set P includes
alphanumeric strings. Other elements of P are denoted by identifiers which start with a lowercase letter. Elements of L
are denoted by identifiers which start with an uppercase letter.
The graphs of the Hypernode Model are defined by equations of the form
E)
where G - L and (N,E) is graph such that N - (P - L). We term such equations hypernode equations. Examples are
the following, where P1, P2, N1, N2 are labels and name, spouse, title, "Ms", "Mr", "A", "B", "Floyd", "Tring" are
primitive nodes :
A hypernode repository (or simply a repository) is a finite set of hypernode equations satisfying the following two conditions
no two equations have the same left hand side;
(H2) for any label appearing in the right hand side of an equation, there exists an equation with that label on its left
hand side.
Given a hypernode repository, HR, we denote by LABELS(HR) the set of labels appearing in the equations of HR and
by PRIM(HR) the set of primitive nodes appearing in the equations of HR.
For example, the four equations above satisfy the criteria for a hypernode repository. We note that condition H1 above
corresponds to the entity integrity requirement of [10] since each equation can viewed as representing a real-world
entity. Similarly, condition H2 corresponds to the referential integrity requirement of [10] since it requires that only
existing entities be referenced.
Hypernode repositories can be viewed as storing a set of graphs which may reference other graphs via their labels.
Alternatively, since hypernode repositories are just sets of equations, we would like them to have a unique solution for
the indeterminates (i.e. for the labels G - L) in some well-defined domain. This domain cannot be the universe of
well-founded sets since hypernode equations may be cyclicly defined (for example, the equations defining P1 and P2
above). However, we can appeal to Aczel's theory of non-well-founded sets [4] to solve hypernode repositories. Non-
well-founded sets subsume well-founded sets by including circular sets i.e. sets that may contain themselves. It is
shown in [4] that a set of set-defining equations (of which a hypernode repository is a special case) has a unique solution
in the universe of non-well-founded sets.
Thus, a hypernode repository HR has a unique solution in the universe of non-well-founded sets. This solution assigns
to each label G on the left hand side of an equation a non-well-founded set. We term such a set a hypernode and denote
it by HYP HR (G), or simply HYP(G) if HR is understood from the context. The hypernode HYP(G) is an ordered pair
(N,E), where N is a set of primitive nodes and further hypernodes, and E - (N - N) (we note that any ordered pair (a,b)
can be viewed as the set {a,{a,b}}). For example, given a hypernode repository consisting of the four equations for
P1,P2,N1 and N2 above, we have (ignoring the node sets of the graphs for simplicity) :
spouse-{name-{title-"Mr",initial-"B",surname-"Tring"},spouse-{ .}}}
spouse-{name-{title-"Ms",initial-"A",surname-"Floyd"},spouse-{ . }}}
We note that the sets HYP(N1) and HYP(N2) are well-founded ones while the sets HYP(P1) and HYP(P2) are non-
well-founded ones since they contain themselves.
2.2 Types and Type Repositories
In this and the next two sections we extend our model to incorporate types, which are also graphs. We define type
repositories and types by analogy to hypernode equations, hypernode repositories and hypernodes. We
then define what it means for a hypernode to be of a particular type, and we show that testing a hypernode repository
for well-typedness can be performed in polynomial time with respect to the size of the repository. In Section 2.3 we
illustrate types via an extended example based upon a flights bookings database.
For the purpose of defining types, we assume the availability of two disjoint sets of constants : 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 a hypernode repository is tagged by a unique type label T - (c.f. the types
of object identifiers in object-oriented databases). By analogy to primitive nodes and labels, we distinguish between
primitive types and type labels by using identifiers which start with a lowercase letter for the former and identifiers
which start with an uppercase letter for the latter. We assume that for every type T, primitive or otherwise, there is a
distinguished primitive node, none T , denoting "not present". As we will see below, this node is used to model missing
or incomplete information. Finally, we assume that the set of primitive types includes the type "string".
Types are defined by means of equations of the form
and (M,F) is graph such that M - (TP - TL). We call such equations type equations. A type reposi-
tory, TR, is a finite set of type equations satisfying conditions H1 and H2 for hypernode repositories in Section 2.1.
Again, we can appeal to the theory of non-well-founded sets to solve type repositories i.e. to assign values to the T -
from the universe of non-well-founded sets. We call such values types and denote them by HYP TR (T), or HYP(T)
when TR is understood from context. These values take the form of a pair (M,F), where M is a set of primitive types
and further types, and F - (M - M). We also make the reasonable assumption that primitive nodes and labels are distinct
from primitive types and type labels i.e. (P - L) - (TP - -. Thus, there is no overlap between the data
(hypernodes) and the meta data (types) and the hypernode and type repositories can be merged into one repository. As
well as a uniform storage of data and meta data, this means that the meta data can be queried and updated using the
same formalism as the data, namely Hyperlog.
Typings of hypernodes are defined recursively as follows. Given a hypernode (N,E) and a type (M,F) we say that (N,E)
is of type (M,F) if there exists a homomorphism f : N - M which preserves the types and which satisfies the following
conditions :
Conditions stipulate that a hypernode must contain only nodes and edges which conform to the nodes and
edges of the intended type, while conditions T3 and T4 stipulate that a hypernode must contain at least one instance of
every node and edge in its intended type. These last two conditions are not restrictive since the primitive nodes none T
can be used in place of missing information.
Typings of individual hypernodes are generalised to typings of hypernode repositories as follows. A hypernode reposi-
tory, HR, is well-typed with respect to a type repository, TR, if for every label G T in LABELS(HR), HYP HR (G T ) is of
type HYP TR (T). The following theorem states that testing a hypernode repository for well-typedness is tractable. The
result follows by observing that in order to test a hypernode repository for well-typedness, we can fix the homomorphism
f to map primitive nodes and labels to their types and then check the criteria above for each equation of
HR. If there are m equations in HR to be checked and a maximum of n nodes and e edges in the right hand side of any
hypernode or type equation, the test is achieved in a time proportional to mn 2 e 2 .
THEOREM 1. Testing whether a hypernode repository, HR, is well-typed with respect to a type repository, TR, can be
performed in a time polynomial in the number of equations in HR and the maximum size of individual equations.
2.3 The Flights Bookings Database Example
To illustrate types we now consider a database that stores information about bookings of flights by passengers. The
schema of our database is specified by the type FLIGHT_BOOKINGS_SCHEMA in Figure 3. From now on we use
equation-based and pictorial representations of graphs interchangeably. We also omit the type tags of labels if these are
understood from context.
Fig. 3. The example schema.
RF
FLIGHT_BOOKINGS_SCHEMA
AIRLINES AIRPORTS
FLIGHT_BOOKINGS_SCHEMA contains six further types :
(i) RF, shown in Figure 4, which represents ROUTEs and the FLIGHTs that fly them (each route is followed by a
number of flights).
(ii) PT, shown in Figure 5, which represents PASSENGERs and their TICKETs (each passenger has bought one or
more tickets).
(iii) TC, shown in Figure 6, which represents TICKETs and their COUPONs (each ticket consists of a number of
coupons). We notice the sharing of the graph TICKET by the graphs TC and PT.
(iv) FC, shown in Figure 7, which represents FLIGHTs and their COUPONs (each flight is booked by a number of
coupons).
(v) AIRLINES and AIRPORTS, shown in Figure 8, which contain the known airlines and airports, respectively.
Fig. 4. Routes and flights that fly them.
RF
AIRPORT
to_att
airline_att
FLIGHT
date_of_dep_att
time_of_dep_att TIME
Fig. 5. Passengers and their tickets.
PASSENGER
dependents_att
name_att
PASSENGER
date_of_issue_att
Fig. 6. Tickets and their coupons.
CLASS
status_att
class_att
date_of_issue_att
COUPON
Fig. 7. Flights and their coupons.
time_of_dep_att
date_of_dep_att
FLIGHT
CLASS
status_att
class_att
COUPON
Fig. 8. The set types AIRLINES and AIRPORTS.
AIRPORT
AIRLINES
The remaining types needed to fully specify the FLIGHT_BOOKINGS_SCHEMA are AIRLINE and AIRPORT,
shown in Figure 9, TIME, DATE, FARE and NAME, shown in Figure 10, and finally NAT, shown in Figure 11.
Fig. 9. The types AIRPORT and AIRLINE.
AIRPORT
name_att
code_att
string
name_att
code_att
string
Fig. 10. The types DATE, FARE, TIME and NAME.
string
string
hours_att
initial_att
amount_att
currency_att
month_att
day_att
We can make several observations from the above types :
Fig. 11. The natural numbers type.
(i) Edges in types can be used to represent attributes, for example flight_no_att-NAT in ROUTE. We adopt the
convention that primitive types which end in "_att" represent the attribute names. There is one primitive node of
each such primitive type and it is this node which appears in instances. For example, the primitive nodes
flight_no and airline appearing in Figure 12 are assumed to be of type flight_no_att and airline_att, respectively.
In practice, the user can introduce new primitive types into the set TP at any time, and can populate these types
by introducing new primitive nodes into the set P.
(ii) Edges in types can also be used to represent binary relationships, for example ROUTE-FLIGHT in RF. In gen-
eral, these relationships are many-to-many due to the fact that instances are defined as being homomorphic to
their type. However, cardinality constraints can be enforced within update programs - we give an example in
Section 3.3 below.
(iii) It is possible to define recursive types, for example PASSENGER, whose dependents are also of type
PASSENGER, and NAT, which contains itself.
(iv) The type NAT is used to represent the natural numbers in the Hypernode Model. 0 is represented by a hypernode
which contains the primitive node none NAT , and successive natural numbers are successive nestings of 0
(see

Figure

13). We describe how calculations are performed with these numbers in Section 3.6.
(v) Each hypernode of type FLIGHT_BOOKINGS_SCHEMA will be a Flight Bookings database. A typical
instance will have one node of each of the types RF, PT, TC, FC, AIRLINES, AIRPORTS, representing the
ROUTE-FLIGHTs, PASSENGER-TICKETs, TICKET-COUPONs and FLIGHT-COUPONs relations, and also
the airlines and airports.
We note from FLIGHT_BOOKINGS_SCHEMA that schema design using the Hypernode Model is comparable with
the Entity-Relationship (ER) approach [9]. There are however two fundamental differences between the two modelling
approaches which should be stressed. Firstly, our types can directly model complex objects, which may be hierarchical
or cyclic, while these cannot be modelled directly using ER diagrams. Secondly, our types can encapsulate further
types, for example FLIGHT_BOOKINGS_SCHEMA encapsulates RF, TC, FC, PT, AIRLINES and AIRPORTS, while
TICKET encapsulates DATE and FARE. Such encapsulation encourages a step-wise schema design and, in cases
where the schema is large or has many interconnections, it renders the schema much easier to display and comprehend.
We now illustrate some specific instances of the above types. In Figure 12 we show four hypernodes, R1, and two
versions of R3. We note that R1 and are of type ROUTE, while the first version of R3 is not since conditions T1,
T2, T3 and T4 of Section 2.2 are all violated. R3.1 can be amended to be of the type ROUTE by replacing name by
flight_no, adding an edge from airline to AIR2, and specifying edges for the attributes from_att and to_att, resulting in
R3.2.
R3.1 R3.2
Fig. 12. The routes R1,
PARIS
LONDON
AIR1to
from
airline
flight_no
LONDON
ATHENS
AIR2flight_no
airline
from
to
AIR2airline
name
none AIRPORT
AIR2flight_no
airline
from
to
In

Figure

13 we show the first three natural numbers. In Figure 14 we show the hypernodes AIR1 and AIR2, which are
both of type AIRLINE. We note that AIR2 has two codes.
Fig. 13. The first three natural numbers.0
none1Fig. 14. Two airlines.
"BA"
"British Airways"
name
code code
"OA"
"Olympic"
"Olympic Airways"
namename
In

Figure

15 we show the hypernodes EUROPEAN, AMERICAN and ASIAN. EUROPEAN and AMERICAN are
both of type AIRLINES, while ASIAN violates condition T3 of this type - it can be corrected by adding to it the primitive
node none AIRLINE .
Fig. 15. The sets of airlines, EUROPEAN ans AMERICAN and the incorrectly typed ASIAN.
ASIAN
AMERICAN
none AIRLINE
In

Figure

we show the hypernodes PT1 and PT2 of type PT. We note that the dependents can be nested to any finite
depth. Finally, in Figure 17 we show the hypernodes N1 and N2 of type NAME, F1 of type FARE and D1 of type
DATE. The enforcement of meaningful dates can either be achieved by defining appropriate primitive types for day,
Fig. 16. Two instances of the passenger-ticket relationship.
PASSENGER F1
none
fare
date_of_issue
name
dependents
dependents
name date_of_issue
fare
month and year or via the update programs.
Fig. 17. The names N1 and N2, the fare F1, and the date D1.
"Smith"
"A."
"Mr."
"Smith"
"M."
"Mr."
amount
currency
title
initial
surname surname
initial
titleyearday
month 6
2.4 Expressiveness of Representation
Types and type checking constitute a powerful data modelling and integrity checking tool since they allow database
schemas to be represented and enforced. Also, storage-level optimisations can be carried out based on type informa-
tion. The Hypernode Model is type-complete in the sense that the only allowed type-forming operator (graph
definition) can be applied arbitrarily many times. Also, cyclic types, such as PASSENGER in Figure 5, and cyclic
hypernodes, such as P1 and P2 of Section 2.1 are supported. Bearing these two points in mind, we show below how
some conventional type-forming operators can be simulated using graph definition.
Given a type T, we can represent a set type
Hypernodes of type S contain one or more nodes of type T and the empty set of type S can be represented by a hyper-
node, EMPTY -). The types AIRLINES and AIRPORTS in Figure 8 and the instances EUROPEAN and
AMERICAN in Figure 15 illustrate set types.
Given types T 1 , T 2 , ., T n and attribute names A 1 , A 2 , ., A n (such as flight_no_att, airline_att, from_att and to_att) we
can represent a record type
The types ROUTE and FLIGHT of Figure 4, and TIME, DATE, FARE and NAME shown in Figure 10, illustrate
record types. We note that a record type T is a bipartite graph. We also note that this construction differs from the
usual idea of a record since the attributes A i can be multi-valued i.e. there may be more than one edge emanating from
each A i in an instance of type T. The enforcement of single values can be encoded in the update programs in Hyperlog.
Given a record type T, we can represent a relation type as set(T). The component types of a record type may themselves
be record types and so nested relations [30] can also be represented. The types FLIGHT of Figure 4 and
TICKET of Figure 5 illustrate nested relation types.
Given types T 1 and T 2 , we can represent a mapping type
The types, RF, PT, TC and FC shown in Figures 4, 5, 6 and 7 illustrate mapping types. A further example is the type
Example instances of NAT_to_NAT are the identity function ID, which
maps each natural number to itself, and the mapping GREATER, which maps each natural number to all smaller natural
We note that partial mappings can be represented without violating type correctness (so long as there is at least one
edge in the mapping). For example, in the mapping GREATER, the element 0 is not the source of any edge and the
maximal number MAXNUM is not the sink of any edge.
Finally, given types as a record type
where the attribute types I 1 , I 2 , ., I n contain the primitive constants first, second, ., nth, respectively

In general then, given types T 1 , T 2 , ., T n , the type T defined by
-T
. T i r-1
-T i r
has instances which are heterogeneous sets of isolated nodes (arising from the T i which do not participate in any edge
in T) and edges (arising from the edges of T).
3. MANIPULATION OF HYPERNODES
In this section we introduce Hyperlog, a declarative query and update language for the Hypernode Model. Hyperlog
programs consist of sets of rules. The body of a rule consists of a number of graphs, called queries, which may contain
variables and which act as templates to be matched against the equations in the hypernode repository. The head of a
rule is also a query and indicates the updates (if any) to be undertaken for each match of the graphs in the body. The
evaluation of a program comprises a repeated matching of its set of rules against the hypernode repository until no more
updates can be inferred. In Section 3.1 below we describe syntax of Hyperlog. In Section 3.2 we define the matching
of queries in rule bodies against a hypernode repository and in Section 3.3 we describe the inference of updates from
queries in the heads of rules. In Section 3.4 we define the operational semantics of a Hyperlog program via a fixpoint
operator. We then address efficiency and expressiveness issues of Hyperlog in Sections 3.5 and 3.6 : in 3.5 we address
the efficiency of inference and in 3.6 computational and update expressiveness. We conclude in Section 3.7 with a
brief discussion on how database browsing can be supported by Hyperlog.
We have chosen a rule-based language for the Hypernode Model for two main reasons. Firstly, the high-level, declarative
nature of the language blends in well with the graph-based data model. Secondly, the language is very expressive :
as we will see below, it is in fact complete with respect to computation and database update. As a consequence, programs
which are frequently invoked can be optimised by being built-in without compromising the semantics of the
language. Candidates for optimisation are the arithmetic functions and the database browsing functions.
3.1. Syntax of Hyperlog
For the purposes of Hyperlog, we assume that a countably infinite set of variables, V, is available. We denote elements
of V by uppercase identifiers from the end of the alphabet. We assume that the set of variables V and the set of labels L
are disjoint. We also assume that all variables are typed, that is superscripted with a type T - TP - TL. However, we
often omit these superscripts if they are understood from context.
Each Hyperlog rule has a, possibly empty, set of graphs in its body and a single graph in its head. We call these graphs
queries. A query may have a variable as its label and may have variables in its node set. Also, its nodes and edges may
be negated (meaning "absent", intuitively). More formally, a query is an equation of the form
E)
and (N,E) is a graph such that :
(ii) N is the disjoint union of two sets, N+ and N-. N+ contains "positive" nodes and N- contains "negative" nodes.
(iii) E is the disjoint union of two sets, E+ and E-. E+ contains "positive" edges and E- contains "negative" edges.
Condition (iv) restricts all edges to be between positive nodes : clearly, a positive edge containing a negative (i.e.
absent) node is impossible; also, since no edge can contain a negative node, negative edges containing negative nodes
are meaningless.
For simplicity, we denote a node n - N- as -n and an edge Three examples of queries are
which, informally, finds the route and flight number for routes not with airline AIR1,
which, informally, checks whether route has flight number 301, and
GREATER NAT_TO_NAT =({10,X NAT }, {10- / X})
which finds all the numbers greater or equal to 10, using the GREATER mapping of Section 2.4.
A Hyperlog program is a finite set of rules, a rule being an expression of the form
are queries. For example, we give below a program (ignoring the node sets of graphs for
simplicity) which generates all transitive dependents of passengers and places this information into the mapping
TRANS_DEPS from PASSENGERs to PASSENGERs :
A Hyperlog program, P, can be represented as a labelled graph as follows. For each rule
in P add to the node set N the two graphs q 0 and R body and add to the edge set E the edge
R body -q 0 . We assume that the labels P and R body are drawn from a set of program and rule names, PROG, whose
members are distinct from the set of hypernode labels, L, and the set of type labels, TL. For example, the program
above is represented by the graph shown in Figure 18, where DEPS_PROG, BODY1 and BODY2 are unique identifiers
drawn from PROG (in subsequent figures of programs we often dispense with the outer program label).
We note from Figure 18 that rule heads can be shared between rules in the graphical representation of programs. In

Figure

23 we give an example where rule bodies are also shared. The semantics of a shared rule head are those of dis-
junction, the head being inferred if any of the bodies are true. Conversely, the semantics of a shared rule body are those
of conjunction, all the rule heads being inferred if the rule body is true. We finally note that our graphical representations
of programs are not hypernodes : they are not typed, and the graphs encapsulated within them are not required to
have unique labels (for example, two graphs have label TRANS_DEPS in Figure 18).
3.2. Queries in Rule Bodies
The queries in the bodies of rules act as templates which are matched against the equations in the hypernode repository.
Before defining this matching process, we need the concept of a substitution of variables by constants of the appropriate
type. A substitution, q, is a set of assignments {X 1
each X i is a distinct variable
in V and each C i is a distinct element in L - P of the same type, T i , as X i . The application of a substitution q to a
query E) is the equation E)q resulting from the substitution of each X i in the left hand side and right
hand side of the query by C i . Given a hypernode repository, HR, and a query, match for the
query with respect to the repository is a substitution, q, for all the variables in the query by constants drawn from
such that there exists an equation
We can extend this definition to a set of queries {q 1 , q 2 , ., q n } : a substitution q is a match for this set of queries if it is
a match for each query q i taken separately. We note that in the above definition we are assuming a Herbrand Universe
and the Closed World Assumption [29]. This allows us to infer the negation of a node or edge in the absence of a positive
match c.f. other non-monotonic formalisms [28].
For example, given a hypernode repository containing the following routes :
the sets of possible matches for the four queries
are {{X/R1, Y/605}, {X/R3, Y/400}}, {{}}, {} and {{X/R2}}, respectively.
3.3. Queries in Rule Heads
The query in the head of a rule indicates the updates to be undertaken for each match of the queries in the body of the
rule. A rule, R, in a program, P, may thus modify some of the equations in the hypernode repository by adding or deleting
nodes and edges in their right hand side according to positive or negative nodes and edges in the head of R.
Furthermore, there may be variables appearing in the head of R which do not appear in its body - we denote the set of
such variables by NEW R . In this case, if the head of R does not match any exising equation in the repository, a set of
new equations is generated, one for each positive variable in NEW R . The labels on the left hand sides of these new
equations are hitherto unused in the hypernode repository and in the program P and are chosen non-deterministically.
Also, if P consists of a number of rules, R 1 ,. R r , the sets of new labels generated for the sets of variables NEW R 1
NEW R are pairwise disjoint. Clearly, new labels may be left as dangling references after the execution of the program
P. Thus, we relax condition H2 of our definition of hypernode repositories in Section 2.1 to assume an equation
for any dangling label G T , where the null graph null(T) is defined as follows for any type
-T
We now illustrate some hypernode programs. The program DEPS_PROG in Figure 18 generates all transitive dependents
of passengers and places this information into the mapping TRANS_DEPS.
Y
Y
PASS_TO_PASS
TRANS_DEPS
TRANS_DEPS
Fig. 18. Program to generate all dependents.
PASSENGER
dependents
PASSENGER
Y PASSENGER
PASSENGER
dependents X
Z
Z
The program in Figure 19 generates the GREATER relation between natural numbers. It assumes that all the natural
numbers are contained in the node set of a distinguished hypernode with the label NUMBERS. The program in Figure
places into a RESULT hypernode the passengers who are paying a fare of more than $200 on some ticket. The program
in Figure 21 adds passenger P3 to the dependents of passenger P1, deleting any null value that might be there if
Fig. 19. Program to generate the GREATER relation.
GREATER
Y
NUMBERS
Y
GREATER
Z
Y
Y Z
GREATER
Y
NUMBERS NAT
Fig. 20. Program to find passengers paying more than $200.
"USdollars"
PASSENGER
amount Z NAT
PASSENGER
Y
fare
GREATERZ
Y NAT
currency
PASSENGERS
RESULT
amount Z NAT
PASSENGER
Y
fare
GREATERZ
Y NAT
currency
PASSENGERS
RESULT
P3 is the first recorded dependent of P1. We note that any edge from P1 to none PASSENGER will also be deleted. We
also note that, by the semantics of this update program, a passenger can have any number of dependents.
Fig. 21. Program to add P3 to the dependents of P1.
PASSENGER
none
PASSENGER
dependents
PASSENGER
The program in Figure 22 replaces the old time of departure of the flight FL1 FLIGHT by the new time (by the
type-correctness of FL1, there must be some old time in FL1). This program illustrates how the cardinality of the
time_of_dep attribute can be limited to 1.
Fig. 22. Program to replace time of departure of flight FL1 by T1.
time_of_dep
FLIGHT
Our final program in Figure 23 restructures the information about passengers so that it is stored in a number of mappings
(c.f. functional data modelling [31]) rather than in one hypernode per passenger (c.f. relational data modelling).
Fig. 23. Program to restructure passenger information into a number of mappings.
PASS_TO_string
PASS_TO_string
PASS_TO_string
PASS_TO_PASS
SURNAMES
TITLES
string
string
string
Z
surname
initial
title
Y
Y
PASSENGER
name
dependents
INITIALS
We conclude this section by noting that it is not possible to write a Hyperlog rule which deletes an equation. Thus, in
practice, garbage collection has to be achieved outside Hyperlog.
3.4. Operational Semantics of Hyperlog Programs
In this section we specify the operational semantics of Hyperlog via a 2-ary operator INFER(P,HR) where P is a
Hyperlog program and HR is a hypernode repository. INFER(P,HR) returns a new hypernode repository which differs
from HR by the insertions and deletions which are inferred from HR by firing in parallel all the rules in P. A further
operator, FIX(P,HR), computes the fixpoint of P with respect to HR by successive application of INFER(P,HR).
We begin by defining two binary operators on sets of equations, - and #- . Given two sets of equations HR and HR-,
consists of
(i) every equation in HR or HR- such that G - LABELS(HR) - LABELS(HR-), and
(ii) for every pair of equations in HR- with the same left hand side, G, the equation
and HR #- HR- consists of
(i) every equation in HR such that G - LABELS(HR-), and
(ii) for every pair of equations in HR- with the same left hand side, G, the equation
Now, let R be a rule q 0 - q 1 , q 2 , ., q n in a program P, where the head, q 0 , is the query
q be a match for the set of queries {q 1 , q 2 , ., q n }. Given q, let q new be a substitution for NEW R defined as follows :
(i) If NEW
(ii) If there are one or more matches for q 0 q, let q new be an arbitrary one of these matches.
are new labels
superscripted with the appropriate type.
We denote the singleton set {Qqq new = (N+, E+)q} by POS R (q) and the singleton set {Qqq new = (N-, E-)q} by
R (q). We note that the equation in a NEG R (q) may have a right hand side which is not a graph since it may be the
case that there is an edge (n 1 , n 2 ) in E- in which case n 1 - N- and n 2 - N-.
Finally, we define our main operator INFER(P,HR) to be
provided the set of inferred insertions and the set of inferred deletions do not intersect i.e. provided
We do not wish any inferences to be made in the presence of such conflicts since we want a declarative semantics. So
if the above equality does not hold we define INFER(P,HR) to be the old hypernode repository, HR.
We conclude by defining the operator FIX(P,HR) which computes the fixpoint of a hypernode program P with respect
to a hypernode repository HR :
(a) FIX k+1
The following proposition states that FIX(P,HR) is indeed a hypernode repository i.e. it satisfies conditions H1 and H2
of Section 2.1. The proof of the proposition follows easily from the definition of INFER(P,HR), - and #- .
PROPOSITION 1. FIX(P,HR) is a hypernode repository.
Of course the computation of the fixpoint might not terminate. For example, the following program generates the successor
Y NAT of each natural number X NAT , assuming the representation of the natural numbers we have used above and
assuming that 0 is already in the repository. Clearly, this program will carry on generating successors
ad infinitum.
The above rule contains a variable in its head that is not in its body but this is not the only way in which non-termination
can arise. For example, the following program inserts and deletes PER1 into C ad infinitum :
The following proposition states that, if the computation of FIX(P,HR) does terminate, the resulting repository is unique
up to the generation of new labels and the choice of the substitutions q new . The proof follows from the observation that
these are the only non-deterministic steps in INFER(P,HR).
PROPOSITION 2. FIX(P,HR) is unique, up to the drawing of new labels from L and the choice of q new .
We conclude this section by noting that FIX(P,HR) as defined above ignores the type-correctness of the new repository.
In fact, a static type checking of programs can be performed before the fixpoint is computed : a program P is type-correct
if each rule R - P is type-correct; a rule q 0 - q 1 , q 2 , ., q n is type-correct if each query q i is partially typed;
finally, a query Q partially typed if the graph (N+ - N-, E+ - E-) satisfies conditions T1 and
of Section 2.2 with respect to the type T.
We can make a number of observations. Firstly, verifying that the queries in the body of each rule are partially typed
prevents the evaluation of programs which are a priori type-incorrect. Secondly, if the queries in the heads of rule are
partially typed and contain only insertions, the hypernode repository FIX(P,HR) must be well typed (we recall from
Section 3.3 that the null graph null(T), is assumed for dangling labels of type T). Thirdly, deletions in rule heads may
cause conditions (T3) and (T4) of Section 2.2 to be violated. This situation should not be allowed to occur, either by
signaling a run-time error or by inserting (as part of the #- operator) into partially typed graphs the appropriate nodes
and edges from null(T). In order to simplify program specification, we have adopted the latter solution.
3.5. Efficiency of Inference
In this section we examine the efficiency of the INFER(P,HR) operator. We begin by observing that INFER(P,HR) is
decidable since, given a repository HR, there are only a finite number of matches q for a query q with respect to HR
(due to the fact that there are only a finite number of constants that can be drawn from HR). Furthermore, for each rule
and each match q for the body of R, q new is either chosen arbitrarily from a finite number of existing substitutions
or obtained from a finite number of new labels. We now consider two aspects of the efficiency of INFER(P,HR) : the
complexity of finding a match for a query with respect to a hypernode repository, and the potential number of matches
for a query.
The next theorem states that finding a match for a query with respect to a hypernode repository is in general NP-complete

THEOREM 2. Finding a substitution, q, which is a match for a query, q, with respect to a repository, HR, is NP-complete

PROOF. We first show NP-Hardness by showing that this problem contains sub-graph isomorphism, which is known
to be NP-Complete [15], as a sub-problem. Let Q be a positive query of the form G = (N+, E+), where the elements of
N+ are all variables of the same type, and let there be an equation HR. The result follows since q is the
required one-to-one mapping from (N+,E+) to (N-,E-).
We next show that the problem is in NP. Given a query first guess a substitution q for the query with
respect to HR. If there is no equation in HR with left hand side Qq we are done. It remains to show that testing
whether the equation is a match for the query can be performed in a time polynomial in
the size of (N,E) and (N-,E-). The result follows since, on examining the definition of a match given in Section 3.2, we
see that the testing can performed in a time proportional to |N||N-|
Despite this negative result, finding a match is less expensive in the case of certain graphs. For example, in the case
that the graphs in the repository and the graphs in queries are trees, the problem can be solved in polynomial time in the
size of the repository [15]. In practice, much data is record-based and so the corresponding graphs in the repository are
forests (see, for example, the graphs in previous examples). Each such forest is equivalent to one tree whose root is the
label of the graph, and so matching queries is tractable.
With respect to the number of matches for a query, there may exist an exponential number of matches : for example,
given a query (N+,-) such that the elements of N+ are variables of the same type and an equation the
number of matches is |N|!/(|N| - |N+|)!. Negated nodes in queries can also lead to complexity. Consider for example
matching the following rule body :
string }, -)
Clearly, there may be a large number of matches for Y (all the string constants in the database which are not the name
of person PER1). This problem can be avoided by not allowing variables to appear negatively in the body of a rule
without also appearing positively there. Then, given a rule q 0 - q 1 , q 2 , ., q n , if any variable appearing in some N i -
also appears in some N j +, we can construct substitutions q for {q 1 , q 2 , ., q n } by matching all positive information first
(this technique is commonly known as range restriction [2]). For example, we can range restrict the strings in the
above rule body to be names of people thus :
string }, -), X
Negative variables are not the only problem with negative information : negative constant nodes can also lead to additional
complexity when they occur within a query with a variable label. Consider for example matching the following
In such cases the Hyperlog evaluator can at least make use of the type information to search for matches only within
hypernodes of type PERSON.
Reducing the cost of finding all matches for positive information is more problematic. Clearly, given a query
the more variables there are in N+, the greater the number of possible substitutions for these variables.
Again, the type tags of the variables narrow down the number of choices. The edge information (if any) is also of help
here. In addition, for record-based data whose attribute values are polynomially bounded (e.g. single-valued attributes)
the number of matches for a query is polynomial in the size of the repository.
3.6 Expressiveness of Computation
Clearly, Hyperlog is a powerful language with respect to its expressiveness of computations and updates. In fact, it is
both computationally complete and update complete.
We first demonstrate the computational completeness of Hyperlog by showing that it can simulate counter programs,
which are known to be computationally complete [18]. Counter programs manipulate natural numbers which are stored
in variables called counters. Four operations are allowed on counters
where X and Y are counters and := denotes assignment. In addition, counter programs support sequential composition
and a goto statement conditional upon some counter variable being 0.
We can simulate counters in Hyperlog by equations with distinguished left hand side's, CTR NAT , CTR1 NAT , CTR2 NAT ,
. say. We recall that the natural numbers are represented as successive nestings of the primitive node none NAT , where
},-). We can sequence the firing of rules in a counter program by using a set of distinguished labels,
. The current step is contained in the node set of a further hypernode with label SEQ STEPS ,
({STEP},-). At the start of each program, this hypernode is assumed to be
For example, assigning zero to the counter CTR is achieved by inserting 0 into its node set and deleting any non-zero
element already there :
Assigning the value of CTR to a counter CTR1 is achieved by the following rule :
Adding one to CTR is achieved by the following rules, which may generate a new natural number, Y NAT :
Subtracting one from CTR is achieved by the following rule :
Testing CTR for zero is achieved by using the query in the body of a rule. Finally, sequential firing of
rules and conditional goto are achieved by associating STEPs with rules and by updating the SEQ hypernode with the
current STEP. For example, assuming a program with four steps :
the goto statement at STEP2 is simulated by the following rule :
We conclude this section by examining the expressiveness of Hyperlog with respect to database updates. We first
define what an update is in our context and then define the concept of update completeness, by analogy to previous
work in relational databases [1, 8].
Given a type repository TR, we define the set inst(TR) to contain all hypernode repositories which are well-typed with
respect to TR. We define an update to be a partial recursive mapping from inst(TR) to inst(TR) that is C-generic. C-
genericity was introduced in [21] and intuitively means that, apart from a set of distinguished constants C (which may
be the empty set), only the structure of a database is relevant to an update, not the values of the constants in the data-
base. In our case an update, U, is C-generic if the following holds : given a finite set C of constants whose types are
contained in PRIM(TR) - LABELS(TR), for each HR - inst(TR) and each isomorphism r that maps primitive nodes
to primitive nodes, labels to labels, and is invariant on C, r(U(HR)) is equal to U(r(HR)) up to a renaming of newly
generated labels. The set C may be thought of as the constants (primitive nodes or labels) which appear explicitly in
the update program.
Thus, a query language is update complete for the Hypernode Model if it precisely defines the set of updates as defined
above. The update completeness of Hyperlog in particular follows from similar results in [1, 2, 8, 21] for logic-based
languages of comparable semantics.
3.7 Using Hyperlog for Database Browsing
Up to now we have considered querying (and updating) the database by partially specifying the contents of hypernodes.
In contrast, browsing allows the user to navigate through the structure of the database independent of actual values. In
the case of the Hypernode Model, navigation can follow edges either forwards or backwards, it can descend into a node
from a parent graph, or it can ascend into a parent graph from a node. We show below how these navigational operators
can be implemented in Hyperlog. In general, it will be difficult for the user to predict the types of the hypernodes
that will be encountered while browsing to the database. So in order to facilitate browsing we introduce the type ANY
as a super-type of every type i.e. we consider any hypernode or primitive node to be of type ANY.
We first define three types :
Instances of type CONTEXT will typically contain two nodes, one of type CURRENT_HYP which contains a hypernode
and the other of type CURRENT_NODE which contains a specific node within this hypernode. The current context
can thus be recorded in a hypernode
where CUR_HYP contains the current hypernode in the navigation and CUR_NODE contains the specific node within
the current hypernode currently being browsed.
The current hypernode can be updated from a hypernode OLD, say, to a hypernode NEW by the rule
Similarly, the current node can be updated from OLD to NEW by the rule
We observe that this rule verifies the new current node is indeed in the node set of the current hypernode.
In order to navigate forwards, we can store in a hypernode CUR_OUT CURRENT_NODE the nodes connected to the current
node by edges outgoing from it : we initialise the previous contents of CUR_OUT using the rule
and we store the "next" nodes in CUR_OUT using the rule
Similarly, in order to navigate backwards, we can store in a hypernode CUR_IN CURRENT_NODE the nodes connected to
the current node by edges incoming to it : we initialise the previous contents of CUR_IN as for CUR_OUT above and
we store the "previous" nodes in CUR_IN using the rule
In order to navigate upwards, we store in a hypernode CUR_UP CURRENT_NODE all the hypernodes containing the current
hypernode : we initialise the previous contents of CUR_UP and use the rule
Finally, in order to navigate downwards, we store in a hypernode CUR_DOWN CURRENT_NODE all the nodes contained in
the node set of the current node (if this is not a primitive node) : we initialise the previous contents of CUR_DOWN
and use the rule
Browsing using Hyperlog was investigated further in [13]. In particular, it was shown that Hyperlog can support the
declarative querying of the content and structure of a Hypertext database. This database was constructed by associating
hypernodes with fragments of text and by using further hypernodes to store named links between these fragments. A
"history" hypernode records the user's navigation through the database. A number of alternative "trails" can be set up
and stored. The navigational functions supported include display of a hypernode (and any associated text), and the four
operators described above.
4. COMPARISON WITH RELATED WORK
In this section we compare the Hypernode Model and Hyperlog with related languages and models. We begin with the
logic-based database language IQL [2] from which the semantics of Hyperlog are partly derived. We next consider
three recent graph-based data models [12, 17, 23]. Finally we consider recent work on hypergraph-based models [25,
33, 36].
IQL incorporates object-identities into a typed rule-based query language which is update complete. The fixpoint
semantics of Hyperlog are similar to those discussed in [2, 3], but our label generation semantics differ from IQL's
invention of object identities in that we generate new labels as a necessary consequence of new graphs being inferred
whereas in IQL the generation of an object identity and the assignment of a value to it are independent events. Also,
IQL's types are constructed using tuple, set, union and intersection constructors while Hyperlog has one general-purpose
graph constructor which can simulate all of these.
We next compare the Hypernode Model with three recent graph-based data models : the Logical Data Model (LDM)
[23], GOOD [17], and Graphlog [12]. In LDM only database schemas are directed graphs : instances consist of 2-
column tables each of which associates entities of a particular type with their values. Also, LDM's schema graphs use
three types of node, basic (for primitive data types), composition (for tuple types) and collection (for set types),
whereas we can represent tuple types and set types by our one general-purpose graph constructor. Graphlog [12] is a
query language operating on a database which comprises a directed labelled graph (a semantic net). The edges in this
graph represent predicates. Unlike Hyperlog, Graphlog queries are formulated as graphs whose edges are annotated
with predicates, transitive closures thereof or, more generally, regular expressions. These query graphs are matched
against the database graph and return sub-graphs thereof. GOOD [17] is a graphically-represented functional data
model [31] with an associated transformation language. GOOD embeds semantics into the nodes and edges of this
graph, nodes being printable or non-printable and edges being single-valued or multi-valued. The queries of GOOD's
transformation language are graphs called patterns, which match sub-graphs of the total instance graph c.f. our matching
of queries against a hypernode repository. In contrast to Hyperlog's rule-based updates, GOOD's instance graph is
updated by five graphically-represented primitive operations (add or delete a node or an edge, and an operation called
"abstraction") which can be incorporated into patterns.
In summary, a feature common to all these models is that the database consists of a single flat graph. This has the
drawback that, in practice, complex objects consisting of many inter-connected nodes are hard to present to the user in
a clear way. In contrast, a hypernode database consists of a set of nested graphs. This unique feature of our model provides
inherent support for data abstraction and the ability to represent each real-world object as a separate database
entity. GOOD does allow for an "abstraction" operation but this generates a non-printable entity and connects it to
other, related, entities at the same level c.f. our nesting of a set of graphs within a graph. Unlike GOOD and Graphlog,
we do not label edges in the Hypernode Model. However, we can attain the same data modelling expressiveness by
encapsulating edges which would have the same label in GOOD or Graphlog within one hypernode with a similar label.
For example, we can represent the set of GOOD edges
by the hypernode :
We conclude this section with a review of recent work on hypergraph-based data models [25, 33, 36], and a comparison
of this work with our model. We first observe that hypergraphs can be modelled by hypernodes by encapsulating the
contents of each hyperedge within a further hypernode. In contrast, the multi-level nesting provided by hypernodes
cannot easily be captured by hypergraphs.
In [33], hypergraphs are used to model page-oriented Hypertext databases. The nodes of a hypergraph are associated
with pages of information. Each hyperedge consists of a related set of labelled directed edges. Nodes and directed
edges can be shared between hyperedges. Querying of a hypergraph is navigational and uses a number of predefined
browsing forwards or backwards along directed edges from a set of marked nodes, marking a new set of
nodes, reading the set of pages associated with the current marked nodes, querying the current state, and saving and
resetting current states. Views can be created and the database hypergraph can be updated by a number of further primitive
operators. Unlike the Hypernode Model, hypergraphs are not typed and so updates are not semantically con-
strained. Also unlike Hyperlog, querying by database content is not supported.
In [36] a hypergraph-based model of data access is presented which aims to integrate browsing and querying. In this
model, entities are represented by nodes and relationships between them by hyperedges. The resulting hypergraph is
transient, lasting for the duration of a query session. It starts off consisting of one hyperedge containing all the database
entities and further hyperedges are added to it in response to user queries. At any stage, the hypergraph can be
traversed by moving within hyperedges, and from hyperedge to hyperedge via a common node. There are a number of
differences between this work and our own. Firstly, all the database entities are assumed to be of the same type and are
stored as tuples in a single, flat, relation. Secondly, the attributes of entities are not represented graphically within the
hypergraph and exist only in the underlying relation. Thirdly, although browsing is graph-based, querying is not - it
consists of specifying boolean-valued expressions in the values of attributes - hence, a hybrid model of browsing and
querying is obtained.
In [25] we described a data model called GROOVY (Graphically-Represented Object-Oriented data model with
Values). In GROOVY, real-world entities are represented by means of instances of object schemas. We showed that
the representation of object schemas by means of hypergraphs leads to a natural formalisation of the notions of sub-object
sharing and structural inheritance. We also showed how instances of object schemas can be represented by
hypergraphs labelled with object identifiers. GROOVY is a conceptual data model which influenced the development
of the Hypernode Model. It has been superseded by our more recent work on types, Hyperlog, and implementation.
5. SYSTEM ARCHITECTURE AND IMPLEMENTATION
We are currently coming to the end of a two-year project whose goal is to implement a prototype DBMS based on the
Hypernode Model and to tailor it to the needs of Hypertext databases. The architecture of our system is shown in Figure
Graph-based
User Interface
Hyperlog
Evaluator
Transient
Hypernode Store
Storage Manager

Figure

24. The Hypernode Database System architecture.
In this architecture, the Storage Manager stores hypernodes, types and programs while the Index Manager supports
efficiently three operations :
(i) given a label, G, return the unique graph (N,E) such that
(ii) given a primitive node, n, return the set of labels {G 1 , ., G r } such that for each equation G
(iii) given a label, G, return the set of labels {G 1 , ., G r } such that for each equation G
A detailed description of the Storage Manager appears in [34]. Briefly, the Storage Manager supports a number of
object stores, each object store containing graphs of one type. Two object stores are reserved for the storage of types
and programs. Associated with each object store is a label table which maps labels to the physical addresses of the
graphs they define, thereby implementing operation (i) above. Operation (ii) is implemented using a simple prefix B-tree
and operation (iii) is implemented by an extendible hashing scheme.
These operations are invoked by the Hyperlog Evaluator during its matching of queries. The evaluator computes the
fixpoint of a program with respect to the repository, after verifying that the program is correctly typed. Updated hypernodes
are amassed in the Transient Hypernode Store during each inference step. The evaluator currently uses bottom-
9up, naive [35] evaluation of Hyperlog programs although we are now looking at optimising the fixpoint computation by
drawing on existing optimisation techniques for logic database languages, such as semi-naive evaluation [35].
6.


We have presented the Hypernode Model, a graph-based data model which stores nested graphs in the form of
equations and manipulates them via a rule-based language. The key innovations of the model are :
its formal foundation on graphs and set theory,
its use of graphs throughout all levels, from the user interface down to the physical level,
its inherent support for data modelling concepts such as object identity, complex objects, and encapsulation,
its provision for types and type checking,
its associated query language Hyperlog which can support both querying and browsing, and which allows both
derivations and database updates,
its uniform storage of data (hypernodes), meta data (types), and procedural data (Hyperlog programs).
We have examined the efficiency of type checking and have shown it can be performed in polynomial time. We have
also examined the expressiveness of representation, computation and update of our model and have shown that Hyper-
log is computationally and update complete. Although the evaluation of Hyperlog programs is intractable in the general
case, we have discussed cases when evaluation becomes tractable. We have compared our model with other graph-based
models. Our comparison has highlighted the advantages of nested graphs, both at the type and the instance lev-
els. Finally, we have briefly discussed a prototype DBMS architecture and implementation. Our current research effort
is directed towards tailoring our hypernode DBMS to the needs of Hypertext. This includes optimisation of Hyperlog,
support for versioning, and provision of special-purpose access methods to implement more efficiently the browsing
and text retrieval operations.

ACKNOWLEDGEMENTS

The Hypernode Project is supported financially by the U.K. Science and Engineering Research Council (grant number
GR/G26662).



--R

Procedural and declarative database update languages.
Object identity as a query language primitive.
Fixpoint extensions of first-order logic and Datalog-like languages

Formal models for object oriented databases.

Logic Programming and Databases

P-S. The Entity-Relationship Model - towards a unified view of data
Extending the database relational model to capture more meaning.
An introduction and survey.
Mendelzon A.
A hypertext database implemented using the Hypernode Model.

Johnson D.
Three principles of representation for semantic networks.
A graph-oriented object database model

On visual formalisms.
database modelling


M.
The hypernode model and its associated query language.
An object-oriented data model formalised through hypergraphs
A logical language for data and knowledge bases.
Complex object modelling
Semantic issues in deductive databases and logic programs.
On closed world databases.
The relational model with relation-valued attributes
The functional data model and the data language DAPLEX.
Research Directions in Object-Oriented Programming
A data model for flexible hypertext database systems.
A storage manager for the Hypernode Model.
Principles of Database and Knowledge-Base Systems
A transient hypergraph-based model for data access

--TR
The relational model with relation-valued attributes
Hypertext: an introduction and survey
Algorithmics: the spirit of computing
On visual formalisms
Principles of database and knowledge-base systems, Vol. I
database modeling: survey, applications, and research issues
A logical language for data and knowledge bases
A data model for flexible hypertext database systems
Object identity as a query language primitive
Untyped sets, invention, and computable queries
Fixpoint extensions of first-order logic and datalog-like languages
Logic programming and databases
Complex objects modeling: an entity-relationship approach
A transient hypergraph-based model for data access
The hypernode model and its associated query language
An object-oriented data model formalised through hypergraphs
GraphLog
A graph-oriented object database model
Procedural and declarative database update languages
The functional data model and the data languages DAPLEX
Three principles of representation for semantic networks
Extending the database relational model to capture more meaning
The entity-relationship modelMYAMPERSANDmdash;toward a unified view of data
Computers and Intractability
A new approach to database logic
Object-Oriented Databases
A Storage Manager for the Hypernode Model

--CTR
Stefan G. Hild , Alexandra Poulovassilis, Hyperlog: a system for database querying and browsing, Proceedings of the workshop on Advanced visual interfaces, May 27-29, 1996, Gubbio, Italy
Sankhayan Choudhury , Nabendu Chaki , Swapan Bhattacharya, GDM: a new graph based data model using functional abstractionx, Journal of Computer Science and Technology, v.21 n.3, p.430-438, May 2006
Mark Levene , Alexandra Poulovassilis , Kerima Benkerimi , Sara Schwartz , Eran Tuv, Implementation of a graph-based data model for complex objects, ACM SIGMOD Record, v.22 n.4, p.26-31, Dec. 1993
Manoj Chavda , Peter T. Wood, Towards an ODMG-Compliant Visual Object Query Language, Proceedings of the 23rd International Conference on Very Large Data Bases, p.456-465, August 25-29, 1997
Alexandra Poulovassilis , Stefan G. Hild, Hyperlog: A Graph-Based System for Database Browsing, Querying, and Update, IEEE Transactions on Knowledge and Data Engineering, v.13 n.2, p.316-333, March 2001
Mark Levene , George Loizou, A Graph-Based Data Model and its Ramifications, IEEE Transactions on Knowledge and Data Engineering, v.7 n.5, p.809-823, October 1995
Giorgio Busatto , Hans-Jrg Kreowski , Sabine Kuske, Abstract hierarchical graph transformation, Mathematical Structures in Computer Science, v.15 n.4, p.773-819, August 2005
Salvatore T. March , Charles A. Wood , Gove N. Allen, Research Frontiers in Object Technology, Information Systems Frontiers, v.1 n.1, p.51-74, July 1999
object store;rule-based query and update language;complex object;nested graph;types