More Web Proxy on the site http://driver.im/

article

Free access

A transient hypergraph-based model for data access

Editor: Robert B. Allen Authors:

Carolyn Watters,

Michael A. ShepherdAuthors Info & Claims

ACM Transactions on Information Systems (TOIS), Volume 8, Issue 2

Pages 77 - 102

https://doi.org/10.1145/96105.96107

Published: 01 April 1990 Publication History

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]

AUSIELLO, G., AND D'ATRI, A. Graph algorithms for the synthesis and manipulation of data base schemes. In Lecture Notes in Computer Science. G. Goos and J. Hartmanis, Eds., Springer- Verlag, Berlin, 1981, 212-235.

[2]

BATINI, C., AND D'ATRI, A. Schema hypergraphs: A formalism to investigate logical data base design. In Lecture Notes in Computer Science. G. Goos and J. Hartmanis, Eds. Springer-Verlag, Berlin, 1981, 177-194.

[3]

BELKIN, N. J., AND KWASMICK, B.H. Using structural representations of anomalous states of knowledge for choosing document retrieval strategies. In Proceedings of the 1986 ACM Conference on Research and Development in Information Science (Pisa, Sept. 8-10, 1986). ACM, New York, 1986, 11-22.

[4]

BERGE, C. Graphs and Hypergraphs. North-Holland, Amsterdam, 1973.

[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]

CATER, S., AND KRAFT, D. TIRS: A topological information retrieval system satisfying the requirements of the Waller-Kraft wish list. In Proceedings of the Tenth Annual International A CMSIGIR Conference on Research and Development in Information Retrieval (New Orleans, La., June 3-5, 1987). ACM, New York, 1987, 171-180.

[8]

CONKLIN, J. Hypertext: An introduction and survey. IEEE Comput. 20, 9 (1987), 17-41.

[9]

CONKLIN, J. A survey of hypertext. Tech. Rep. STP-356-86, Rev. 2, Microelectronics and Computer Technology Corp., Austin, Tex., 1987.

[10]

CONSENS, M. P., AND MENDELZON, A.O. Expressing structural hypertext queries in GraphLog. In Hypertext '89 Proceedings (Pittsburgh, Pa., Nov. 5-8, 1989). ACM, New York, 1989, 269-292.

[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]

CROFT, W. B., AND THOMPSON, R.H. I3R: A new approach to the design of document retrieval systems. J. Am. Soc. Inf. Sci. 38, 6 (1987), 389-404.

[13]

CROFT, W. B., AND TURTLE, H. A retrieval model incorporating hypertext links. In Hypertext '89 Proceedings (Pittsburgh, Pa., Nov. 5-8, 1989). ACM, New York, 1989, 213-224.

[14]

CROUCH, D. B., CROUCH, C. J., AND ANDREAS, G. The use of cluster hierarchies in hypertext information retrieval. In Hypertext '89 Proceedings (Pittsburgh, Pa., Nov. 5-8, 1989). ACM, New York, 1989, 225-237.

[15]

DELISLE, N., AND SCHWARTZ, M. Neptune: A hypertext system for CAD applications. In Proceedings of SIGMOD '86 (Washington, D.C., May 28-30, 1986), 132-143.

[16]

DELISLE, N., AND SCHWARTZ, M. Contexts--A partitioning concept for hypertext. ACM Trans. Office Inf. Syst. 5, 2 (1987), 168-186.

[17]

FAGIN, R., MENDELZON, A., AND ULLMAN, J. A simplified universal relation assumption and its properties. ACM Trans. Database Syst. 7, 3 (1982), 343-360.

[18]

FIDERIO, J. A grand vision. Byte 13, 10 (1988), 237-244.

[19]

FRISSE, M.E. Searching for information in a hypertext medical handbook. In Proceedings of Hypertext "87 (Univ. of North Carolina, Nov. 13-15, 1987), 57-66.

[20]

FRISSE, M. E., AND COUSINS, S. B. Information retrieval from hypertext: Update on the dynamic medical handbook project. In Hypertext '89 Proceedings (Pittsburgh, Pa., Nov. 5-8, 1989). ACM, New York, 1989, 199-212.

[21]

FURUTA, R., AND STOTTS, P.D. Programmable browsing semantics in trellis. In Hypertext '89 Proceedings (Pittsburgh, Pa., Nov. 5-8, 1989). ACM, New York, 1989, 27-42.

[22]

GARG, P.K. Abstraction mechanisms in hypertext. Commun. ACM 31, 7 (1988), 862-870.

