Expressing structural hypertext queries in graphlog

ABSTRACT

GraphLog is a visual query language in which queries are formulated by drawing graph patterns. The hyperdocument graph is searched for all occurrences of these patterns. The language is powerful enough to allow the specification and manipulation of arbitrary subsets of the network and supports the computation of aggregate functions on subgraphs of the hyperdocument. It can support dynamically defined structures as well as inference capabilities, going beyond current static and passive hypertext systems. The expressive power of the language is a fundamental issue: too little power limits the applications of the language, while too much makes efficient implementation difficult and probably affects ease of use. The complexity and expressive power of GraphLog can be characterized precisely by using notions from deductive database theory and descriptive complexity. In this paper, from a practical point of view, we present examples of GraphLog queries applied to several different hypertext systems, providing evidence for the expressive power of the language, as well as for the convenience and naturalness of its graphical representation. We also describe an ongoing implementation of the language.

REFERENCES

• Adam87: Sam S. Adams. NodeGraph-80 Version 1.0. Knowledge Systems Corporation, 1987.
• Aho79: Alfred V. Aho , Jeffrey D. Ullman, Universality of data retrieval languages, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.110-119, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567763]
• Bege88: Michael L. Begeman , Jeff Conklin, The right tool for the job, BYTE, v.13 n.10, p.255-266, October 1988
• Bige88: James Bigelow, Hypertext and CASE, IEEE Software, v.5 n.2, p.23-27, March 1988 [doi>10.1109/52.2007]
• Bige87: James Bigelow , Victor Riley, Manipulating source code in DynamicDesign, Proceeding of the ACM conference on Hypertext, p.397-408, November 1987, Chapel Hill, North Carolina, United States [doi>10.1145/317426.317454]
• Camp87: Brad Campbell , Joseph M. Goodman, HAM: a general-purpose hypertext abstract machine, Proceeding of the ACM conference on Hypertext, p.21-32, November 1987, Chapel Hill, North Carolina, United States [doi>10.1145/317426.317429]
• Cons89: Mariano P. Consens. Graphlog: "real life" recursive queries using graphs. Master's thesis, Department of Computer Science, University of Toronto, 1989.
• Deli86: Norman Delisle , Mayer Schwartz, Neptune: a hypertext system for CAD applications, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.132-143, May 28-30, 1986, Washington, D.C., United States
• Fris88a: Mark Frisse, From text to hypertext, BYTE, v.13 n.10, p.247-253, October 1988
• Fris88b: Mark,E. Frisse, Searching for information in a hypertext medical handbook, Communications of the ACM, v.31 n.7, p.880-886, July 1988 [doi>10.1145/48511.48518]
• Garg88: Pankaj,K. Garg, Abstraction mechanisms in hypertext, Communications of the ACM, v.31 n.7, p.862-870, July 1988 [doi>10.1145/48511.48516]
• Gold84: Adele Goldberg, SMALLTALK-80: the interactive programming environment, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984
• Gold83: Adele Goldberg , David Robson, Smalltalk-80: the language and its implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• Hala88: Frank,G. Halasz, Reflections on NoteCards: seven issues for the next generation of hypermedia systems, Communications of the ACM, v.31 n.7, p.836-852, July 1988 [doi>10.1145/48511.48514]
• Hala87: Frank G. Halasz , Thomas P. Moran , Randall H. Trigg, Notecards in a nutshell, Proceedings of the SIGCHI/GI conference on Human factors in computing systems and graphics interface, p.45-52, April 05-09, 1987, Toronto, Ontario, Canada
• Klug82: Anthony Klug, Equivalence of Relational Algebra and Relational Calculus Query Languages Having Aggregate Functions, Journal of the ACM (JACM), v.29 n.3, p.699-717, July 1982 [doi>10.1145/322326.322332]
• Mend89: A. O. Mendelzon , P. T. Wood, Finding regular simple paths in graph databases, Proceedings of the 15th international conference on Very large data bases, p.185-193, July 1989, Amsterdam, The Netherlands
• Ullm88: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

General Terms:
Design, Languages