ylkingsbury@watdragon.waterloo.edu (Yvonne Kingsbury) (06/21/89)
The University of Waterloo
200 University Avenue
Waterloo, Ontario
The Institute of Computer Research (ICR)
Presents a Colloquium on
The G+ Project: Graphs, Databases, and Hypertext
by Dr. Alberto O. Mendelzon
of Department of Computer Science, University of Toronto
ABSTRACT
Two different technologies for providing access to information have developed
in parallel: relational databases, with powerful query and data manipulation
languages, and Hypertext systems that emphasize text and graphical information
and provide interactive interfaces for browsing and editing. Typical database
systems offer poor interaction facilities which fail to exploit today's
workstation architectures, while Hypertext systems lack adequate query
mechanisms. The research we will describe aims to combine the advantages of
database systems with those of Hypertext.
A collection of documents in a Hypertext system can be viewed as a directed
labelled multigraph. We view queries as graph patterns; the answer to the
query is the set of subgraphs of the database graph that match the given
pattern. Graph patterns are themselves graphs, and they can be specified
by drawing them on a screen. We will present our query interface, called G+,
which incorporates into a Hypertext system the ability to formulate complex
queries.
We will also discuss the theoretical underpinnings of G+: expressive power,
computational complexity of query evaluation, and efficient algorithms for
query answering. Some of these results have guided the design of a new
language called GraphLog. GraphLog incorporates negation and a simpler
semantics that makes it exactly equivalent to stratified linear Datalog.
We will show how GraphLog can be used to express a variety of queries that have
been proposed in the Hypertext literature.
Wednesday, June 28, 1989
3:30 p.m.
William G. Davis Computer Research Centre, Room 1302
Everyone is welcome. Refreshments served.