[23]

GARG, P. K., AND SCACCHI, W. On designing intelligent hypertext systems for information management in software engineering. In Proceedings of Hypertext "87 (Univ. of North Carolina, Nov. 1:3-15, 1987), 409-432.

[24]

HALASZ, F.G. Reflections on notecards: Seven issues for the next generation of hypermedia systems. Commun. ACM 31, 7 (1988), 836-852.

[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]

LARSON, J.A. A visual approach to browsing in a database environment. IEEE Computer 19, 1 (1986), 62-71.

[27]

LECLUSE, C., AND SPYRATOS, N. Implementing queries and updates on universal scheme interfaces. In Proceedings of the 14th VLDB Conference (Los Angeles, Aug. 29-Sept. 1, 1988), 62-75.

[28]

MAIER, D., AND ULLMAN, J. Maximal objects and the semantics of universal relation databases. ACM Trans. Database Syst. 8, 1 (1983), 1-14.

[29]

MARON, M. E., AND KUHNS, J. L. On relevance, probabilistic indexing and information retrieval. J. ACM 7, 3 ( July 1960), 216-243.

[30]

NELSON, T.H. Managing immense storage. Byte 13, 1 (1988), 225-238.

[31]

OWRAN60, M. M., AND MILLER, L.L. Query translation based on hypergraph models. Computer J. 31, 2 (1988), 155-164.

[32]

PARUNAK, H. VAN DYKE Hypermedia topologies and user navigation. In Hypertext '89 Proceedings (Pittsburgh, Pa., Nov. 5-8, 1989). ACM, New York, 1989, 43-50.

[33]

RAYMOND, D. R., AND TOMPA, F.W. Hypertext and the Oxford English Dictionary. Commun. ACM 31, 7 (1988), 836-852.

[34]

SALTON, G. In Automatic Information Organization and Retrieval. McGraw-Hill, New York, 1968, Ch. 2, pp. 21-65.

[35]

SALTON, G., WONG, A., AND YANG, C.S. A vector space model for automatic indexing. Commun. ACM 18, 11 (Nov. 1975), 613-620.

[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]

SHEPHERD, M. A., WATTERS, C. R., AND CAI, Y. Transient hypergraphs for citation networks. Inf. Process. Manage. 26, 3 (1990), 395-412.

[39]

STOTTS, P. D., AND FURUTA, R. Petri-net-based hypertext: Document structure with browsing semantics. ACM Trans. Inf. Syst. 7, 1 (Jan. 1989), 3-29.

[40]

TOMPA, F.W. A data model for flexible hypertext database systems. A CM Trans. Inf. Syst. 7, 1 (Jan. 1989), 85-100.

[41]

ULLMAN, J. D. Principles of Database Systems. 2nd ed., Computer Science Press, Rockville, Md., 1982.

[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]

YANKELOVICH, S., ET AL. Intermedia: The concept and the construction of a seamless information environment. IEEE Computer 21, 1 (1988), 81-96.

[44]

ZLOOF, M. Query by example: A data base language. In Proceedings of 1975 National Computer Conference (Anaheim, Calif., June 1975).

Cited By

Reznichenko V(2022)60 Years of Databases (part four)PROBLEMS IN PROGRAMMING10.15407/pp2022.02.057(57-95)Online publication date: Jun-2022
https://doi.org/10.15407/pp2022.02.057
Tonellotto NMacdonald C(2020)Using an Inverted Index Synopsis for Query Latency and Performance PredictionACM Transactions on Information Systems10.1145/338979538:3(1-33)Online publication date: 18-May-2020
https://dl.acm.org/doi/10.1145/3389795
Huang JChen CYe FHu WZheng Z(2020)Nonuniform Hyper-Network Embedding with Dual MechanismACM Transactions on Information Systems10.1145/338892438:3(1-18)Online publication date: 5-May-2020
https://dl.acm.org/doi/10.1145/3388924
Show More Cited By

Recommendations

Ontology-Based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP
Invited Articles Issue, SIGMOD 2013, PODS 2013 and ICDT 2013

Ontology-based data access is concerned with querying incomplete data sources in the presence of domain-specific knowledge provided by an ontology. A central notion in this setting is that of an ontology-mediated query, which is a database query coupled ...
Ontology-based data access: a study through disjunctive datalog, CSP, and MMSNP
PODS '13: Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGAI symposium on Principles of database systems

