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: hfac4045c4360b689
Venue: PODS
Year: 1990
Pagerank: 0.00021840374
Overall Rank: 297 | 98.01%
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
130	A Query Language and Optimization Techniques for Unstructured Data	1996	SIGMOD	0.00030320165
288	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00021969641
356	Regular Path Queries with Constraints	1997	PODS	0.00020103855
419	Cypher: An Evolving Query Language for Property Graphs	2018	SIGMOD	0.0001854669
582	From Structured Documents to Novel Query Facilities	1994	SIGMOD	0.00015982468
719	Querying Graph Databases	2013	PODS	0.00014529156
1,315	DTD Inference for Views of XML Data	2000	PODS	0.00011058412
1,350	GraphDB: Modeling and Querying Graphs in Databases	1994	VLDB	0.0001094492
1,468	Expressive Languages for Path Queries over Graph-Structured Data	2010	PODS	0.00010566509
1,560	Joining Extractions of Regular Expressions	2018	PODS	0.00010251636
2,041	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS	9.1421879e-05
2,241	Querying Network Directories	1999	SIGMOD	8.7708234e-05
2,637	Optimizing Queries on Files	1994	SIGMOD	8.1877616e-05
3,474	The Complexity of Evaluating Path Expressions in SPARQL	2012	PODS	7.2718547e-05
4,006	Hy+: A Hygraph-based Query and Visualization System	1993	SIGMOD	6.8593128e-05
4,553	GQL and SQL/PGQ: Theoretical Models and Expressive Power	2025	VLDB	6.5393335e-05
4,915	Horton+: A Distributed System for Processing Declarative Reachability Queries over Partitioned Graphs	2013	VLDB	6.356048e-05
4,936	Colorful XML: One Hierarchy Isn't Enough	2004	SIGMOD	6.3464763e-05
4,965	GPC: A Pattern Calculus for Property Graphs	2023	PODS	6.3360914e-05
5,050	On the Optimization of Recursive Relational Queries: Application to Graph Queries	2020	SIGMOD	6.2976106e-05
5,096	Querying Graph Patterns	2011	PODS	6.2743507e-05
5,557	Representing Paths in Graph Database Pattern Matching	2023	VLDB	6.085853e-05
5,617	The G+/GraphLog Visual Query System	1990	SIGMOD	6.0637955e-05
6,713	G-SQL: Fast Query Processing via Graph Exploration	2016	VLDB	5.7002243e-05
7,140	Semantic Acyclicity on Graph Databases	2013	PODS	5.6005794e-05
7,437	Conjunctive Regular Path Queries with String Variables	2020	PODS	5.5274952e-05
7,551	TriAL for RDF: Adapting Graph Query Languages for RDF Data	2013	PODS	5.4980866e-05
8,981	DOODLE: A Visual Language for Object-Oriented Databases	1992	SIGMOD	5.2434048e-05
9,043	GBLENDER: Towards Blending Visual Query Formulation and Query Processing in Graph Databases	2010	SIGMOD	5.2315718e-05
10,384	A Logical View of GNN-Style Computation and the Role of Activation Functions	2026	PODS	4.9793485e-05
11,181	Dangers of List Processing in Querying Property Graphs	2025	SIGMOD	4.9793485e-05
12,519	Spanners: A Formal Framework for Information Extraction	2013	PODS	4.9793485e-05
13,329	Database Graph Views: A Practical Model to Manage Persistent Graphs	1994	VLDB	4.9793485e-05
13,414	Factoring Augmented Regular Chain Programs	1990	VLDB	4.9793485e-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
177	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.000266613
366	Object Identity As A Query Language Primitive	1989	SIGMOD	0.00019923978
633	Parallel Evaluation of Recursive Rule Queries	1986	PODS	0.00015380574
635	LDL: A Logic-Based Data-Language	1986	VLDB	0.00015368492
1,597	Finding Regular Simple Paths in Graph Databases	1989	VLDB	0.0001012429
2,065	One-Sided Recursions	1987	PODS	9.0940924e-05
2,109	A Study of Transitive Closure As a Recursion Mechanism	1987	SIGMOD	9.0238479e-05
3,766	Neptune: a Hypertext System for CAD Applications	1986	SIGMOD	7.0363934e-05

Semantically Similar Papers

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