article

Free access

A nested-graph model for the representation and manipulation of complex objects

Editor: Robert B. Allen Authors:

Alexandra Poulovassilis,

Mark LeveneAuthors Info & Claims

ACM Transactions on Information Systems (TOIS), Volume 12, Issue 1

Pages 35 - 68

https://doi.org/10.1145/174608.174610

Published: 02 January 1994 Publication History

PDF eReader

Abstract

Three recent trends in database research are object-oriented and deductive databases and graph-based user interfaces. We draw these trends together in a data model we call the Hypernode Model. The single data structure of this model is the hypernode, a graph whose nodes can themselves be graphs. Hypernodes are typed, and types, too, are nested graphs. We give the theoretical foundations of hypernodes and types, and we show that type checking is tractable. We show also how conventional type-forming operators can be simulated by our graph types, including cyclic types. The Hypernode Model comes equipped with a rule-based query language called Hyperlog, which is complete with respect to computation and update. We define the operational semantics of Hyperlog and show that the evaluation can be performed efficiently. We discuss also the use of Hyperlog for supporting database browsing, an essential feature of Hypertext databases. We compare our work with other graph-based data models—unlike previous graph-based models, the Hypernode Model provides inherent support for data abstraction via its nesting of graphs. Finally, we briefly discuss the implementation of a DBMS based on the Hypernode Model.

References

[1]

ABITEBOUL, S., AND KANELLAKIS, P.C. 1989. Object identity as a query language primitive. In Proceedings of the ACM SIGMOD International Conference on the Management of Data (Portland, Ore., 1989). ACM, New York, 159-173.

Crossref

Google Scholar

[2]

ABITEBOUL, S., AND VIANU, V. 1988. Procedural and declarativedatabase update languages. In Proceedings of the ACM Symposium on Principles of Database Systems (Austin, Tex., 1988). ACM, New York, 240-250.

Crossref

Google Scholar

[3]

ABITEBOUL, S, AND VIANU, V. 1989. Fixpoint extensions of first-order logic and Datalog-like languages. In Proceedings of the Symposium of Logic in Computer Science. 71 79.

Crossref

Google Scholar

[4]

ACZEL, P. 1988. Non-Well-Founded Sets. Lecture notes, no. 14. Center for the Study of Language and Information (CSLI), Stanford, Calif.

Google Scholar

[5]

BEERI, C. 1989. Formal models for object oriented databases. In Proceedings of the International Conference on Deductive and Object-Oriented Databases. 370-395.

Google Scholar

[6]

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

Crossref

Google Scholar

[7]

CERI, S., GOTTLOB, C., AND TANCA, L. 1990. Logic Programming and Databases. Surveys in Computer Science. Springer-Verlag, New York.

Crossref

Google Scholar

[8]

CHANDRA, A. K., AND HAREL, D. 1980. Computable queries for relational data bases. J. Comput. Syst. Sci. 21, 156-178.

Google Scholar

[9]

CHrN, P. P-S. 1976. The Entity-Relationship Model--towards a unificd view of data. ACM Trans. Database Syst. 1, 1, 9 36.

Crossref

Google Scholar

[10]

CODD, E.F. 1979. Extending the database relational model to capture more meaning. ACM Trans. Database Syst. 4, 1, 397-434.

Crossref

Google Scholar

[11]

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

Crossref

Google Scholar

[12]

CONSENS, M. P., AND MENDELZON, A. O. 1990. Graphlog: A visual formalism for real life recursion. In Proceedings of the ACM Symposium on Principles of Database Systems (Nashville, Tenn., 1990). ACM, New York, 404-416.

Crossref

Google Scholar

[13]

DEARDEN, A. 1990. A hypertext database implemented using the Hypernode Model. Masters thesis, Dept. of Computer Science, Univ. College London, London.

Google Scholar

[14]

GAREY, R. G., AND JOHNSON, D.S. 1979. Computers and Intractability, A Guide to the Theory of NP-Completeness. W. H. Freeman, New York.

