]. A. Aap-`-13aap-`-aap-`-13, D. Abouzied, C. H. Angluin, J. M. Papadimitriou, A. Hellerstein et al., Learning and verifying quantified boolean queries by example Highly expressive query languages for unordered data trees, PODS ICDT, pp.49-60, 2012.

C. [. Amano, L. David, F. Libkin, and . Murlak, XML Schema Mappings, Journal of the ACM, vol.61, issue.2, pp.12-68, 2014.
DOI : 10.1145/2590773

A. Comput, ]. J. Survagw01, D. Albert, D. Giammarresi, and . Wood, Normal form algorithms for extended context-free grammars, Theor. Comput. Sci, vol.40, issue.26712, pp.14535-14582, 2001.

J. [. Abouzied, A. Hellerstein, and . Silberschatz, Playful query specification with DataPlay, Proceedings of the VLDB Endowment, vol.5, issue.12, pp.1938-1941, 2012.
DOI : 10.14778/2367502.2367542

R. [. Abiteboul, V. Hull, and . Vianu, Foundations of Databases 104 [AL08] M. Arenas and L. Libkin. XML data exchange: Consistency and query answering, Ang80] D. Angluin. Inductive inference of formal languages from positive data. Information and Control, pp.68117-135, 1980.

]. D. Ang82, ]. Angluinang88, F. Antonopoulos, F. Neven, and . Servais, Inference of reversible languages Queries and concept learning Definability problems for graph query languages, Machine Learning ICDT, pp.741-765, 1982.

J. [. Arenas and . Pérez, Querying semantic web data with SPARQL, Proceedings of the 30th symposium on Principles of database systems of data, PODS '11, pp.305-316, 2011.
DOI : 10.1145/1989284.1989312

]. B. Atckt11a, B. Alexe, P. G. Ten-cate, W. C. Kolaitis, and . Tan, Designing and refining schema mappings via data examples, SIGMOD Conference, pp.133-144, 2011.

]. B. Atckt11b, B. Alexe, P. G. Ten-cate, W. C. Kolaitis, and . Tan, EIRENE: Interactive design and refinement of schema mappings via data examples, PVLDB, vol.4, issue.100, pp.1414-1417, 2011.

S. [. Amer-yahia, L. V. Cho, D. Lakshmanan, . Srivastavaban78-]-f, and . Bancilhon, Tree pattern query minimization, MFCSBar13] P. Barceló. Querying graph databases. In PODS, pp.315-331, 1978.
DOI : 10.1007/s00778-002-0076-7

A. [. Boneva, R. Bonifati, G. Ciucanu, A. Bagan, B. Bonifati et al., Graph data exchange with target constraints A trichotomy for regular simple path queries on graphs Recognizing shuffled languages Interactive path query specification on graph databases Learning path queries on graph databases, PODS LATA Schema Matching and Mapping EDBT EDBTBCLS14] A. Bonifati, R. Ciucanu, A. Lemay, and S. Staworko. A paradigm for learning queries on big data. In Data4U, pp.171-176, 2011.

R. [. Boneva, S. Ciucanu, . Staworkobcs14a-]-i, R. Boneva, S. Ciucanu et al., Simple schemas for unordered XML, WebDB, pp.13-18, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00824459

]. A. Bcs14b, R. Bonifati, S. Ciucanu, and . Staworko, Interactive inference of join queries, EDBTBCS14c] A. Bonifati, R. Ciucanu, and S. Staworko. Interactive join query inference with JIM. PVLDB, pp.451-462, 2014.

]. A. Bcs14d, R. Bonifati, S. Ciucanu, and . Staworko, Learning join queries from user examples (under journal submission), 2014.

]. K. Bel14 and . Belhajjame, Annotating the behavior of scientific modules using data examples: A practical approach, EDBT, pp.726-737, 2014.

W. [. Benedikt, F. Fan, P. A. Geerts, I. Boncz, A. Fundulaki et al., XPath satisfiability in the presence of DTDs The linked data benchmark council project. Datenbank-Spektrum Learning deterministic regular expressions for the inference of schemas from XML data One-unambiguous regular languages Querying graph patterns Schemas for integration and translation of structured and semi-structured data, PODS ICDT Björklund, W. Martens, and T. Schwentick. Validity of tree pattern queries with respect to schema information MFCS, pp.56121-129, 1998.

F. [. Bex, T. Neven, K. Schwentick, and . Tuyls, Inference of concise DTDs from XML data, VLDB, pp.115-126, 2006.

F. [. Bex, T. Neven, S. Schwentick, and . Vansummeren, Inference of concise regular expressions and DTDs, Bex, F. Neven, and S. Vansummeren. Inferring XML schema definitions from XML data. In VLDB, pp.95-998, 2007.
DOI : 10.1145/1735886.1735890

]. G. Bnvdb04, F. Bex, J. Neven, ]. P. Van-den-busschebpr13, J. Barceló et al., DTDs versus XML Schema: A practical study Schema mappings and data exchange for graph databases Automata and logics for unranked and unordered trees, WebDB ICDT RTA, pp.79-84, 2004.

I. Boneva, J. Talbot, S. Tisonbv84, C. Beeri, M. Y. Vardi et al., Expressiveness of a spatial logic for trees A proof procedure for data dependencies Deciding definability by deterministic regular expressions, LICS FoSSaCS, pp.280-289, 1984.

G. [. Cardelli, ]. A. Ghellicgk13, G. Calì, M. Gottlob, J. Kifer et al., TQL: a query language for semistructured data based on the ambient logic, Machine Learning, pp.285-327, 2004.
DOI : 10.1017/S0960129504004141

G. [. Colazzo, L. Ghelli, C. Pardini, and . Sartiani, Almostlinear inclusion for XML regular expression types, ACM Trans. Database Syst, vol.38, issue.23, pp.15-56, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00923690

D. Colazzo, G. Ghelli, C. Sartianiciu13-]-r, and . Ciucanu, Efficient inclusion for a class of XML types with interleaving and counting, SIGMOD/PODS PhD Symposium, pp.643-656, 2009.
DOI : 10.1016/j.is.2008.10.001
URL : https://hal.archives-ouvertes.fr/inria-00535983

S. [. Ciucanu, ]. S. Staworko, Y. Cohen, and . Weiss, Learning schemas for unordered XML Certain and possible XPath answers Characteristic sets for polynomial grammatical inference, ICDT Machine Learning Grammatical Inference: Learning Automata and Grammars, pp.31-40, 1997.

[. Sarma, A. Parameswaran, H. Garcia-molina, and J. Widom, Synthesizing view definitions from data, ICDT, pp.89-103, 2010.

D. [. Dal-zilio, ]. W. Lugiezfglx11, F. Fan, J. Geerts, M. Li et al., XML schema, tree logic and sheaves automata Discovering conditional functional dependencies, RTA, pp.246-263, 2003.

M. [. Fletcher, J. Gyssens, D. Paredaens, and . Van-gucht, On the Expressive Power of the Relational Algebra on Finite Sets of Relation Pairs, IEEE Transactions on Knowledge and Data Engineering, vol.21, issue.6, pp.939-942, 2009.
DOI : 10.1109/TKDE.2008.221

T. [. Freydenberger and . Kötzing, Fast learning of restricted regular expressions and DTDs, ICDT, pp.45-56, 2013.

. J. Fkk-`-11fkk-`-fkk-`-11-]-m, D. Franklin, T. Kossmann, S. Kraska, R. Ramesh et al., CrowdDB: answering queries with crowdsourcing Data exchange: semantics and query answering Managing semi-structured data, SIGMOD Conference Ghelli, D. Colazzo, and C. Sartiani. Linear time membership in a class of regular expressions with interleaving and counting. In CIKM, pp.61-72, 2005.

