A. Amarilli, P. Bourhis, M. Monet, and P. Senellart, Combined tractability of query evaluation via tree automata and cycluits, ICDT, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01439294

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

Y. Amsterdamer, D. Deutch, and V. Tannen, On the limitations of provenance for queries with difference, 2011.

Y. Amsterdamer, D. Deutch, and V. Tannen, Provenance for aggregate queries, Proceedings of the 30th symposium on Principles of database systems of data, PODS '11, 2011.
DOI : 10.1145/1989284.1989302
URL : http://arxiv.org/pdf/1101.1110.pdf

O. Benjelloun, A. Das-sarma, A. Halevy, and J. Widom, ULDBs: Databases with uncertainty and lineage, VLDB, 2006.
DOI : 10.1007/s00778-007-0080-z

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

P. Buneman, S. Khanna, and W. Tan, Why and Where: A Characterization of Data Provenance, ICDT, 2001.
DOI : 10.1007/3-540-44503-X_20

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
URL : http://www.nowpublishers.com/media/Journal-Article-PDFs/1900000006.pdf

Y. Cui and J. Widom, Practical lineage tracing in data warehouses, Proceedings of 16th International Conference on Data Engineering (Cat. No.00CB37073), 2000.
DOI : 10.1109/ICDE.2000.839437
URL : http://www-db.stanford.edu/pub/papers/trace.ps

N. Dalvi and D. Suciu, Efficient query evaluation on probabilistic databases, The VLDB Journal, vol.16, issue.4, 2007.
DOI : 10.1007/s00778-006-0004-3

N. Dalvi and D. Suciu, The dichotomy of probabilistic inference for unions of conjunctive queries, Journal of the ACM, vol.59, issue.6, p.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.8, issue.1-2, 2001.
DOI : 10.1016/0304-3975(94)00078-W

A. Darwiche, New advances in compiling CNF to decomposable negation normal form, ECAI, 2004.
DOI : 10.1145/502090.502091
URL : http://www.cs.ucla.edu/~darwiche/dnnf-jacm-pp.pdf

A. Darwiche and P. Marquis, A knowledge compilation map, J. Artificial Intelligence Research, vol.17, issue.1, 2002.

B. Susan, J. Davidson, and . Freire, Provenance and scientific workflows: challenges and opportunities, SIGMOD, 2008.

D. Deutch, T. Milo, S. Roy, and V. Tannen, Circuits for Datalog provenance, ICDT, 2014.

M. Droste, W. Kuich, and H. Vogler, Handbook of weighted automata, 2009.
DOI : 10.1007/978-3-642-01492-5

N. Fuhr and T. Rölleke, A probabilistic relational algebra for the integration of information retrieval and database systems, ACM Transactions on Information Systems, vol.15, issue.1, 1997.
DOI : 10.1145/239041.239045

F. Geerts and A. Poggi, On database query languages for K-relations, Journal of Applied Logic, vol.8, issue.2
DOI : 10.1016/j.jal.2009.09.001
URL : https://doi.org/10.1016/j.jal.2009.09.001

G. Green, T. J. Karvounarakis, Z. Ives, and V. Tannen, Provenance in ORCHESTRA, IEEE Data Eng. Bull, vol.33, issue.3, 2010.

J. Todd and . Green, Containment of conjunctive queries on annotated relations, Theory of Computing Systems, 2011.

J. Todd, G. Green, V. Karvounarakis, and . Tannen, Provenance semirings, PODS, 2007.

J. Todd, V. Green, and . Tannen, Models for incomplete and probabilistic information, IEEE Data Eng. Bull, vol.29, issue.1, 2006.

S. Grumbach and T. Milo, Towards tractable algebras for bags, J. Computer and System Sciences, vol.52, issue.3, 1996.
DOI : 10.1006/jcss.1996.0042
URL : https://doi.org/10.1006/jcss.1996.0042

O. Hartig, Provenance information in the web of data, LDOW, 2009.

T. Imielinski and W. Lipski-jr, Incomplete information in relational databases, J. ACM, vol.31, issue.4, 1984.

A. Jha, D. Olteanu, and D. Suciu, Bridging the gap between intensional and extensional query evaluation in probabilistic databases, Proceedings of the 13th International Conference on Extending Database Technology, EDBT '10, 2010.
DOI : 10.1145/1739041.1739082

A. Jha and D. Suciu, Knowledge compilation meets database theory, Proceedings of the 14th International Conference on Database Theory, ICDT '11, p.2013
DOI : 10.1145/1938551.1938574

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

J. Lagniez and P. Marquis, An Improved Decision-DNNF Compiler, Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, 2017.
DOI : 10.24963/ijcai.2017/93

V. Laks, N. Lakshmanan, R. Leone, V. Ross, and . Subrahmanian, Probview: A flexible probabilistic database system, ACM Transactions on Database Systems, vol.22, issue.3, 1997.

L. Libkin and L. Wong, Query Languages for Bags and Aggregate Functions, Journal of Computer and System Sciences, vol.55, issue.2
DOI : 10.1006/jcss.1997.1523
URL : https://doi.org/10.1006/jcss.1997.1523

S. Maniu, R. Cheng, and P. Senellart, An Indexing Framework for Queries on Probabilistic Graphs, Computer and System sciences, p.2017, 1997.
DOI : 10.1145/1835804.1835885
URL : https://hal.archives-ouvertes.fr/hal-01437580

M. Mohri, Semiring frameworks and algorithms for shortest-distance problems, J. Automata, Languages and Combinatorics, vol.7, issue.3, 2002.

M. Monet, Probabilistic Evaluation of Expressive Queries on Bounded-Treewidth Instances, Proceedings of the 2016 on SIGMOD'16 PhD Symposium, SIGMOD'16 PhD, 2016.
DOI : 10.1137/0208032

J. Christian, . Muise, A. Sheila, C. Mcilraith, E. I. Beck et al., Dsharp: Fast d-DNNF compilation with sharpSAT, Canadian Conference on AI, 2012.

D. Olteanu, J. Huang, and C. Koch, Approximate confidence computation in probabilistic databases, 2010 IEEE 26th International Conference on Data Engineering (ICDE 2010), 2010.
DOI : 10.1109/ICDE.2010.5447826
URL : http://www.cs.cornell.edu/~koch/download/icde2010_ohk.pdf

A. Souihli and P. Senellart, Optimizing approximations of DNF query lineage in probabilistic XML, 2013 IEEE 29th International Conference on Data Engineering (ICDE), 2013.
DOI : 10.1109/ICDE.2013.6544869
URL : https://hal.archives-ouvertes.fr/hal-00874442

D. Suciu, D. Olteanu, C. Ré, and C. Koch, Probabilistic Databases, 2011.
DOI : 10.2200/s00362ed1v01y201105dtm016

G. Tseitin, On the complexity of derivation in propositional calculus, Studies in Constrained Mathematics and Mathematical Logic, 1968.

I. Wegener, The complexity of Boolean functions, 1987.

A. Woodruff and M. Stonebraker, Supporting fine-grained data lineage in a database visualization environment, Proceedings 13th International Conference on Data Engineering, 1997.
DOI : 10.1109/ICDE.1997.581742