Crossref

Google Scholar

[15]

GRIFFITH, R.L. 1982. Three principles of representation for semantic networks. ACM Trans. Database Syst. 7, 3, 417-442.

Crossref

Google Scholar

[16]

GYSSENS, M., PAREDAENS, J., AND VAN GUCHT, D.V. 1990. A graph-oriented object database model. In Proceedings of the ACM Symposium on Principles of Database Systems (Nashville, Tenn., 1990). ACM, New York, 417-424.

Crossref

Google Scholar

[17]

HAREL, D. 1988. On visual formalisms. Commun. ACM 31, 5, 514-530.

Crossref

Google Scholar

[18]

HAREL, D. 1987. Algorithmics--The Spirit of Computing. Addison-Wesley, Reading, Mass.

Crossref

Google Scholar

[19]

HULL, R., AND KING, R. 1987. Semantic database modeling: Survey, applications, and research issues. ACM Comput. Surv. 19, 3,201-260.

Crossref

Google Scholar

[20]

HULL, R., AND SU, J. 1989. Untyped sets, invention, and computable queries. In Proceedings of the ACM Sympostum on Principles of Database Systems (Philadelphia, Penn., 1989). ACM, New York, 347-359.

Crossref

Google Scholar

[21]

KIM, W. 1990. Object-oriented databases: Definition and research directions. IEEE Trans. Knowl. Data Eng. 2, 3, 327-341.

Crossref

Google Scholar

[22]

KUPER, G. M., AND VARm, M. ~. 1984. A new approach to databaselogic. In Proceedings of the ACM Symposium on Princtples of Database Systems (Waterloo, 1984). ACM, New York, 86-96.

Crossref

Google Scholar

[23]

LEVENE, M., AND POULOVASSILIS, A. 1991. An object-oriented data model formalized through hypergraphs. Data Knowl. Eng. 6, 3, 205-224.

Crossref

Google Scholar

[24]

LEVENE, M., AND POULOVASSILIS, A. 1990. The hypernode model and its associated query language. In Proceedings of the 5th JCIT. IEEE Computer Society Press, Los Alamitos, Calif., 520-530.

Crossref

Google Scholar

[25]

NAQVI, S., AND TSUR, S. 1989. A Logical Language for Data andKnowledge Bases. Computer Science Press, New York.

Crossref

Google Scholar

[26]

PARENT, C., AND SPACCAPtETRA, S. 1989. Complex object modelling: An entity-relationship approach. In Nested Relatmns and Complex Objects ~n Databases, S. Abiteboul, P. C. Fischer, and H.-J. Schek, Eds., Springer-Verlag, Berlin, 272-296.

Crossref

Google Scholar

[27]