M. Garofalakis, A. Gionis, R. Rastogi, S. Seshadri, K. Shimgm13 et al., XTRACT: Learning document type descriptors from XML document collections The quality of the XML web, Gelade, W. Martens, and F. Neven. Optimizing schema languages for XML: Numerical constraints and interleaving, pp.23-56, 2003.
DOI : 10.1023/A:1021560618289

S. J. Computgol78-]-e, . Goldgs10-]-g, P. Gottlob, . Senellartgv90-]-p, E. Garcia et al., Complexity of automaton identification from given data Schema mapping discovery from data instances Inference of k-testable languages in the strict sense and application to syntactic pattern recognition, Information and Control J. ACM IEEE Trans. Pattern Anal. Mach. Intell, vol.38, issue.129, pp.2021-2043, 1978.

]. C. Hei01 and . Heinlein, Workflow and process synchronization with interaction expressions and graphs, ICDE, pp.243-252, 2001.

Y. [. Hashimoto, Y. Kusunoki, T. Ishihara, and . Fujiwara, Validity of positive XPath queries with wildcard in the presence of DTDs, DBPL, p.56, 2011.

]. D. Hov12 and . Hovland, The membership problem for regular expressions with unordered concatenation and numerical constraints, LATA, pp.313-324, 2012.

