Information dependencies.
This paper uses the tools of information theory to examine and reason about the information content of the attributes within a relation instance. For two sets of attributes X and Y, an information dependency measure (InD measure) characterizes the uncertainty remaining about the values for the set Y when the values for the set X are known. A variety of arithmetic inequalities (InD inequalities) are shown to hold among InD measures; InD inequalities hold in any relation instance. Numeric constraints (InD constraints) on InD measures, consistent with the InD inequalities, can be applied to relation instances. Remarkably, functional and multivalued dependencies correspond to setting certain constraints to zero, with Armstrong's axioms shown to be consequences of the arithmetic inequalities applied to constraints. As an analog of completeness, for any set of constraints consistent with the inequalities, we may construct a relation instance that approximates these constraints within any positive &egr;. InD measures suggest many valuable applications in areas such as data mining.
Introduction
That the well-developed discipline of information theory seemed to have so little to say about information
systems is a long-standing conundrum. Attempts to use information theory to "measure"
the information content of a relation are blocked by the inability to accurately characterize the
underlying domain. An answer to this mystery is that we have been looking in the wrong place.
The tools of information theory, dealing closely with representation issues, apply within a relation
instance and between the various attributes of that instance.
The traditional approach to information theory is based upon communication via a channel. In
each instance there is a fixed set of messages when one of these is transmitted
from the sender to the receiver (via the channel), the receiver gains a certain amount of information.
The less likely a message is to be sent, the more meaningful is its receipt. This is formalized by
assigning to each message v i a probability p i (subject to the natural constraint that
and defining the information content of v i to be log 1 / p i (all logarithms in this paper are base 2).
Another way of viewing this measure is that the amount of information in a message is related
to how "surprising" the message is-a weather report during the month of July contains little
information if the prediction is "hot," but a prediction of "snow" carries a lot of information.
The issue of surprise is also related to the recipient's ``state of knowledge.'' In the weather report
example, the astonishment of the report "snow" was directly related to the knowledge that it
was July; in January the information content of the two reports would be vastly different. Thus
the in- or inter-dependence of two sets of messages is highly significant. If two message sets are
independent ( in the intuitive and the statistical sense), receipt of a message from one set does
not alter the information content of the other (e.g. temperature and wind speed). If two message
sets are not independent, receipt of a message from the first set may greatly alter the likelihood
of receipt, and hence information content, of messages from the second set (e.g. temperature and
form of precipitation).
A central concept in information theory is the entropy H of a set of messages, the weighted
average of the message information:
Definition 1.1 Entropy. Given a set of messages with probabilities
g, the entropy of M is
Entropy is closely related to encoding of messages, in that encoding each v i using log 1 / p i bits
gives the minimal number of expected bits for transmitting messages of M .
Remark 1 Suppose for messages of M , no probability is 0 and
M contains a single message.
In a database context, information content is measured in terms of selection (specification of
a specific value) rather than transmission. This avoids the thorny problem which seems to say
that, since the database is stored on site and no transmission occurs, there is no information. In
particular, the model looks at an instance of a single relation and at values for some arbitrarily
selected tuple. For simplicity, we assume that the message source is ergodic-all tuples are equally
likely; a probability distribution could be applied to the tuples with less impact on the formalism
than on the intuition. Because of the assumption that all tuples are equally likely, the information
required to specify one particular tuple from a relation instance with n tuples is, of course, log n
and the minimal cost of encoding requires uniformly log n bits. We treat an attribute A as the
equivalent of a message source, where the message set is the active domain and each value v i has
probability c i/ n , when v i occurs c i times. Thus a single value carries log n bits only if it is drawn
from an attribute which has n distinct values, that is, when the attribute is a key. The class
standing code at a typical four-year college has approximately two bits of information (somewhat
less, to the extent that attrition has skewed enrollment) while gender at VMI has little information
(using the entropy measure, since the information content of the value "female" is high, but its
receipt is unlikely).
The major results of this paper use the common definition of information to characterize information
dependencies. This characterization has three steps. The first extends the use of entropy as a
measure of information to be an information dependency measure (Section 4). The second derives a
number of arithmetic inequalities which must always hold between particular measures in a relation
instance (Section 5). The third investigates the consequences of placing numeric constraints on some
or all measures of a relation instance. Most significantly, functional and multi-valued dependency
result from constraining certain particular measures (or their differences) to zero (Section 6).
For example, in a weather report database, month has entropy 3.58 and we might discover that
condition has entropy 1.9. But in a fixed month, condition has entropy approximately 1.6.
Thus knowing the value of month contributes approximately 0.3 bits of information to knowledge of
condition, with 1.6 bits of uncertainty. On the other hand, in a personnel database where EmpID
provides the entire information content of salary with 0 bits uncertain.
In addition, the measure/constraint formulation exhibits an analog of completeness in that, for
any set of numeric constraints consistent with the arithmetic inequalities and any positive ffl, there
is a relation instance that achieves those constraints within ffl (Section 7).
This characterization of information dependency has many important theoretic and practical im-
plications. It allows us to more carefully investigate notions of approximate functional dependency.
It can help with normalization. It opens up whole realms of data mining approaches.
Preliminaries
Here are the notations and conventions.
Relations All relation instances are non-empty and multi-sets. r, s denote instances 1 . Operators
oe do not filter for distinctiveness.
Attributes R is schema for instance r and X;Y; Z; V; W ' R. XY denotes X [ Y and A is
equivalent to fAg for A 2 R. X;Y; Z partition R.
Values v is equivalent to hvi when hvi 2 A (r). enumerates the
instances of distinct( X (r)), so 1  i  ', similarly for m and y j wrt Y , and n and z k wrt Z.
Probabilities
count(r) for S ' R. use of i is consistent
with above), similarly
Two central notions to entropy are conditional probability and statistical independence. Conditional
probability allows us to make a possibly more informed probability measure of a set of values
by narrowing the scope of overall possibilities. Independence establishes a bound on how informed
the conditional probability enables us to be.
Definition 2.1 Conditional Probability. The conditional probability of
in the instance oe X=x i
(r). In symbols,
Definition 2.2 Independence. X;Y are independent if P
In this paper, there are log function expressions of the form log(1=0). By convention (continuity
real number a ? 0.
Lemma 2.1 log x
Lemma 2.2 Let be a probability distribution and such that
log q i/ p i  q i/
Null values are not considered here.
3 The bounds on entropy
To ease notation, we write HX for H(X). From now on, we understand that H is always associated
with a non-empty instance r. When r is not clear from context, we write H r X . In the remainder of
this section, we establish upper and lower bounds on the entropy function.
Lemma 3.1 Upper and Lower Bounds on Entropy. 0  HX  log '.
consequently, HX  0. Suppose
By Lemma 2.2, log 1 / 'p
Intuitively, the entropy of a set X ' R equal to zero signifies that there exists no uncertainty or
information, whereas, equal to log ' signifies complete uncertainty or information. A consequence
of our notation allows us to find the joint entropy of sets X;Y ' R. The joint entropy of X;Y ,
written HXY , is
Lemma 3.2 Bounds on Joint Entropy. X;Y ' R,
with HX +H are independent.
PROOF First inequality:
When X and Y are independent, p thus, the inequality in the above deduction is
in fact equality.
Second inequality: Observe that
mg. Then for any j,
consequently, log 1 / p i;j  log 1 / q i and thus,
and symmetrically for H Y as well.
4 InD measures
An information dependency measure (InD measure) between X and Y , for X;Y ' R, attempts
to answer the question "How much do we not know about Y provided we know X?" Using the
notation of Section 2, if we know that then we are possibly more informed about
and therefore, can recalculate the entropy of Y as
log
Amortizing this over each of the ' different X values according to the respective probabilities
gives the entropy of Y dependent on X, resulting in the following definition of an information
dependency measure. Note that these are measures, not metrics.
r
a e
a f
a e
a f
c g
InD measures
H A

Figure

1: (left) An instance r. (right) InD measures of r. Observe that H
Definition 4.1 Information Dependency Measure. The information dependency measure (InD
measure) of Y given Xis HX!Y ,
We will now normally drop the word "entropy" when referring to these measures, but that this
value is not a declaration of dependency (as is the case with FDs) but a measure of dependency is
important to keep in mind. We now characterize an InD measure HX!Y in terms of InD measures
HX and HXY .
Lemma 4.1
HX!Y
Note that HX!Y is a measure of the information needed to represent Y given that X is known,
not the information that X contains about Y . This latter quantity of course is measured by
5 InD measure inequalities
The relationships among InD measures are characterized by inequalities and expressions involving
the various measures. Of these formulae, several are named according to the corresponding
functional dependency inference rules, which they characterize under special circumstances.
Lemma 5.1 Reflexivity.
X. Then by Lm 4.1
Lemma 5.2
d: 111 111

Figure

2: Encodings of A, B, B given A from Fig.1. The u contains the portion of the bit string that encodes
similarly for B. Where u
t overlap shows the portion of the encoding of B that is contained within the
encoding of A. The surprise after receiving A=a is witnessed by the fact that, although we know we will receive
the first bit of B=e or B=f, i.e. 0, we need an additional 1=4 bits for both the second bit of B=e and B=f.
Receipt of A=b,A=c, or A=d, on the other hand, poses no surprise since B=g is completely contained therein.
illustrate the situation: two InDs may interact little so they combine to sum their InDs, or they
may interact strongly, so their combination yields total dependencies. Putting restrictions on the
left- or right-hand sides constrains the interactions and hence tightens the InD relationships.
Lemma 5.3 Union (left). HX!Y +HX!Z  HX!Y Z with equality if p jji and p kji are independent

Lemma 5.4 HX!Y
Lemma 5.5 HXY!Z  HX!Z .
HXY!Z
HX!Z
Lemma 5.6 Union (right). min(HX!Z
HX!Z  HXY!Y Lm 5.5
Lemma 5.7 Augmentation (1). HXZ!YZ  HX!Y .
HX!Y Lm 5.5
Lemma 5.8 Transitivity. HX!Y +H Y !Z  HX!Z .
HX!XY +HXY!XZ Lm 5.7
Lemma 5.9 Union (full). HX!Y +HW!Z  HXW!YZ
HXW!YW +HWY!ZY Lm 5.7
HXW!YZ Lm 5.8
Lemma 5.10 Decomposition. if Z ' Y , then HX!Y  HX!Z .
HX!Y  HX!Z
Lemma 5.11 Psuedotransitivity. HX!Y +HWY!Z  HXW!Z .
HXW!YW +HWY!Z Lm 5.7
HXW!Z Lm 5.8
Lemma 5.12 For XY
HWX!Y Z .
PROOF By Lm 5.2 we may assume wlog V ' W ' Y [ Z. Let
Z +H XZ
Y
Z +H XZ
Y
Y
6 FDs, MVDs, and
Armstrong's axioms
6.1 Functional dependencies
Functional dependencies (FDs) are long-known and well-studied [8, 10]. For X;Y ' R, X functionally
determines Y , written value yields a single Y value.
PROOF Recasting this in terms of probabilities, given any x i 2 X, there is a single y
such that p i;j ? 0, and consequently p
a singleton; hence,
6.2 Armstrong's axioms
Armstrong's axioms [8] are important for functional dependency theory because they provide the
basis for a dependency inferencing system. There are commonly three rules given as the Armstrong
Axioms, which are merely specializations of the above inequalites.
1. Reflexivity If Y ' X then
2. Augmentation
3. Transitivity
Theorem 6.1 The Armstrong axioms can be derived directly from InD inequalities.
PROOF Reflexivity follows directly from Lm 5.1, augmentation from Lm 5.7, and transitivity from
Lm 5.8.
An additional three rules derived from the axioms are often cited as fundamental: union, psue-
dotransitivity, decomposition. These also follow from Lm 5.3, Lm 5.11, and Lm 5.10 respectively.
Interestingly, a critical distinction between Armstrong's axioms and InD inequalities is that in the
former, union can be derived from the original three axioms, whereas the latter union must be
derived from first principles.
6.2.1 Fixed arity dependencies
Lemma 6.1 for FDs is alternatively a statement about the number of distinct values any x i 2 X
determines (we work through an example to motivate this). In the case of FDs and
in a non-empty r. In practice, however, the
size is often not unity and FDs are ill-suited for this e.g., consider a fParent; Childg relation r.
Biologically count-distinct( Parent (oe Child=c child c 2 Child. InDs measures
can be used to model this dependency easily; H Child!Parent
6.3 Multivalued dependencies
In the following, X;Y;Z partition R. Multivalued dependencies (MVDs) arise naturally in database
design and are intimately related to the (natural) join operator . A multivalued dependency,
Intuitively, we see that the values of Y and Z are
not related to each other wrt an particular value of X.
Lemma 6.2 MVD count. Assume X i Y in r. Then for all x
PROOF By definition of MVDs.
Lemma 6.3 X i Y jZ holds iff HX!Y
6.2, the conditional probabilities of Y; Z wrt X must be independent, which
is the condition required in Lemma 5.3 for equality to hold.
(:By Lemma 5.3 for equality, the conditional probabilities of Y; Z wrt X are independent; hence,
by Lemma 6.2, X i Y .
Since acyclic join dependencies can be characterized by a set of MVDs, it is clear that InD
inequalities can characterize them as well, though the "work" is really done by the characterization
of the set of MVDs.
6.4 Additional InD inference rules
There are three standard rules of MVD inference:
1. Complementation If
2. Augmentation For
3. Transitivity If
Both complementation and augmentation trivially true under InD inequalies. The last rule, tran-
sitivity, is rather interesting. For its proof, we find an alternative characterization of MVDs.
Intuitively, the proof establishes that .
HX!Y +HX!Z= HX!Y Z Lm 6.3
HX!Y +HX!Z= HX!Y +HXY!ZLm 5.4
Interestingly, this is an alternative characterization of MVDs. In this case, Y does not contribute
any information about Z.
Lemma
Lemma 6.6 As a consequence of Lm 6.5,
Lemma 6.7 If Y iW jV X, then XY iW jV by Lm 5.12.
Lemma 6.8 Let
HX!R
HX!R
Lemma 6.9 Transitivity for MVDs.
HX!R
6.5 Rules involving both FDs and MVDs
There are a pair of rules that allow mixing of FDs and MVDs:
1. Conversion
2. Interaction
The rule for conversion is trivial. Interaction follows from Lm 6.4.
In Section 6.2, we stated a critical difference between Armstrong axioms and InD inequalities
was the distinction between what were axioms and derivable rules. Additionally, there appear to
be other fundamental differences between FDs and MVDs, and InD inequalities. For example,
consider the following problem. Let R be a schema and set of FDs
over R. Let I(R; F ) be the set of all relation instances over R that satisfy F . For X ' R, let
)g. The question is whether there exists a set G of FDs over X
such that \Pi X (I(R; F G). It is known that in general such a G does not exist. Further,
a similar negative result holds for MVDs. InD measures are a broader class than FDs and MVDs,
and the expectation is that a theorem holds: it does, trivially since all relation instances satisfy
any set of InD inequalities.
7 InD measure constraints
To summarize the previous sections, we have defined InD measures on an instance, values that
reflect how much information is additionally required about a second set of attributes given a
first set. We have proved a number of arithmetic equalities and inequalities between various InD
measures for a given schema; these (in)equalities must hold for any instance of that schema. And we
have shown that constraining certain InD measures, or simple expressions involving InD measures,
to 0 imposes functional or multivalued dependences on the instances. We now generalize this last
step by considering arbitrary numeric constraints upon InD measures, e.g., HX!Y  4=9. A
relation instance r over R ' fX; Y g is a solution to this constraint if H r
X!Y  4=9 by standard
arithmetic. Formally,
Definition 7.1 An InD constraint system over schema R is an m \Theta n linear system
a
a
The constraint system is characterized by
will be written as AHX  b, where Transpose . Observe that Definition 7.1 is
sufficient to describe any InD measure or inequality. InD constraint systems can be as simple as
requiring a single FD or as extensive as specifying the entropies of all subsets of R. However, not
every A, b, and X make sense as applied to a relation instance. Either the A and b may admit
no solutions (e.g. or the solutions may violated the InD measure
constraints for X (e.g.
Definition 7.2 An InD constraint system A, b, X is feasible provided that the linear system A,
b plus all InD measure constraints inferable from X is solvable.
Observe that a solution to this extended system involves finding values for each HX
7.1 Instances for feasible constraint systems
The question naturally arises whether an instance always exists for a feasible constraint system.
The affirmative answer to this question, whose proof is sketched below, provides InD measures with
an analog to completeness.
Before venturing into the proof of the theorem itself, we prove a simple result merely for the
sake of providing intuition for what comes after. There are two things to be observed while reading
the following proof: first, the duality between instance counts and approximate probabilities, and,
second, the way interpolation occurs.
Lemma 7.1 Given a rational c  0, there exists a relation instance r over a single attribute A
such that jH r
1). By the intermediate value theorem, since f is a continuous
function on the interval [0; 1], and c is a value between f(0) and f(1), then there exists some
a 2 [0; 1] such that a) is the
probability distribution. From this distribution we can approximate r by constructing an instance
" r over fAg with distinct values that is sufficiently large such that if
count(oe A=i ("
While this proof is non-constructive, we can find a suitable x by, for example, binary search.
Theorem 7.1 Instance existence. For any feasible constraint system A, b, and X, and any ffl ? 0,
there is a relation instance r that satisfies A, b, and X within ffl.
1. Using the observation from Definition 7.2, solve A, b, and X for fixed values for
2. Pick m ? 1=ffl
3. Give every attribute a value with large probability, namely is the number
of attributes. Note that these highly probable attributes contribute a negligible amount to any
entropy since their probabilities are so close to 1.
4. The remaining probabilities for each attribute A i will be divided among b i equal size buckets.
Thus, HA i
log b i . Find b i such that ff
Remark 2 Wlog, the A i are ordered in decreasing entropy. Hence b i  b i+1 .
We will add attributes in order A 1 ; A
5. At stage construction has included A and we are adding A i+1 ; that is, we
already have
and want to construct
. We also have a single distribution q
corresponding to A i+1 . We actually construct two distributions p' and pu, for "p lower" and
"p upper".
(a) The upper case is simple: A i+1 is independent from A
\Theta
(b) The lower case is found by allocating the q j among the various p's. Because b i  b i+1 ,
there are more than enough i buckets to go around. With some small error, each non-zero
will correspond to a unique q 6= 0.
and by induction H p'
An
Interpolate between p ' and p u to match other entropies
This is conceptually similar to Lm 7.1, but relies upon the unusual structure of pu caused by
the almost-unity cases of p and q and another iteration.
8 Applications and extensions
We have presented a formal foundation incorporating information theory in relational databases.
There are many interesting and valuable applications and extensions of this work that we are
already pursuing.
8.1 Datamining
Datamining [3], the search for interesting patterns in large databases, motivated our initial work, our
interest in establishing what it means to be "interesting." A primary objective here is to certainly
find all the InD measures HX!Y  ffi given an instance r over R. The search in r takes place upon
the lattice of h2 R ; 'i, where HX!Y  ffi is checked for every X ( Y . The InD inequalities facilitate
this search.
Kivinen et. al. [4], considers finding approximate FDs. The central notion is that of violating
for an instance r over R and X;Y ' R, a pair of tuples s;
They define three normalized measures are based
upon the number of violating pairs, the number of violating tuples, and the number of violating
tuples removed to achieve a dependency, respectively. The authors state that problematically
the measures give very different values for some particular relations, and therefore, choosing
which measure is the best-if any are-is difficult. We feel that the InD measure can shed
some light upon the metrics. The connection between these measures and InD measures is illustrated
with three instances
r 1.52 .80 .16 .8 .4
s 1.37 .95 .36 .8 .4
This example shows that HX!Y can sometimes make finer distinctions than g i s. On the applications
side, Kivinen et. al have done substantial work related to approximate FDs as in [4]. The
paper is important not only for the notion of approximate dependency, but also a brief discussion
about how the errors can be cast into Armstrong Axiom-like inequalities.
8.2 Other Metrics
Rather than considering what information X lacks about Y , we may look at the information
contains about Y , that is "
its normalized form
I=H Y .
Some interesting results about I and "
I are max(IX!Y
I Y !X . While I makes the specification of FDs more natural
cannot be used to characterize MVDs. Another interesting measure that uses
additional notions from information theory is rate of the language
X =count(r) which is
the average number of bits required for each tuple projected on X. The absolute rate is s ab =
log(count(r)). The difference s ab \Gamma s indicates the redundancy. As X approaches R, the average
tuple entropy increases, reducing redundancy. This is pertinant especially to the following section.
8.3 Connections to relational algebra
Examining how InDs behave with relational operators. For example,
Lemma 8.1 Let R = fX; Y; Zg and r be an instance of R. if r
For instance, when employing a lossless decomposition, how will both the InD measures and rates
(from above) change to indicate the decomposition was indeed lossless.
9 Related work
There is a dearth of literature in this area, marrying information theory to information systems.
The closest work seems to be Piatesky-Shapiro in [2] who proposes a generalization of functional
dependencies, called probabilitistic dependency (pdep). The author begins with the
(using our notation). To relate two sets of attributes X;Y , pdep(X; Y
Observe that pdep approaches 1 as X comes closer to functionally determining Y . Since pdep is
itself inadequate, the author normalizes it using proportion in variation, resulting in the known
statistical measure (X; Y
Y is a better FD than Y ! X (and vice versa). The author describes the expectation
of both pdep effeciently sample for these values.
In the area of artificial intelligence, an algorithm developed to create decision trees, a means of
classification, by Quinlan, notably ID3 [5] and C4.5 [6] uses entropy to dictate how the building
should proceed. In this case of supervised learning, an attribute A is selected as the target, and
the remaining attributes R \Gamma fAg the classifier. The algorithm works by progressively selecting
attributes from the intial set R \Gamma fAg, measuring be classified properly.

Acknowledgements

The authors would like to thank Dennis Groth, Dirk Van Gucht, Chris Giannella, Richard Martin,
and C.M. Rood for their helpful suggestions.



--R

The Elements of Real Analysis Second Edition.
Probabilistic data dependencies.
From data mining to knowledge discovery: An overview.
Approximate inference of functional dependencies from relations.
Induction of decision trees.

Coding and Information Theory.
Foundations of Databases.
Elements of Information Theory.
Principles of Database and Knowledge-Base Systems Vol
--TR
Principles of database and knowledge-base systems, Vol. I
Coding and information theory
Elements of information theory
C4.5: programs for machine learning
Approximate inference of functional dependencies from relations
From data mining to knowledge discovery
Bottom-up computation of sparse and Iceberg CUBE
Foundations of Databases
Data Cube
Induction of Decision Trees
Recovering Information from Summary Data

--CTR
Chris Giannella , Edward Robertson, A note on approximation measures for multi-valued dependencies in relational databases, Information Processing Letters, v.85 n.3, p.153-158, 14 February
Ullas Nambiar , Subbarao Kambhampati, Mining approximate functional dependencies and concept similarities to answer imprecise queries, Proceedings of the 7th International Workshop on the Web and Databases: colocated with ACM SIGMOD/PODS 2004, June 17-18, 2004, Paris, France
Marcelo Arenas , Leonid Libkin, An information-theoretic approach to normal forms for relational and XML data, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.15-26, June 09-11, 2003, San Diego, California
Periklis Andritsos , Rene J. Miller , Panayiotis Tsaparas, Information-theoretic tools for mining database structure from large data sets, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
Luigi Palopoli , Domenico Sacc , Giorgio Terracina , Domenico Ursino, Uniform Techniques for Deriving Similarities of Objects and Subschemes in Heterogeneous Databases, IEEE Transactions on Knowledge and Data Engineering, v.15 n.2, p.271-294, February
Marcelo Arenas , Leonid Libkin, An information-theoretic approach to normal forms for relational and XML data, Journal of the ACM (JACM), v.52 n.2, p.246-283, March 2005
Solmaz Kolahi , Leonid Libkin, On redundancy vs dependency preservation in normalization: an information-theoretic study of 3NF, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA
Bassem Sayrafi , Dirk Van Gucht, Differential constraints, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland
Solmaz Kolahi , Leonid Libkin, XML design for relational storage, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada
Chris Giannella , Edward Robertson, On approximation measures for functional dependencies, Information Systems, v.29 n.6, p.483-507, September 2004
multivalued dependency;armstrong's axioms;functional dependency;entropy;information dependency