Evènement pour le groupe Séminaire Méthodes Formelles

Date 2016-06-28  11:00-12:00
TitreNesting Depth of Operators in Graph DatabaseQueries: Expressiveness vs. Evaluation Complexity 
RésuméExpressiveness and efficient algorithms for query evaluation are conflicting goals while designing languages for querying graph structured data. To better handle dynamically changing data, recent work has been done on designing query languages that can compare values stored in the graph database, without hard coding the values in the query. The main idea is to allow variables in the query and bind the variables to values when evaluating the query. For query languages that bind variables only once, query evaluation is usually NP-complete. There are query languages that allow binding inside the scope of Kleene star operators, which can themselves be in the scope of bindings and so on. Uncontrolled nesting of binding and iteration within one another results in query evaluation being PSPACE-complete. In this talk, we present a way to syntactically control the nesting depth of iterated bindings, and study how this affects the expressiveness and complexity of query evaluation. This is joint work with B. Sreevathsan. **Séminaire en salle 178** 
OrateurM. Praveen 
UrlCMI Chennai 

Aucun document lié à cet événement.

Retour à l'index