J. [. Hopcroft, . Ullmanilj84-]-t, W. Imielinski, and . Lipski-jr, Introduction to Automata Theory, Languages and Computation Incomplete information in relational databases Making database systems usable, SIGMOD Conference, pp.152761-791, 1979.

. Jkl-`-14jkl-`-jkl-`-14-]-n, A. Jayaram, C. Khan, X. Li, R. Yan et al., Towards a query-by-example system for knowledge graphs, GRADES, p.147, 2014.

U. [. Koschmieder, . G. Leserkpss14-]-p, R. Kolaitis, E. Pichler, V. Sallinger et al., Lower bounds for natural proof systems Nested dependencies: structure and reasoning The complexity of data exchange Parikh images of grammars: Complexity and applications, SSDBM FOCS PODS PODS LICS Kearns and U. V. Vazirani. An introduction to computational learning theory Leskovec and C. Faloutsos. Sampling from large graphs KDD, pp.177-194, 1977.

]. G. Lln-`-14lln-`-lln-`-14, A. Laurence, J. Lemay, S. Niehren, M. Staworko et al., Learning sequential tree-to-word transducers The complexity of regular expressions and property paths in SPARQL A learning algorithm for top-down XML transformations, LATA PODS, pp.490-502, 2010.

S. [. Lohrey, E. Maneth, ]. A. Noethlng06, J. Lemay, R. Niehren et al., XML compression via DAGs Learning n-ary node selecting tree transducers from completely annotated examples, ICDT ICGI, pp.69-80, 2006.

