Representation of functional dependencies in relational databases using linear graphs

Functional dependencies in relational databases are investigated. Eight binary relations, viz., (1) dependency relation, (2) equipotence relation, (3) dissidence relation, (4) completion relation, and dual relations of each of them are described. Any one of these eight relations can be used to represent the functional dependencies in a database. Results from linear graph theory are found helpful in obtaining these representations. The dependency relation directly gives the functional dependencies. The equipotence relation specifies the dependencies in terms of attribute sets which functionally determine each other. The dissidence relation specifies the dependencies in terms of saturated sets in a very indirect way. Completion relation represents the functional dependencies as a function, the range of which turns out to be a lattice. Depletion relation which is the dual of the completion relation can also represent functional dependencies and similarly can the duals of dependency, equipotence, and dissidence relations. The class of depleted sets, which is the dual of saturated sets, is defined and used in the study of depletion relations.

An (O)over-tilde(mn) Gomory-Hu Tree Construction Algorithm for Unweighted Graphs

We present a fast algorithm for computing a Gomory-Hu tree or cut tree for an unweighted undirected graph G = (V, E). The expected running time of our algorithm is (O) over tilde (mc) where vertical bar E vertical bar = m and c is the maximum u-v edge connectivity, where u, v is an element of V. When the input graph is also simple (i.e., it has no parallel edges), then the u-v edge connectivity for each pair of vertices u and v is at most n - 1; so the expected run-ning time of our algorithm for simple unweighted graphs is (O) over tilde (mn). All the algorithms currently known for constructing a Gomory-Hu tree [8, 9] use n - 1 minimum s-t cut (i.e., max flow) subroutines. This in conjunction with the current fastest (O) over tilde (n(20/9)) max flow algorithm due to Karger and Levine[11] yields the current best running time of (O) over tilde (n(20/9)n) for Gomory-Hu tree construction on simple unweighted graphs with m edges and n vertices. Thus we present the first (O) over tilde (mn) algorithm for constructing a Gomory-Hu tree for simple unweighted graphs. We do not use a max flow subroutine here; we present an efficient tree packing algorithm for computing Steiner edge connectivity and use this algorithm as our main subroutine. The advantage in using a tree packing algorithm for constructing a Gomory-Hu tree is that the work done in computing a minimum Steiner cut for a Steiner set S subset of V can be reused for computing a minimum Steiner cut for certain Steiner sets S' subset of S.

On the Arrangement of Cliques in Chordal Graphs with respect to the Cuts

A cut (A, B) (where B = V - A) in a graph G = (V, E) is called internal if and only if there exists a vertex x in A that is not adjacent to any vertex in B and there exists a vertex y is an element of B such that it is not adjacent to any vertex in A. In this paper, we present a theorem regarding the arrangement of cliques in a chordal graph with respect to its internal cuts. Our main result is that given any internal cut (A, B) in a chordal graph G, there exists a clique with kappa(G) + vertices (where kappa(G) is the vertex connectivity of G) such that it is (approximately) bisected by the cut (A, B). In fact we give a stronger result: For any internal cut (A, B) of a chordal graph, and for each i, 0 <= i <= kappa(G) + 1 such that vertical bar K-i vertical bar = kappa(G) + 1, vertical bar A boolean AND K-i vertical bar = i and vertical bar B boolean AND K-i vertical bar = kappa(G) + 1 - i. An immediate corollary of the above result is that the number of edges in any internal cut (of a chordal graph) should be Omega(k(2)), where kappa(G) = k. Prompted by this observation, we investigate the size of internal cuts in terms of the vertex connectivity of the chordal graphs. As a corollary, we show that in chordal graphs, if the edge connectivity is strictly less than the minimum degree, then the size of the mincut is at least kappa(G)(kappa(G)+1)/2 where kappa(G) denotes the vertex connectivity. In contrast, in a general graph the size of the mincut can be equal to kappa(G). This result is tight.

Behaviour of methylmethacrylate-acrylonitrile random copolymers in dilute solution

Studies on the dilute solution properties of methylmethacrylate-acrylonitrile random copolymers of three different compositions, 0.236, 0.5 and 0.74 mole fraction (m.f.) of acrylonitrile (AN) designated as MAa, MAb and MAc, respectively, have been made in good solvents and theta solvents. MAa has been studied in benzene (Bz) and ethylacetate (EAc). MAb in acetonitrile (MeCN), dimethyl sulphoxide (DMSO) and a binary solvent mixture of Bz and dimentyl formamide (DMF) in the volume ratio 6.5:1 designated as BM1 and MAc in MeCN, DMSO and Bz + DMF in the volume ratio 1.667:1 designated as BM2. The Mark-Houwink exponent ‘a’ reveals that Bz is a theta solvent for MAa at 20°C. For MAb and MAc, BM1 and BM2, respectively have ‘a’ values of 0.5 at all three temperatures studied (30°, 40° and 50°C). It is not clear whether they represent theta states or preferential adsorption plays a role complicating the behaviour in solution. The values of A2 are very low in MeCN considering that it is a very good solvent for the copolymer, ‘a’ values for MAb and MAc being 0.75 and 0.7, respectively.

