Abstract
This paper is concerned with the evaluation of a graph-based declarative language called Hyperlog. Hyperlog is a query- and update-language for a graph-based data model called the Hypernode Model. The single data structure of this model is the hypernode — a graph whose nodes can themselves be graphs. A Hyperlog program is a set of rules whose bodies consist of templates to be matched against a database of graphs. The heads of rules are also templates and indicate the updates to the database to be undertaken for each match of the templates in the body. These updates may include the update of existing graphs or the generation of new graphs.
We first define the semantics of Hyperlog programs in terms of a bottom-up “naive” evaluation strategy. We then show the semi-naive evaluation algorithm developed for relational languages can be adapted for the more efficient evaluation of Hyperlog programs. This is achieved by partitioning the templates in the bodies of rules into those templates which cannot be affected by any updates to the database during the evaluation of the programs and those templates which may be affected by updates to the database. The former templates are the analogue of EDB predicates and the latter of IDB predicates in relational rules.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
M. Levene and A. Poulovassilis, The hypernode model and its associated query language, In Proceedings of the 5th Jerusalem Conference on Information Technology, IEEE Press, pp 520–530, 1990.
A. Poulovassilis and M. Levene, A nested-graph model for the representation and manipulation of complex objects, ACM Transactions on Information Systems, 1993, in press.
E. Tuv, A. Poulovassilis and M. Levene, A storage manager for the hypernode model, In Proceedings of the 10th British National Conference on Databases, Springer-Verlag, pp 59–77, 1992.
M.P. Consens and A.O. Mendelzon, Graphlog: a visual formalism for real life recursion, In Proceedings of the ACM Symposium on Principles of Database Systems, Nashville, Tennessee, pp 404–416, 1990.
M. Gyssens, J. Paredaens and D.V. Van Gucht, A graph-oriented object model for database end-user interfaces, In Proceedings of the ACM SIGMOD International Conference on the Management of Data, Atlantic City, New Jersey, pp 24–33, 1990.
J. Paredaens, P. Peelman and L. Tanca, G-Log: A Declarative Graphical Query Language, In Proceedings of the 1st International Conference on Deductive and Object-Oriented Databases, pp 108–128, 1991.
F.W. Tompa, A data model for flexible hypertext database systems, ACM Transactions on Information Systems, 7(1), pp 85–100, 1989.
C. Watters and M.A. Shepherd, A transient hypergraph-based model for data access, ACM Transactions on Information Systems, 8(2), pp 77–102, 1990.
J. D. Ullman, Principles of Database and Knowledge-Base Systems, Computer Science Press, Rockville, Maryland, 1988.
P. Aczel, Non-well-founded Sets, Center for the Study of Language and Information (CSLI) Lecture notes no. 14, Stanford, California, 1988.
S. Abiteboul and P.C. Kanellakis, Object identity as a query language primitive, In Proceedings of the ACM SIGMOD International Conference on the Management of Data, Portland, Oregon, pp 159–173, 1989.
C. Beeri and R. Ramakrishnan, On the Power of Magic, In Proceedings of the ACM Symposium on Principles of Databases Systems, pp 269–283, 1987.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1994 British Computer Society
About this paper
Cite this paper
Benkerimi, K., Poulovassilis, A. (1994). Semi-Naive Evaluation for Hyperlog, a Graph-Based Language for Complex Objects. In: Paton, N.W., Williams, M.H. (eds) Rules in Database Systems. Workshops in Computing. Springer, London. https://doi.org/10.1007/978-1-4471-3225-7_15
Download citation
DOI: https://doi.org/10.1007/978-1-4471-3225-7_15
Publisher Name: Springer, London
Print ISBN: 978-3-540-19846-8
Online ISBN: 978-1-4471-3225-7
eBook Packages: Springer Book Archive