GraphLog: a Visual Formalism for Real Life Recursion

Summary: Introduces GraphLog, a visual query language where queries are graph patterns and query edges denote edges or regular-expression-qualified paths, enabling natural expression of recursion over graph data. Shows GraphLog’s power equals stratified linear Datalog, FO+transitive closure and NLOGSPACE (with ordering), and describes extensions for aggregates and path summarization plus a prototype. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 917
Venue: PODS
Year: 1990
Pagerank: 0.00022046803
Overall Rank: 300 | 97.95%
DOI: 10.1145/298514.298591

Incoming Non-self Citations Over Time

Authors

1. Mariano P. Consens (University of Toronto)
2. Alberto O. Mendelzon (University of Toronto)

BibTeX Citation

@inproceedings{consens_pods90,
        address = {New York, NY, USA},
        series = {{PODS} '90},
        title = {{GraphLog: a Visual Formalism for Real Life Recursion}},
        url = {https://dl.acm.org/doi/10.1145/298514.298591},
        doi = {10.1145/298514.298591},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Consens, Mariano P. and Mendelzon, Alberto O.},
        year = {1990}
}

Incoming Citations (Sorted by Pagerank)

Showing 34 of 34 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
124	A Query Language and Optimization Techniques for Unstructured Data	1996	SIGMOD	0.00030950263
294	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00022253507
348	Regular Path Queries with Constraints	1997	PODS	0.00020518814
547	Cypher: An Evolving Query Language for Property Graphs	2018	SIGMOD	0.00016731552
571	From Structured Documents to Novel Query Facilities	1994	SIGMOD	0.0001632382
747	Querying Graph Databases	2013	PODS	0.00014400452
1,290	DTD Inference for Views of XML Data	2000	PODS	0.00011312135
1,359	GraphDB: Modeling and Querying Graphs in Databases	1994	VLDB	0.00011040427
1,528	Joining Extractions of Regular Expressions	2018	PODS	0.00010486718
1,575	Expressive Languages for Path Queries over Graph-Structured Data	2010	PODS	0.00010318258
2,066	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS	9.2348082e-05
2,201	Querying Network Directories	1999	SIGMOD	8.9653966e-05
2,588	Optimizing Queries on Files	1994	SIGMOD	8.3742403e-05
3,452	The Complexity of Evaluating Path Expressions in SPARQL	2012	PODS	7.4007472e-05
3,922	Hy+: A Hygraph-based Query and Visualization System	1993	SIGMOD	7.016223e-05
4,813	Horton+: A Distributed System for Processing Declarative Reachability Queries over Partitioned Graphs	2013	VLDB	6.4974292e-05
4,822	Colorful XML: One Hierarchy Isn't Enough	2004	SIGMOD	6.4919484e-05
4,972	On the Optimization of Recursive Relational Queries: Application to Graph Queries	2020	SIGMOD	6.4193234e-05
4,986	Querying Graph Patterns	2011	PODS	6.4120976e-05
5,418	Representing Paths in Graph Database Pattern Matching	2023	VLDB	6.2255373e-05
5,425	GPC: A Pattern Calculus for Property Graphs	2023	PODS	6.223218e-05
5,482	The G+/GraphLog Visual Query System	1990	SIGMOD	6.202193e-05
7,028	Semantic Acyclicity on Graph Databases	2013	PODS	5.7228058e-05
7,289	Conjunctive Regular Path Queries with String Variables	2020	PODS	5.654364e-05
7,410	TriAL for RDF: Adapting Graph Query Languages for RDF Data	2013	PODS	5.6242786e-05
7,603	GQL and SQL/PGQ: Theoretical Models and Expressive Power	2025	VLDB	5.5853593e-05
7,769	G-SQL: Fast Query Processing via Graph Exploration	2016	VLDB	5.5474529e-05
8,816	DOODLE: A Visual Language for Object-Oriented Databases	1992	SIGMOD	5.363753e-05
8,884	GBLENDER: Towards Blending Visual Query Formulation and Query Processing in Graph Databases	2010	SIGMOD	5.3514928e-05
10,167	A Logical View of GNN-Style Computation and the Role of Activation Functions	2026	PODS	5.093636e-05
10,756	Dangers of List Processing in Querying Property Graphs	2025	SIGMOD	5.093636e-05
12,228	Spanners: A Formal Framework for Information Extraction	2013	PODS	5.093636e-05
13,039	Database Graph Views: A Practical Model to Manage Persistent Graphs	1994	VLDB	5.093636e-05
13,124	Factoring Augmented Regular Chain Programs	1990	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
174	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.00027231487
355	Object Identity As A Query Language Primitive	1989	SIGMOD	0.00020351749
616	Parallel Evaluation of Recursive Rule Queries	1986	PODS	0.00015712636
622	LDL: A Logic-Based Data-Language	1986	VLDB	0.00015686753
1,658	Finding Regular Simple Paths in Graph Databases	1989	VLDB	0.00010092304
2,033	One-Sided Recursions	1987	PODS	9.2819369e-05
2,076	A Study of Transitive Closure As a Recursion Mechanism	1987	SIGMOD	9.212586e-05
3,739	Neptune: a Hypertext System for CAD Applications	1986	SIGMOD	7.1594837e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	544	A New Approach to Database Logic	1984	PODS
2	4,745	Graph Queries in a Next-Generation Datalog System	2013	VLDB
3	7,972	On the First-Order Expressibility of Recursive Queries	1989	PODS
4	294	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD
5	1,575	Expressive Languages for Path Queries over Graph-Structured Data	2010	PODS
6	7,885	IDLOG: Extending the Expressive Power of Deductive Database Languages	1990	SIGMOD
7	10,582	FlowLog: Efficient and Extensible Datalog via Incrementality	2026	VLDB
8	5,482	The G+/GraphLog Visual Query System	1990	SIGMOD
9	9,430	A Theory of Regular Queries	2016	PODS
10	312	A Graphical Query Language Supporting Recursion	1987	SIGMOD