A New Class of Lineage Expressions over Probabilistic Databases Computable in P-Time

1. Beeri, C., Fagin, R., Maier, D., Yannakakis, M.: On the desirability of acyclic database schemes. J. ACM 30, 479–513 (1983)

   Article  MathSciNet  MATH  Google Scholar 

2. Benjelloun, O., Sarma, A., Halevy, A., Theobald, M., Widom, J.: Databases with uncertainty and lineage. VLDB Journal 17(2), 243–264 (2008)

   Article  Google Scholar 

3. Cavallo, R., Pittarelli, M.: The theory of probabilistic databases. In: VLDB, pp. 71–81 (1987)

   Google Scholar 

4. Chaplick, S.: Path Graphs and PR-trees. PhD thesis, Charles University, Prague (January 2012)

   Google Scholar 

5. Dalvi, N., Schnaitter, K., Suciu, D.: Computing query probability with incidence algebras. In: PODS, pp. 203–214. ACM (2010)

   Google Scholar 

6. Dalvi, N., Suciu, D.: Efficient query evaluation on probabilistic databases. VLDB Journal 16, 523–544 (2007)

   Article  Google Scholar 

7. Dietz, P.F.: Intersection Graph Algorithms. PhD thesis, Cornell University (August 1984)

   Google Scholar 

8. Duris, D.: Some characterizations of γ and β-acyclicity of hypergraphs. Inf. Process. Lett. 112(16), 617–620 (2012)

   Article  MathSciNet  MATH  Google Scholar 

9. Fuhr, N., Rölleke, T.: A probabilistic relational algebra for the integration of information retrieval and database systems. ACM Transactions on Information Systems 15, 32–66 (1994)

   Article  Google Scholar 

10. Gavril, F.: The intersection graphs of subtrees in trees are exactly the chordal graphs. Journal of Combinatorial Theory, Series B 16(1), 47–56 (1974)

    Article  MathSciNet  MATH  Google Scholar 

11. Gavril, F.: A recignition algorithm for the intersection graphs of directed paths in directed trees. Discrete Mathematics 13, 237–249 (1975)

    Article  MathSciNet  MATH  Google Scholar 

12. Golumbic, M., Mintz, A., Rotics, U.: Factoring and recognition of read-once functions using cographs and normality. In: DAC (June 2001)

    Google Scholar 

13. Jha, A.K., Suciu, D.: Knowledge compilation meets database theory: compiling queries to decision diagrams. In: ICDT, pp. 162–173 (2011)

    Google Scholar 

14. Kenig, B., Gal, A., Strichman, O.: A new class of lineage expressions over probabilistic databases computable in p-time. Technical Report IE/IS-2013-01, Technion – Israel Institute of Technology (January 2013), http://ie.technion.ac.il/tech_reports/1365582056_TechReportSUM2013.pdf

15. Koller, D., Friedman, N.: Probabilistic Graphical Models: Principles and Techniques. The MIT Press (August 2009)

    Google Scholar 

16. Olteanu, D., Huang, J.: Using OBDDs for efficient query evaluation on probabilistic databases. In: Greco, S., Lukasiewicz, T. (eds.) SUM 2008. LNCS (LNAI), vol. 5291, pp. 326–340. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

17. Olteanu, D., Huang, J., Koch, C.: Approximate confidence computation in probabilistic databases. In: ICDE, pp. 145–156 (2010)

    Google Scholar 

18. Roy, S., Perduca, V., Tannen, V.: Faster query answering in probabilistic databases using read-once functions. In: ICDT, pp. 232–243 (2011)

    Google Scholar 

19. Sen, P., Deshpande, A., Getoor, L.: Read-once functions and query evaluation in probabilistic databases. PVLDB 3(1), 1068–1079 (2010)

    Google Scholar 

20. Tarjan, R.E., Yannakakis, M.: Addendum: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput. 14(1), 254–255 (1985)

    Article  MathSciNet  MATH  Google Scholar 

Download references