TRANSACTION PROCESSING AND CONCURRENCY CONTROL

1. What are the ACID properties? APRIL/MAY-2011

(atomicity, consistency, isolation, durability) is a set of properties that guarantee database

transactions are processed reliably. In the context of databases, a single logical operation on the data is called a transaction. For example, a transfer of funds from one bank account to another, even though that might involve multiple changes (such as debiting one account and crediting another), is a single transaction.

2. What are two pitfalls (problem) of lock-based protocols? APRIL/MAY-2011

Ø Deadlock

Ø Starvation

3. What is transaction?

Collections of operations that form a single logical unit of work are called transactions.

4. What are the two statements regarding transaction?

The two statements regarding transaction of the form:

Ø Begin transaction

Ø End transaction

5. What are the properties of transaction?

The properties o f transactions are:

Ø Atomicity

Ø Consistency

Ø Isolation

Ø Durability

Application: Intermittently Synchronized Databases

• In some of the applications, a server or a group of servers manages the central database and the clients carry laptops or palmtops with a resident DBMS software to do “local” transaction activity for most of the time.
• The clients connect via a network or a dial-up connection (or possibly even through the Internet) with the server, typically for a short session—say, 30 to 60 minutes.
• They send their updates to the server, and the server must in turn enter them in its central database, which must maintain up-to-date data and prepare appropriate copies for all clients on the system.
• Thus, whenever clients connect—through a process known in the industry as synchronization of a client with a server—they receive a batch of updates to be installed on their local database.
• The primary characteristic of this scenario is that the clients are mostly disconnected; the server is not necessarily able to reach the client. This environment has problems similar to those in distributed and client-server databases, and some from mobile databases, but presents several additional research problems for investigation.
• We refer to this environment as Intermittently Synchronized Database Environment (ISDBE), and the corresponding databases as Intermittently Synchronized Databases (ISDBs).

Data Management Issues

From a data management standpoint, mobile computing may be considered a variation of distributed computing. Mobile databases can be distributed under two possible scenarios:

1. The entire database is distributed mainly among the wired components, possibly with full or partial replication. A base station or fixed host manages its own database with a DBMS-like functionality, with additional functionality for locating mobile units and additional query and transaction management features to meet the requirements of mobile environments.

2. The database is distributed among wired and wireless components. Data management responsibility is shared among base stations or fixed hosts and mobile units.

(All the Distributed data management issues can be applied to Mobile)

• Data distribution and replication: Data is unevenly distributed among the base stations and mobile units. The consistency constraints compound the problem of cache management. Caches attempt to provide the most frequently accessed and updated data to mobile units that process their own transactions and may be disconnected over long periods.
• Transaction models: Issues of fault tolerance and correctness of transactions are aggravated in the mobile environment. A mobile transaction is executed sequentially through several base stations and possibly on multiple data sets depending upon the movement of the mobile unit. Central coordination of transaction execution is lacking, particularly in scenario (2) above. Moreover, a mobile transaction is expected to be long-lived because of disconnection in mobile units. Hence, traditional ACID properties of transactions may need to be modified and new transaction models must be defined.
• Query processing: Awareness of where the data is located is important and affects the cost/benefit analysis of query processing. Query optimization is more complicated because of mobility and rapid resource changes of mobile units. The query response needs to be returned to mobile units that may be in transit or may cross cell boundaries yet must receive complete and correct query results. 
• Recovery and fault tolerance: The mobile database environment must deal with site, media, transaction, and communication failures. Site failure at an MU is frequently due to limited battery power. If an MU has a voluntary shutdown, it should not be treated as a failure. Transaction failures are more frequent during handoff when an MU crosses cells. MU failure causes a network partitioning and affects routing algorithms.

Characteristics of Mobile Environments

Some of the characteristics of computing in the mobile environment include

·   High communication latency

·   Intermittent wireless connectivity

·   Limited battery life

·   Changing client location.

·         Latency is caused by the processes unique to the wireless medium, such as coding data for wireless transfer, and tracking and filtering wireless signals at the receiver.

·         Battery life is directly related to battery size, and indirectly related to the mobile device’s capabilities.

·         Intermittent connectivity (Types)

                                i.      Intentional

             Intentional disconnections occur by user intent, e.g., during the takeoff of an airplane, or when the mobile device is powered down.

                              ii.      Unintentional.

Unintentional disconnections happen in areas wireless signals cannot reach, e.g., elevator shafts or subway tunnels.

·         To compensate for high latencies and unreliable connectivity, clients cache replicas of important, frequently accessed data, and work offline, if necessary.

·         Besides increasing data availability and response time, caching can also reduce client power consumption by eliminating the need to make energy-consuming wireless data transmissions for each data access.

·         On the other hand, the server may not be able to reach a client. A client may be unreachable because it is dozing—in an energy-conserving state in which many subsystems are shut down—or because it is out of range of a base station.

·         In either case, neither client nor server can reach the other, and modifications must be made to the architecture in order to compensate for this case.

