×

Lattices of structure models and database schemes. (English) Zbl 0756.06003

Summary: This paper deals with basic properties of lattices of structure models. The form of models considered here is used in at least three areas: reconstructability analysis, analysis of contingency tables, and relational and probabilistic database design. The fact that the set of all models is structured as a lattice has been part of the basic formulation of problems in reconstructability analysis, while in the other two areas this aspect, while not necessarily less important, has represented a less major line of development. Various classes of models are considered here. The paper characterizes and explores lattice properties of these classes of models, and develops means to make structural comparisons among them, including definition of a structural distance with which the lattice of models is a metric lattice. The paper includes a proof of the modularity of the lattices and of a formula for determining their height, as well as a number of algorithms for determining the structural distance. The paper gives a detailed consideration of a strategy for partition search of the lattice of models and defines a recursive Boolean lattice as a data structure that extends the partition search strategy by recursive partitioning.

MSC:

06C05 Modular lattices, Desarguesian lattices
68P15 Database theory
93A10 General systems
68P05 Data structures
05C65 Hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ashby W. R., General Systems Yearbook 9 pp 99– (1964)
[2] Birkhoff G., Lattice Theory (1967)
[3] DOI: 10.1080/03081077908960903 · Zbl 0458.93003 · doi:10.1080/03081077908960903
[4] DOI: 10.1080/03081078108934805 · Zbl 0464.93009 · doi:10.1080/03081078108934805
[5] Cavallo R. E., In Proceedings of the 13th International Conference on Very Large Databases pp 71– (1987)
[6] Dcdekind R., Math. Annalen 53 pp 371– · JFM 31.0211.01 · doi:10.1007/BF01448979
[7] DOI: 10.1145/2402.322390 · Zbl 0624.68088 · doi:10.1145/2402.322390
[8] Higashi M., A Systems Modelling Methodology Probabilistic and Possibilistic Approaches. (1984)
[9] Klir G. J., Architecture of Systems Problem Solving (1985) · Zbl 0648.68105
[10] DOI: 10.1080/03081077908547453 · Zbl 0422.93004 · doi:10.1080/03081077908547453
[11] DOI: 10.1002/sres.3850020206 · Zbl 0564.93001 · doi:10.1002/sres.3850020206
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.