Articles by "DDBMS"
Showing posts with label DDBMS. Show all posts

at June 02, 2018 0

Distributed Shared Memory (DSM)



In DSM the different physical memories are logically shared over a large address space( virtual memory). So the processes going on accesses the physical memory through these logically shared address space. DSM have no physical shared memory. The shared memory model provides a virtual address space shared between all nodes. The term "shared" does not mean that there is a single centralized memory but "shared" essentially means that the address space is shared (same physical address on two processors refers to the same location in memory).


Shared Memory (SM)


In computer science, shared memory is memory that may be simultaneously accessed by multiple programs with an intent to provide communication among them or avoid redundant copies. Shared memory is an efficient means of passing data between programs. Depending on context, programs may run on a single processor or on multiple separate processors.
In computer software, shared memory is either
-a method of inter-process communication (IPC), i.e. a way of exchanging data between programs running at the same time. One process will create an area in RAM which other processes can access;
-a method of conserving memory space by directing accesses to what would ordinarily be copies of a piece of data to a single instance instead, by using virtual memory mappings.



Read more »

at June 01, 2018 0

Layers of Query Processing

The problem of query processing can itself be decomposed into several subproblems, corresponding to various layers. A generic layering scheme for query processing is shown where each layer solves a well-defined subproblem. To simplify the discussion, let us assume a static and semicentralized query processor that does not exploit replicated fragments. The input is a query on global data expressed in relational calculus.

This query is posed on global (distributed) relations, meaning that data distribution is hidden. Four main layers are involved in distributed query processing. The first three layers map the input query into an optimized distributed query execution plan. They perform the functions of query decomposition, data localization, and global query optimization.

Query decomposition and data localization correspond to query rewriting. The first three layers are performed by a central control site and use schema information stored in the global directory. The fourth layer performs distributed query execution by executing the plan and returns the answer to the query. It is done by the local sites and the control site.
Layers of Query Processing

Generic Layering Scheme for Distributed Query Processing

Query Decomposition

The first layer decomposes the calculus query into an algebraic query on global relations. The information needed for this transformation is found in the global conceptual schema describing the global relations. However, the information about data distribution is not used here but in the next layer. Thus the techniques used by this layer are those of a centralized DBMS.

Query decomposition can be viewed as four successive steps. First, the calculus query is rewritten in a normalized form that is suitable for subsequent manipulation. Normalization of a query generally involves the manipulation of the query quantifiers and of the query qualification by applying logical operator priority.

Second, the normalized query is analyzed semantically so that incorrect queries are detected and rejected as early as possible. Techniques to detect incorrect queries exist only for a subset of relational calculus. Typically, they use some sort of graph that captures the semantics of the query.
Third, the correct query (still expressed in relational calculus) is simplified. One way to simplify a query is to eliminate redundant predicates. Note that redundant queries are likely to arise when a query is the result of system transformations applied to the user query. Such transformations are used for performing semantic data control (views, protection, and semantic integrity control).

Fourth, the calculus query is restructured as an algebraic query. That several algebraic queries can be derived from the same calculus query, and that some algebraic queries are “better” than others. The quality of an algebraic query is defined in terms of expected performance. The traditional way to do this transformation toward a “better” algebraic specification is to start with an initial algebraic query and transform it in order to find a “good” one.

The initial algebraic query is derived immediately from the calculus query by translating the predicates and the target statement into relational operators as they appear in the query. This directly translated algebra query is then restructured through transformation rules. The algebraic query generated by this layer is good in the sense that the worse executions are typically avoided. For instance, a relation will be accessed only once, even if there are several select predicates. However, this query is generally far from providing an optimal execution, since information about data distribution and fragment allocation is not used at this layer.

Data Localization

The input to the second layer is an algebraic query on global relations. The main role of the second layer is to localize the query’s data using data distribution information in the fragment schema. We saw that relations are fragmented and stored in disjoint subsets, called fragments, each being stored at a different site. This layer determines which fragments are involved in the query and transforms the distributed query into a query on fragments. Fragmentation is defined by fragmentation predicates that can be expressed through relational operators.

A global relation can be reconstructed by applying the fragmentation rules, and then deriving a program, called a localization program, of relational algebra operators, which then act on fragments. Generating a query on fragments is done in two steps. First, the query is mapped into a fragment query by substituting each relation by its reconstruction program (also called materialization program). Second, the fragment query is simplified and restructured to produce another “good” query. Simplification and restructuring may be done according to the same rules used in the decomposition layer. As in the decomposition layer, the final fragment query is generally far from optimal because information regarding fragments is not utilized.

