In the second part, we further investigate algebraic structure of relational databases. The decomposition theory for relational databases is based on data dependencies. Nevertheless, the set-theoretic representations of data dependencies in terms of the attributes of relation schemes are incompatible with partial ordering operations. This brings a gap between the database decomposition theory and our theory. We identify the unique component constraint as a necessary condition for binary decomposition of a relation, i.e. there is a unique component for every join key value in the bipartite graph. We generalize the running intersection property as the partial ordering counterpart under the unique component constraint. It follows that we characterize the multivalued and acyclic join dependencies in terms of commutativity and unique component constraint. This shows the decompositions specified by these dependencies are special cases of our theory. Furthermore, we propose a lossless decomposition method for the class of data dependencies that is based on commutativity, and demonstrate that existing relational operations are sufficient for this method. / Relational information systems, systems that can be represented by tables of finite states, are widely used in many areas such as logic circuits, finite state machines, and relational databases. Decomposition is a natural method to remove redundancy of complex systems. It divides a system into a network of simpler components. In order to preserve the original functionalities of the system, any valid decomposition has to be lossless. This work is divided into two parts. In the first part, we develop a mathematical model for lossless decompositions of relational information systems. Commutative partitions play an important role in decompositions. The commutativity is essentially a general algebraic formulation of independency of two partitions. We express the interdependency of two commutative partitions by a bipartite graph, and classify the hierarchical independency structures by the topological property of bipartite graphs. In particular, we show that two partitions are decomposable, the strongest kind of independency, if and only if the associated bipartite graph is uniform. Moreover, we adopt Shannon's entropy to quantify the amount of information contained in each partition, and formulate information-lossless decompositions by entropy equalities. Under the assumption of running intersection property, we show that the general formulation of information-lossless decompositions of relational information systems is given by the entropy inclusion-exclusion equality. We also present the applications of these formulations to the above engineering systems to manifest the information-lossless decomposition processes. / Lo, Ying Hang. / Adviser: Tony T. Lee. / Source: Dissertation Abstracts International, Volume: 70-06, Section: B, page: 3606. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2008. / Includes bibliographical references (leaves 159-163). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstracts in English and Chinese. / School code: 1307.

A transitive decomposition of a graph is a partition of the arc set such that there exists a group of automorphisms of the graph which preserves and acts transitively on the partition. This turns out to be a very broad idea, with several striking connections with other areas of mathematics. In this thesis we first develop some general theory of transitive decompositions, and in particular we illustrate some of the more interesting connections with certain combinatorial and geometric structures. We then give complete, or nearly complete, structural characterisations of certain classes of transitive decompositions preserved by a group with a rank 3 action on vertices (such a group has exactly two orbits on ordered pairs of distinct vertices). The main classes of rank 3 groups we study (namely those which are imprimitive, or primitive of grid type) are derived in some way from 2-transitive groups (that is, groups which are transitive on ordered pairs of distinct vertices), and the results we achieve make use of the classification by Sibley in 2004 of transitive decompositions preserved by a 2-transitive group.

Not available

Jackson and Wormald show that every 3-connected K_1,d-free graph, on n vertices, contains a cycle of length at least 1/2 n^g(d) where g(d) = (log_2 6 + 2 log_2 (2d+1))^-1. For d = 3, g(d) ~ 0.122. Improving this bound, we prove that if G is a 3-connected claw-free graph on at least 6 vertices, then there exists a cycle C in G such that |E(C)| is at least c n^g+5, where g = log_3 2 and c > 1/7 is a constant. To do this, we instead prove a stronger theorem that requires the cycle to contain two specified edges. We then use Tutte decomposition to partition the graph and then use the inductive hypothesis of our theorem to find paths or cycles in the different parts of the decomposition.

Thesis (Ph. D.)--University of California, Berkeley, 1996. / Cover title. "June 1997" [i.e. 1996]. Includes bibliographical references.

Thesis (Ph.D.)--Tufts University, 2004. / Adviser: Joseph Noonan. Submitted to the Dept. of Electrical Engineering. Includes bibliographical references (leaves 162-180). Access restricted to members of the Tufts University community. Also available via the World Wide Web;

Thesis (M. Sc.)--University of Canterbury, 2006. / Typescript (photocopy). Includes bibliographical references (p. 77-79). Also available via the World Wide Web.

Thesis (Ph. D.)--University of Texas at Austin, 2007. / Vita. Includes bibliographical references.

Thesis(M.S.)--Auburn University, 2006. / Abstract. Vita. Includes bibliographic references (p.30).

Thesis (Ph. D.)--Auburn University, 2008. / Abstract. Vita. Includes bibliographical references (p. 50-51).