Submitted by: JUNAID MUZAFFAR
Roll No: 13031756-016

Vertical Partitioning Algorithm for database Design
Vertical Partitioning Algorithms for Database
Design
SHAMKANT NAVATHE, STEFANO CERI, GIO WIEDERHOLD, AND
JINGLIE DOU
Stanford University
This paper define the vertical partitioning in which spread or break the logical relation into group of attributes according to transaction that access the attribute are group of attribute. The vertical partition is defined in three context memory level a centralized database and the most important is distributed database like placed data in different sites. In this paper we focus on distributed database. in which local transaction should be minimize.
In this paper we use two phases the first approach is that we have no first knowledge and second is cost optimization. Fragmented may be no overlapping or overlapping.
Summary
Partitioning in database design is the process of assign object from the logical schema to the physical several objects. Vertical partition is the process of divide attribute into group (fragments) and assign to physical object. In vertical fragmentation we make maximum and all minimum possible fragments it mean that fragment may be overlap or non-overlap.
So we make cluster of fragments that one overlap or no overlap but we use the both disjoint and no disjoint cases in partitioning. We use fragmentation to improve the performance of query optimization .according to distribution point of view the different approach is like hierarchy of memory partition. In this approach we used vertical partitioning in that way the attribute that are mostly accessed are placed inthat way the attributes that are highly access are placed in the fastest memory level.in the distribution environment we also use normally fragmentation but replica is also used . in the vertical fragmentation we use physical file structure to the improve the performance of the fragment must be closely match according to the requirement of the transaction . the ideal case is where all the fragments according to the truncation queries. The trival design process is when the set of attributes where B(m) is the mth Bell number; for large m, B(m) approaches m"; for m =
15, it is ElO’, for m = 30, it is =1023
The main contribute of this paper in following areas:
We extend the work of Hoffer and Severance that defined attribute In such way that attribute of a object that are highly accessed means that attribute that have high affinity are grouped together . The main concept is overlapping and no overlapping. * We consider the application of partitioning to databases that use one level of memory or a memory hierarchy. We also consider the application of vertical
Partitioning to distributed databases by determining the allocation of fragments to different sites, allowing no replicated or replicated fragments. Thus we apply vertical partitioning is more general environment. * A unique feature of this paper is the two step design of fragments. in the first step the vertical partitioned is governed by an empirical notion of partitioning. Where one expects that the need for transaction to visit multiple fragments should be minimized.in this approach does not require detailed cost factors. The second step is the refining the design of fragments according to estimated cost factors which reflect the physical environment. * Problem description * An object can be vertical partitioned by considering its projection onto different set of attributes as creating new object is called fragment. If intersection of two fragments is empty then approach is no overlapping otherwise is overlapping.
The transaction specification relevant to the vertical partitioning of an object consists of the following information: * the frequency (per unit time period) of occurrence of the transaction; * when the same transaction can be issued at multiple sites in a distributed * database, the frequency at each site is specified; * the subset of the attributes used for retrieval or update by the transaction; * the total number of instances of the object selected on the average by one occurrence of the transaction.
Approach to place the vertical partitioning problem in this paper
Three kinds of decision can be refined to place the vertical partitioning problem * logic decision concerning the structure and the composition of the fragment * Distribution and allocation decision * Physical decision concerning the storage structure and access method for each fragment The use of the terms logical and physical above is only for convenience: it is difficult to argue where the exact boundary lies between these two types of decisions. This paper concentrates on the logical and distribution decisions, Database and transaction specification the transaction specification relevant to vertical partitioning assumption of knowing important transaction common practice of distributed application information.
Vertical partitioning will be addressed in two phases:
(1) Empirical design of fragments based on the specified logical access frequencies of the transactions.
(2) Design based on cost factors related to the physical environment; this produces a refinement of fragmentation and, if applicable, the allocation of fragments to multiple levels of a memory hierarchy or to multiple sites of a distributed database. In an environment in single object is fragmented and allocated into different sites Identification is required to identify each fragment this is done by replicating the primary key are using unique tuple identification
Previous work done in this field and solution of this problem:
The previous is grouped into two major categories. In the first approach is the optimal solution of the problem under restrictive assumption and the second approach is heuristic. Hoffer developed an nonlinear zero one program for the solution of the petitioning problem which minimize linear combination of the problem retrieval and update cost.Babed formulated the less restricted vertical problem in this model one sub record is created as a primary record all requested addressed to this sub record. This problem is un manageable when large attributes.
Papers of the second category describe heuristic approaches to the attribute partitioning problem. We agree with Hammer and Niamir that the general vertical partitioning problem is “heuristic in nature,” and that optimal methods cannot deal with it adequately. Hoffer and severance measure the affinity between attribute and used bond energy algorithm. Their attribute similarity function uses the notion of an attribute being “required for processing,” or “required only if the record is selected,” or finally “not required.” We feel that in database systems the first and the second cases cannot be distinguished because all attributes of the same record are accessed together; therefore, we prefer the notion of logical accesses. In the Hoffer length approach that update a fragment of long length attribute or small length attribute. But in this paper we not use length factor to measure affinity. Hammer and niamer try to summarize unsolved problem
BEB try to ordering the attribute but is left unsolved to clump the attributes together to form fragments. Similarity of pairs of attributes can be inadequate if the similarity among larger groups of attributes is not taken into account Our present paper extends the results of by giving algorithms for the design of fragments that perform the activity for automatically and by taking into account in our algorithms “blocks” of attributes with similar properties,

The hammer and nimear used grouping technique heuristic starts by assigning each attribute to a different partition; The major criticism of this approach is regarding the direction in which to explore the lattice-while Hammer and Niamir proceed “up” by grouping, we proceed “down” by splitting. The rationale behind this approach is that the “optimal” solution, in our opinion, is much closer to the group composed of all attributes, assumed to be our starting point, than to groups that are single attribute partitions.
Further extensions of this work will be in the direction of developing site-specific affinity measures for distributed databases, of incorporating different transaction processing strategies, and of considering new applications of vertical partitioning, such as parallel processing of transactions.