GraphLog

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

GraphLog: a visual formalism for real life recursion

Full text

Pdf (1.35 MB)

Source

Symposium on Principles of Database Systems archive
Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems table of contents

Nashville, Tennessee, United States

Pages: 404 - 416

Year of Publication: 1990

ISBN:0-89791-352-3

Authors

Mariano P. Consens	Computer Systems Research Institute, University of Toronto, Toronto, Canada M5S 1A4
Alberto O. Mendelzon	Computer Systems Research Institute, University of Toronto, Toronto, Canada M5S 1A4

Sponsors

SIGART: ACM Special Interest Group on Artificial Intelligence
SIGMOD: ACM Special Interest Group on Management of Data
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 13, Downloads (12 Months): 71, Citation Count: 62

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/298514.298591 What is a DOI?

ABSTRACT

We present a query language called GraphLog, based on a graph representation of both data and queries. Queries are graph patterns. Edges in queries represent edges or paths in the database. Regular expressions are used to qualify these paths. We characterize the expressive power of the language and show that it is equivalent to stratified linear Datalog, first order logic with transitive closure, and non-deterministic logarithmic space (assuming ordering on the domain). The fact that the latter three classes coincide was not previously known. We show how GraphLog can be extended to incorporate aggregates and path summarization, and describe briefly our current prototype implementation.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	Ada87	Sam S. Adams. NodeGraph.80 Version 1.0. Knowledge Systems Corporation, 1987.
	AK89	Serge Abiteboul and Paris C. Kanellakis. Object identity as a query language primitive. Technical Report 1022, INRIA, April 1989.
	AU79	Alfred V. Aho , Jeffrey D. Ullman, Universality of data retrieval languages, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.110-119, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567763]
	Bee88	C. Beeri, Data models and languages for databases, Lecture notes in computer science on ICDT '88, p.19-40, October 1988, Bruges, Belgium
	CH82	A.K. Chandra and D. Harel. Structure and complexity of relational queries. Journal of Computer and System Sciences, 25(1):99- 128, 1982.
	CH85	A.K. Chandra and D. Harel. Horn clause queries and generalizations. J. Logic Programming, 2(1):1-15, 1985.
	CK86	S Cosmadakis , P Kanellakis, Parallel evaluation of recursive rule queries, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.280-293, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15421]
	CM89	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]
	CMW88	I.F. Cruz, A.O. Mendelzon, and P.T. Wood. G+: Recursive queries without recursion. In Larry Kerschberg, editor, Proceedings of the Second International Conference on Expert Database Systems, pages 355-368, 1988.
	Con89	Mariano P. Consens. Graphlog: "real life" recursive queries using graphs. Master's thesis, Department of Computer Science, University of Toronto, 1989.
	DS86	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
	Imm87	Neil Immerman, Languages that capture complexity classes, SIAM Journal on Computing, v.16 n.4, p.760-778, Aug. 1987 [doi>10.1137/0216051]
	Imm88a	Nail Immerman. Descriptive and computational complexity. Technical report, Department of Computer Science, Yale University, New Haven, 1988.
	Imm88b	Nail Immerman. Nondeterministic space is closed under complementation. In Third Structure in Complexity Theory Conference, 1988.
	JAN87	H. V. Jagadish , Rakesh Agrawal , Linda Ness, A study of transitive closure as a recursion mechanism, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.331-344, May 27-29, 1987, San Francisco, California, United States
	Kan87	P. C. Kanellakis, Logic programming and parallel complexity, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
	Klu82	Anthony Klug, Equivalence of Relational Algebra and Relational Calculus Query Languages Having Aggregate Functions, Journal of the ACM (JACM), v.29 n.3, p.699-717, July 1982 [doi>10.1145/322326.322332]
	MW89	A. O. Mendelzon , P. T. Wood, Finding regular simple paths in graph databases, Proceedings of the 15th international conference on Very large data bases, p.185-193, July 1989, Amsterdam, The Netherlands
	Nau87	J. F. Naughton, One-sided recursions, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.340-348, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28695]
	Shm87	O. Shmueli, Decidability and expressiveness aspects of logic queries, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.237-249, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28685]
	TZ86	Shalom Tsur , Carlo Zaniolo, LDL: A Logic-Based Data Language, Proceedings of the 12th International Conference on Very Large Data Bases, p.33-41, August 25-28, 1986
	Ull89	Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
	UvG86	J.D. Ullman and A. van Calder. Parallel complexity of logical query programs. Proc. 27th Ann. Symp. on Foundations of Computer Science, pages 438-454, 1986.

