S. Abiteboul, R. Hull, and V. Vianu, Foundations of Databases, 1995.

R. Angles, The property graph database model, AMW, volume 2100 of CEUR Workshop Proceedings, 2018.

R. Angles, M. Arenas, P. Barceló, A. Hogan, J. L. Reutter et al., Foundations of modern query languages for graph databases, ACM Computing Surveys, vol.50, p.40, 2017.

D. Angluin, Queries and concept learning, Machine Learning, vol.2, pp.319-342, 1988.

A. Arioua and A. Bonifati, User-guided repairing of inconsistent knowledge bases, EDBT, pp.133-144, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01979680

P. B. Baeza, Querying graph databases, PODS, pp.175-188, 2013.

G. Bagan, A. Bonifati, R. Ciucanu, G. H. Fletcher, A. Lemay et al., Generating Flexible Workloads for Graph Databases, PVLDB, vol.9, issue.13, pp.1457-1460, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01330111

G. Bagan, A. Bonifati, R. Ciucanu, G. H. Fletcher, A. Lemay et al., gMark: Schema-driven generation of graphs and queries, IEEE Transactions on Knowledge and Data Engineering, vol.29, issue.4, pp.856-869, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01591706

G. Bagan, A. Bonifati, and B. Groz, A Trichotomy for Regular Simple Path Queries on Graphs, PODS, pp.261-272, 2013.
URL : https://hal.archives-ouvertes.fr/hal-02435355

F. Bancilhon, D. Maier, Y. Sagiv, and J. D. Ullman, Magic Sets and Other Strange Ways to Implement Logic Programs, PODS, pp.1-15, 1986.

C. Bizer, J. Lehmann, G. Kobilarov, S. Auer, C. Becker et al., DBpedia -A crystallization point for the Web of Data, Journal of Web Semantics, vol.7, issue.3, pp.154-165, 2009.

A. Bonifati, R. Ciucanu, and A. Lemay, Interactive Path Query Specification on Graph Databases, EDBT, pp.505-508, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01187975

A. Bonifati, R. Ciucanu, and A. Lemay, Learning Path Queries on Graph Databases, EDBT, pp.109-120, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01187966

A. Bonifati, R. Ciucanu, A. Lemay, and S. Staworko, A Paradigm for Learning Queries on Big Data, vol.4, p.7, 2014.
URL : https://hal.archives-ouvertes.fr/hal-01052676

A. Bonifati, R. Ciucanu, and S. Staworko, Learning Join Queries from User Examples, ACM Transactions on Database Systems, vol.40, issue.4, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01187986

A. Bonifati, S. Dumbrava, and E. J. Arias, Certified Graph View Maintenance with Regular Datalog. Theory and Practice of Logic Programming, vol.18, pp.372-389, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01932818

A. Bonifati, G. H. Fletcher, H. Voigts, and N. Yakovets, Querying Graphs. Synthesis Lectures on Data Management, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01974379

A. Bonifati, W. Martens, and T. Timm, An Analytical Study of Large SPARQL Query Logs, PVLDB, vol.11, issue.2, pp.149-161, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01979692

A. K. Chandra and P. M. Merlin, Optimal Implementation of Conjunctive Queries in Relational Data Bases, STOC, pp.77-90, 1977.

S. Cohen and Y. Weiss, Certain and possible XPath answers, ICDT, pp.237-248, 2013.

C. De-la-higuera, Grammatical Inference: Learning Automata and Grammars, 2010.
URL : https://hal.archives-ouvertes.fr/hal-00476128

R. Delanaux, A. Bonifati, M. Rousset, and R. Thion, Query-based linked data anonymization, ISWC, pp.530-546, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01896276

S. Dumbrava, A. Bonifati, A. Ruiz-diaz, and R. Vuillemot, Approximate Query Processing for Label-Constrained Reachability Queries, 2018.

O. Erling, A. Averbuch, J. Larriba-pey, H. Chafi, A. Gubichev et al., The LDBC social network benchmark: Interactive workload, SIGMOD, pp.619-630, 2015.

E. M. Gold, Complexity of automaton identification from given data, Information and Control, vol.37, issue.3, pp.302-320, 1978.

G. Gonthier, A. Asperti, J. Avigad, Y. Bertot, C. Cohen et al., A Machine-Checked Proof of the Odd Order Theorem, ITP, pp.163-179, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00816699

A. Gupta, I. S. Mumick, and V. S. Subrahmanian, Maintaining Views Incrementally. SIGMOD Record, vol.22, pp.157-166, 1993.

J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages and Computation, 1979.

T. Imielinski and W. Lipski, Incomplete information in relational databases, Journal of the ACM, vol.31, issue.4, pp.761-791, 1984.

A. P. Iyer, A. Panda, S. Venkataraman, M. Chowdhury, A. Akella et al., Bridging the GAP: towards approximate graph analytics, GRADES, vol.10, pp.1-10, 2018.

H. V. Jagadish, R. Agrawal, and L. Ness, A Study of Transitive Closure As a Recursion Mechanism, SIGMOD, pp.331-344, 1987.

K. Losemann and W. Martens, The complexity of regular expressions and property paths in SPARQL, ACM Transactions on Database Systems, vol.38, issue.4, 2013.

W. Martens and T. Trautner, Evaluation and Enumeration Problems for Regular Path Queries, ICDT, pp.1-21, 2018.

M. Dumontier, A. Callahan, J. Cruz, -. Toledo, P. Ansell et al., Bio2RDF Release 3: A larger, more connected network of Linked Data for the Life Sciences, ISWC, pp.401-404, 2014.

J. Oncina and P. García, Inferring regular languages in polynomial update time, Pattern Recognition and Image Analysis, pp.49-61, 1992.

J. L. Reutter, M. Romero, and M. Y. Vardi, Regular queries on graph databases. Theory of Computing Systems, vol.61, pp.31-83, 2017.

, The Coq Development Team. The Coq proof assistant, 2018.

L. G. Valiant, The complexity of computing the permanent, Theoretical Computer Science, vol.8, pp.189-201, 1979.

M. Y. Vardi, A theory of regular queries, PODS, pp.1-9, 2016.

D. Vrande?i? and M. Krötzsch, Wikidata: A Free Collaborative Knowledgebase, Communications of the ACM, vol.57, issue.10, pp.78-85, 2014.