A. Amarilli, Y. Amsterdamer, and T. Milo, On the Complexity of Mining Itemsets from the Crowd Using Taxonomies, Proc. ICDT, pp.15-25, 2014.
URL : https://hal.archives-ouvertes.fr/hal-00986184

A. Amarilli and M. Benedikt, Combining Existential Rules and Description Logics, Proc. IJCAI, pp.2691-2697, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01190601

A. Amarilli and M. Benedikt, Finite Open-World Query Answering with Number Restrictions url: https, Proc. LICS, pp.305-316, 2015.

A. Amarilli, P. Bourhis, and P. Senellart, Provenance Circuits for Trees and Treelike Instances, Proc. ICALP, pp.56-68, 2015.
DOI : 10.1007/978-3-662-47666-6_5
URL : https://hal.archives-ouvertes.fr/hal-01178399

A. Amarilli, P. Bourhis, and P. Senellart, Tractable Lineages on Treelike Instances, Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS '16, pp.226-238, 2016.
DOI : 10.1145/2902251.2902301
URL : https://hal.archives-ouvertes.fr/hal-01336514

R. Tang, A. Amarilli, P. Senellart, and S. Bressan, Get a Sample for a Discount, Proc. DEXA, pp.20-34, 2014.
DOI : 10.1007/978-3-319-10073-9_3
URL : https://hal.archives-ouvertes.fr/hal-01069820

A. Amarilli, The Possibility Problem for Probabilistic XML, Proc. AMW. url, 2014.
URL : https://hal.archives-ouvertes.fr/hal-01190712

A. Amarilli, Structurally Tractable Uncertain Data, Proceedings of the 2015 ACM SIGMOD on PhD Symposium, SIGMOD '15 PhD Symposium, pp.39-44, 2015.
DOI : 10.1145/2744680.2744690
URL : https://hal.archives-ouvertes.fr/hal-01190610

A. Amarilli, Y. Amsterdamer, and T. Milo, Uncertainty in Crowd Data Sourcing Under Structural Constraints, Proc. UnCrowd, 2014.
DOI : 10.1007/978-3-662-43984-5_27
URL : https://hal.archives-ouvertes.fr/hal-01190716

A. Talaika, J. Biega, A. Amarilli, and F. M. Suchanek, IBEX, Proceedings of the 18th International Workshop on Web and Databases, WebDB'15, 2015.
DOI : 10.1145/2767109.2767116
URL : https://hal.archives-ouvertes.fr/hal-01190629

. Webdb and . Acm, url: https, pp.13-19

A. Amarilli, Possibility for Probabilistic XML url: https://arxiv, pp.53-75, 2015.

R. Tang, A. Amarilli, P. Senellart, and S. Bressan, A Framework for Sampling-Based XML Data Pricing, pp.116-138, 2016.
DOI : 10.1007/978-3-662-49214-7_4
URL : https://hal.archives-ouvertes.fr/hal-01261958

A. Amarilli, Y. Amsterdamer, T. Milo, and P. Senellart, Top-k Queries on Unknown Values under Order Constraints, pp.215-230, 2016.

A. Amarilli, L. M. Ba, D. Deutch, and P. Senellart, Possible and Certain Answers for Queries over Order-Incomplete Data, pp.215-230, 2016.

A. Amarilli and M. Benedikt, Finite Open-World Query Answering with Number Restrictions, 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science, pp.233-238, 2016.
DOI : 10.1109/LICS.2015.37
URL : https://hal.archives-ouvertes.fr/hal-01190580

A. Amarilli, L. Galárraga, N. Preda, and F. M. Suchanek, Recent Topics of Research around the YAGO Knowledge Base, Proc. APWEB. LNCS, vol.8709, issue.239, pp.1-1234912, 2014.
DOI : 10.1007/978-3-319-11116-2_1
URL : https://hal.archives-ouvertes.fr/hal-01190642