Architecture of Mobile Ad-hoc network

Client/Network Relationships:

·        Mobile units can move freely in a geographic mobility domain, an area that is circumscribed by wireless network coverage.

·        To manage the mobility of units, the entire geographic mobility domain is divided into one or more smaller domains called cells, each of which is supported by at least one base station.

·        The mobile discipline requires that the movement of mobile units be unrestricted throughout the cells of a geographic mobility domain, while maintaining information access contiguity—i.e., movement, especially intercell movement, does not negatively affect the data retrieval process.

Explanation:

• In a MANET, co-located mobile units do not need to communicate via a fixed network, but instead, form their own using cost-effective technologies such as Bluetooth.
• In a MANET, mobile units are responsible for routing their own data, effectively acting as base stations as well as clients.
• Moreover, they must be robust enough to handle changes in the network topology, such as the arrival or departure of other mobile units.
• MANET applications can fall under the peer-to-peer paradigm, meaning that a mobile unit is simultaneously a client and a server.
• Transaction processing and data consistency control become more difficult since there is no central control in this architecture.
• Resource discovery and data routing by mobile units make computing in a MANET more complicated.

Mobile Databases

·         Recent advances in portable and wireless technology have led to mobile computing, a new dimension in data communication and processing.

·         Portable computing devices coupled with wireless communications allow clients to access data from virtually anywhere and at any time.

·         This feature is especially useful to geographically dispersed organizations.

·         Some of the software problems, which may involve data management, transaction management, and database recovery—have their origins in distributed database systems.

Explanation:

·         It is a distributed architecture where a number of computers, generally referred to as Fixed Hosts (FS) and Base Stations (BS), are interconnected through a high-speed wired network.

·         Fixed hosts are general purpose computers that are not typically equipped to manage mobile units but can be configured to do so.

·         Base stations are Mobile Units' (MU) gateways to the fixed network. They are equipped with wireless interfaces and offer network access services of which mobile units are clients.

Image Databases

Definition

Ø  Computer system where image files are kept in an organised form.

Ø  Software that facilitates organised storage and retrieval of digital images is called Image database system.

Characteristics of Image Database

The main characteristics of image database system

1. possibility to handle large amount of images of different types.
2. possibility for content and similarity based retrieval.
3. possibilities to compose the query of text, images, sketches and making use of colour palette.
4. The query response time is fast.

Global Image Representation

            Traditionally there have been two major approaches for global image representation.

ü  The parametric approach.

ü  The syntactic approach

