Probabilistic Inference with Algebraic Constraints: Theoretical Limits and Practical Approximations