{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T18:39:52Z","timestamp":1725475192454},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540692690"},{"type":"electronic","value":"9783540692706"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11965893_11","type":"book-chapter","created":{"date-parts":[[2006,12,7]],"date-time":"2006-12-07T07:52:22Z","timestamp":1165477942000},"page":"149-163","source":"Crossref","is-referenced-by-count":2,"title":["Query Evaluation on a Database Given by a Random Graph"],"prefix":"10.1007","author":[{"given":"Nilesh","family":"Dalvi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"11_CR1","doi-asserted-by":"crossref","unstructured":"Abiteboul, S., Duschka, O.M.: Complexity of answering queries using materialized views. In: PODS, pp. 254\u2013263 (1998)","DOI":"10.1145\/275487.275516"},{"key":"11_CR2","doi-asserted-by":"crossref","unstructured":"Babcock, B., Chaudhuri, S.: Towards a robust query optimizer: a principled and practical approach. In: SIGMOD, pp. 119\u2013130 (2005)","DOI":"10.1145\/1066157.1066172"},{"issue":"1-2","key":"11_CR3","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/S0004-3702(96)00003-3","volume":"87","author":"F. Bacchus","year":"1996","unstructured":"Bacchus, F., Grove, A.J., Halpern, J.Y., Koller, D.: From statistical knowledge bases to degrees of belief. Artificial Intelligence\u00a087(1-2), 75\u2013143 (1996)","journal-title":"Artificial Intelligence"},{"key":"11_CR4","doi-asserted-by":"crossref","unstructured":"Chandra, A.K., Merlin, P.M.: Optimal implementation of conjunctive queries in relational data bases. In: STOC, pp. 77\u201390 (1977)","DOI":"10.1145\/800105.803397"},{"key":"11_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30570-5_20","volume-title":"Database Theory - ICDT 2005","author":"N. Dalvi","year":"2004","unstructured":"Dalvi, N., Milkau, G., Suciu, D.: Asymptotic conditional probabilities for conjunctive queries. In: Eiter, T., Libkin, L. (eds.) ICDT 2005. LNCS, vol.\u00a03363, Springer, Heidelberg (2004)"},{"key":"11_CR6","unstructured":"Dalvi, N., Suciu, D.: Query answering using probabilistic views. In: VLDB, pp. 805\u2013816 (2005)"},{"key":"11_CR7","doi-asserted-by":"crossref","unstructured":"Dalvi, N., Suciu, D.: Query evaluation on a database given by a random graph (April 2006)","DOI":"10.1007\/11965893_11"},{"key":"11_CR8","doi-asserted-by":"crossref","unstructured":"Evfimievski, A., Gehrke, J., Srikant, R.: Limiting privacy breaches in privacy preserving data mining. In: PODS, pp. 211\u2013222 (2003)","DOI":"10.1145\/773153.773174"},{"issue":"1","key":"11_CR9","doi-asserted-by":"publisher","first-page":"50","DOI":"10.2307\/2272945","volume":"41","author":"R. Fagin","year":"1976","unstructured":"Fagin, R.: Probabilities on finite models. Journal of Symbolic Logic\u00a041(1), 50\u201358 (1976)","journal-title":"Journal of Symbolic Logic"},{"key":"11_CR10","doi-asserted-by":"crossref","unstructured":"Getoor, L., Taskar, B., Koller, D.: Selectivity estimation using probabilistic models. In: SIGMOD, pp. 461\u2013472 (2001)","DOI":"10.1145\/375663.375727"},{"key":"11_CR11","unstructured":"Glebski\u012d, Y.V., Kogan, D.I., Liogon\u2019ki\u012d, M.I., Talanov, V.A.: Range and degree of realizability of formulas in the restricted predicate calculus. Kibernetika, 2, 17\u201328, (1969); [Engl. Transl. Cybernetics, vol. 5, 142\u2013154 (1972)]"},{"issue":"4","key":"11_CR12","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1007\/s007780100054","volume":"10","author":"A.Y. Halevy","year":"2001","unstructured":"Halevy, A.Y.: Answering queries using views: A survey. The VLDB Journal\u00a010(4), 270\u2013294 (2001)","journal-title":"The VLDB Journal"},{"key":"11_CR13","doi-asserted-by":"crossref","unstructured":"Hemaspaandra, L.A., Vollmer, H.: The satanic notations: Counting classes beyond #p and other definitional adventures. Technical report, Rochester, NY, USA (1994)","DOI":"10.1145\/203610.203611"},{"key":"11_CR14","doi-asserted-by":"crossref","unstructured":"Kifer, D., Gehrke, J.E.: Injecting utility into anonymized datasets. In: SIGMOD (2006)","DOI":"10.1145\/1142473.1142499"},{"key":"11_CR15","doi-asserted-by":"crossref","unstructured":"Lenzerini, M.: Data integration: a theoretical perspective. In: PODS, pp. 233\u2013246 (2002)","DOI":"10.1145\/543613.543644"},{"key":"11_CR16","doi-asserted-by":"publisher","first-page":"856","DOI":"10.1007\/BF01146404","volume":"6","author":"M.I. Liogon\u2019kii","year":"1969","unstructured":"Liogon\u2019ki\u012d, M.I.: On the conditional satisfyability ratio of logical formulas. Mathematical Notes of the Academy of the USSR\u00a06, 856\u2013861 (1969)","journal-title":"Mathematical Notes of the Academy of the USSR"},{"issue":"1","key":"11_CR17","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1002\/rsa.3240030105","volume":"3","author":"J.F. Lynch","year":"1992","unstructured":"Lynch, J.F.: Probabilities of sentences about very sparse random graphs. Random struct. algorithms\u00a03(1), 33\u201354 (1992)","journal-title":"Random struct. algorithms"},{"key":"11_CR18","doi-asserted-by":"crossref","unstructured":"Lynch, J.F.: Infinitary logics and very sparse random graphs. In: Logic in Computer Science, pp. 191\u2013198 (1993)","DOI":"10.1109\/LICS.1993.287588"},{"key":"11_CR19","doi-asserted-by":"crossref","unstructured":"Machanavajjhala, A., Gehrke, J., Kifer, D., Venkitasubramaniam, M.: l-diversity: Privacy beyond k-anonymity. In: ICDE, p. 24 (2006)","DOI":"10.1109\/ICDE.2006.1"},{"key":"11_CR20","doi-asserted-by":"crossref","unstructured":"Miklau, G., Suciu, D.: A formal analysis of information disclosure in data exchange. In: SIGMOD (2004)","DOI":"10.1145\/1007568.1007633"},{"key":"11_CR21","doi-asserted-by":"crossref","unstructured":"Spencer, J., Shelah, S.: Zero-one laws for sparse random graphs. J. Amer. Math. Soc, 97\u2013115 (1988)","DOI":"10.2307\/1990968"},{"key":"11_CR22","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L. Valiant","year":"1979","unstructured":"Valiant, L.: The complexity of computing the permanent. Theoretical Computer Science\u00a08, 189\u2013201 (1979)","journal-title":"Theoretical Computer Science"},{"key":"11_CR23","doi-asserted-by":"crossref","unstructured":"Vardi, M.Y.: The complexity of relational query languages. In: STOC, pp. 137\u2013146 (1982)","DOI":"10.1145\/800070.802186"},{"issue":"1-2","key":"11_CR24","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0304-3975(87)90049-1","volume":"51","author":"K.W. Wagner","year":"1987","unstructured":"Wagner, K.W.: More complicated questions about maxima and minima, and some closures of NP. Theor. Comput. Sci.\u00a051(1-2), 53\u201380 (1987)","journal-title":"Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Database Theory \u2013 ICDT 2007"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11965893_11.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:23:20Z","timestamp":1619508200000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11965893_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540692690","9783540692706"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/11965893_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}