The efficient evaluation of visual queries within a logic-based framework

Master Thesis

1995

Permanent link to this Item
http://hdl.handle.net/11427/13526
Files
thesis_sci_1995_maharaj_a.pdf (5.32 MB)
Authors
Maharaj, Anish
Supervisors
Wood, Peter Theodore
Journal Title
Link to Journal
Journal ISSN
Volume Title
Publisher
Publisher

University of Cape Town

Department
Department of Computer Science
Faculty
Faculty of Science
License
Series
Abstract
There has been much research in the area of visual query systems in recent years. This has stemmed from the need for a more powerful database visualization and querying ability. In addition, there has been a pressing need for a more intuitive interface for the non-expert user. Systems such as Hy+, developed at the University of Toronto, provide environments that satisfy a wide range of database interaction and querying, with the advantage of maintaining a visual interface abstraction throughout. This thesis explores issues related to the translation and evaluation of visual queries, including semantic and optimization possibilities. The primary focus will be on the GraphLog query language, defined in the context of the Hy+ visualization system. GraphLog is translated to the deductive database language Datalog, which is subsequently evaluated by the CORAL logic database system. We propose graph semantics, which define the meaning of visual queries in terms of paths in a graph, for monotone GraphLog. This provides a more intuitive meaning which is not linked to any particular translation. Therefore, Datalog generated by a translation may be compared to well-defined semantics to ensure that the translation preserves the intended meaning. By examining various queries in terms of the graph semantics, we uncover a shortcoming in the existing GraphLog translation. In addition, an alternative translation to Datalog, based on the construction of a nondeterministic finite state automaton, is described for GraphLog queries. The translation has the property that visual queries containing constants are optimized using a technique known as factoring. In addition, the translation performs an optimization on queries with multiple edges that contain no constants, referred to here as variable constraining.
Description

Bibliography: leaves 149-153.

Keywords
Computer Science

Reference:

Maharaj, A. 1995. The efficient evaluation of visual queries within a logic-based framework. University of Cape Town.

Collections
Masters