In the parametric approach image elements are represented by vectors of features ((e.g., colour, Size, etc.), which features can be measured from the images.

In the syntactic representation the image features are represented as sets of symbolic entities, that is an alphabet of image primitives is used.

The image indexing mechanism combines the two approaches and allows quick search based on multilevel index.

The user can make use besides of simple text-based queries, also of tools for drawing sketches, picking colour from colour palette, drawing image element, extracting parts from example images, etc. The searching mechanism combines image and text description of colour, shape and attribute of the image and its elements. The overall description reduces the search.

Image Indexing

The basis of image indexing is a semantic image representation. The total image representation is defined as: Global image representation and Image Elements representation,

where

Global image representation = {Image Name, Image Colour, Image Attribute}

And Image Elements representation includes the Image element representations and their places.

Image Element representation = {Element name, Element colour, Element shape, Element attribute}.

An Element is a small patch in the image with descriptive power. The best choice for an ensemble element is to form a set from which the image is composed.

The different elements in the semantic image representations are defined as:

1.      Name description.

Name of an image or elements in it could be given during the image entering.

2.      Attribute description.

It is borrowed from outside sources concerning the image elements. In the case of geographic maps, if the element represents a legend sign for a town, the user could enter the town population. The attribute description could be text or number.

3.      Colour description.

Each image voxel is considered as a point in a 3D colour space (Red, Green, Blue).

Spatial Data Transfer Standard (SDTS)

Spatial Data Transfer Standard (SDTS)

ü  Adopted by US as Federal Information Processing Standard(FIPS)

ü  SDTS: self-contained standard intended for transfer of spatial data

ü  ESRI(ArcINFO),LEICA(ErdasIMAGINE), Intergraph and MapInfo

GIS application and software

ü  Military Government

ü  Real Estate in past decade and today

ü  Decision making applications for large and small companies

ü  Environment science

ü  City planning, navigation, transportation, emergency services, law enforcement, census tracking

Variety of products interact with GIS

ü  ArcInfo of ESRI – editing of data and advanced analysis tools

ü  ArcGis by ESRI – simple map making, report and analysis

ü  ArcPad from ESRI - Provides  mapping and data collections

Mobile is integrated with GIS and GPS

Example of GIS Software

ü  ArcInfo – designed for mini computers

ü  GeoDatabase These software are the products of ESRI(Environmental Systems Research Institute)

DBMS enhancements for GIS

ü  GIS were based on Proprietary data models in mid 1990’s.

ü  They are all file based models.

ü  Creates an inherent problem of data sharing.

ü  To overcome this , Spatial features are included.

ü  Still had a problem of limited scalability and inefficient for data recovery and backups.

ü  3 types of DBMS are evolved. They are;

Ø  Relational (RDBMS),

Ø  Object (ODBMS),

Ø  Object-relational (ORDBMS).

Conceptual Data model for GIS

The well known models for storing Geo data are:

             1. Raster Data model:

ü  Raster data- an array of Cells.

ü  Each cell value represents an attribute.

ü  Meta data stored in File header includes cell size, the number of rows and columns.

ü  Manly used for Analytical applications like modeling, map algebra and clustering..

            2. Vector Data model:

ü  Representation of discrete object as points, lines and polygons.

ü  Spatial analyses are done using this model for decision making.

3. Network Model:

ü  Special type of topological feature model.

ü  Allows modeling of flow and transport of resources and services.

ü  Defines how lines are connected to each other.

ü  The rules are stored in Connectivity table.

ü  Everyday application uses this model usually.

4. TIN Data model:

ü  Triangulated Irregular Network -TIN

ü  Mainly used to create and represent Surfaces.

ü  Surfaces are represented as non-overlapping triangles constructed from irregularly spaced points.

ü  Easy calculation of elevation, slope and line-of –sight between points

Constraints in GIS

Constraints in GIS:

Ø  Important aspects of geographic objects in GIS.

Ø  4 types of constraints:

            1.Toplogical:

ü  Deals with behavior and spatial relationship between objects.

ü  used during Insert and Update process, mostly to reduce errors and improve data quality.

            2. Semantic:

ü  Deals with the “meaning” of the spatial features.

ü  Define whether the database is valid according to semantic rules(2 buildings can’t share the same edge).

3. User-defined:

ü  Business rules of non-spatial DBMS.

ü  e.g.- a house should be located within a certain distance from a fire hydrant.

4. Temporal: it has 2 types

1. Punctual- defines an occurring of an event with a specific time. E.g. accident, earthquake….

2. Durable- description changes that occur over time. E.g. a bridge was built, maintained and demolished

Characteristics of Data in GIS

Characteristics of Data in GIS:

1. Location:

ü  Spatial locations are defined by co-ordinates in specific reference system.

ü  Represented by Lines, points and polygons.

2. Temporality:

ü  DB model should consider both existence and change over time of features.

ü  Especially crucial with dynamic data.

ü  We are in need to represent current valid data

3. Complex spatial Features:

ü  Several representations includes points, lines, polygons and raster

4. Thematic values:

ü  Different properties and qualities of objects are represented as attributes.

5. Generalization:

ü  Relates to the level of scale and details associated with objects.

ü  Aggregation of objects is from lower to higher scale.

6. Roles:

ü  Objects are assumed with different roles according to the universe of closure.

ü  Usually application dependent.

7. Object ID:

ü  Objects should uniquely identified within data model.

ü  It is necessary for data exchange purpose.

8. Data Quality:

ü  Refers to credibility and accuracy of data.

ü  2types of Quality:

o   Quantitative-relates to measurable components such as spatial accuracy.

o   Qualitative- non measured components that are not to specific objects

Components of GIS

Components of GIS:

            Integration of 3 components: Hardware and Software, data and people

1. Hardware and Software:

ü  Devices used by the end users such as plotters or graphic devices, scanners.

ü  Data Storage and manipulation is done by a range of processors

ü  Web servers for web applications

ü  Software which is based on their applications

ü  GIS follows 3 tier architecture

2. Data:

            Geographic data can be divided into vector and raster

            Vector:

ü  Discrete objects represented by Lines, points and polygons.

ü  Lines are formed by connecting two or more points.

ü  Polygons are closed set of lines

            Raster:

§  Continuous grid of cells in two dimensions, It has two types:

·         Categorical- Every cell value is linked to a category in a separate table.

o   Ex: soil types, vegetation types, land suitability and so on.

·         Continuous- describes continuous phenomena in space.

o   Ex: Digital Elevation Models (DEM) –does not have an attribute/category table

3. People:

Involved in all phases of developing GIS system and in collecting data, has2 types of people:

ü  Cartographers & Surveyors- creates maps and survey the land.

ü  System users-collecting data, upload data to system, manipulate the system and analyze the result.

Geographic information system (GIS)

Definition:

            Systematic integration of Hardware and Software for capturing, storing, displaying, updating, manipulating and analyzing the spatial data

Few Examples:

            Accuracy of maps, designing time-dependant geographic data models and developing better conversion tools and methods.

Spatial data:

Ø  Also called Geospatial data.

Ø  Information that identifies the geographic location of features and boundaries on earth.

Spatial data is usually stored as coordinates and topology

Why Spatial Data Special?

Describes objects that have a distinct position-attributes and relationship to each other within a defined space