Uniform probabilistic generation of relation instances satisfying a functional dependency
作者：
Highlights：
• Schema normalization affects the complexity of uniform random instance generation.
• Naive approaches fail to achieve uniform distribution for non-normalized schemas.
• Duplicate-freeness and dependency satisfaction might strongly interfere.
• Achieving uniformity has to observe number-theoretic issues like integer partitions.
• Cases of exponential runtimes require substantial optimization and approximation.
摘要
•Schema normalization affects the complexity of uniform random instance generation.•Naive approaches fail to achieve uniform distribution for non-normalized schemas.•Duplicate-freeness and dependency satisfaction might strongly interfere.•Achieving uniformity has to observe number-theoretic issues like integer partitions.•Cases of exponential runtimes require substantial optimization and approximation.
论文关键词：Boyce–Codd normal form,Combinatorial analysis,Domain cardinality,Duplicate-freeness,Functional dependency,Probabilistic instance generation
论文评审过程：Received 15 December 2020, Revised 15 April 2021, Accepted 19 May 2021, Available online 6 July 2021, Version of Record 12 July 2021.
论文官网地址：https://doi.org/10.1016/j.is.2021.101848