Ontology-based data access is concerned with querying incomplete data sources in the presence of domain-specific knowledge provided by an ontology. A central notion in this setting is that of an ontology-mediated query, which is a database query coupled ...
Parallel data access for multiway rank joins
ICWE'11: Proceedings of the 11th international conference on Web engineering

Rank join operators perform a relational join among two or more relations, assign numeric scores to the join results based on the given scoring function and return K join results with the highest scores. The top-K join results are obtained by accessing ...

Reviews

Reviewer: Philip H. Teplitzky

One of the more important aspects of reviewing a paper is to determine whether its style, language, level of abstraction, and structure are appropriate for the journal's audience. This paper is right on target. It provides the right level of detail, abstraction, and theory for the ACM Transactions on Information Systems. It would not be appropriate for Datamation or ComputerWorld because it would not be understood by most people working in commercial data processing or databases. The paper is very interesting, however. The notion of using a hypergraph as a representation of search strategies is intriguing. Several commercial possibilities (if you will pardon the expression) come to mind. This could be a reasonable analysis tool in building an executive information system or a text-based document retriev al system. The linkage to relational databases makes it not only intellectually interesting but implementable in a “real world” environment (please pardon the obvious oxymoron—unreal worlds are difficult to manage). I would like to see copies of the promised follow-up research on the user interface. Watters and Shepherd may be on to something. I recommend this paper to the serious data person who is interested in alternative approaches to representing and thinking about data access.

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Information Systems

ACM Transactions on Information Systems Volume 8, Issue 2

Apr. 1990

104 pages

ISSN:1046-8188

EISSN:1558-2868

DOI:10.1145/96105

Editor:
Robert B. Allen
Bellcore, Morristown, NJ

Issue’s Table of Contents

Copyright © 1990 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1990

Published in TOIS Volume 8, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

57
Total Citations
View Citations
732
Total Downloads

Downloads (Last 12 months)65
Downloads (Last 6 weeks)10

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Reznichenko V(2022)60 Years of Databases (part four)PROBLEMS IN PROGRAMMING10.15407/pp2022.02.057(57-95)Online publication date: Jun-2022
https://doi.org/10.15407/pp2022.02.057
Tonellotto NMacdonald C(2020)Using an Inverted Index Synopsis for Query Latency and Performance PredictionACM Transactions on Information Systems10.1145/338979538:3(1-33)Online publication date: 18-May-2020
https://dl.acm.org/doi/10.1145/3389795
Huang JChen CYe FHu WZheng Z(2020)Nonuniform Hyper-Network Embedding with Dual MechanismACM Transactions on Information Systems10.1145/338892438:3(1-18)Online publication date: 5-May-2020
https://dl.acm.org/doi/10.1145/3388924
Liu YWu Y(2020)FNEDACM Transactions on Information Systems10.1145/338625338:3(1-33)Online publication date: 5-May-2020
https://dl.acm.org/doi/10.1145/3386253
Jagerman RMarkov IRijke M(2020)Safe Exploration for Optimizing Contextual BanditsACM Transactions on Information Systems10.1145/338567038:3(1-23)Online publication date: 21-Apr-2020
https://dl.acm.org/doi/10.1145/3385670
Oliveira WDorini LMinetto RSilva T(2020)OutdoorSentACM Transactions on Information Systems10.1145/338518638:3(1-28)Online publication date: 21-Apr-2020
https://dl.acm.org/doi/10.1145/3385186
Watters CShepherd M(2018)Hypertext Access and the New Oxford English DictionaryHypermedia10.1080/09558543.1991.120311903:1(59-79)Online publication date: 29-Oct-2018
https://doi.org/10.1080/09558543.1991.12031190
Angles RGutierrez C(2018)An Introduction to Graph Data ManagementGraph Data Management10.1007/978-3-319-96193-4_1(1-32)Online publication date: 1-Nov-2018
https://doi.org/10.1007/978-3-319-96193-4_1
Mukhopadhyay SPalakal MMaddu K(2010)Multi-way association extraction and visualization from biological text documents using hyper-graphsArtificial Intelligence in Medicine10.1016/j.artmed.2010.03.00249:3(145-154)Online publication date: 1-Jul-2010
https://dl.acm.org/doi/10.1016/j.artmed.2010.03.002
Angles RGutierrez C(2008)Survey of graph database modelsACM Computing Surveys10.1145/1322432.132243340:1(1-39)Online publication date: 22-Feb-2008
https://dl.acm.org/doi/10.1145/1322432.1322433
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents