GraphLog
Mariano P. Consens, Alberto O. Mendelzon · Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems · 1990
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.
Cited by 342 works. doi:10.1145/298514.298591 Open-access PDF
Authors
References
- Principles of database and knowledge-base systems
- Department of Computer Science
- Principles of database and knowledge-base systems, Vol. I
- Universality of data retrieval languages
- Neptune: a hypertext system for CAD applications
- Neptune: a hypertext system for CAD applications
- Finding Regular Simple Paths in Graph Databases
- Structure and complexity of relational queries
- Object identity as a query language primitive
- Expressing structural hypertext queries in graphlog