ML Anthology

Querying Data Graphs with Arithmetical Regular Expressions

Maciej Grabon, Jakub Michaliszyn, Jan Otop, Piotr Wieczorek
IJCAI 2016 pp. 1088-1094
/ijcai/2016/grabon2016ijcai-querying/

Abstract

We propose a query language LARE for graphs whose edges are labelled by a finite alphabet and nodes store unbounded data values. LARE is based on a variant of regular expressions with memory. Queries of LARE can compare quantities of memorised graph nodes and their neighbourhoods. These features allow us to express a number of natural properties, while keeping the data complexity (with a query fixed) in non-deterministic logarithmic space. We establish an algorithm that works efficiently not only with LARE, but also with a wider language defined using effective relational conditions, another formalism we propose. PDF

PDF IJCAI Semantic Scholar

Cite

Text

Grabon et al. "Querying Data Graphs with Arithmetical Regular Expressions." International Joint Conference on Artificial Intelligence, 2016.

Markdown

[Grabon et al. "Querying Data Graphs with Arithmetical Regular Expressions." International Joint Conference on Artificial Intelligence, 2016.](https://mlanthology.org/ijcai/2016/grabon2016ijcai-querying/)

BibTeX

@inproceedings{grabon2016ijcai-querying,
  title     = {{Querying Data Graphs with Arithmetical Regular Expressions}},
  author    = {Grabon, Maciej and Michaliszyn, Jakub and Otop, Jan and Wieczorek, Piotr},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2016},
  pages     = {1088-1094},
  url       = {https://mlanthology.org/ijcai/2016/grabon2016ijcai-querying/}
}