GraphLog: a Visual Formalism for Real Life Recursion.
Mariano P. Consens, Alberto O. Mendelzon:
GraphLog: a Visual Formalism for Real Life Recursion.
PODS 1990: 404-416@inproceedings{DBLP:conf/pods/ConsensM90,
author = {Mariano P. Consens and
Alberto O. Mendelzon},
title = {GraphLog: a Visual Formalism for Real Life Recursion},
booktitle = {Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on
Principles of Database Systems, April 2-4, 1990, Nashville, Tennessee},
publisher = {ACM Press},
year = {1990},
isbn = {0-89791-352-3},
pages = {404-416},
ee = {http://doi.acm.org/10.1145/298514.298591, db/conf/pods/ConsensM90.html},
crossref = {DBLP:conf/pods/90},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
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.
Copyright © 1990 by the ACM,
Inc., used by permission. Permission to make
digital or hard copies is granted provided that
copies are not made or distributed for profit or
direct commercial advantage, and that copies show
this notice on the first page or initial screen of
a display along with the full citation.
Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98.
and ...
Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings.
and ...
BibTeX
Printed Edition
Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, April 2-4, 1990, Nashville, Tennessee.
ACM Press 1990, ISBN 0-89791-352-3
Contents BibTeX
References
- [Ada87]
- ...
- [AK89]
- Serge Abiteboul, Paris C. Kanellakis:
Object Identity as a Query Language Primitive.
SIGMOD Conference 1989: 159-173 BibTeX
- [Au79]
- Alfred V. Aho, Jeffrey D. Ullman:
The Universality of Data Retrieval Languages.
POPL 1979: 110-120 BibTeX
- [Bee88]
- Catriel Beeri:
Data Models and Languages for Databases.
ICDT 1988: 19-40 BibTeX
- [CH82]
- Ashok K. Chandra, David Harel:
Structure and Complexity of Relational Queries.
J. Comput. Syst. Sci. 25(1): 99-128(1982) BibTeX
- [CH85]
- Ashok K. Chandra, David Harel:
Horn Clauses Queries and Generalizations.
J. Log. Program. 2(1): 1-15(1985) BibTeX
- [CK86]
- Stavros S. Cosmadakis, Paris C. Kanellakis:
Parallel Evaluation of Recursive Rule Queries.
PODS 1986: 280-293 BibTeX
- [CM89]
- Mariano P. Consens, Alberto O. Mendelzon:
Expressing Structural Hypertext Queries in GraphLog.
Hypertext 1989: 269-292 BibTeX
- [CMW88]
- Isabel F. Cruz, Alberto O. Mendelzon, Peter T. Wood:
G+: Recursive Queries Without Recursion.
Expert Database Conf. 1988: 645-666 BibTeX
- [Con89]
- ...
- [DS86]
- Norman M. Delisle, Mayer D. Schwartz:
Neptune: a Hypertext System for CAD Applications.
SIGMOD Conference 1986: 132-143 BibTeX
- [Imm87]
- Neil Immerman:
Languages that Capture Complexity Classes.
SIAM J. Comput. 16(4): 760-778(1987) BibTeX
- [Imm88a]
- ...
- [Imm88b]
- ...
- [JAN87]
- H. V. Jagadish, Rakesh Agrawal, Linda Ness:
A Study of Transitive Closure As a Recursion Mechanism.
SIGMOD Conference 1987: 331-344 BibTeX
- [Kan87]
- ...
- [Klu82]
- Anthony C. Klug:
Equivalence of Relational Algebra and Relational Calculus Query Languages Having Aggregate Functions.
J. ACM 29(3): 699-717(1982) BibTeX
- [MW89]
- Alberto O. Mendelzon, Peter T. Wood:
Finding Regular Simple Paths in Graph Databases.
VLDB 1989: 185-193 BibTeX
- [Nau87]
- Jeffrey F. Naughton:
One-Sided Recursions.
PODS 1987: 340-348 BibTeX
- [Shm87]
- Oded Shmueli:
Decidability and Expressiveness of Logic Queries.
PODS 1987: 237-249 BibTeX
- [TZ86]
- Shalom Tsur, Carlo Zaniolo:
LDL: A Logic-Based Data Language.
VLDB 1986: 33-41 BibTeX
- [Ull89]
- Jeffrey D. Ullman:
Principles of Database and Knowledge-Base Systems, Volume II.
Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX
- [UvG86]
- Jeffrey D. Ullman, Allen Van Gelder:
Parallel Complexity of Logical Query Programs.
FOCS 1986: 438-454 BibTeX
Referenced by
- Holger Meuss, Klaus U. Schulz, François Bry:
Towards Aggregated Answers for Semistructured Data.
ICDT 2001: 346-360
- Yannis Papakonstantinou, Victor Vianu:
DTD Inference for Views of XML Data.
PODS 2000: 35-46
- Sergio Flesca, Sergio Greco:
Querying Graph Databases.
EDBT 2000: 510-524
- H. V. Jagadish, Laks V. S. Lakshmanan, Tova Milo, Divesh Srivastava, Dimitra Vista:
Querying Network Directories.
SIGMOD Conference 1999: 133-144
- Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, Moshe Y. Vardi:
Rewriting of Regular Expressions and Regular Path Queries.
PODS 1999: 194-204
- Jeonghee Kim, Taisook Han, Suk Kyoon Lee:
Visualization of Path Expressions in a Virtual Object-Oriented Database Query Language.
DASFAA 1999: 99-108
- Avigdor Gal, Opher Etzion:
A Multiagent Update Process in a Database with Temporal Data Dependencies and Schema Versioning.
IEEE Trans. Knowl. Data Eng. 10(1): 21-37(1998)
- Daniela Florescu, Alon Y. Levy, Alberto O. Mendelzon:
Database Techniques for the World-Wide Web: A Survey.
SIGMOD Record 27(3): 59-74(1998)
- Tiziana Catarci, Giuseppe Santucci, John Cardiff:
Graphical Interaction with Heterogeneous Databases.
VLDB J. 6(2): 97-120(1997)
- Serge Abiteboul, Victor Vianu:
Regular Path Queries with Constraints.
PODS 1997: 122-133
- Peter Buneman, Susan B. Davidson, Mary F. Fernandez, Dan Suciu:
Adding Structure to Unstructured Data.
ICDT 1997: 336-350
- Robert M. Colomb, Anne-Grethe Eilertsen:
Use of a Persistent Graph Abstract Data Type for Representing CASE Tools Repositories.
DASFAA 1997: 155-164
- Tiziana Catarci, Shi-Kuo Chang, Maria Francesca Costabile, Stefano Levialdi, Giuseppe Santucci:
A Graph-Based Framework for Multiparadigmatic Visual Access to Databases.
IEEE Trans. Knowl. Data Eng. 8(3): 455-475(1996)
- Peter Buneman, Susan B. Davidson, Gerd G. Hillebrand, Dan Suciu:
A Query Language and Optimization Techniques for Unstructured Data.
SIGMOD Conference 1996: 505-516
- Jan Paredaens, Peter Peelman, Letizia Tanca:
G-Log: A Graph-Based Query Language.
IEEE Trans. Knowl. Data Eng. 7(3): 436-453(1995)
- Mark Levene, George Loizou:
A Graph-Based Data Model and its Ramifications.
IEEE Trans. Knowl. Data Eng. 7(5): 809-823(1995)
- Serge Abiteboul, Richard Hull, Victor Vianu:
Foundations of Databases.
Addison-Wesley 1995, ISBN 0-201-53771-0
Contents - Marc Gyssens, Jan Paredaens, Jan Van den Bussche, Dirk Van Gucht:
A Graph-Oriented Object Database Model.
IEEE Trans. Knowl. Data Eng. 6(4): 572-586(1994)
- Ralf Hartmut Güting:
GraphDB: Modeling and Querying Graphs in Databases.
VLDB 1994: 297-308
- Alejandro Gutiérrez, Philippe Pucheral, Hermann Steffen, Jean-Marc Thévenin:
Database Graph Views: A Practical Model to Manage Persistent Graphs.
VLDB 1994: 391-402
- Mariano P. Consens, Tova Milo:
Optimizing Queries on Files.
SIGMOD Conference 1994: 301-312
- Vassilis Christophides, Serge Abiteboul, Sophie Cluet, Michel Scholl:
From Structured Documents to Novel Query Facilities.
SIGMOD Conference 1994: 313-324
- Mariano P. Consens, Alberto O. Mendelzon, Dimitra Vista:
Deductive Database Support for Data Visualization.
EDBT 1994: 45-58
- Shaul Dar, Rakesh Agrawal:
Extending SQL with Generalized Transitive Closure Functionality.
IEEE Trans. Knowl. Data Eng. 5(5): 799-812(1993)
- Mariano P. Consens, Alberto O. Mendelzon:
Hy+: A Hygraph-based Query and Visualization System.
SIGMOD Conference 1993: 511-516
- Isabel F. Cruz:
DOODLE: A Visual Language for Object-Oriented Databases.
SIGMOD Conference 1992: 71-80
- Peter T. Wood:
Factoring Augmented Regular Chain Programs.
VLDB 1990: 255-263
- Mariano P. Consens, Alberto O. Mendelzon:
The G+/GraphLog Visual Query System.
SIGMOD Conference 1990: 388
- Mariano P. Consens, Alberto O. Mendelzon:
Low Complexity Aggregation in GraphLog and Datalog.
ICDT 1990: 379-394
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:34:02 2009