Abstract
We study a spatial logic for reasoning about labelled directed graphs, and the application of this logic to provide a query language for analysing and manipulating such graphs. We give a graph description using constructs from process algebra. We introduce a spatial logic in order to reason locally about disjoint subgraphs. We extend our logic to provide a query language which preserves the multiset semantics of our graph model. Our approach contrasts with the more traditional set-based semantics found in query languages such as TQL, Strudel and GraphLog.
Supported by an EPSRC Advanced Fellowship.
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
S. Abiteboul, P. Buneman, and D. Suciu. Data on the Web. Morgan Kaufmann, 2000.
P. Buneman, S. Davidson, G. Hillebrand, and D. Suciu. A query language and optimization techniques for unstructured data. In SIGMOD, LNCS 2044, pages 505–515, 1996.
L. Caires. A Model for Declarative Programming and Specification with Concurrency and Mobility. PhD thesis, University of Lisbon, 1999.
L. Caires and L. Cardelli. A spatial logic for concurrency (part 1). In TACS, LNCS 2215. Springer, 2001. Journal paper to be in Information and Comp.
L. Cardelli and A. Gordon. Anytime, anywhere: Modal logics for mobile ambients. In POPL. ACM, 2000.
L. Cardelli and G. Ghelli. A query language based on the ambient logic. In ESOP/ETAPS, LNCS 2028. Springer, 2001.
L. Cardelli and A. Gordon. Logical properties of name restriction. In TLCA, LNCS 2044. Springer, 2001.
L. Cardelli, P. Gardner, and G. Ghelli. A spatial logic for querying graphs. Fuller version found at http://www.doc.ic.ac.uk/~pg, 2001.
M. Consens and A. Mendelzon. Graphlog: a visual formalism for real life recursion. In Principles of Database Systems, pages 404–416. ACM, 1990.
A. Corradini, U. Montanari, and F. Rossi. An abstract machine for concurrent modular systems: Charm. TCS, 122:165–200, 1994.
Bruno Courcelle. The expression of graph properties and graph transformations in monadic second-order logic. Graph grammars and computing by graph transformations, 1:313–400, 1997.
M. Fernandez, D. Florescu, J. Kang, A. Levy, and D. Suciu. Strudel: A web-site management system. In SIGMOD Management of Data, 1997.
P. Gardner and L. Wischik. Explicit fusions. MFCS, LNCS 893, 2000. Journal version submitted to Theoretical Computer Science.
H. Hosoya and B. Pierce. Regular expression pattern matching for xml. In POPL.ACM, 2001.
S. Ishtiaq and P. O’Hearn. Bi as an assertion language for mutable data structures. In POPL, 664. ACM, 2001.
P. O’Hearn and D. Pym. The logic of bunched implications. Bulletin of Symbolic Logic, 5(2):215–244, 1999.
J.C. Reynolds. Intuitionistic reasoning about shared mutable data structure. Millenial Perspectives in Computer Science, Palgrove, 2000.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cardelli, L., Gardner, P., Ghelli, G. (2002). A Spatial Logic for Querying Graphs. In: Widmayer, P., Eidenbenz, S., Triguero, F., Morales, R., Conejo, R., Hennessy, M. (eds) Automata, Languages and Programming. ICALP 2002. Lecture Notes in Computer Science, vol 2380. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45465-9_51
Download citation
DOI: https://doi.org/10.1007/3-540-45465-9_51
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43864-9
Online ISBN: 978-3-540-45465-6
eBook Packages: Springer Book Archive