Query Evaluation on a Database Given by a Random Graph

1. Abiteboul, S., Duschka, O.M.: Complexity of answering queries using materialized views. In: PODS, pp. 254–263 (1998)

   Google Scholar 

2. Babcock, B., Chaudhuri, S.: Towards a robust query optimizer: a principled and practical approach. In: SIGMOD, pp. 119–130 (2005)

   Google Scholar 

3. Bacchus, F., Grove, A.J., Halpern, J.Y., Koller, D.: From statistical knowledge bases to degrees of belief. Artificial Intelligence 87(1-2), 75–143 (1996)

   Article  MathSciNet  Google Scholar 

4. Chandra, A.K., Merlin, P.M.: Optimal implementation of conjunctive queries in relational data bases. In: STOC, pp. 77–90 (1977)

   Google Scholar 

5. Dalvi, N., Milkau, G., Suciu, D.: Asymptotic conditional probabilities for conjunctive queries. In: Eiter, T., Libkin, L. (eds.) ICDT 2005. LNCS, vol. 3363, Springer, Heidelberg (2004)

   Chapter  Google Scholar 

6. Dalvi, N., Suciu, D.: Query answering using probabilistic views. In: VLDB, pp. 805–816 (2005)

   Google Scholar 

7. Dalvi, N., Suciu, D.: Query evaluation on a database given by a random graph (April 2006)

   Google Scholar 

8. Evfimievski, A., Gehrke, J., Srikant, R.: Limiting privacy breaches in privacy preserving data mining. In: PODS, pp. 211–222 (2003)

   Google Scholar 

9. Fagin, R.: Probabilities on finite models. Journal of Symbolic Logic 41(1), 50–58 (1976)

   Article  MATH  MathSciNet  Google Scholar 

10. Getoor, L., Taskar, B., Koller, D.: Selectivity estimation using probabilistic models. In: SIGMOD, pp. 461–472 (2001)

    Google Scholar 

11. Glebskiĭ, Y.V., Kogan, D.I., Liogon’kiĭ, M.I., Talanov, V.A.: Range and degree of realizability of formulas in the restricted predicate calculus. Kibernetika, 2, 17–28, (1969); [Engl. Transl. Cybernetics, vol. 5, 142–154 (1972)]

    Google Scholar 

12. Halevy, A.Y.: Answering queries using views: A survey. The VLDB Journal 10(4), 270–294 (2001)

    Article  MATH  Google Scholar 

13. Hemaspaandra, L.A., Vollmer, H.: The satanic notations: Counting classes beyond #p and other definitional adventures. Technical report, Rochester, NY, USA (1994)

    Google Scholar 

14. Kifer, D., Gehrke, J.E.: Injecting utility into anonymized datasets. In: SIGMOD (2006)

    Google Scholar 

15. Lenzerini, M.: Data integration: a theoretical perspective. In: PODS, pp. 233–246 (2002)

    Google Scholar 

16. Liogon’kiĭ, M.I.: On the conditional satisfyability ratio of logical formulas. Mathematical Notes of the Academy of the USSR 6, 856–861 (1969)

    Article  MathSciNet  Google Scholar 

17. Lynch, J.F.: Probabilities of sentences about very sparse random graphs. Random struct. algorithms 3(1), 33–54 (1992)

    Article  MATH  MathSciNet  Google Scholar 

18. Lynch, J.F.: Infinitary logics and very sparse random graphs. In: Logic in Computer Science, pp. 191–198 (1993)

    Google Scholar 

19. Machanavajjhala, A., Gehrke, J., Kifer, D., Venkitasubramaniam, M.: l-diversity: Privacy beyond k-anonymity. In: ICDE, p. 24 (2006)

    Google Scholar 

20. Miklau, G., Suciu, D.: A formal analysis of information disclosure in data exchange. In: SIGMOD (2004)

    Google Scholar 

21. Spencer, J., Shelah, S.: Zero-one laws for sparse random graphs. J. Amer. Math. Soc, 97–115 (1988)

    Google Scholar 

22. Valiant, L.: The complexity of computing the permanent. Theoretical Computer Science 8, 189–201 (1979)

    Article  MATH  MathSciNet  Google Scholar 

23. Vardi, M.Y.: The complexity of relational query languages. In: STOC, pp. 137–146 (1982)

    Google Scholar 

24. Wagner, K.W.: More complicated questions about maxima and minima, and some closures of NP. Theor. Comput. Sci. 51(1-2), 53–80 (1987)

    Article  MATH  Google Scholar 

Download references