Global Query Optimization

The input to the third layer is an algebraic query on fragments. The goal of query optimization is to find an execution strategy for the query which is close to optimal. Remember that finding the optimal solution is computationally intractable. An execution strategy for a distributed query can be described with relational algebra operators and communication primitives (send/receive operators) for transferring data between sites.

The previous layers have already optimized the query, for example, by eliminating redundant expressions. However, this optimization is independent of fragment characteristics such as fragment allocation and cardinalities. In addition, communication operators are not yet specified. By permuting the ordering of operators within one query on fragments, many equivalent queries may be found.

Query optimization consists of finding the “best” ordering of operators in the query, including communication operators that minimize a cost function. The cost function, often defined in terms of time units, refers to computing resources such as disk space, disk I/Os, buffer space, CPU cost, communication cost, and so on. Generally, it is a weighted combination of I/O, CPU, and communication costs.

Nevertheless, a typical simplification made by the early distributed DBMSs, as we mentioned before, was to consider communication cost as the most significant factor. This used to be valid for wide area networks, where the limited bandwidth made communication much more costly than local processing. This is not true anymore today and communication cost can be lower than I/O cost. To select the ordering of operators it is necessary to predict execution costs of alternative candidate orderings.

Determining execution costs before query execution (i.e., static optimization) is based on fragment statistics and the formulas for estimating the cardinalities of results of relational operators. Thus the optimization decisions depend on the allocation of fragments and available statistics on fragments which are recorder in the allocation schema.

An important aspect of query optimization is join ordering, since permutations of the joins within the query may lead to improvements of orders of magnitude. One basic technique for optimizing a sequence of distributed join operators is through the semijoin operator. The main value of the semijoin in a distributed system is to reduce the size of the join operands and then the communication cost.

However, techniques which consider local processing costs as well as communication costs may not use semijoins because they might increase local processing costs. The output of the query optimization layer is a optimized algebraic query with communication operators included on fragments. It is typically represented and saved (for future executions) as a distributed query execution plan.

Distributed Query Execution

The last layer is performed by all the sites having fragments involved in the query. Each subquery executing at one site, called a local query, is then optimized using the local schema of the site and executed. At this time, the algorithms to perform the relational operators may be chosen. Local optimization uses the algorithms of centralized systems.

The goal of distributed query processing may be summarized as follows: given a calculus query on a distributed database, find a corresponding execution strategy that minimizes a system cost function that includes I/O, CPU, and communication costs.

An execution strategy is specified in terms of relational algebra operators and communication primitives (send/receive) applied to the local databases (i.e., the relation fragments). Therefore, the complexity of relational operators that affect the performance of query execution is of major importance in the design of a query processor.
Read more »

at May 29, 2018 1

Fragmentation in Distributed Database Management System (DDBMS)

Fragmentation in Distributed Database Management System (DDBMS)

 

Fragmentation is the task of dividing a table into a set of smaller tables. The subsets of the table are called fragments. Fragmentation can be of three types: horizontal, vertical, and hybrid (combination of horizontal and vertical). Horizontal fragmentation can further be classified into two techniques: primary horizontal fragmentation and derived horizontal fragmentation.

Fragmentation should be done in a way so that the original table can be reconstructed from the fragments. This is needed so that the original table can be reconstructed from the fragments whenever required. This requirement is called “reconstructiveness.”

Advantages of Fragmentation

  • Since data is stored close to the site of usage, efficiency of the database system is increased.
  • Local query optimization techniques are sufficient for most queries since data is locally available.
  • Since irrelevant data is not available at the sites, security and privacy of the database system can be maintained.

