\documentclass[11pt,twoside]{article}\makeatletter \IfFileExists{xcolor.sty}% {\RequirePackage{xcolor}}% {\RequirePackage{color}} \usepackage{colortbl} \usepackage{wrapfig} \usepackage{ifxetex} \ifxetex \usepackage{fontspec} \usepackage{xunicode} \catcode`⃥=\active \def⃥{\textbackslash} \catcode`❴=\active \def❴{\{} \catcode`❵=\active \def❵{\}} \def\textJapanese{\fontspec{Noto Sans CJK JP}} \def\textChinese{\fontspec{Noto Sans CJK SC}} \def\textKorean{\fontspec{Noto Sans CJK KR}} \setmonofont{DejaVu Sans Mono} \else \IfFileExists{utf8x.def}% {\usepackage[utf8x]{inputenc} \PrerenderUnicode{–} }% {\usepackage[utf8]{inputenc}} \usepackage[english]{babel} \usepackage[T1]{fontenc} \usepackage{float} \usepackage[]{ucs} \uc@dclc{8421}{default}{\textbackslash } \uc@dclc{10100}{default}{\{} \uc@dclc{10101}{default}{\}} \uc@dclc{8491}{default}{\AA{}} \uc@dclc{8239}{default}{\,} \uc@dclc{20154}{default}{ } \uc@dclc{10148}{default}{>} \def\textschwa{\rotatebox{-90}{e}} \def\textJapanese{} \def\textChinese{} \IfFileExists{tipa.sty}{\usepackage{tipa}}{} \fi \def\exampleFont{\ttfamily\small} \DeclareTextSymbol{\textpi}{OML}{25} \usepackage{relsize} \RequirePackage{array} \def\@testpach{\@chclass \ifnum \@lastchclass=6 \@ne \@chnum \@ne \else \ifnum \@lastchclass=7 5 \else \ifnum \@lastchclass=8 \tw@ \else \ifnum \@lastchclass=9 \thr@@ \else \z@ \ifnum \@lastchclass = 10 \else \edef\@nextchar{\expandafter\string\@nextchar}% \@chnum \if \@nextchar c\z@ \else \if \@nextchar l\@ne \else \if \@nextchar r\tw@ \else \z@ \@chclass \if\@nextchar |\@ne \else \if \@nextchar !6 \else \if \@nextchar @7 \else \if \@nextchar (8 \else \if \@nextchar )9 \else 10 \@chnum \if \@nextchar m\thr@@\else \if \@nextchar p4 \else \if \@nextchar b5 \else \z@ \@chclass \z@ \@preamerr \z@ \fi \fi \fi \fi \fi \fi \fi \fi \fi \fi \fi \fi \fi \fi \fi \fi} \gdef\arraybackslash{\let\\=\@arraycr} \def\@textsubscript#1{{\m@th\ensuremath{_{\mbox{\fontsize\sf@size\z@#1}}}}} \def\Panel#1#2#3#4{\multicolumn{#3}{){\columncolor{#2}}#4}{#1}} \def\abbr{} \def\corr{} \def\expan{} \def\gap{} \def\orig{} \def\reg{} \def\ref{} \def\sic{} \def\persName{}\def\name{} \def\placeName{} \def\orgName{} \def\textcal#1{{\fontspec{Lucida Calligraphy}#1}} \def\textgothic#1{{\fontspec{Lucida Blackletter}#1}} \def\textlarge#1{{\large #1}} \def\textoverbar#1{\ensuremath{\overline{#1}}} \def\textquoted#1{‘#1’} \def\textsmall#1{{\small #1}} \def\textsubscript#1{\@textsubscript{\selectfont#1}} \def\textxi{\ensuremath{\xi}} \def\titlem{\itshape} \newenvironment{biblfree}{}{\ifvmode\par\fi } \newenvironment{bibl}{}{} \newenvironment{byline}{\vskip6pt\itshape\fontsize{16pt}{18pt}\selectfont}{\par } \newenvironment{citbibl}{}{\ifvmode\par\fi } \newenvironment{docAuthor}{\ifvmode\vskip4pt\fontsize{16pt}{18pt}\selectfont\fi\itshape}{\ifvmode\par\fi } \newenvironment{docDate}{}{\ifvmode\par\fi } \newenvironment{docImprint}{\vskip 6pt}{\ifvmode\par\fi } \newenvironment{docTitle}{\vskip6pt\bfseries\fontsize{22pt}{25pt}\selectfont}{\par } \newenvironment{msHead}{\vskip 6pt}{\par} \newenvironment{msItem}{\vskip 6pt}{\par} \newenvironment{rubric}{}{} \newenvironment{titlePart}{}{\par } \newcolumntype{L}[1]{){\raggedright\arraybackslash}p{#1}} \newcolumntype{C}[1]{){\centering\arraybackslash}p{#1}} \newcolumntype{R}[1]{){\raggedleft\arraybackslash}p{#1}} \newcolumntype{P}[1]{){\arraybackslash}p{#1}} \newcolumntype{B}[1]{){\arraybackslash}b{#1}} \newcolumntype{M}[1]{){\arraybackslash}m{#1}} \definecolor{label}{gray}{0.75} \def\unusedattribute#1{\sout{\textcolor{label}{#1}}} \DeclareRobustCommand*{\xref}{\hyper@normalise\xref@} \def\xref@#1#2{\hyper@linkurl{#2}{#1}} \begingroup \catcode`\_=\active \gdef_#1{\ensuremath{\sb{\mathrm{#1}}}} \endgroup \mathcode`\_=\string"8000 \catcode`\_=12\relax \usepackage[a4paper,twoside,lmargin=1in,rmargin=1in,tmargin=1in,bmargin=1in,marginparwidth=0.75in]{geometry} \usepackage{framed} \definecolor{shadecolor}{gray}{0.95} \usepackage{longtable} \usepackage[normalem]{ulem} \usepackage{fancyvrb} \usepackage{fancyhdr} \usepackage{graphicx} \usepackage{marginnote} \renewcommand{\@cite}[1]{#1} \renewcommand*{\marginfont}{\itshape\footnotesize} \def\Gin@extensions{.pdf,.png,.jpg,.mps,.tif} \pagestyle{fancy} \usepackage[pdftitle={An Analytical Review of Orientation Based Concurrency Control Algorithm}, pdfauthor={}]{hyperref} \hyperbaseurl{} \paperwidth210mm \paperheight297mm \def\@pnumwidth{1.55em} \def\@tocrmarg {2.55em} \def\@dotsep{4.5} \setcounter{tocdepth}{3} \clubpenalty=8000 \emergencystretch 3em \hbadness=4000 \hyphenpenalty=400 \pretolerance=750 \tolerance=2000 \vbadness=4000 \widowpenalty=10000 \renewcommand\section{\@startsection {section}{1}{\z@}% {-1.75ex \@plus -0.5ex \@minus -.2ex}% {0.5ex \@plus .2ex}% {\reset@font\Large\bfseries}} \renewcommand\subsection{\@startsection{subsection}{2}{\z@}% {-1.75ex\@plus -0.5ex \@minus- .2ex}% {0.5ex \@plus .2ex}% {\reset@font\Large}} \renewcommand\subsubsection{\@startsection{subsubsection}{3}{\z@}% {-1.5ex\@plus -0.35ex \@minus -.2ex}% {0.5ex \@plus .2ex}% {\reset@font\large}} \renewcommand\paragraph{\@startsection{paragraph}{4}{\z@}% {-1ex \@plus-0.35ex \@minus -0.2ex}% {0.5ex \@plus .2ex}% {\reset@font\normalsize}} \renewcommand\subparagraph{\@startsection{subparagraph}{5}{\parindent}% {1.5ex \@plus1ex \@minus .2ex}% {-1em}% {\reset@font\normalsize\bfseries}} \def\l@section#1#2{\addpenalty{\@secpenalty} \addvspace{1.0em plus 1pt} \@tempdima 1.5em \begingroup \parindent \z@ \rightskip \@pnumwidth \parfillskip -\@pnumwidth \bfseries \leavevmode #1\hfil \hbox to\@pnumwidth{\hss #2}\par \endgroup} \def\l@subsection{\@dottedtocline{2}{1.5em}{2.3em}} \def\l@subsubsection{\@dottedtocline{3}{3.8em}{3.2em}} \def\l@paragraph{\@dottedtocline{4}{7.0em}{4.1em}} \def\l@subparagraph{\@dottedtocline{5}{10em}{5em}} \@ifundefined{c@section}{\newcounter{section}}{} \@ifundefined{c@chapter}{\newcounter{chapter}}{} \newif\if@mainmatter \@mainmattertrue \def\chaptername{Chapter} \def\frontmatter{% \pagenumbering{roman} \def\thechapter{\@roman\c@chapter} \def\theHchapter{\roman{chapter}} \def\thesection{\@roman\c@section} \def\theHsection{\roman{section}} \def\@chapapp{}% } \def\mainmatter{% \cleardoublepage \def\thechapter{\@arabic\c@chapter} \setcounter{chapter}{0} \setcounter{section}{0} \pagenumbering{arabic} \setcounter{secnumdepth}{6} \def\@chapapp{\chaptername}% \def\theHchapter{\arabic{chapter}} \def\thesection{\@arabic\c@section} \def\theHsection{\arabic{section}} } \def\backmatter{% \cleardoublepage \setcounter{chapter}{0} \setcounter{section}{0} \setcounter{secnumdepth}{2} \def\@chapapp{\appendixname}% \def\thechapter{\@Alph\c@chapter} \def\theHchapter{\Alph{chapter}} \appendix } \newenvironment{bibitemlist}[1]{% \list{\@biblabel{\@arabic\c@enumiv}}% {\settowidth\labelwidth{\@biblabel{#1}}% \leftmargin\labelwidth \advance\leftmargin\labelsep \@openbib@code \usecounter{enumiv}% \let\p@enumiv\@empty \renewcommand\theenumiv{\@arabic\c@enumiv}% }% \sloppy \clubpenalty4000 \@clubpenalty \clubpenalty \widowpenalty4000% \sfcode`\.\@m}% {\def\@noitemerr {\@latex@warning{Empty `bibitemlist' environment}}% \endlist} \def\tableofcontents{\section*{\contentsname}\@starttoc{toc}} \parskip0pt \parindent1em \def\Panel#1#2#3#4{\multicolumn{#3}{){\columncolor{#2}}#4}{#1}} \newenvironment{reflist}{% \begin{raggedright}\begin{list}{} {% \setlength{\topsep}{0pt}% \setlength{\rightmargin}{0.25in}% \setlength{\itemsep}{0pt}% \setlength{\itemindent}{0pt}% \setlength{\parskip}{0pt}% \setlength{\parsep}{2pt}% \def\makelabel##1{\itshape ##1}}% } {\end{list}\end{raggedright}} \newenvironment{sansreflist}{% \begin{raggedright}\begin{list}{} {% \setlength{\topsep}{0pt}% \setlength{\rightmargin}{0.25in}% \setlength{\itemindent}{0pt}% \setlength{\parskip}{0pt}% \setlength{\itemsep}{0pt}% \setlength{\parsep}{2pt}% \def\makelabel##1{\upshape ##1}}% } {\end{list}\end{raggedright}} \newenvironment{specHead}[2]% {\vspace{20pt}\hrule\vspace{10pt}% \phantomsection\label{#1}\markright{#2}% \pdfbookmark[2]{#2}{#1}% \hspace{-0.75in}{\bfseries\fontsize{16pt}{18pt}\selectfont#2}% }{} \def\TheFullDate{2011-12-18 (revised: 18 December 2011)} \def\TheID{\makeatother } \def\TheDate{2011-12-18} \title{An Analytical Review of Orientation Based Concurrency Control Algorithm} \author{}\makeatletter \makeatletter \newcommand*{\cleartoleftpage}{% \clearpage \if@twoside \ifodd\c@page \hbox{}\newpage \if@twocolumn \hbox{}\newpage \fi \fi \fi } \makeatother \makeatletter \thispagestyle{empty} \markright{\@title}\markboth{\@title}{\@author} \renewcommand\small{\@setfontsize\small{9pt}{11pt}\abovedisplayskip 8.5\p@ plus3\p@ minus4\p@ \belowdisplayskip \abovedisplayskip \abovedisplayshortskip \z@ plus2\p@ \belowdisplayshortskip 4\p@ plus2\p@ minus2\p@ \def\@listi{\leftmargin\leftmargini \topsep 2\p@ plus1\p@ minus1\p@ \parsep 2\p@ plus\p@ minus\p@ \itemsep 1pt} } \makeatother \fvset{frame=single,numberblanklines=false,xleftmargin=5mm,xrightmargin=5mm} \fancyhf{} \setlength{\headheight}{14pt} \fancyhead[LE]{\bfseries\leftmark} \fancyhead[RO]{\bfseries\rightmark} \fancyfoot[RO]{} \fancyfoot[CO]{\thepage} \fancyfoot[LO]{\TheID} \fancyfoot[LE]{} \fancyfoot[CE]{\thepage} \fancyfoot[RE]{\TheID} \hypersetup{citebordercolor=0.75 0.75 0.75,linkbordercolor=0.75 0.75 0.75,urlbordercolor=0.75 0.75 0.75,bookmarksnumbered=true} \fancypagestyle{plain}{\fancyhead{}\renewcommand{\headrulewidth}{0pt}} \date{} \usepackage{authblk} \providecommand{\keywords}[1] { \footnotesize \textbf{\textit{Index terms---}} #1 } \usepackage{graphicx,xcolor} \definecolor{GJBlue}{HTML}{273B81} \definecolor{GJLightBlue}{HTML}{0A9DD9} \definecolor{GJMediumGrey}{HTML}{6D6E70} \definecolor{GJLightGrey}{HTML}{929497} \renewenvironment{abstract}{% \setlength{\parindent}{0pt}\raggedright \textcolor{GJMediumGrey}{\rule{\textwidth}{2pt}} \vskip16pt \textcolor{GJBlue}{\large\bfseries\abstractname\space} }{% \vskip8pt \textcolor{GJMediumGrey}{\rule{\textwidth}{2pt}} \vskip16pt } \usepackage[absolute,overlay]{textpos} \makeatother \usepackage{lineno} \linenumbers \begin{document} \author[1]{Sumit Kumar} \author[2]{Ms. Ritu Devi} \affil[1]{ M M University, India} \renewcommand\Authands{ and } \date{\small \em Received: 4 November 2011 Accepted: 3 December 2011 Published: 18 December 2011} \maketitle \begin{abstract} There is an ever-increasing demand for higher throughputs in transaction processing systems leading to higher degrees of transaction concurrency.Concurrency control in Database management systems ensures that database transactions are performed concurrently without violating the data integrity of the database. Thus concurrency control is an essential element for correctness in any system where two database transactions or more, executed with time overlap, can access the same data. There are problems like Deadlock,Livelock and prevention of these problems is vital in concurrency control of distributed database systems.Many techniques have been proposed for managing concurrent execution of transactions in database systems.A new method for concurrency control in distributed DBMS?s,is discussed which will improve system performance by reducing the chances of deadlock and livelock and reducing restart ratio. \end{abstract} \keywords{concurrency, deadlock, timestamp, lock etc.} \begin{textblock*}{18cm}(1cm,1cm) % {block width} (coords) \textcolor{GJBlue}{\LARGE Global Journals \LaTeX\ JournalKaleidoscope\texttrademark} \end{textblock*} \begin{textblock*}{18cm}(1.4cm,1.5cm) % {block width} (coords) \textcolor{GJBlue}{\footnotesize \\ Artificial Intelligence formulated this projection for compatibility purposes from the original article published at Global Journals. However, this technology is currently in beta. \emph{Therefore, kindly ignore odd layouts, missed formulae, text, tables, or figures.}} \end{textblock*} \let\tabcellsep& \section[{INTRODUCTION}]{INTRODUCTION}\par oncurrency control is the activity of coordinating concurrent accesses to a database in a multiuser database management system (DBMS). Concurrency control permits users to access a database in a multiprogrammed fashion while preserving the illusion that each user is executing alone ona dedicated system \hyperref[b1]{[2]}. The main technical difficulty in attaining this goal is to prevent database updates performed by one user from interfering with database retrievals and updates performed by another. The concurrency control problem is exacerbated in a distributed DBMS (DDBMS) because (1) users may access data stored in many different computers in a distributed system, and (2) a concurrency control mechanism at one computer cannot instantaneously know about interactions at other computers. \section[{II.}]{II.} \section[{BACKGROUND OF CONCURRENCY CONTROL METHODS}]{BACKGROUND OF CONCURRENCY CONTROL METHODS}\par Many methods for concurrency control exist \hyperref[b0]{[1]} [4] \hyperref[b4]{[5]}[6] \hyperref[b9]{[8]}[9] \hyperref[b11]{[10]}.The major methods, which have each many variants,are:\par Author ? : Computer Science \& Engg. Department, M M University, India. E-mail : sumit0709@gmail.com Author ? : Computer Science \& Engg. Department, M M University, India. E-mail : ritudevi@rediffmail.com 1. Locking -Locking is a mechanism commonly used to solve the problem of synchronizing access to shared data \hyperref[b7]{[6]}.Controlling access to data by locks assigned to the data.Several types of locks are used in concurrency control such as Binary(1 or 0) locks,Shared/Exclusive locks. each data item has a lock associated with it. Before a transaction T, may access a data item, the scheduler first examines the associated lock. If no transaction holds the lock, then the scheduler obtains the lock on behalf of T,. If another transaction T, does hold the lock, then T, has to wait until T2 gives up the lock. That is, the scheduler will not give T, the lock until T releases it. The scheduler thereby ensures that only one transaction can hold the lock at a time, so only one transaction can access the data item at a time.When a lock is set, other transactions that need to set a conflicting lock are blocked until the lock is released, usually when the transaction is completed. The more transactions that are running concurrently, the greater the probability that transactions will be blocked, leading to reduced throughput and increased response times.One variation of basic locking protocol that ensure serializability is two phase locking protocol \hyperref[b11]{[10]}.This protocol requires that each transaction issue lock and unlock requests in two phases:\par 1. Growing phase -A transaction may obtain locks,but may not release lock. 2. Shrinking phase -A transaction may release locks,but may not obtain any new locks.\par A method called optimistic method with dummy locks is also there for concurrency control in distributed databases. The advantage of using dummy locks is that although they are long-term locks, they do not block the execution of transactions in any way[] 2. Serialization graph checking (also called Serializability, or Conflict, or Precedence graph checking) -Although two phase locking ensure serializability,they may lead to a deadlock.Deadlock occurs when each transaction T in a set of two or more transaction is waiting for some item that is loked by some other transaction T1 in the set. There are otherways one could enforce serializability as well.Deadlock can be precisely detected by constructing a directed graph called wait-for-graph.The nodes of WFG are labelled with active transaction names.In a WFG there exist an edge from Ti to Tj iff transaction Ti is waiting for transaction Tj to release some lock.Is there 3. Timestamp ordering (TO) -In an alternative approach to locking is use of timestamps \hyperref[b3]{[4]} \hyperref[b11]{[10]}. Ordered timestamps are assigned to transactions, and controlling or checking access to data by timestamp order. The general idea is to give each transaction a "timestamp" which indicates when the transaction began (serial number or system time). To generate timestamp values,transaction manager can use system clock value i.e TS(T) is equal to value of clock when T has entered the system.Alternatively,the transaction manager can use a counter that is incremented after a new timestamp has been assigned.To implement this scheme,the timestamp ordering algorithm associates with each data item X two timestamp values:\par A. write\textunderscore TS(X) -the maximum timestamp value of a transaction that successfully executed write\textunderscore item(X). B. read\textunderscore TS(X) -the maximum timestamp value of a transaction that successfully executed read\textunderscore item(X).\par 1. When T tries to write(X)\par ? if Read\textunderscore TS(X) > TS(T) or Write\textunderscore TS(S) > TS(T) Intuition: X has been read or written by a "later" transaction ? Abort T else ? Execute and set write-TS(X) = TS(T) \section[{When T tries to read(X)}]{When T tries to read(X)}\par ? if Write\textunderscore TS(X) > TS(S) X was written by a "later" transaction ? Abort T else ? Execute and update read-TS(X) \section[{III. RULES FOR A DATABASE TRANSACTION}]{III. RULES FOR A DATABASE TRANSACTION}\par A database transaction is a unit of work, typically encapsulating a number of operations over a database (e.g., reading a database object, writing, acquiring lock, etc.).Every database transaction obeys the following rules:\par ? Atomicity -Either the effects of all or none of its operations remain ("all or nothing") when a transaction is completed (committed or aborted respectively). In other words, to the outside world a committed transaction appears (by its effects on the database) to be indivisible, atomic, and an aborted transaction does not leave effects on the database at all, as if never existed. transactions must persist through crashes (typically by recording the transaction's effects and its commit event in a non-volatile memory).\par IV. \section[{REQUIREMENTS FOR DATABASE TRANSCATION}]{REQUIREMENTS FOR DATABASE TRANSCATION}\par Every database transaction should fullfill following requirements:\par ? Safety Property: The safety property states that at any point of time, only one transaction can access the data. ? Liveness Property: This property states the absence of deadlock and starvation. Two or more transactions should not endlessly wait for a particular object which will never arrive. In addition, a transaction must not wait indefinitely to access an object while other transactions are repeatedly acquiring the same. ? Fairness: Fairness property states that each transaction should get chance to access an object. In concurrency control algorithms, the fairness property generally means the requests are executed in the order of their arrival (time is determined by a logical clock) in the system. \section[{V. NEED FOR CONCURRENCY CONTROL}]{V. NEED FOR CONCURRENCY CONTROL}\par If transactions are executed serially, i.e. sequentially with no overlap in time, no transaction concurrency control required.However if concurrent transactions with interleaving operations are allowed in an uncontrolled manner, some unexpected, undesirable result may occur. Here are some typical examples:\par 1. The lost update problem: when a transaction writes a new value of a data-item on top of a first value written by a first concurrent transaction, and the first value is lost to other transactions running concurrently which need to read the first value.\par 2. The dirty read problem: when Transactions read a value written by a transaction that has been later aborted. This value disappears from the database upon abort, and should not have been read by any transaction ("dirty read"). The reading transactions end with incorrect results. 3. The incorrect summary problem: While one transaction takes a summary over the values of all the instances of a repeated data-item, a second transaction updates some instances of that data-item. The resulting summary does not reflect a correct result for any precedence order between the two transactions (if one is executed before the other), but rather some random result, depending on the timing of the updates, and whether certain update results have been included in the summary or not.\par VI. \section[{REVIEW OF TIMESTAMP AND ORIENTATION BASED CURRENCY CONTROL ALGORITHM}]{REVIEW OF TIMESTAMP AND ORIENTATION BASED CURRENCY CONTROL ALGORITHM}\par In the concept of timestamp ordering \hyperref[b3]{[4]}[7], transaction timestamp TS(T) is a unique identifier assigned to each transaction based on the order in which transaction are started.Hence if transaction T 1 starts before transaction T 2 then TS(T1)