We study the asymptotic probabilities of conjunctive queries on random graphs. We consider a probabilistic model where the expected graph size remains constant independent of the number of vertices. While it has been known that a convergence law holds for conjunctive queries under this model, we focus on the calculation of conditional probabilities. This has direct applications to database problems like query-view security, i.e. evaluating the probability of a sensitive query given the knowledge of a set of published views. We prove that a convergence law holds for conditional probabilities of conjunctive queries and we give a procedure for calculating the conditional probabilities.
展开▼