Disadvantages of Fragmentation

  • When data from different fragments are required, the access speeds may be very high.
  • In case of recursive fragmentations, the job of reconstruction will need expensive techniques.
  • Lack of back-up copies of data in different sites may render the database ineffective in case of failure of a site.



    Vertical Fragmentation

    In vertical fragmentation, the fields or columns of a table are grouped into fragments. In order to maintain reconstructiveness, each fragment should contain the primary key field(s) of the table. Vertical fragmentation can be used to enforce privacy of data.

    For example, let us consider that a University database keeps records of all registered students in a Student table having the following schema.

    STUDENT

    Regd_No Name Course Address Semester Fees Marks       
    Now, the fees details are maintained in the accounts section. In this case, the designer will fragment the database as follows −

    CREATE TABLE STD_FEES AS 
   SELECT Regd_No, Fees 
   FROM STUDENT;

    Horizontal Fragmentation

    Horizontal fragmentation groups the tuples of a table in accordance to values of one or more fields. Horizontal fragmentation should also confirm to the rule of reconstructiveness. Each horizontal fragment must have all columns of the original base table.

    For example, in the student schema, if the details of all students of Computer Science Course needs to be maintained at the School of Computer Science, then the designer will horizontally fragment the database as follows −

    CREATE COMP_STD AS 
   SELECT * FROM STUDENT  
   WHERE COURSE = "Computer Science";

    Hybrid Fragmentation

    In hybrid fragmentation, a combination of horizontal and vertical fragmentation techniques are used. This is the most flexible fragmentation technique since it generates fragments with minimal extraneous information. However, reconstruction of the original table is often an expensive task.

    Hybrid fragmentation can be done in two alternative ways −
  • At first, generate a set of horizontal fragments; then generate vertical fragments from one or more of the horizontal fragments.
  • At first, generate a set of vertical fragments; then generate horizontal fragments from one or more of the vertical fragments.


Read more »

at May 29, 2018 1

Design Strategies in Distributed Database Management System (DDBMS)


Database Design Strategies

There are two approaches for developing any database, the top-down method and the bottom-up method. While these approaches appear radically different, they share the common goal of utilising a system by describing all of the interaction between the processes.
  1. Top-down  design method
  2. Bottom – up design method
1. Top – down design method
The top-down design method starts from the general and moves to the specific. In other words, you start with a general idea of what is needed for the system and then work your way down to the more specific details of how the system will interact. This process involves the identification of different entity types and the definition of each entity’s attributes.

Design Strategies in Distributed Database Management System (DDBMS)


2. Bottom – up design method
The bottom-up approach begins with the specific details and moves up to the general. This is done by first identifying the data elements (items) and then grouping them together in data sets. In other words, this method first identifies the attributes, and then groups them to form entities.

Design Strategies in Distributed Database Management System (DDBMS)

Read more »

at May 28, 2018 4

Architecture Model of Distributed Database Management System (DDBMS)

Architecture Models for DDBMSs (or more generally for multiple DBMSs) canbe classified along three dimensions:
  1. – Autonomy
  2. – Distribution
  3. – Heterogeneity



  1. Distribution − It states the physical distribution of data across the different sites.
  2. Autonomy − It indicates the distribution of control of the database system and the degree to which each constituent DBMS can operate independently.
  3. Heterogeneity − It refers to the uniformity or dissimilarity of the data models, system components and databases.


    Architectural Models

    Some of the common architectural models are

    1. Client - Server Architecture for DDBMS
    2. Peer - to - Peer Architecture for DDBMS
    3. Multi - DBMS Architecture

1. Client - Server Architecture for DDBMS

This is a two-level architecture where the functionality is divided into servers and clients. The server functions primarily encompass data management, query processing, optimization and transaction management. Client functions include mainly user interface. However, they have some functions like consistency checking and transaction management.
The two different client - server architecture are −
  • Single Server Multiple Client
  • Multiple Server Multiple Client 

2. Peer- to-Peer Architecture for DDBMS

In these systems, each peer acts both as a client and a server for imparting database services. The peers share their resource with other peers and co-ordinate their activities.
This architecture generally has four levels of schemas −
  • Global Conceptual Schema − Depicts the global logical view of data.
  • Local Conceptual Schema − Depicts logical data organization at each site.
  • Local Internal Schema − Depicts physical data organization at each site.
  • External Schema − Depicts user view of data.

     

    3. Multi - DBMS Architectures

    This is an integrated database system formed by a collection of two or more autonomous database systems.
    Multi-DBMS can be expressed through six levels of schemas −
  • Multi-database View Level − Depicts multiple user views comprising of subsets of the integrated distributed database.
  • Multi-database Conceptual Level − Depicts integrated multi-database that comprises of global logical multi-database structure definitions.
  • Multi-database Internal Level − Depicts the data distribution across different sites and multi-database to local data mapping.
  • Local database View Level − Depicts public view of local data.
  • Local database Conceptual Level − Depicts local data organization at each site.
  • Local database Internal Level − Depicts physical data organization at each site.


