Using variable automata for querying data graphs.

*(English)*Zbl 1317.68048Summary: Thus far query languages for graphs databases that, in addition to navigating the structure of a graph, also consider data values encountered along the paths they traverse, seem to exhibit somewhat dual behaviour in terms of the efficiency of their query evaluation problem. Namely, their combined complexity is either tractable, or are at least PSpace-hard. In this paper we show how to use the model of variable automata to get a query language with intermediate (NP-complete) combined complexity of query evaluation. Since variable automata are incomparable in terms of expressive power with previously studied querying mechanisms for data graphs we also show how to join their capabilities with the ones of previously used languages without an increase in the complexity of query evaluation, thus getting the best of both worlds.

##### MSC:

68P15 | Database theory |

68P05 | Data structures |

68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |

68Q45 | Formal languages and automata |

PDF
BibTeX
XML
Cite

\textit{D. Vrgoč}, Inf. Process. Lett. 115, No. 3, 425--430 (2015; Zbl 1317.68048)

Full Text:
DOI

##### References:

[1] | Barceló, P., Querying graph databases, (PODS, (2013)) |

[2] | Calvanese, D.; De Giacomo, G.; Lenzerini, M.; Vardi, M., Containment of conjunctive regular path queries with inverse, (KR, (2000)) |

[3] | Consens, M.; Mendelzon, A., Graphlog: a visual formalism for real life recursion, (PODS, (1990)) |

[4] | Dex, DEX query language, sparsity technologies, (2013) |

[5] | Figueira, D., Reasoning on words and trees with data, (2010), ÉNS de Cachan, Ph.D. thesis |

[6] | Grumberg, O.; Kupferman, O.; Sheinvald, S., Variable automata over infinite alphabets, (LATA, (2010)) · Zbl 1284.68352 |

[7] | O. Grumberg, O. Kupferman, S. Sheinvald, Variable automata over infinite alphabets, Manuscript, 2010. · Zbl 1284.68352 |

[8] | Kaminski, M.; Francez, N., Finite memory automata, Theor. Comput. Sci., 134, 2, (1994) · Zbl 0938.68711 |

[9] | Libkin, L.; Martens, W.; Vrgoč, D., Querying graph databases with xpath, (ICDT, (2013)) |

[10] | Libkin, L.; Tan, T.; Vrgoč, D., Regular expressions with binding over data words for querying graph databases, (DLT, (2013)) · Zbl 1381.68126 |

[11] | Libkin, L.; Vrgoč, D., Regular path queries on graphs with data, (ICDT, (2012)), 74-85 |

[12] | Neo4j, Neo4j, the graph database, (2013) |

[13] | Pérez, J.; Arenas, M.; Gutierrez, C., Nsparql: a navigational language for RDF, J. Web Semant., 8, 4, 255-270, (2010) |

[14] | Vrgoč, D., Querying graphs with data, (2014), School of Informatics, University of Edinburgh, Ph.D. thesis |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.