A transient hypergraph-based model for data access

ABSTRACT

Two major methods of accessing data in current database systems are querying and browsing. The more traditional query method returns an answer set that may consist of data values (DBMS), items containing the answer (full text), or items referring the user to items containing the answer (bibliographic). Browsing within a database, as best exemplified by hypertext systems, consists of viewing a database item and linking to related items on the basis of some attribute or attribute value. A model of data access has been developed that supports both query and browse access methods. The model is based on hypergraph representation of data instances. The hyperedges and nodes are manipulated through a set of operators to compose new nodes and to instantiate new links dynamically, resulting in transient hypergraphs. These transient hypergraphs are virtual structures created in response to user queries, and lasting only as long as the query session. The model provides a framework for general data access that accommodates user-directed browsing and querying, as well as traditional models of information and data retrieval, such as the Boolean, vector space, and probabilistic models. Finally, the relational database model is shown to provide a reasonable platform for the implementation of this transient hypergraph-based model of data access.

REFERENCES

• 1: Giorgio Ausiello , Alessandro D'Atri, Graph Algorithms for the Synthesis and Manipulation of Data Base Schemes, Proceedings of the International Workshop on Graphtheoretic Concepts in Computer Science, p.212-233, June 15-18, 1980
• 2: Carlo Batini , Alessandro D'Atri, Schema Hypergraphs: A Formalism to Investigate Logical Data Base Design, Proceedings of the International Workshop on Graphtheoretic Concepts in Computer Science, p.177-194, June 15-18, 1980
• 3: N. J. Belkin , B. H. Kwaśnik, Using structural representation of anomalous states of knowledge for choosing document retrieval strategies, Proceedings of the 9th annual international ACM SIGIR conference on Research and development in information retrieval, p.11-22, September 1986, Palazzo dei Congressi, Pisa, Italy [doi>10.1145/253168.253175]
• 4: C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985
• 5: BOOKSTEIN, A., AND SWANSON, D.R. Probabilistic models for automatic indexing. J. Am. Soc. Inf. Sci. 26, 1 (Jan.-Feb. 1975), 45-50.
• 6: BUSH, V. As we may think. Atlantic Monthly 176 (July 1945), 101-108.
• 7: S. Cater , D. Kraft, TIRS: a topological information retrieval system satisfying the requirements of the Waller-Kraft wish list, Proceedings of the 10th annual international ACM SIGIR conference on Research and development in information retrieval, p.171-180, June 03-05, 1987, New Orleans, Louisiana, United States [doi>10.1145/42005.42025]
• 8: Jeff Conklin, Hypertext: an introduction and survey, Computer, v.20 n.9, p.17-41, Sept. 1987 [doi>10.1109/MC.1987.1663693]
• 9: CONKLIN, J. A survey of hypertext. Tech. Rep. STP-356-86, Rev. 2, Microelectronics and Computer Technology Corp., Austin, Tex., 1987.
• 10: M. P. Consens , A. O. Mendelzon, Expressing structural hypertext queries in graphlog, Proceedings of the second annual ACM conference on Hypertext, p.269-292, November 1989, Pittsburgh, Pennsylvania, United States [doi>10.1145/74224.74247]
• 11: CRAWFORD, R. G., AND YEUNG, K. Specifying information retrieval models in a relational system. Canadian J. Inf. Sci. 13, 1/2 (Sept. 1988), 1-16.
• 12: W. B. Croft , R. H. Thompson, I3R: a new approach to the design of document retrieval systems, Journal of the American Society for Information Science, v.38 n.6, p.389-404, Nov. 1987 [doi>10.1002/(SICI)1097-4571(198711)38:6<389::AID-ASI1>3.0.CO;2-4]
• 13: W. B. Croft , H. Turtle, A retrieval model incorporating hypertext links, Proceedings of the second annual ACM conference on Hypertext, p.213-224, November 1989, Pittsburgh, Pennsylvania, United States [doi>10.1145/74224.74242]
• 14: D. B. Crouch , C. J. Crouch , G. Andreas, The use of cluster hierarchies in hypertext information retrieval, Proceedings of the second annual ACM conference on Hypertext, p.225-237, November 1989, Pittsburgh, Pennsylvania, United States [doi>10.1145/74224.74243]
• 15: 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
• 16: Norman M. Delisle , Mayer D. Schwartz, Contexts—a partitioning concept for hypertext, ACM Transactions on Information Systems (TOIS), v.5 n.2, p.168-186, April 1987 [doi>10.1145/27636.27639]
• 17: Ronald Fagin , Alberto O. Mendelzon , Jeffrey D. Ullman, A simplied universal relation assumption and its properties, ACM Transactions on Database Systems (TODS), v.7 n.3, p.343-360, Sept. 1982 [doi>10.1145/319732.319735]
• 18: Janet Fiderio, A grand vision, BYTE, v.13 n.10, p.237-244, October 1988
• 19: Mark Edwin Frisse, Searching for information in a hypertext medical handbook, Proceeding of the ACM conference on Hypertext, p.57-66, November 1987, Chapel Hill, North Carolina, United States [doi>10.1145/317426.317433]
• 20: M. E. Frisse , S. B. Cousins, Information retrieval from hypertext: update on the dynamic medical handbook project, Proceedings of the second annual ACM conference on Hypertext, p.199-212, November 1989, Pittsburgh, Pennsylvania, United States [doi>10.1145/74224.74241]
• 21: R. Furuta , P. D. Stotts, Programmable browsing semantics in Trellis, Proceedings of the second annual ACM conference on Hypertext, p.27-42, November 1989, Pittsburgh, Pennsylvania, United States [doi>10.1145/74224.74227]
• 22: 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]
• 23: Pankaj K. Garg , Walt Scacchi, On designing intelligent hypertext systems for information management in software engineering, Proceeding of the ACM conference on Hypertext, p.409-432, November 1987, Chapel Hill, North Carolina, United States [doi>10.1145/317426.317455]
• 24: 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]
• 25: KACMAR, C., LEGGETT, J., SCHNASE, J. L., AND BOYLE, C. Data management facilities of existing hypertext systems. Tech. Rep. TAMU 88-018, Hypertext Research Lab., Texas A&M Univ., College Station, Tex., 1988, 28.
• 26: James A. Larson, A visual approach to browsing in a database environment, Computer, v.19 n.6, p.62-71, June 1986 [doi>10.1109/MC.1986.1663255]
• 27: Christophe Lécluse , Nicolas Spyratos, Implementing Queries and Updates on Universal Scheme Interfaces, Proceedings of the 14th International Conference on Very Large Data Bases, p.62-75, August 29-September 01, 1988
• 28: David Maier , Jeffrey D. Ullman, Maximal objects and the semantics of universal relation databases, ACM Transactions on Database Systems (TODS), v.8 n.1, p.1-14, March 1983 [doi>10.1145/319830.319831]
• 29: M. E. Maron , J. L. Kuhns, On Relevance, Probabilistic Indexing and Information Retrieval, Journal of the ACM (JACM), v.7 n.3, p.216-244, July 1960 [doi>10.1145/321033.321035]
• 30: Theodor H. Nelson, Managing immense storage, BYTE, v.13 n.1, p.225-238, January 1988
• 31: M.M. Owrang , L. L. Miller, Query translation based on hypergraph models, The Computer Journal, v.31 n.2, p.155-164, April, 1988 [doi>10.1093/comjnl/31.2.155]
• 32: H. Van Dyke Parunak, Hypermedia topologies and user navigation, Proceedings of the second annual ACM conference on Hypertext, p.43-50, November 1989, Pittsburgh, Pennsylvania, United States [doi>10.1145/74224.74228]
• 33: Darrell,R. Raymond , Frank,WM. Tompa, Hypertext and the Oxford English dictionary, Communications of the ACM, v.31 n.7, p.871-879, July 1988 [doi>10.1145/48511.48517]
• 34: Gerard. Salton, Automatic Information Organization and Retrieval., McGraw Hill Text, 1968
• 35: G. Salton , A. Wong , C. S. Yang, A vector space model for automatic indexing, Communications of the ACM, v.18 n.11, p.613-620, Nov. 1975 [doi>10.1145/361219.361220]
• 36: SCHNASE, J. L., LEGGETT, J., KACMAR, C., AND BOYLE, C. A comparison of hypertext systems. Tech. Rep. TAMU 88-017. Hypertext Research Lab., Texas A&M Univ., 1988.
• 37: SHEPHERD, M. A., AND WATTERS, C.R. Hypertext: User-driven interfaces. Mid-Year Conference of the American Society for Information Science (San Diego, Calif., May 21-24, 1989). In Press.
• 38: M. A. Shepard , C. R. Watters , Y. Cai, Transient hypergraphs for citation networks, Information Processing and Management: an International Journal, v.26 n.3, p.395-412, 1990 [doi>10.1016/0306-4573(90)90099-N]
• 39: P. David Stotts , Richard Furuta, Petri-net-based hypertext: document structure with browsing semantics, ACM Transactions on Information Systems (TOIS), v.7 n.1, p.3-29, Jan. 1989 [doi>10.1145/64789.64791]
• 40: Frank WM. Tompa, A data model for flexible hypertext database systems, ACM Transactions on Information Systems (TOIS), v.7 n.1, p.85-100, Jan. 1989 [doi>10.1145/64789.64993]
• 41: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983
• 42: WATTERS, C. R., AND SHEPHERD, M.A. Transient links in hypertext. Paper presented at the 17th Annual Conference of the Canadian Association for Information Science (Toronto, May 31-June 2, 1989).
• 43: Nichole Yankelovich , Bernard J. Haan , Norman K. Meyrowitz , Steven M. Drucker, Intermedia: The Concept and the Construction of a Seamless Information Environment, Computer, v.21 n.1, p.81-83, 90-96, January 1988 [doi>10.1109/2.222120]
• 44: ZLOOF, M. Query by example: A data base language. In Proceedings of 1975 National Computer Conference (Anaheim, Calif., June 1975).

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods
      H.2.4 Systems
          Subjects: Query processing
  H.3 INFORMATION STORAGE AND RETRIEVAL
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.1 Multimedia Information Systems
          Subjects: Hypertext navigation and maps**

General Terms:
Design