There are two design alternatives for multi-DBMS −
  • Model with multi-database conceptual level.
  • Model without multi-database conceptual level.


Read more »

at May 26, 2018 1

Advantage and Disadvantage of Distributed Database Management System (DDBMS)


 The distribution of data and applications has potential advantages over traditional centralized database systems. Unfortunately, there are also disadvantages; in this section we review the advantages and disadvantages of DDBMS.

Advantages of DDBMS

Following are the advantages of distributed databases over centralized databases.

1. Modular Development 

If the system needs to be expanded to new locations or new units, in centralized database systems, the action requires substantial efforts and disruption in the existing functioning. However, in distributed databases, the work simply requires adding new computers and local data to the new site and finally connecting them to the distributed system, with no interruption in current functions.

2. More Reliable 

In case of database failures, the total system of centralized databases comes to a halt. However, in distributed systems, when a component fails, the functioning of the system continues may be at a reduced performance. Hence DDBMS is more reliable.

3. Better Response 

If data is distributed in an efficient manner, then user requests can be met from local data itself, thus providing faster response. On the other hand, in centralized systems, all queries have to pass through the central computer for processing, which increases the response time.

4. Lower Communication Cost 

In distributed database systems, if data is located locally where it is mostly used, then the communication costs for data manipulation can be minimized. This is not feasible in centralized systems.

5. Improved Performance

As the data is located near the site of 'greatest demand', and given the inherent parallelism of distributed DBMSs, speed of database access may be better than that achievable from a remote centralized database. Furthermore, since each site handles only a part of the entire database, there may not be the same contention for CPU and I/O services as characterized by a centralized DBMS.

6. Improved share ability and local autonomy

The geographical distribution of an organization can be reflected in the distribution of the data; users at one site can access data stored at other sites. Data can be placed at the site close to the users who normally use that data. In this way, users have local control of the data, and they can consequently establish and enforce local policies regarding the use of this data. A global database administrator (DBA) is responsible for the entire system. Generally, part of this responsibility is assigned the local level, so that the local DBA can manage the local DBMS.

Disadvantages of DDBMS

There are following disadvantages of DDBMSs:

1. Complexity

A distributed DBMS that hides the distributed nature from the user and provides an acceptable level of performance, reliability, availability is inherently more complex then a centralized DBMS. The fact that data can be replicated also adds an extra level of complexity to the distributed DBMS. If the software does not handle data replication adequately, there wi1l be degradation in availability, reliability and performance compared with the centralized system, and the advantages we cites above will become disadvantages.

2. Cost

Increased complexity means that we can expect the procurement and maintenance costs for a DDBMS to be higher than those for a centralized DBMS. Furthermore, a distributed
DBMS requires additional hardware to establish a network between sites. There are ongoing communication costs incurred with the use of this network. There are also additional labor costs to manage and maintain the local DBMSs and the underlying network.

3. Security

In a centralized system, access to the data can be easily controlled. However, in a distributed DBMS not only does access to replicated data have to be controlled in multiple locations but also the network itself has to be made secure. In the past, networks were regarded as an insecure communication medium. Although this is still partially true, significant developments have been made to make networks more secure.

4. Integrity control more difficult

Database integrity refers to the validity and consistency of stored data. Integrity is usually expressed in terms of constraints, which are consistency rules that the database is not permitted to violate. Enforcing integrity constraints generally requires access to a large amount of data that defines the constraints. In a distributed DBMS, the communication and processing costs that are required to enforce integrity constraints are high as compared to centralized system.

5. Lack of Standards

Although distributed DBMSs depend on effective communication, we are only now starting to see the appearance of standard communication and data access protocols. This lack of standards has significantly limited the potential of distributed DBMSs. There are also no tools or methodologies to help users convert a centralized DBMS into a distributed DBMS

6. Lack of experience

General-purpose distributed DBMSs have not been widely accepted, although many of the protocols and problems are well understood. Consequently, we do not yet have the same level of experience in industry as we have with centralized DBMSs. For a prospective adopter of this technology, this may be a significant deterrent.

7. Database design more complex

Besides the normal difficulties of designing a centralized database, the design of a distributed database has to take account of fragmentation of data, allocation of fragmentation to specific sites, and data replication.


Read more »
Subscribe to: Posts (Atom)