A. Amarilli, S. Maniu, and P. Senellart, Intensional Data on the Web url: https : //a3nm, SIGWEB Newsletter Summer 2015, pp.1-4, 2015.

A. Amarilli, Leveraging the Structure of Uncertain Data, p.244, 2016.
URL : https://hal.archives-ouvertes.fr/tel-01345836

S. Abiteboul, R. Hull, and V. Vianu, Foundations of Databases (cit, pp.189-227, 1995.

Y. Amsterdamer, D. Deutch, and V. Tannen, On the Limitations of Provenance for Queries with Difference, Proc. TaPP (cit, p.78, 2011.

Y. Amsterdamer, Y. Grossman, T. Milo, and P. Senellart, Crowd mining, Proceedings of the 2013 international conference on Management of data, SIGMOD '13, 2013.
DOI : 10.1145/2463676.2465318
URL : https://hal.archives-ouvertes.fr/hal-00874443

L. Antova, C. Koch, and D. Olteanu, World-Set Decompositions: Expressiveness and Efficient Algorithms, Proc. ICDT (cit, p.231, 2007.
DOI : 10.1007/11965893_14

S. Arnborg, J. Lagergren, and D. Seese, Easy problems for tree-decomposable graphs, Journal of Algorithms, vol.12, issue.2, p.75, 1991.
DOI : 10.1016/0196-6774(91)90006-K

J. Baget, M. Leclère, and M. Mugnier, On rules with existential variables: Walking the decidability line, Proc. KR (cit. on pp. 8, p.234, 2010.
DOI : 10.1016/j.artint.2011.03.002
URL : https://hal.archives-ouvertes.fr/lirmm-00587012

J. Baget, M. Leclère, M. Mugnier, and E. Salvat, Extending Decidable Cases for Rules with Existential Variables, Proc. IJCAI (cit. on pp. 9, p.235, 2009.
URL : https://hal.archives-ouvertes.fr/lirmm-00410130

V. Bárány, G. Gottlob, and M. Otto, Querying the Guarded Fragment, LICS (cit, pp.130-215, 2010.

D. Barbará, H. Garcia-molina, and D. Porter, The management of probabilistic data, IEEE Transactions on Knowledge and Data Engineering, vol.4, issue.5, pp.51-61, 1992.
DOI : 10.1109/69.166990

C. Bizer, J. Lehmann, G. Kobilarov, S. Auer, C. Becker et al., DBpedia - A crystallization point for the Web of Data, Web Semantics: Science, Services and Agents on the World Wide Web, vol.7, issue.3, 2009.
DOI : 10.1016/j.websem.2009.07.002

H. L. Bodlaender, A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth, In: SIAM J. Comput, vol.25, issue.21, p.31, 1996.

M. Hans and L. Bodlaender, Probabilistic Inference and Monadic Second Order Logic, Proc. IFIP TCS (cit, p.58, 2012.

G. Brightwell and P. Winkler, Counting linear extensions, Order, vol.39, issue.2, 1991.
DOI : 10.1007/BF00383444

R. E. Bryant, Symbolic Boolean manipulation with ordered binary-decision diagrams, ACM Computing Surveys, vol.24, issue.3, pp.43-228, 1992.
DOI : 10.1145/136035.136043

A. Calì, G. Gottlob, and A. Pieris, Towards more expressive ontology languages: The query answering problem, Artif. Intel. 193 (cit. on pp. 9, pp.139-218, 2012.
DOI : 10.1016/j.artint.2012.08.002

A. Calì, D. Lembo, and R. Rosati, On the decidability and complexity of query answering over inconsistent and incomplete databases, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems , PODS '03, pp.129-139, 2003.
DOI : 10.1145/773153.773179

A. Calì, D. Lembo, and R. Rosati, Query Answering by Rewriting in GLAV Data Integration Systems Under Constraints, Proc. IJCAI (cit, p.139, 2003.
DOI : 10.1007/978-3-540-31839-2_13

A. Calì, G. Gottlob, and A. Pieris, Advanced processing for ontological queries, Proceedings of the VLDB Endowment, vol.3, issue.1-2, 2010.
DOI : 10.14778/1920841.1920912

D. Calvanese, G. D. Giacomo, and M. Y. Vardi, Decidable Containment of Recursive Queries, 2005.

D. Calvanese, T. Eiter, and M. Ortiz, Regular Path Queries in Expressive Description Logics with Nominals, Proc. IJCAI (cit, p.218, 2009.

A. Carlson, J. Betteridge, B. Kisiel, B. Settles, R. Estevam et al., Toward an Architecture for Never-Ending Language Learning, Proc. AAAI (cit, p.224, 2010.

M. A. Casanova, R. Fagin, and C. H. Papadimitriou, Inclusion Dependencies and Their Interaction with Functional Dependencies, 1984.

S. Chaudhuri and M. Y. Vardi, On the Equivalence of Recursive and Nonrecursive Datalog Programs, Proc. PODS (cit, pp.28-30, 1992.

C. Chekuri and J. Chuzhoy, Polynomial Bounds for the Grid- Minor Theorem, Proc. STOC (cit, pp.93-96, 2014.

C. Chekuri and J. Chuzhoy, Polynomial Bounds for the Grid-Minor Theorem, CoRR abs/1305, 2014.

J. Cheney, L. Chiticariu, and W. Tan, Provenance in Databases: Why, How, and Where, Foundations and Trends in Databases, vol.1, issue.4, 2009.
DOI : 10.1561/1900000006

F. Edgar and . Codd, A Relational Model of Data for Large Shared Data Banks, 1970.

S. Cohen, B. Kimelfeld, and Y. Sagiv, Running tree automata on probabilistic XML, Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, PODS '09, pp.65-71, 2009.
DOI : 10.1145/1559795.1559831

H. Comon, M. Dauchet, R. Gilleron, C. Löding, F. Jacquemard et al., Tree Automata: Techniques and Applications, pp.47-88, 2007.

S. S. Cosmadakis, P. C. Kanellakis, and M. Y. Vardi, Polynomial-time implication problems for unary inclusion dependencies, Journal of the ACM, vol.37, issue.1, pp.140-143, 1990.
DOI : 10.1145/78935.78937

B. Courcelle, J. A. Makowsky, and U. Rotics, Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width, TCS 33, 2000.

B. Courcelle, The monadic second-order logic of graphs. I. Recognizable sets of finite graphs, Information and Computation, vol.85, issue.1, pp.30-105, 1990.
DOI : 10.1016/0890-5401(90)90043-H
URL : https://hal.archives-ouvertes.fr/hal-00353765

B. Courcelle, J. Engelfriet, and G. Rozenberg, Handle-rewriting hypergraph grammars, JCSS 46, 1993.
DOI : 10.1016/0022-0000(93)90004-G

N. Dalvi, K. Schnaitter, and D. Suciu, Computing query probability with incidence algebras, Proceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems of data, PODS '10, p.73, 2010.
DOI : 10.1145/1807085.1807113

N. Dalvi and D. Suciu, Efficient Query Evaluation on Probabilistic Databases, pp.24-225, 2007.

N. Dalvi and D. Suciu, The dichotomy of probabilistic inference for unions of conjunctive queries, Journal of the ACM, vol.59, issue.6, pp.15-17, 2012.
DOI : 10.1145/2395116.2395119

A. Darwiche, On the Tractable Counting of Theory Models and its Application to Truth Maintenance and Belief Revision, Journal of Applied Non-Classical Logics, vol.141, issue.10, pp.45-51, 2001.
DOI : 10.1145/136035.136043

D. Deutch, T. Milo, S. Roy, and V. Tannen, Circuits for Datalog Provenance, In: ICDT (cit. on pp, vol.4, issue.219, pp.78-216, 2014.

A. Deutsch, A. Nash, and J. Remmel, The chase revisited, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems , PODS '08, p.136, 2008.
DOI : 10.1145/1376916.1376938

R. Diestel, Graph Theory, 2005.

X. Dong, A. Y. Halevy, and C. Yu, Data integration with uncertainty, The VLDB Journal, vol.29, issue.1, 2007.
DOI : 10.1007/s00778-008-0119-9

F. Feodor, F. V. Dragan, P. A. Fomin, and . Golovach, Spanners in Sparse Graphs, 2011.

M. Droste and P. Gastin, Weighted Automata and Weighted Logics, p.216, 2007.
DOI : 10.1016/j.tcs.2007.02.055
URL : https://hal.archives-ouvertes.fr/hal-00772642

C. Dwork, R. Kumar, M. Naor, and D. Sivakumar, Rank aggregation methods for the Web, Proceedings of the tenth international conference on World Wide Web , WWW '01, p.231, 2001.
DOI : 10.1145/371920.372165

R. Fagin, P. G. Kolaitis, R. J. Miller, and L. Popa, Data Exchange: Semantics and Query Answering, Proc. ICDT (cit, p.136, 2003.
DOI : 10.1016/j.tcs.2004.10.033
URL : http://doi.org/10.1016/j.tcs.2004.10.033

R. Fagin, A. Lotem, and M. Naor, Optimal aggregation algorithms for middleware, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems , PODS '01, p.231, 2001.
DOI : 10.1145/375551.375567

J. Flum, M. Frick, and M. Grohe, Query Evaluation via Tree- Decompositions, In: J. ACM, vol.49, issue.102, pp.32-34, 2002.
DOI : 10.1007/3-540-44503-x_2
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.120.8500

J. , N. Foster, T. J. Green, and V. Tannen, Annotated XML: Queries and Provenance, Proc. PODS (cit, p.78, 2008.

R. Ganian, P. Hlinený, J. Kneis, D. M. Obdrzálek, P. Rossmanith et al., Are There Any Good Digraph Width Measures, Proc. IPEC (cit. on p. 103), 2010.
DOI : 10.1007/978-3-642-17493-3_14
URL : http://arxiv.org/abs/1004.1485

R. Ganian, P. Hlinený, J. Kneis, D. M. Obdrzálek, P. Rossmanith et al., Are there any good digraph width measures?, In: J. Comb. Theory, Ser. B, vol.116, 2016.
DOI : 10.1007/978-3-642-17493-3_14
URL : http://arxiv.org/abs/1004.1485

R. Ganian, P. Hlin?n-`-hlin?n-`-y, A. Langer-obdr?álek, P. Rossmanith, and S. Sikdar, Lower Bounds on the Complexity of MSO 1 Model- Checking, pp.105-108, 2014.
URL : https://hal.archives-ouvertes.fr/hal-00678189

W. Gatterbauer and D. Suciu, Approximate lifted inference with probabilistic databases, Proceedings of the VLDB Endowment, vol.8, issue.5, 2015.
DOI : 10.14778/2735479.2735494

F. Gavril, The intersection graphs of subtrees in trees are exactly the chordal graphs, Journal of Combinatorial Theory, Series B, vol.16, issue.1, 1974.
DOI : 10.1016/0095-8956(74)90094-X

B. Glimm, I. Horrocks, C. Lutz, and U. Sattler, Conjunctive Query Answering for the Description Logic SHIQ, p.31, 2008.

T. Gogacz and J. Marcinkowski, Converging to the Chase ? A Tool for Finite Controllability, Proc. LICS (cit. on pp. 10, pp.215-236, 2013.

G. Gottlob, E. Grädel, and H. Veith, Datalog LITE: a deductive query language with linear time model checking, ACM Transactions on Computational Logic, vol.3, issue.1, 2002.
DOI : 10.1145/504077.504079

G. Gottlob, R. Pichler, and F. Wei, Monadic Datalog over Finite Structures of Bounded Treewidth, 2010.

E. Grädel, Efficient Evaluation Methods for Guarded Logics and Datalog LITE, Proc. LPAR, 2000.
DOI : 10.1007/3-540-44404-1_26

E. Grädel, C. Hirsch, and M. Otto, Back and Forth between Guarded and Modal Logics, pp.29-33, 2002.

J. Grant, Null values in a relational data base, Information Processing Letters, vol.6, issue.5, 1977.
DOI : 10.1016/0020-0190(77)90013-8

T. J. Green, G. Karvounarakis, and V. Tannen, Provenance semirings, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems , PODS '07, pp.77-79, 2007.
DOI : 10.1145/1265530.1265535

J. Todd, V. Green, and . Tannen, Models for Incomplete and Probabilistic Information, Proc. IIDB (cit. on pp. 4, pp.53-215, 2006.

M. Grohe, Logic, Graphs, and Algorithms, Logic and Automata: History and Perspectives 2 (cit, p.94, 2007.

S. Grumbach and T. Milo, An Algebra for Pomsets, Inf. Comput, vol.150, issue.2, 1999.

U. S. Gsa, Data.gov. https://www.data.gov/ (cit, p.219, 2015.

M. Haklay and P. Weber, OpenStreetMap: User-Generated Street Maps, Pervasive Computing, 2008.
DOI : 10.1109/MPRV.2008.80

G. Hansel, Nombre minimal de contacts de fermeture nécessaires pour réaliser une fonction booléenne symétrique de n variables, Sc. Paris, vol.258, 1964.

J. Håstad, The shrinkage exponent of de Morgan formulas is 2, In: SIAM J. Comput, vol.27, issue.1, 1998.

C. Huang and A. Darwiche, Inference in belief networks: A procedural guide, International Journal of Approximate Reasoning, vol.15, issue.3, 1996.
DOI : 10.1016/S0888-613X(96)00069-2

J. Huang, L. Antova, C. Koch, and D. Olteanu, MayBMS, Proceedings of the 35th SIGMOD international conference on Management of data, SIGMOD '09, pp.51-53, 2009.
DOI : 10.1145/1559845.1559984

Y. Ibáñez-garcía, C. Lutz, and T. Schneider, Finite Model Reasoning in Horn Description Logics, Proc. KR (cit, pp.129-131, 2014.

T. Imieli?ski and W. Lipski-jr, Incomplete Information in Relational Databases, J. ACM 31, vol.4, issue.2, pp.42-53, 1984.

K. Iwama and H. Morizumi, An Explicit Lower Bound of 5n ??? o(n) for Boolean Circuits, MFCS (cit, p.216, 2002.
DOI : 10.1007/3-540-45687-2_29

M. Jacob, B. Kimelfeld, and J. Stoyanovich, A system for management and analysis of preference data, Proceedings of the VLDB Endowment, vol.7, issue.12, 2014.
DOI : 10.14778/2732977.2732998

A. Kumar, J. , and D. Suciu, On the Tractability of Query Compilation and Bounded Treewidth, ICDT (cit. on pp. 41, pp.45-123, 2012.

A. Kumar, J. , and D. Suciu, Knowledge Compilation Meets Database Theory: Compiling Queries to Decision Diagrams, pp.41-45, 2013.

S. David, A. C. Johnson, and . Klug, Testing Containment of Conjunctive Queries under Functional and Inclusion Dependencies, pp.131-139, 1984.

R. Kannan, L. Lovász, and M. Simonovits, Random Walks and an O * (n 5 ) Volume Algorithm for Convex Bodies, In: Random Struct. Algorithms, vol.11, issue.1, 1997.

G. Karvounarakis and T. J. Green, Semiring-annotated data, ACM SIGMOD Record, vol.41, issue.3, 2012.
DOI : 10.1145/2380776.2380778

Y. Kazakov, A Polynomial Translation from the Two-Variable Guarded Fragment with Number Restrictions to the Guarded Fragment, Proc. JELIA (cit. on pp, 2004.
DOI : 10.1007/978-3-540-30227-8_32

B. Kimelfeld, Y. Kosharovsky, and Y. Sagiv, Query efficiency in probabilistic XML models, Proceedings of the 2008 ACM SIGMOD international conference on Management of data , SIGMOD '08, p.69, 2008.
DOI : 10.1145/1376616.1376687

B. Kimelfeld and P. Senellart, Probabilistic XML: Models and Complexity Advances in Probabilistic Databases for Uncertain Information Management, p.225, 2013.

S. Kreutzer, Algorithmic meta-theorems, Parameterized and Exact Computation, 2008.
DOI : 10.1007/978-3-540-79723-4_3
URL : http://arxiv.org/abs/0902.3616

S. Kreutzer and C. Riveros, Quantitative Monadic Second-Order Logic, 2013 28th Annual ACM/IEEE Symposium on Logic in Computer Science, p.216, 2013.
DOI : 10.1109/LICS.2013.16

S. Kreutzer and S. Tazari, Lower Bounds for the Complexity of Monadic Second-Order Logic, 2010 25th Annual IEEE Symposium on Logic in Computer Science, p.229, 2010.
DOI : 10.1109/LICS.2010.39

L. Steffen, D. J. Lauritzen, and . Spiegelhalter, Local Computations with Probabilities on Graphical Structures and Their Application to Expert Systems, In: J. Royal Statistical Society. Series B, vol.44, issue.53, 1988.

L. Libkin, Incomplete data, Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, PODS '14, p.224, 2014.
DOI : 10.1145/2594538.2594561

M. Liskiewicz, M. Ogihara, and S. Toda, The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes, Theoretical Computer Science, vol.304, issue.1-3, 2003.
DOI : 10.1016/S0304-3975(03)00080-X

J. A. Makowsky and J. P. Marino, Tree-width and the monadic quantifier hierarchy, TCS 303.1 (cit, 2003.
DOI : 10.1016/S0304-3975(02)00449-8

S. Maniu, R. Cheng, and P. Senellart, ProbTree: A Query- Efficient Representation of Probabilistic Graphs, Proc. BUDA (cit, p.217, 2014.

A. Grigori and . Margulis, Explicit Constructions of Graphs Without Short Cycles and Low Density Codes, 1982.

A. R. Meyer, Weak monadic second order theory of succesor is not elementary-recursive, Proc. Logic Colloquium (cit, pp.29-217, 1975.
DOI : 10.1007/BFb0064872

C. John and . Mitchell, The Implication Problem for Functional and Inclusion Dependencies, In: Information and Control, vol.563, 1983.

M. Mohri, F. Pereira, and M. Riley, Weighted Finite-State Transducers in Speech Recognition, Computer Speech & Language, vol.16, issue.1, 2002.

H. Mühleisen and C. Bizer, Web Data Commons ? Extracting Structured Data from Two Large Web Corpora, p.937, 2012.

F. Neven and T. Schwentick, Query automata over finite trees, Theoretical Computer Science, vol.275, issue.1-2, p.66, 2002.
DOI : 10.1016/S0304-3975(01)00301-2
URL : http://doi.org/10.1016/s0304-3975(01)00301-2

D. Olteanu and J. Huang, Using OBDDs for Efficient Query Evaluation on Probabilistic Databases, Proc. SUM (cit. on pp. 4, pp.41-43, 2008.
DOI : 10.1007/978-3-540-87993-0_26

A. Onet, The Chase Procedure and its Applications in Data Exchange, Data Exchange, Integration, and Streams (cit, p.136, 2013.

M. Otto, Modal and Guarded Characterisation Theorems over Finite Transition Systems, LICS (cit. on pp. 11, pp.203-237, 2002.
DOI : 10.1016/j.apal.2004.04.003
URL : http://doi.org/10.1016/j.apal.2004.04.003

M. Otto, Highly Acyclic Groups, Hypergraph Covers, and the Guarded Fragment, J. ACM, vol.59, issue.1, 2012.

A. Parameswaran, H. Garcia-molina, H. Park, N. Polyzotis, A. Ramesh et al., CrowdScreen, Proceedings of the 2012 international conference on Management of Data, SIGMOD '12, 2012.
DOI : 10.1145/2213836.2213878

R. Pichler, S. Rümmele, and S. Woltran, Counting and Enumeration Problems with Bounded Treewidth, Logic for Programming, 2010.
DOI : 10.1007/978-3-642-17511-4_22

I. Pratt-hartmann, Data-complexity of the two-variable fragment with counting quantifiers, Information and Computation, vol.207, issue.8, pp.129-130, 2009.
DOI : 10.1016/j.ic.2009.02.004

J. , S. Provan, and M. O. Ball, The Complexity of Counting Cuts and of Computing the Probability That a Graph is Connected, In: SIAM Journal on Computing, vol.12, issue.4, 1983.

C. Ré and D. Suciu, Materialized Views in Probabilistic Databases: For Information Exchange and Query Optimization, Proc. VLDB (cit. on pp. 4, pp.52-61, 2007.

N. Robertson and P. D. Seymour, Graph minors. V. Excluding a planar graph, Journal of Combinatorial Theory, Series B, vol.41, issue.1, p.96, 1986.
DOI : 10.1016/0095-8956(86)90030-4
URL : http://doi.org/10.1006/jctb.1999.1919

R. Rosati, On the decidability and finite controllability of query processing in databases with incomplete information, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems , PODS '06, pp.137-218, 2006.
DOI : 10.1145/1142351.1142404

R. Rosati, Finite Model Reasoning in DL-Lite, Proc. ESWC (cit. on pp. 10, pp.131-137, 2008.
DOI : 10.1007/978-3-540-68234-9_18

R. Rosati, On the finite controllability of conjunctive query answering in databases under open-world assumption, Journal of Computer and System Sciences, vol.77, issue.3, pp.129-131, 2011.
DOI : 10.1016/j.jcss.2010.04.011

S. Rudolph and B. Glimm, Nominals, Inverses, Counting, and Conjunctive Queries or: Why Infinity is your Friend, p.39, 2010.

M. Fabian, G. Suchanek, G. Kasneci, and . Weikum, YAGO: A Core of Semantic Knowledge, Proc. WWW (cit, pp.219-239, 2007.

D. Suciu, D. Olteanu, C. Ré, and C. Koch, Probabilistic Databases, pp.51-52, 2011.

W. James, J. B. Thatcher, and . Wright, Generalized Finite Automata Theory with an Application to a Decision Problem of Second-Order Logic, Math. Systems Theory, p.35, 1968.

S. Tobies, Complexity Results and Practical Algorithms for Logics in Knowledge Representation, p.217, 2001.

D. Toman and G. E. Weddell, On Path-Functional Dependencies as First-Class Citizens in Description Logics, Proc. DL (cit, p.218, 2005.

G. Leslie and . Valiant, The Complexity of Enumeration and Reliability Problems, In: SIAM J. Comput, vol.8, issue.3, 1979.

D. Vrande?i? and M. Krötzsch, Wikidata, Communications of the ACM, vol.57, issue.10, pp.219-224, 2014.
DOI : 10.1145/2629489

E. Grant and . Weddell, A Theory of Functional Dependencies for Object-Oriented Data Models, Proc. DOOD (cit, p.218, 1989.

I. Wegener, The Complexity of Boolean Functions, pp.47-50, 1987.

M. Xia, P. Zhang, and W. Zhao, Computational complexity of counting problems on 3-regular planar graphs, Theoretical Computer Science, vol.384, issue.1, pp.95-96, 2007.
DOI : 10.1016/j.tcs.2007.05.023