CITED BY 62

	Mariano P. Consens , Alberto O. Mendelzon, The G+/GraphLog Visual Query System, ACM SIGMOD Record, v.19 n.2, p.388, Jun. 1990
	Dennis Shasha , Jason T. L. Wang , Rosalba Giugno, Algorithmics and applications of tree and graph searching, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin
	Yannis Papakonstantinou , Victor Vianu, DTD inference for views of XML data, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.35-46, May 15-18, 2000, Dallas, Texas, United States
	Alexandra Poulovassilis , Mark Levene, A nested-graph model for the representation and manipulation of complex objects, ACM Transactions on Information Systems (TOIS), v.12 n.1, p.35-68, Jan. 1994
	Mariano Consens , Alberto Mendelzon , Arthur Ryman, Visualizing and querying software structures, Proceedings of the 14th international conference on Software engineering, p.138-156, May 11-15, 1992, Melbourne, Australia
	Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini , Moshe Y. Vardi, Rewriting of regular expressions and regular path queries, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.194-204, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
	Peter Buneman , Susan Davidson , Gerd Hillebrand , Dan Suciu, A query language and optimization techniques for unstructured data, ACM SIGMOD Record, v.25 n.2, p.505-516, June 1996
	Mariano Consens , Alberto Mendelzon, Hy+: a Hygraph-based query and visualization system, ACM SIGMOD Record, v.22 n.2, p.511-516, June 1, 1993
	H. V. Jagadish , Mark A. Jones , Divesh Srivastava , Dimitra Vista, Flexible list management in a directory, Proceedings of the seventh international conference on Information and knowledge management, p.10-19, November 02-07, 1998, Bethesda, Maryland, United States
	H. V. Jagadish , Laks V. S. Lakshmanan , Tova Milo , Divesh Srivastava , Dimitra Vista, Querying network directories, ACM SIGMOD Record, v.28 n.2, p.133-144, June 1999
	Serge Abiteboul , Victor Vianu, Regular path queries with constraints, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.122-133, May 11-15, 1997, Tucson, Arizona, United States
	Mariano P. Consens , Tova Milo, Optimizing queries on files, ACM SIGMOD Record, v.23 n.2, p.301-312, June 1994
	Isabel F. Cruz, DOODLE: a visual language for object-oriented databases, ACM SIGMOD Record, v.21 n.2, p.71-80, June 1, 1992
	Bernd Amann , Michel Scholl , Antoine Rizk, Querying typed hypertexts in Multicard/O2, Proceedings of the 1994 ACM European conference on Hypermedia technology, p.198-205, September 19-23, 1994, Edinburgh, Scotland
	Bernd Amann , Michel Scholl, Gram: a graph data model and query languages, Proceedings of the ACM conference on Hypertext, p.201-211, November 30-December 04, 1992, Milan, Italy
	Avigdor Gal , Opher Etzion, A Multiagent Update Process in a Database with Temporal Data Dependencies and Schema Versioning, IEEE Transactions on Knowledge and Data Engineering, v.10 n.1, p.21-37, January 1998
	Dario Lucarella , Antonella Zanzi, A visual retrieval environment for hypermedia information systems, ACM Transactions on Information Systems (TOIS), v.14 n.1, p.3-29, Jan. 1996
	V. Christophides , S. Abiteboul , S. Cluet , M. Scholl, From structured documents to novel query facilities, ACM SIGMOD Record, v.23 n.2, p.313-324, June 1994
	Taekyong Lee , Lei Sheng , Tolga Bozkaya , Nevzat Hurkan Balkir , Z. Meral Özsoyoglu , Gultekin Özsoyoglu, Querying Multimedia Presentations Based on Content, IEEE Transactions on Knowledge and Data Engineering, v.11 n.3, p.361-385, May 1999
	Holger Meuss , Klaus U. Schulz, Complete answer aggregates for treelike databases: a novel approach to combine querying and navigation, ACM Transactions on Information Systems (TOIS), v.19 n.2, p.161-215, April 2001
	S. Dar , R. Agrawal, Extending SQL with Generalized Transitive Closure, IEEE Transactions on Knowledge and Data Engineering, v.5 n.5, p.799-812, October 1993
	Dimitra Vista, Deductive database support for data visualization, Proceedings of the 1993 conference of the Centre for Advanced Studies on Collaborative research: distributed computing, October 24-28, 1993, Toronto, Ontario, Canada
	Masum Z. Hasan , Alberto O. Mendelzon , Dimitra Vista, Visual web surfing with Hy⁺, Proceedings of the 1995 conference of the Centre for Advanced Studies on Collaborative research, p.28, November 07-09, 1995, Toronto, Ontario, Canada
	Jacob Slonim , Patrick Finnigan , Alberto Mendelson , Toby Teorey , Michael Bauer , Paul Larson , Richard McBride , Yechiam Yemini , Shaula Yemini, Towards a new distributed programming environment (CORDS), Proceedings of the 1991 conference of the Centre for Advanced Studies on Collaborative research, October 28-30, 1991, Toronto, Ontario, Canada
	Jacob Slonim , Patrick Finnigan , Alberto Mendelson , Toby Teorey , Michael Bauer , Paul Larson , Richard McBride , Yechiam Yemini , Shaula Yemini, Towards a new distributed programming environment (CORDS), Proceedings of the 1991 conference of the Centre for Advanced Studies on Collaborative research, October 28-30, 1991, Toronto, Ontario, Canada
	Mariano Consens , Alberto Mendelzon , Arthur Ryman, Visualizing and querying software structures, Proceedings of the 1991 conference of the Centre for Advanced Studies on Collaborative research, October 28-30, 1991, Toronto, Ontario, Canada
	Mariano P. Consens , Masum Z. Hasan , Alberto O. Mendelzon, Using Hy⁺ for network management and distributed debugging, Proceedings of the 1993 conference of the Centre for Advanced Studies on Collaborative research: software engineering, October 24-28, 1993, Toronto, Ontario, Canada
	Gunnar Gotshalks, A theory-model formalization of FlexOr, Proceedings of the 1992 conference of the Centre for Advanced Studies on Collaborative research, November 09-12, 1992, Toronto, Ontario, Canada
	Masum Z. Hasan , Gene Golovchinsky , Emanuel G. Noik , Nipon Charoenkitkarn , Mark Chignell , Alberto O. Mendelzon , David Modjeska, Browsing local and global information, Proceedings of the 1995 conference of the Centre for Advanced Studies on Collaborative research, p.27, November 07-09, 1995, Toronto, Ontario, Canada
	Jan Paredaens , Peter Peelman , Letizia Tanca, G-Log: A Graph-Based Query Language, IEEE Transactions on Knowledge and Data Engineering, v.7 n.3, p.436-453, June 1995
	M. Gyssens , J. Paredaens , J. Van den Bussche , D. Van Gucht, A Graph-Oriented Object Database Model, IEEE Transactions on Knowledge and Data Engineering, v.6 n.4, p.572-586, August 1994
	H. V. Jagadish , Laks V. S. Lakshmanan , Monica Scannapieco , Divesh Srivastava , Nuwee Wiwatwattana, Colorful XML: one hierarchy isn't enough, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
	Gopi K. Attaluri , Dexter Bradshaw , Patrick J. Finnigant , Nigel Hinds , Michael Kalantar , Kelly A. Lyons , Andrew D. Marshall , Jan K. Pachl , Hong Tran, Operation jump start: a CORDS integration prototype using DCE, Proceedings of the 1993 conference of the Centre for Advanced Studies on Collaborative research: distributed computing, October 24-28, 1993, Toronto, Ontario, Canada
	Michael A. Bauer , Pat J. Finnigan , James W. Hong , Jan K. Pachl , Toby J. Teorey, An integrated distributed systems management architecture, Proceedings of the 1993 conference of the Centre for Advanced Studies on Collaborative research: software engineering, October 24-28, 1993, Toronto, Ontario, Canada
	Robert Ayres, The Functional Data Model as the Basis for an Enriched Database Query Language, Journal of Intelligent Information Systems, v.12 n.2-3, p.139-164, March 1999
	Mark Levene , George Loizou, A Graph-Based Data Model and its Ramifications, IEEE Transactions on Knowledge and Data Engineering, v.7 n.5, p.809-823, October 1995
	Sergio Flesca , Sergio Greco, Partially ordered regular languages for graph queries, Journal of Computer and System Sciences, v.70 n.1, p.1-25, February 2005
	Tiziana Catarci , Shi-Kuo Chang , Maria F. Costabile , Stefano Levialdi , Giuseppe Santucci, A Graph-Based Framework for Multiparadigmatic Visual Access to Databases, IEEE Transactions on Knowledge and Data Engineering, v.8 n.3, p.455-475, June 1996
	Alexandra Poulovassilis , Stefan G. Hild, Hyperlog: A Graph-Based System for Database Browsing, Querying, and Update, IEEE Transactions on Knowledge and Data Engineering, v.13 n.2, p.316-333, March 2001
	Agostino Cortesi , Agostino Dovier , Elisa Quintarelli , Letizia Tanca, Operational and abstract semantics of the query language G-Log, Theoretical Computer Science, v.275 n.1-2, p.521-560, March 28 2002
	Markku Rontu , Ari Korhonen , Lauri Malmi, System for enhanced exploration and querying, Proceedings of the working conference on Advanced visual interfaces, May 23-26, 2006, Venezia, Italy
	Huahai He , Ambuj K. Singh, Graphs-at-a-time: query language and access methods for graph databases, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada
	Sergio Flesca , Filippo Furfaro , Sergio Greco, A graph grammars based framework for querying graph-like data, Data & Knowledge Engineering, v.59 n.3, p.652-680, December 2006
	R. Ian Bull, Integrating dynamic views using model driven development, Proceedings of the 2006 conference of the Center for Advanced Studies on Collaborative research, October 16-19, 2006, Toronto, Ontario, Canada
	Elena Baralis , Paolo Garza , Elisa Quintarelli , Letizia Tanca, Answering XML queries by means of data summaries, ACM Transactions on Information Systems (TOIS), v.25 n.3, p.10-es, July 2007
	T. Catarci , G. Santucci , J. Cardiff, Graphical interaction with heterogeneous databases, The VLDB Journal — The International Journal on Very Large Data Bases, v.6 n.2, p.097-120, May 1997
	Peter Buneman , Mary Fernandez , Dan Suciu, UnQL: a query language and algebra for semistructured data based on structural recursion, The VLDB Journal — The International Journal on Very Large Data Bases, v.9 n.1, p.76-110, March 2000
	Martin Traverso , Spiros Mancoridis, On the Automatic Recovery of Style-Specific Architectural Relations in Software Systems, Automated Software Engineering, v.9 n.4, p.331-360, October 2002
	Ralf Hartmut Güting, GraphDB: Modeling and Querying Graphs in Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.297-308, September 12-15, 1994
	Alejandro Gutiérrez , Philippe Pucheral , Hermann Steffen , Jean-Marc Thévenin, Database Graph Views: A Practical Model to Manage Persistent Graphs, Proceedings of the 20th International Conference on Very Large Data Bases, p.391-402, September 12-15, 1994
	Peter T. Wood, Factoring Augmented Regular Chain Programs, Proceedings of the 16th International Conference on Very Large Data Bases, p.255-263, August 13-16, 1990
	Masum Z. Hasan , Alberto O. Mendelzon , Dimitra Vista, Applying database visualization to the World Wide Web, ACM SIGMOD Record, v.25 n.4, p.45-49, Dec. 1996
	Mariano P. Consens , Isabel F. Cruz , Alberto O. Mendelzon, Visualizing queries and querying visualizations, ACM SIGMOD Record, v.21 n.1, p.39-46, March 1992
	Wolfgang May, XPath-logic and XPathLog: A logic-programming style XML data manipulation language, Theory and Practice of Logic Programming, v.4 n.3, p.239-287, May 2004
	Manuel Tamashiro , Alex Thomo , Srinivasan Venkatesh, Towards practically feasible answering of regular path queries in lav data integration, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal
	Sergio Flesca , Filippo Furfaro , Sergio Greco, A Query Language for XML Based on Graph Grammars, World Wide Web, v.5 n.2, p.125-157, 2002
	Silvia Gordillo , Alicia Díaz, Design and Query Strategies to Hypermedia Applications, Multimedia Tools and Applications, v.7 n.3, p.213-225, November 1998
	A. Dovier , E. Quintarelli, Applying model-checking to solve queries on semistructured data, Computer Languages, Systems and Structures, v.35 n.2, p.143-172, July, 2009
	Eyal Oren , Renaud Delbru , Michele Catasta , Richard Cyganiak , Holger Stenzhorn , Giovanni Tummarello, Sindice.com: a document-oriented lookup index for open linked data, International Journal of Metadata, Semantics and Ontologies, v.3 n.1, p.37-52, November 2008
	Pak Chung Wong , Harlan Foote , Patrick Mackey , Ken Perrine , George Chin Jr., Generating Graphs for Visual Analytics through Interactive Sketching, IEEE Transactions on Visualization and Computer Graphics, v.12 n.6, p.1386-1398, November 2006
	Maryam Shoaran , Alex Thomo, Fault-tolerant computation of distributed regular path queries, Theoretical Computer Science, v.410 n.1, p.62-77, January, 2009
	Faisal Alkhateeb , Jean-François Baget , Jérôme Euzenat, Extending SPARQL with regular expression patterns (for querying RDF), Web Semantics: Science, Services and Agents on the World Wide Web, v.7 n.2, p.57-73, April, 2009