PRZYMUSINSKA, H., AND PRZYMUSINSKI, T. 1990. Semantic issues in deductive databases and logic programs. {n Formal Techniques in Arti~cml Intelligence, a Sourcebook, R. B. Banerji, Ed. Elsevier Science, Amsterdam, 321-367.

Google Scholar

[28]

RmTER, R. 1978. On closed world databases. In Logic and Databases, H. Gallaire and J. Minker, Eds. Plenum Press, New York, 55 76.

Google Scholar

[29]

SCHEK, H.-J., AND SCHOLL, M.H. 1986. The relational model with relation-valued attributes. Inf. Syst. 11, 2, 137-147.

Crossref

Google Scholar

[30]

SmPMAN, D. 1981. The functional data model and the data language DAPLEX. ACM Trans. Database Syst. 6, 1, 140-173.

Crossref

Google Scholar

[31]

SHRrWR, B., AND WEGNER, P., Eds. 1987. Research Directions in Object-Oriented Programming. MIT Press, Cambridge, Mass.

Google Scholar

[32]

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

Crossref

Google Scholar

[33]

Tuv, E., POULOVASSILIS, A., AND LEVENE, M. 1992. A storage manager for the Hypernode Model. In Proceedings of BNCOD-lO--Advances in Database Systems. Lecture Notes in Computer Science, vol. 618. Springer-Verlag, New York, 59-77.

Crossref

Google Scholar

[34]

ULLMAN, J.D. 1988. Principles of Database and Knowledge-Base Systems. Computer Science Press, Rockville, Md.

Crossref

Google Scholar

[35]

WATTERS, C., AND SHEPHERD, M.h. 1990. A transient hypergraph-based model for data access. ACM. Trans. Inf. Syst. 8, 2, 77-102.

Crossref

Google Scholar

[36]

WONG, K., AND LOCHOVSKY, F., Eds. 1989. Object-Oriented Languages, Applications, and database,ACM press frontier series, new york.

Google Scholar

Cited By

View all

Benelhaj-Sghaier SGillet ALeclercq É(2024)Knowledge Graph Multilevel Abstraction: A Property Graph Reification Based ApproachResearch Challenges in Information Science10.1007/978-3-031-59468-7_2(12-19)Online publication date: 4-May-2024
https://doi.org/10.1007/978-3-031-59468-7_2
Ślusarczyk GStrug BPaszyńska AGrabska EPalacz W(2023)Semantic-driven Graph Transformations in Floor Plan DesignComputer-Aided Design10.1016/j.cad.2023.103480158:COnline publication date: 1-May-2023
https://dl.acm.org/doi/10.1016/j.cad.2023.103480
Ben-Nun TGianinazzi LHoefler TOltchik Y(2023)Maximum Flows in Parametric Graph TemplatesAlgorithms and Complexity10.1007/978-3-031-30448-4_8(97-111)Online publication date: 13-Jun-2023
https://dl.acm.org/doi/10.1007/978-3-031-30448-4_8
Show More Cited By

Index Terms

A nested-graph model for the representation and manipulation of complex objects
1. Information systems
  1. Data management systems
    1. Database design and models
    2. Query languages
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

Self-Representation in Girard's System U
POPL '15: Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages

In 1991, Pfenning and Lee studied whether System F could support a typed self-interpreter. They concluded that typed self-representation for System F "seems to be impossible", but were able to represent System F in F_ω. Further, they found that the ...
Nested bitemporal relational data model
An algebraic approach to databases with complex objects

Reviews

Reviewer: Ferdi W. J. Put

A new data model is presented that contains a single general-purpose data structure: the hypernode, a graph whose nodes can themselves be graphs. This data model incorporates types, which are also graphs. The hypernode model comes equipped with a rule-based query and update language called Hyperlog. The authors define the operational semantics of Hyperlog programs. Efficiency and expressiveness issues of Hyperlog are discussed. The authors show how data browsing can be supported by Hyperlog. The paper contains a comparison with related work. Implementation issues are discussed briefly. Interestingly, the paper makes progress in combining three recent trends in database research: object-oriented and deductive databases and graph-based user interfaces. The hypernode model and its associated query language Hyperlog support object identity and complex objects, including cyclic objects. The expressiveness of the hypernode model in terms of semantic modeling is limited, however. The model does not provide inherent support for conventional type-forming operators such as tuple, set, and relation (the authors show how these operators can be simulated). Some common semantic aspects (such as cardinality constraints) cannot be represented in a database scheme but have to be enforced within update programs.

Reviewer: Jozef Wijsen

A new data model is presented that contains a single general-purpose data structure: the hypernode, a graph whose nodes can themselves be graphs. This data model incorporates types, which are also graphs. The hypernode model comes equipped with a rule-based query and update language called Hyperlog. The authors define the operational semantics of Hyperlog programs. Efficiency and expressiveness issues of Hyperlog are discussed. The authors show how database browsing can be supported by Hyperlog. The paper contains a comparison with related work. Implementation issues are discussed briefly. Interestingly, the paper makes progress in combining three recent trends in database research: object-oriented and deductive databases and graph-based user interfaces. The hypernode model and its associated query language Hyperlog support object identity and complex objects, including cyclic objects. The expressiveness of the hypernode model in terms of semantic modeling is limited, however. The model does not provide inherent support for conventional type-forming operators such as tuple, set, and relation (the authors show how these operators can be simulated). Some common semantic aspects (such as cardinality constraints) cannot be represented in a database scheme but have to be enforced within update programs.

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

ACM Transactions on Information Systems Volume 12, Issue 1

Jan. 1994

111 pages

ISSN:1046-8188

EISSN:1558-2868

DOI:10.1145/174608

Editor:
Robert B. Allen
Bellcore, Morristown, NJ

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 January 1994

Published in TOIS Volume 12, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

54
Total Citations
View Citations
1,365
Total Downloads

Downloads (Last 12 months)270
Downloads (Last 6 weeks)34

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Benelhaj-Sghaier SGillet ALeclercq É(2024)Knowledge Graph Multilevel Abstraction: A Property Graph Reification Based ApproachResearch Challenges in Information Science10.1007/978-3-031-59468-7_2(12-19)Online publication date: 4-May-2024
https://doi.org/10.1007/978-3-031-59468-7_2
Ślusarczyk GStrug BPaszyńska AGrabska EPalacz W(2023)Semantic-driven Graph Transformations in Floor Plan DesignComputer-Aided Design10.1016/j.cad.2023.103480158:COnline publication date: 1-May-2023
https://dl.acm.org/doi/10.1016/j.cad.2023.103480
Ben-Nun TGianinazzi LHoefler TOltchik Y(2023)Maximum Flows in Parametric Graph TemplatesAlgorithms and Complexity10.1007/978-3-031-30448-4_8(97-111)Online publication date: 13-Jun-2023
https://dl.acm.org/doi/10.1007/978-3-031-30448-4_8
Toktoshov G(2022)The route choosing methodology for networks and communications layingThe Herald of the Siberian State University of Telecommunications and Informatics10.55648/1998-6920-2022-16-1-97-107(97-107)Online publication date: 13-May-2022
https://doi.org/10.55648/1998-6920-2022-16-1-97-107
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
Nguyen Tien TNguyen K(2022)Decision graph for timely delivery of multi-AGVs in healthcare environmentProceedings of the 11th International Symposium on Information and Communication Technology10.1145/3568562.3568652(186-192)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1145/3568562.3568652
Ivanova K(2021)NLA-Bit: A Basic Structure for Storing Big Data with Complexity O(1)Big Data and Cognitive Computing10.3390/bdcc50100085:1(8)Online publication date: 24-Feb-2021
https://doi.org/10.3390/bdcc5010008
Toktoshov G(2021)The Routes Choosing Methodology for Laying Networks in Three-Dimensional Space2021 17th International Asian School-Seminar "Optimization Problems of Complex Systems (OPCS)10.1109/OPCS53376.2021.9588733(139-143)Online publication date: 13-Sep-2021
https://doi.org/10.1109/OPCS53376.2021.9588733
Toktoshov GMigov D(2019)The Application of the k-shortest Paths Method for Constructing an Optimal Hypernet2019 15th International Asian School-Seminar Optimization Problems of Complex Systems (OPCS)10.1109/OPCS.2019.8880221(162-166)Online publication date: Aug-2019
https://doi.org/10.1109/OPCS.2019.8880221
Bergami GPetermann AMontesi D(2018)THoSPProceedings of the 1st ACM SIGMOD Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA)10.1145/3210259.3210267(1-10)Online publication date: 10-Jun-2018
https://dl.acm.org/doi/10.1145/3210259.3210267
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Abstract

References

Cited By

Index Terms

Recommendations

Self-Representation in Girard's System U

Nested bitemporal relational data model

An algebraic approach to databases with complex objects

Reviews

Access critical reviews of Computing literature here

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations