Query evaluation on a database given by a random graph

DOI10.1007/S00224-008-9148-4MaRDI QIDQ2272222zbMATH OpenOpenAlexFDO

Authors Nilesh N. Dalvi

Publication date 6 August 2009

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-008-9148-4

zbMATH Keywords

asymptotic probabilitiesconjunctive queriesrandom graphs

Mathematics Subject Classification ID

Database theory (68P15)

Recommendations

• Database Theory - ICDT 2005
• scientific article; zbMATH DE number 3876623
• Random Databases with Correlated Data
• Probabilities of Sentences about Very Sparse Random Graphs
• Mathematical Foundations of Computer Science 2005

Cites work

• A formal analysis of information disclosure in data exchange
• Answering queries using views: A survey
• Correlation inequalities on some partially ordered sets
• Database Theory - ICDT 2005
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3769673 (Why is no real title available?)
• More complicated questions about maxima and minima, and some closures of NP
• On the conditional degree of satisfiability of logical formulas
• Probabilities of Sentences about Very Sparse Random Graphs
• Probabilities on finite models
• The complexity of computing the permanent
• Zero-One Laws for Sparse Random Graphs

Cited in

(1)

• Database Theory - ICDT 2005

This page was built for publication: Query evaluation on a database given by a random graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2272222)