=Paper=
{{Paper
|id=Vol-1810/GraphQ_invited
|storemode=property
|title=None
|pdfUrl=https://ceur-ws.org/Vol-1810/GraphQ_invited.pdf
|volume=Vol-1810
|dblpUrl=https://dblp.org/rec/conf/edbt/Bonifati17
}}
==None==
https://ceur-ws.org/Vol-1810/GraphQ_invited.pdf
Graph Queries: Generation, Evaluation and Learning
Angela Bonifati
University Lyon 1
angela.bonifati@univ-lyon1.fr
1. INVITED TALK ABSTRACT [2] G. Bagan, A. Bonifati, R. Ciucanu, G. H. L. Fletcher,
Several modern graph query languages are capable of ex- A. Lemay, and N. Advokaat. gMark: Schema-Driven
pressing sophisticated graph queries, which return nodes Generation of Graphs and Queries. IEEE Trans. on
connected by arbitrarily complex paths. Such paths can be Knowl. Data Eng., In press, 2017.
synthesized by regular expressions and often involve recur- [3] G. Bagan, A. Bonifati, R. Ciucanu, G. H. L. Fletcher,
sion. Such graph queries are known as Regular Path Queries A. Lemay, and N. Advokaat. gMark: Schema-Driven
and correspond to Property Paths in Sparql 1.1. Recently, Generation of Graphs and Queries (Extended
with my colleagues I have been investigating regular path Abstract). In Proceedings of the International
queries and their combinations by looking at the generation Conference on Data Engineering ICDE 2017, San
problem [1, 2, 3, 10], the complexity of query evaluation [5] Diego, USA, To appear, 2017.
and the learning problem [9, 7, 6, 8]. Precisely, we focused [4] G. Bagan, A. Bonifati, G. H. L. Fletcher, and
on schema-driven generation of complex and broad graph H. Kheddouci. Labeling Schemes for RPQs and
queries with user-defined features, on the complexity of the beyond. In preparation, 2017.
evaluation of regular simple path queries and on learning [5] G. Bagan, A. Bonifati, and B. Groz. A trichotomy for
algorithms for regular path queries. In this talk, I will be- regular simple path queries on graphs. In Proceedings
gin with a brief recap of graph queries and their expressive of the 32nd ACM SIGMOD-SIGACT-SIGART
power. I will then provide an overview of a comprehensive Symposium on Principles of Database Systems, PODS
query-oriented graph benchmark that we have designed and 2013, New York, NY, USA, pages 261–272, 2013.
assessed [1, 2, 3, 10]. I will next discuss the theoretical re- [6] A. Bonifati, R. Ciucanu, and A. Lemay. Interactive
sults of our study on the complexity of regular simple path Path Query Specification on Graph Databases. In
queries [5]. I will then present a learning framework for Proceedings of the 18th International Conference on
regular path queries and discuss its potential along with its Extending Database Technology, EDBT 2015,
practical feasibility [7, 6, 8]. To conclude, I will briefly out- Brussels, Belgium, pages 505–508, 2015.
line our ongoing work [4] and pinpoint lingering issues and [7] A. Bonifati, R. Ciucanu, and A. Lemay. Learning Path
research directions in the study of graph queries. Queries on Graph Databases. In Proceedings of the
18th International Conference on Extending Database
Technology, EDBT 2015, Brussels, Belgium, pages
109–120, 2015.
Acknowledgements This is joint work with my colleagues
at CNRS, Eindhoven University of Technology, Université [8] A. Bonifati, R. Ciucanu, A. Lemay, and S. Staworko.
Clermont Auvergne, Université Lille 3 and Université Paris A Paradigm for Learning Queries on Big Data. In
Sud. This work is partially supported by the Palse Impulsion Proceedings of the First International Workshop on
Individual Grant and by the CNRS Mastodons MedClean. Bringing the Value of ”Big Data” to Users,
Data4U@VLDB 2014, Hangzhou, China, 2014.
[9] A. Bonifati, R. Ciucanu, and S. Staworko. Learning
2. REFERENCES Join Queries from User Examples. ACM Trans.
Database Syst., 40(4):24:1–24:38, 2016.
[1] G. Bagan, A. Bonifati, R. Ciucanu, G. H. L. Fletcher,
[10] W. V. Leuween, A. Bonifati, and N. Yakovets.
A. Lemay, and N. Advokaat. Generating Flexible
Stability notions in synthetic graph generation: a
Workloads for Graph Databases. PVLDB,
preliminary study. In Proceedings of the 18th
9(13):1447–1460, 2016.
International Conference on Extending Database
Technology, EDBT 2017, Venice, Italy, To appear,
2017.
c 2017, Copyright is with the authors. Published in the Workshop Proceed-
ings of the EDBT/ICDT 2017 Joint Conference (March 21, 2017, Venice,
Italy) on CEUR-WS.org (ISSN 1613-0073). Distribution of this paper is
permitted under the terms of the Creative Commons license CC-by-nc-nd
4.0