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

 

Show simple item record

dc.contributor.advisor Wood, Peter Theodore en_ZA
dc.contributor.author Maharaj, Anish en_ZA
dc.date.accessioned 2015-07-14T09:03:23Z
dc.date.available 2015-07-14T09:03:23Z
dc.date.issued 1995 en_ZA
dc.identifier.citation Maharaj, A. 1995. The efficient evaluation of visual queries within a logic-based framework. University of Cape Town. en_ZA
dc.identifier.uri http://hdl.handle.net/11427/13526
dc.description Bibliography: leaves 149-153. en_ZA
dc.description.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. en_ZA
dc.language.iso eng en_ZA
dc.subject.other Computer Science en_ZA
dc.title The efficient evaluation of visual queries within a logic-based framework en_ZA
dc.type Master Thesis
uct.type.publication Research en_ZA
uct.type.resource Thesis en_ZA
dc.publisher.institution University of Cape Town
dc.publisher.faculty Faculty of Science en_ZA
dc.publisher.department Department of Computer Science en_ZA
dc.type.qualificationlevel Masters
dc.type.qualificationname MSc en_ZA
uct.type.filetype Text
uct.type.filetype Image
dc.identifier.apacitation Maharaj, A. (1995). <i>The efficient evaluation of visual queries within a logic-based framework</i>. (Thesis). University of Cape Town ,Faculty of Science ,Department of Computer Science. Retrieved from http://hdl.handle.net/11427/13526 en_ZA
dc.identifier.chicagocitation Maharaj, Anish. <i>"The efficient evaluation of visual queries within a logic-based framework."</i> Thesis., University of Cape Town ,Faculty of Science ,Department of Computer Science, 1995. http://hdl.handle.net/11427/13526 en_ZA
dc.identifier.vancouvercitation Maharaj A. The efficient evaluation of visual queries within a logic-based framework. [Thesis]. University of Cape Town ,Faculty of Science ,Department of Computer Science, 1995 [cited yyyy month dd]. Available from: http://hdl.handle.net/11427/13526 en_ZA
dc.identifier.ris TY - Thesis / Dissertation AU - Maharaj, Anish AB - 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. DA - 1995 DB - OpenUCT DP - University of Cape Town LK - https://open.uct.ac.za PB - University of Cape Town PY - 1995 T1 - The efficient evaluation of visual queries within a logic-based framework TI - The efficient evaluation of visual queries within a logic-based framework UR - http://hdl.handle.net/11427/13526 ER - en_ZA


Files in this item

This item appears in the following Collection(s)

Show simple item record