[. Lange and P. Rossmanith, The emptiness problem for intersections of regular languages, MFCS, pp.346-354, 1992.
DOI : 10.1007/3-540-55808-X_33

[. Min, J. Ahn, and C. Chung, Efficient extraction of schemas for XML documents, Lissandrini, Y. Velegrakis, and T. Palpanas. Exemplar queries: Give me an example of what you need. PVLDB, pp.7-12, 2003.
DOI : 10.1016/S0020-0190(02)00345-9

F. [. Martens, W. Neven, F. Martens, T. Neven, F. Schwentick-martens et al., Typechecking topdown XML transformations: Fixed input or output schemas Complexity of decision problems for simple regular expressions Complexity of decision problems for XML schemas and chain regular expressions Word problems-this time with interleaving Miklau and D. Suciu. Containment and equivalence for a fragment of XPath, On the complexity of typechecking top-down XML transformations. Theor. Comput. Sci. MFCSMWK`11MWK`MWK`11] A. Marcus, E. Wu, D. Karger, S. Madden, and R. Miller. Human-powered sorts and joins. PVLDB [MWM07] M. Montazerian, P. T. Wood, and S. R. Mousavi. XPath query satisfiability is in PTIME for real-world DTDs. In XSym, pp.153-180, 1994.

H. [. Nandi and . Jagadish, Guided interaction: Rethinking the query-result paradigm, PVLDB, vol.4, issue.12 1, pp.1466-1469, 2011.

T. [. Neven and . Schwentick, XML schemas without order, p.55, 1999.

T. [. Neven and . Schwentick, On the complexity of XPath containment in the presence of disjunction, DTDs, and variables, Logical Methods in Computer Science, vol.2, issue.3, pp.15-56, 2006.
DOI : 10.2168/LMCS-2(3:1)2006

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

]. D. Opp78 and . Oppen, A 2 2 2 pn upper bound on the complexity of Presburger arithmetic, J. Comput. Syst. Sci, vol.16, issue.87, pp.323-332, 1978.

]. J. Par78 and . Paredaens, On the expressive power of the relational algebra, Inf. Process. Lett, vol.7, issue.4, pp.107-111, 1978.

]. A. Plc-`-08plc-`-plc-`-08, D. Poggi, D. Lembo, G. Calvanese, M. De-giacomo et al., Linking data to ontologies Highperformance information extraction with AliBaba, EDBT, pp.133-173, 2008.

V. [. Papakonstantinou and . Vianu, DTD inference for views of XML data, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems , PODS '00, pp.35-46, 2000.
DOI : 10.1145/335168.335173

]. L. Pvm-`-02pvm-`-pvm-`-02, Y. Popa, R. J. Velegrakis, M. A. Miller, R. Hernández et al., Translating web data Sample-driven schema mapping, VLDB SIGMOD Conference, pp.598-609, 2002.

P. [. Russell, . Norvigrs09-]-r, O. Ronen, and . Shmueli, Artificial Intelligence -A Modern Approach (3. internat Pearson Education SoQL: A language for querying and creating data in social networks, ICDE, pp.124-1595, 2009.

M. [. Sequeda, D. P. Arenas, and . Miranker, On directly mapping relational databases to RDF and OWL, Proceedings of the 21st international conference on World Wide Web, WWW '12, pp.649-658, 2012.
DOI : 10.1145/2187836.2187924

H. R. Prud-'hommeaux and . Solbrig, Complexity and expressiveness of ShEx for RDF, ICDT, pp.195-211, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01218552

]. T. Sch78 and . Schaefer, The complexity of satisfiability problems, STOC, pp.216-226, 1921.

M. [. Sellam and . Kersten, Meet Charles, big data query advisor, CIDR, p.143, 2013.

A. [. Stockmeyer, L. Meyer, C. Segoufin, ]. H. Sirangelossm08, T. Seidl et al., Word problems requiring exponential time: Preliminary report Constant-memory validation of streaming XML documents against DTDs Counting in trees Validating streaming XML documents, STOC ICDT Logic and Automata PODS ICDT, pp.1-9, 1973.

I. Carey, R. Manolescu, V. Busse-cate, P. G. Dalmau, and . Kolaitis, XMark: A benchmark for XML data management Learning schema mappings Query by output, VLDB SIGMOD Conference, pp.974-985, 2002.

. [. Van-gucht, On the expressive power of the extended relational algebra for the unnormalized relational model, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems , PODS '87, pp.302-312, 1987.
DOI : 10.1145/28659.28692

J. Wang, G. Li, T. Kraska, M. J. Franklin, J. Feng-yan et al., Leveraging transitive relations for crowdsourced joins Query languages for graph databases Datadriven understanding and refinement of schema mappings, SIGMOD Conference SIGMOD Conference, pp.229-240, 2001.

]. Z. Yzi-`-13yzi-`-yzi-`-13, N. Yan, Z. G. Zheng, P. P. Ives, C. Talukdar et al., Actively soliciting feedback for query answers in keyword searchbased data integration Reverse engineering complex join queries, SIGMOD Conference Zloof. Query by example AFIPS National Computer Conference, pp.205-216, 1975.