GraphLog

GraphLog: a visual formalism for real life recursion. 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 in zbMATH (referenced in 32 articles )

Showing results 1 to 20 of 32.
Sorted by year (citations)

1 2 next

  1. Michaliszyn, Jakub; Otop, Jan; Wieczorek, Piotr: Modular path queries with arithmetic (2021)
  2. Kostylev, Egor V.; Reutter, Juan L.; Vrgoč, Domagoj: Containment of queries for graphs with data (2018)
  3. Martens, Wim; Trautner, Tina: Evaluation and enumeration problems for regular path queries (2018)
  4. Michaliszyn, Jakub; Otop, Jan; Wieczorek, Piotr: Querying best paths in graph databases (2018)
  5. Reutter, Juan L.; Romero, Miguel; Vardi, Moshe Y.: Regular queries on graph databases (2017)
  6. Reutter, Juan L.; Vrgoč, Domagoj: Navigational and rule-based languages for graph databases (2017)
  7. Barceló, Pablo; Romero, Miguel; Vardi, Moshe Y.: Semantic acyclicity on graph databases (2016)
  8. Kostylev, Egor V.; Reutter, Juan L.; Vrgoč, Domagoj: Static analysis of navigational XPath over graph databases (2016)
  9. Fagin, Ronald; Kimelfeld, Benny; Reiss, Frederick; Vansummeren, Stijn: Document spanners: a formal approach to information extraction (2015)
  10. Vrgoč, Domagoj: Using variable automata for querying data graphs (2015)
  11. Barceló, Pablo; Libkin, Leonid; Reutter, Juan L.: Querying regular graph patterns (2014)
  12. Barceló, Pablo; Figueira, Diego; Libkin, Leonid: Graph logics with rational relations (2013)
  13. Santini, Simone: Regular languages with variables on graphs (2012)
  14. Dovier, A.; Quintarelli, E.: Applying model-checking to solve queries on semistructured data (2009)
  15. Shoaran, Maryam; Thomo, Alex: Fault-tolerant computation of distributed regular path queries (2009)
  16. Vaisman, Alejandro A.; Espil, Mauricio Minuto; Paradela, Martín: P2P OLAP: data model, implementation and case study (2009) ioport
  17. Flesca, Sergio; Greco, Sergio: Partially ordered regular languages for graph queries (2005)
  18. Libkin, Leonid: Expressive power of SQL. (2003)
  19. Calvanese, Diego; De Giacomo, Giuseppe; Lenzerini, Maurizio; Vardi, Moshe Y.: Rewriting of regular expressions and regular path queries (2002)
  20. Cortesi, Agostino; Dovier, Agostino; Quintarelli, Elisa; Tanca, Letizia: Operational and abstract semantics of the query language G-Log (2002)

1 2 next