Nonstationary Random Critical Seismic Excitations

A method is presented to find nonstationary random seismic excitations with a constraint on mean square value such that the response variance of a given linear system is maximized. It is also possible to incorporate the dominant input frequency into the analysis. The excitation is taken to be the product of a deterministic enveloping function and a zero mean Gaussian stationary random process. The power spectral density function of this process is determined such that the response variance is maximized. Numerical results are presented for a single-degree system and an earth embankment modeled as shear beam.

A necessary and sufficient condition for acyclic graphs

This letter gives a new necessary and sufficient condition to determine whether a directed graph is acyclic.

Distribution of the angle of rotation plane random walks

We study the probability distribution of the angle by which the tangent to the trajectory rotates in the course of a plane random walk. It is shown that the determination of this distribution function can be reduced to an integral equation, which can be rigorously transformed into a differential equation of Hill's type. We derive the asymptotic distribution for very long walks.

Improvement On Brooks Chromatic Bound For A Class Of Graphs

Brooks' Theorem says that if for a graph G,Δ(G)=n, then G is n-colourable, unless (1) n=2 and G has an odd cycle as a component, or (2) n>2 and Kn+1 is a component of G. In this paper we prove that if a graph G has none of some three graphs (K1,3;K5−e and H) as an induced subgraph and if Δ(G)greater-or-equal, slanted6 and d(G)<Δ(G), then χ(G)<Δ(G). Also we give examples to show that the hypothesis Δ(G)greater-or-equal, slanted6 can not be non-trivially relaxed and the graph K5−e can not be removed from the hypothesis. Moreover, for a graph G with none of K1,3;K5−e and H as an induced subgraph, we verify Borodin and Kostochka's conjecture that if for a graph G,Δ(G)greater-or-equal, slanted9 and d(G)<Δ(G), then χ(G)<Δ(G).

Approximation algorithm for maximum independent set in planar traingle-free graphs

The maximum independent set problem is NP-complete even when restricted to planar graphs, cubic planar graphs or triangle free graphs. The problem of finding an absolute approximation still remains NP-complete. Various polynomial time approximation algorithms, that guarantee a fixed worst case ratio between the independent set size obtained to the maximum independent set size, in planar graphs have been proposed. We present in this paper a simple and efficient, O(|V|) algorithm that guarantees a ratio 1/2, for planar triangle free graphs. The algorithm differs completely from other approaches, in that, it collects groups of independent vertices at a time. Certain bounds we obtain in this paper relate to some interesting questions in the theory of extremal graphs.

Algorithms for Constructing Hierarchical Graphs

An algorithm is described for developing a hierarchy among a set of elements having certain precedence relations. This algorithm, which is based on tracing a path through the graph, is easily implemented by a computer.

A note on the effective medium theory of random resistive-reactive medium

The effective medium theory for a system with randomly distributed point conductivity and polarisability is reformulated, with attention to cross-terms involving the two disorder parameters. The treatment reveals a certain inconsistency of the conventional theory owing to the neglect of the Maxwell-Wagner effect. The results are significant for the critical resistivity and dielectric anomalies of a binary liquid mixture at the phase separation point.

Dilute Solution Properties of Methyl Methacrylate/Acrylonitrile Random Copolymers, 2a)

The Stockmayer-Fixman relation was used to evaluate the short range and long range interaction parameters for methyl methacrylate/acrylonitrile copolymers of 0,566 and 0,657 mole fraction of monomeric units of acrylonitrile in the solvents acetonitrile, 2-butanone, dimethyl formamide, and y-butyrolactone, at different temperatures (30, 45, and 60 “C). The values of KO were found to be lower than those of the parent homopolymers, and their values depend on both solvent and temperature. Even negative Ko-values were obtained, in cases in which the Mark Houwink exponent a is nearly unity. The values of the polymer-solvent interaction parameter, x, , are high and close to 0,5, indicating that these solvents are not good. The values of the excess interaction parameter, xAB, are negative and are not affected by temperature. The large extension of these copolymer chains, as exhibited by a and a;-values, can be understood in terms of unusual short range interactions only. Similar results were obtained for some cellulose derivatives.

Algorithms for Constructing Hierarchical Graphs

An algorithm is described for developing a hierarchy among a set of elements having certain precedence relations. This algorithm, which is based on tracing a path through the graph, is easily implemented by a computer.

Multi-state-choice automata model for expedient learning in random environment

A new automata model Mr,k, with a conceptually significant innovation in the form of multi-state alternatives at each instance, is proposed in this study. Computer simulations of the Mr,k, model in the context of feature selection in an unsupervised environment has demonstrated the superiority of the model over similar models without this multi-state-choice innovation.