Kybernetika 50 no. 3, 322-362, 2014

Equivalence of compositional expressions and independence relations in compositional models

Francesco M. MalvestutoDOI: 10.14736/kyb-2014-3-0322


We generalize Jiroušek's (\emph {right}) \emph {composition operator} in such a way that it can be applied to distribution functions with values in a "semifield", and introduce (parenthesized) \emph {compositional expressions}, which in some sense generalize Jiroušek's "generating sequences" of compositional models. We say that two compositional expressions are \emph {equivalent} if their evaluations always produce the same results whenever they are defined. Our first result is that a set system $\cal H$ is star-like with centre $X$ \emph {if and only if} every two compositional expressions with "base scheme" $\cal H$ and "key" $X$ are equivalent. This result is stronger than Jiroušek's result which states that, if $\cal H$ is star-like with centre $X$, then every two generating sequences with base scheme $\cal H$ and key $X$ are equivalent. Then, we focus on \emph {canonical expressions}, by which we mean compositional expressions $\theta$ such that the sequence of the sets featured in $\theta$ and arranged in order of appearance enjoys the "running intersection property". Since every compositional expression, whose base scheme is a star-like set system with centre $X$ and whose key is $X$, is a canonical expression, we investigate the equivalence between two canonical expressions with the same base scheme and the same key. We state a graphical characterization of those set systems $\cal H$ such that every two canonical expressions with base scheme $\cal H$ and key $X$ are equivalent, and also provide a graphical algorithm for their recognition. Finally, we discuss the problem of detecting conditional independences that hold in a compositional model.


compositional expression, compositional model, running intersection property, perfect sequence


05C65, 05C85, 1699, 65C50, 60E99, 68T37


  1. C. Beeri, R. Fagin, D. Maier and M. Yannakakis: On the desirability of acyclic database schemes. J. Assoc. Comput. Mach. 30 (1983), 479-513.   CrossRef
  2. J. R. S. Blair and B.W. Peyton: An Introduction to Chordal Graphs and Clique Trees. Technical Report ORNL/TM-12203, 1992.   CrossRef
  3. I. Csiszár: $I$-divergence geometry of probability distributions and minimization problems. Ann. Probab. 3 (1975), 146-158.   CrossRef
  4. A. P. Dawid: Applications of a general propagation algorithm for probabilistic expert systems. Statist. Comput. 2 (1992), 25-36.   CrossRef
  5. W. E. Deming and F. F. Stephan: On least squares adjustment of a sampled frequency table when the expected marginal totals are known. Ann. Math. Stat. 11 (1940), 427-444.   CrossRef
  6. H. Hara and A. Takemura: Boundary cliques, clique trees and perfect sequences of maximaal cliques of a chordal graph. arXiv:cs/0607055v1 [cs.DM], 11 July 2006, pp. 1-24.   CrossRef
  7. R. Jiroušek: Composition of probability measures on finite spaces. In: Proc. XIII International Conf. on Uncertainty in Artificial Intelligence (D. Geiger and P. P. Shenoy, eds.), Morgan Kaufmann, San Francisco 1997, pp. 274-281.   CrossRef
  8. R. Jiroušek: Decomposition of multidimensional distributions represented by perfect sequences. Ann. Math. Artif. Intelligence 5 (2002), 215-226.   CrossRef
  9. R. Jiroušek: Detection of independence relations from persegrams. In: Proc. VI International Conf. on Information Processing and Management of Uncertainty in Knowledge-Based Systems, Annecy 2002, Vol. C, pp. 1261-1267.   CrossRef
  10. R. Jiroušek: Persegrams of compositional models revisited: conditional independence. In: Proc. XII International Conf. on Information Processing and Management of Uncertainty in Knowledge-Based Systems (L. Magdalena, M. Ojeda-Aciego and J. L. Verdegay, eds.), Malaga 2008, pp. 915-922.   CrossRef
  11. R. Jiroušek: Foundations of compositional model theory. Internat. J. General Systems 40 (2011), 623-678.   CrossRef
  12. R. Jiroušek: Local computations in Dempster-Shafer theory of evidence. Internat. J. Approx. Reason. {\mi 53} (2012), 1155-1167.   CrossRef
  13. R. Jiroušek and P. P. Shenoy: Compositional models in valuation-based systems. Internat. J. Approx. Reason. 55 (2014), 277-293.   CrossRef
  14. R. Jiroušek and J. Vejnarová: General framework for multidimensional models. Internat. J. Approx. Reas. 18 (2003), 107-127.   CrossRef
  15. R. Jiroušek, J. Vejnarová. and M. Daniels: Composition models of belief functions. In: Proc. V Symp. on Imprecise Probabilities and Their Applications (G. De Cooman, J. Vejnarová, and M. Zaffalon, eds.), Action M Agency, Prague 2007, pp. 243-252.   CrossRef
  16. V. Kratochvíl: Characteristic properties of equivalent structures in compositional models. Internat. J. Approx. Reason. 52 (2011), 599-612.   CrossRef
  17. V. Kratochvíl: Probabilistic compositional models: solution of an equivalence problem. Internat. J. Approx. Reason. 54 (2013), 590-601.   CrossRef
  18. S. L. Lauritzen: Graphical Models. Oxford University Press, Oxford 1996.   CrossRef
  19. H.-J. Lenz and B. Talheim: A formal framework of aggregation for the OLAP-OLTP model. J. of Universal Computer Science 15 (2009), 273-303.   CrossRef
  20. F. M. Malvestuto: Tree and local computations in a cross-entropy minimization problem with marginal constraints. Kybernetika 46 (2010), 621-654.   CrossRef
  21. F. M. Malvestuto: The sum-product algorithm: algebraic independence and computational aspects. Kybernetika 49 (2013), 4-22.   CrossRef
  22. F. M. Malvestuto: A join-like operator to combine data cubes, and answer queries from multiple data cubes. Unpublished manuscript, 2013.   CrossRef
  23. F. M. Malvestuto and E. Pourabbas: Local computation of answers to table queries on summary databases. In: Proc. XVII International Conference on Scientific and Statistical Database Management, Santa Barbara 2005, pp. 263-270.   CrossRef
  24. F. Mosteller: On pooling data. J. Amer. Statist. Assoc. 43 (1948), 231-242.   CrossRef
  25. J. Pearl: Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann Pub., San Mateo 1988.   CrossRef
  26. E. Pourabbas and A. Shoshani: Efficient estimation of joint queries from multiple OLAP databases. ACM Trans. Database Systems 32 (2007), 1, Article No. 2.   CrossRef
  27. E. Pourabbas and A. Shoshani: Improving estimation accuracy of aggregate queries on data cubes. Data and Knowledge Engrg. 69 (2010), 50-72.   CrossRef
  28. P. P. Shenoy and G. Shafer: Axioms for probability and belief-function propagation. In: Uncertainty in Artificial Intelligence (R. D. Shachter, T. Levitt, J. F. Lemmer, and L. N. Kanel, eds.), North-Holland 1990, Vol. 4.   CrossRef
  29. R. E. Tarjan and M. Yannakakis: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput. 13 (1984), 566-579.   CrossRef
  30. V. Verma, F. Gagliardi and C. Ferretti: On Pooling Data and Measures. Working Paper No. 84 University of Siena, 2009.   CrossRef
  31. J. Vomlel: Integrating inconsistent data in a probabilistic model. J. Appl. Non-Classical Logics {\mi 49} (2003), 4-22.   CrossRef