
\documentstyle[11pt]{article}




\textwidth = 38.0pc
\textheight = 50.0pc
\oddsidemargin = 0pc
\evensidemargin = 0pc

%%%%%  Definitions file




\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}

\newtheorem{definition}{Definition}[section]
\newtheorem{assumption}[definition]{Assumption}
\newtheorem{remark}[definition]{Remark}
\newtheorem{example}[definition]{Example}

\newcommand{\blackslug}{\penalty 1000\hbox{
    \vrule height 8pt width .4pt\hskip -.4pt
    \vbox{\hrule width 8pt height .4pt\vskip -.4pt
          \vskip 8pt
          \vskip -.4pt\hrule width 8pt height .4pt}
    \hskip -3.9pt
    \vrule height 8pt width .4pt}}
\newenvironment{proof}{\noindent {\sc proof.}\newline}{\noindent\blackslug}

\newenvironment{claim}
 {\noindent {\bf Claim}}{}
\newenvironment{claimproof}
                {\noindent {\bf proof of claim.}\newline}{\noindent
                                             {\bf end of proof of claim}}


\def\mybox#1#2{\begin{center}
        \fbox{\begin{minipage}{#1}#2\end{minipage}}
        \end{center}}
\newenvironment{zboxp}[1]{\mybox{0.95\textwidth}{#1}}{}
\newenvironment{zprog}[1]{
		\begin{tabbing}
                mmm\=mm\=mm\=m\=m\=m\=m\=m\=m\=mmm\=mm\=mm  \kill
                #1 \end{tabbing}
                }{}
\newenvironment{zplainprog}[1]{
                \begin{center}
                \begin{minipage}{0.95\textwidth}{
                \begin{zprog}{#1
                }\end{zprog}
                }\end{minipage}
                \end{center}
                }{}
\newenvironment{zboxprog}[1]{
                \begin{zboxp}{
                \begin{zprog}{#1
                }\end{zprog}
                }\end{zboxp}
                }{}


%% Commands for printing (or non printing of parts)
\newcommand{\skipportion}[1]{
 #1
}
%% Put a single '%' at beginning of next line if these portions are
%% wanted
%\renewcommand{\skipportion}[1]{}

%% Commands for printing (or non printing of parts)
\newcommand{\oldversion}[1]{#1}
%% Put a single '%' at beginning of next line if these portions are
%% wanted
\renewcommand{\oldversion}[1]{}

\newcommand{\e}{\mbox{$\epsilon$}}
%%%%%%%%%%%%%%%%%%%startpoint %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\title{2Q: a low overhead 
high performance buffer management replacement algorithm
	 \footnote{
                Supported by
                U.S. Office of Naval Research \#N00014-91-J-1472 and
                \#N00014-92-J-1719,
                U.S. National Science Foundation grants
                \#CCR-9103953 and IRI-9224601. \newline
		$\mbox{\ }\;\;\;{}^{\dag}$ 
		Authors' e-mail addresses : 
		ted@squall.cis.ufl.edu and
                 shasha@cs.nyu.edu
}}


\author{ Theodore\ Johnson \quad\quad\quad\quad Dennis\ Shasha \\
\\
		Courant Institute, New York University \\
		New York, NY 10012.}


\date{{\today}}



\maketitle
\begin{abstract}
\sl



In a path-breaking paper last year 
Pat and Betty O'Neil and Gerhard Weikum proposed a self-tuning
improvement to the Least Recently Used (LRU) buffer management
algorithm\cite{OOW-93}.
Their improvement is called LRU/k and advocates giving priority\footnote{
Throughout this paper,
if page p has more priority than page p'
then p' will be replaced before p.
}
to buffer pages based on the kth most recent access.
(The standard LRU algorithm is denoted LRU/1 according to this 
terminology.)
If P1's kth most recent access is more more
recent than P2's, then P1 will be replaced after P2.
Intuitively, LRU/k for k > 1 is a good strategy, because 
it gives low priority
to pages that have been scanned or to pages that  belong
to a big randomly accessed file (e.g., the account file in TPC/A).
They found that LRU/2 achieves most of the advantage of their method.

The one problem of their method is the processor overhead
to maintain it.
In contrast to LRU, each access requires log N work to a priority
queue each time a page is accessed where N is the number of pages in
the buffer.

Question: is there an easier way (constant overhead per access
as in LRU) with similar performance to LRU/2?

Answer: Yes. 

Our ``Two Queue'' algorithm (hereafter 2Q)
has constant time overhead, performs as well
as LRU/2, and requires no tuning.
These results hold for real (DB2 commercial) traces
as well as simulated ones.
Based on these experiments, we estimate that 2Q
will provide a 5-10\% improvement for most 
applications and more for some.
We give some analytic reasons for this result.

\end{abstract}

\section{Background}


The cost of fetching a page from disk is approximately a factor
of 1000 greater 
than the cost of fetching it from a RAM buffer.
For this reason, better buffer management can significantly
improve the throughput and response time of any data-intensive system.


Until the early 80's, the least recently used buffer replacement
algorithm (replace the page that was least
recently touched) was considered to be the one to use in all cases.
Indeed, the theoretical community blessed it by showing that LRU
never replaces more than a factor f
as many elements as an optimal
clairvoyant algorithm (where f is the size of the buffer)
\cite{ST-85}.
\footnote{A companion result is that LRU on a buffer
of size B will never
page more than twice as much as a clairvoyant algorithm
on a buffer half the size of B}
But factors this large can heavily influence the behavior of a database
system.
At least since Stonebraker's classic article on why the
UNIX of his era was no good for operating systems 
\cite{S-81}.
Commercial database systems have adopted hybrdid buffer
management schemes --- based on LRU, but not pure LRU.
For example, most commercial database 
systems discard a page resulting from a file scan as soon as the
scan accesses the next page.
Following Stonebraker, they observe that there is no point
in keeping a recently accessed scanned page, since the
scan won't use it again.
(LRU by contrast would give highest priority to the
most recently scanned page.)

The trouble with such hybrid schemes is that they
partition the buffer into smaller buffers
(e.g. for sorts, for compiled queries, and possibly for scans)
reducing the effective available space, say, when one buffer is
not fully utilized.
Also, they don't capture all cases.
For example, 
LRU will give high priority to 
recently accessed random data pages accessed via an index
(e.g. account file pages in TPC/A) even though these pages too
are unlikely to be accessed again.

The O'Neil-Weikum paper provided
a welcome alternative to buffer balkanization.
They suggested a more-or-less self-tuning full buffer
variant of LRU with many of the same properties as the
hybrid schemes.
The essence of their scheme is that a page should
not obtain buffer privileges merely because it is accessed once.
What's important is whether it has been popular over time.
The version they advocate --- called LRU/2 --- replaces
the page whose {\bf penultimate} (second-to-last) access
is least recent among all penultimate accesses.

In order to be able to find that page quickly, they organize pointers to 
the buffer pages in a priority queue based
on penultimate access time.
The operations are deletemin
to get the page to replace and a promotion scheme to move a page
that has been accessed to a new place in the queue.
Priority queue operations 
entail a time complexity that grows
with the log of the size of the buffer.

They examine (i) a synthetic workload with references
to two pools of pages one for an index and one for data pages;
(ii) a synthetic workload with random references based on a Zipfian
distribution of reference frequencies obeying
the 80-20 rule on 1000 poassible pages; and (iii) a commercial
on-line transaction processing workload derived from a Swiss bank.
In every case, they show a significant improvement over LRU,
sometimes as high as 40\%.

One delicate aspect of their algorithm is that there are two
tuning parameters.
The first is the {\em Correlated Reference Period.}
This is an amount of time during which a page is retained
in the buffer once it has been accessed.
It is retained to allow efficient imminent access
from the same process (so-called ``correlated''
accesses).
At the same time, multiple accesses within a correlation period
count only as a single access from the point of view of replacement priority.
The net effect is that if a page is referenced several times within
a correlated reference period and then isn't accessed for a while,
it will have low buffer priority.
that may be of interest for many process 
For example, even a scanned page is not accessed once exactly.
The second tuning parameter is the {\em Retained Information Period}
which is the length of time a page's access history is remembered
after it is ejected from the buffer.
The authors recommend 200 seconds.

Since we spend a lot of time with operating system people
whose favorite data structure is a linked list with constant
time operations and no tuning, we have looked for and found a variant of LRU/2
having comparable performance results, 
constant time overhead (implementable on a list), and 
requiring no tuning.


\section{2Q Algorithm Description}

There are two queues: an accessed-once queue (the A1 queue)
and an accessed-many queue (the Am queue) both of fixed size.
In its simplest form, the algorithm works as follows whenever 
a page is accessed.

{\bf Simplified 2Q}

\begin{zplainprog}{
\rule{15cm}{0.5pt}
\\
if p is on the Am queue
\\
then
\\
\> put p on the front of the Am queue
\\
\> /* just like LRU */
\\
else if p is on the A1 queue
\\
then
\\
\> remove p from the A1 queue 
\\
\> put p on the front of the Am queue
\\
else /* first access we know about concerning p */ 
\\
\> /* find a free page slot for p */ 
\\
\> if there are free page slots available
\\
\> then
\\
\>\> put p in a free page slot 
\\
\> else if A1's size is above a certain tunable threshold then
\\
\>\> delete from the tail of A1
\\
\>\> put p in the freed page slot
\\
\> else 
\\
\>\> delete from the tail of Am
\\
\>\> put p in the freed page slot
\\
\> end if
\\
\> put p on the front of the A1 queue
\\
end if
}\end{zplainprog}


Thus A1 is a FIFO queue and Am is an LRU queue
but for second and subsequent accesses.
If a page is accessed once and never again, it will be put
on A1 and will tend to be deleted earlier than an older page that
had been repeatedly accessed and that was therefore on A2.
There are a few problems however: if a page is accessed several
times in rapid succession it gets promoted to Am even
though it should not.
Second, it is necessary to figure out the size of A1
and the threshhold.
Finally, if the access patterns change abruptly,
the pages accessed earlier will retain priority for a long time
(i.e., the LRU algorithm has hysteresis).

{\bf 2Q, Full Version} 

To resolve the above problems we
partition A1 into A1in and A1out.
The most recent first accesses will be in the memory (up to the
threshold), but then older first accesses will be thrown out
of memory but remembered in A1out.
(Remembering a page address requires only a few bytes (fewer than 10).)
Given a buffer size B,
one divides it into Am, A1in (of maximum size Kin 
and minimum size 1), and A1out (of maximum size Kout).
Fixing these parameters is one goal of this paper
though our current best guess is: Kin should be 1/10 of the buffer
and Kout should hold identifiers for as many pages as would
fit on 4/10 of the buffer.
{\em Ted: Please change this with our current best guess.}


\begin{zplainprog}{
\rule{15cm}{0.5pt}
\\
/* If there is space, we give it to X
\\
 *if there is no space, we free a page slot to make room for page X
\\
*/
\\
reclaimfor(page X) 
\\
begin
\\
\> if there are free page slots then
\\
\>\> put X into a free page slot
\\
\> else if(|A1in|>Kin)
\\
\>\> page out the tail of A1, call it Y
\\
\>\> add identifier of Y to the head of A1out
\\
\>\> if(|A1out|>Kout)
\\
\>\>\> remove  identifier of Y from the tail of A1out
\\
\>\> end if
\\
\>\> put X into the reclaimed page slot
\\
\> else
\\
\>\> page out the tail of Am, call it Y
\\
\>\> // do not put it on A1out; it hasn't been accessed for a while
\\
\>\> put X into the reclaimed page slot
\\
\> end if
\\
end
\\
}\end{zplainprog}


\begin{zplainprog}{
\rule{15cm}{0.5pt}
\\
On accessing a page X : 
\\
begin
\\
\> if X is in Am then
\\
\>\> move X to the head of Am
\\
\> else if (X is in A1in) then
\\
\>\> remove X from A1in
\\
\>\> add X to the head of AM
\\
\> else if (X is in A1out) then
\\
\>\> reclaimfor(X)
\\
\>\> add X to the head of AM
\\
\> else // X is in no queue
\\
\>\> reclaimfor(X)
\\
\>\> add X to the head of A1in
\\
\> end if
\\
end
\\
}\end{zplainprog}


Note: We don't want the A1out buffer to be infinitely large,
because then the algorithm will behave like lru over time.
Even  the least frequently accessed page will be accessed
every once in a while and accessing it again will then
put the page into the lru queue.


\section{Experimental Results}

In all our experiments, we tried to represent LRU/2 as fairly as possible,
but it was difficult to model the tunables of that algorithm exactly.
The LRU/2
algorithm keeps a page in the buffer for a grace period (the Correlated
Reference Period)
and considers a second access to be a legitimate second access
only if it arrived after that period.
It also remembers pages that have been ejected for 200 seconds.
We simulated these tunables as follows. 
{\em Ted: please fill in, saying how we approximated these tunables.
Part of it, I think, is that
The Correlated Reference Period becomes the time it takes
for A1in distinct pages to be referenced. 
}

\subsection{Simulation Experiments}

The experiments in this subsection are from artificially generated traces.
They give some intuition about the behavior of LRU, LRU/2, and 2Q,
but do not necessarily represent a  real application's behavior.

{\bf Zipf Distributions}

These two figures compare the performance of LRU, LRU/2, and 2Q on a 
Zipfian input distribution with parameter 0.5 and 0.8 respectively.
{\em Ted: Please give a parenthetic remark, saying what these 
parameters represent, e.g. 80-20 rule}.
These obey the independent reference model\cite{CD-73}, 
i.e., each
page has a single stationary probability to be accessed at any point in time.

According to the reference, the algorithm called A0 is optimal in
this situation.
A0 always replaces the page whose probability of 
access is lowest.

\begin{figure}
\vspace{3.8in}
\special{psfile=zalgcp5.eps  hscale=60 vscale=60 hoffset=0 voffset=-40}
\caption{Zipf input comparison with parameter 0.5}
\label{fig1}
\end{figure}

\begin{figure}
\vspace{3.8in}
\special{psfile=zalgcp8.eps  hscale=60 vscale=60 hoffset=0 voffset=-40}
\caption{Zipf input comparison with parameter 0.8}
\label{fig2}
\end{figure}


{\bf Mixed Zipf/Scans}

These figures represent experiments where 1/3 of the references
are scans (so one expects a zero hit ratio for these).
The remaining references follow a Zipf distribution with parameters
0.5 or 0.8 respectively.
{\em Ted: Please say how you set A1in and A1out.} 

\begin{figure}
\vspace{3.8in}
\special{psfile=scan10_5.eps  hscale=60 vscale=60 hoffset=0 voffset=-40}
\caption{1/3 Scan Input Mixed with Zipf Input Having Parameter 0.5 }
\label{fig3}
\end{figure}

\begin{figure}
\vspace{3.8in}
\special{psfile=scan10_8.eps  hscale=60 vscale=60 hoffset=0 voffset=-40}
\caption{1/3 Scan Input Mixed with Zipf Input Having Parameter 0.8 }
\label{fig4}
\end{figure}


{\bf Online Transaction Processing-style Index Accesses}

A nice observation of the LRU/2 paper is that randomly accessed
data pages get an excessively high priority within the buffer.
They posited an example where there are 100 index pages
and 1000 data pages.
{\em Ted: How big is the buffer?}
They then showed that LRU/2 gives priority to the index pages
as it should.
This figure shows that 2Q does so as well.
{\em Ted: Please say how you set A1in and A1out.} 

\begin{figure}
\vspace{3.8in}
\special{psfile=twopool.eps  hscale=60 vscale=60 hoffset=0 voffset=-40}
\caption{Behavior of Algorithms on Index Accesses to Data Pages}
\label{fig5}
\end{figure}

\subsection{Experiments on Real Data}

Colleagues at IBM and UNIX System Laboratories
kindly supplied traces of a database application and of hits
on program text, respectively.\footnote{
We attempted to obtain the Swiss Bank traces used in the LRU/2 paper,
but Gerhard Weikum informed us that the bank considers these to be secret.}
For these experiments A1in and A1out were set to the following values
{\em Ted: Please fill in }.
We arrived at these settings based on the simulation studies
described in the next section. 
Since the differences among the various algorithms sometimes fall
below 5\% we represent these results with tables.

{\bf Trace Data from a DB2 Commercial Application}

{\em Ted: Please give table and any other relevant parameters}

{\bf Trace Data from Program Text Accesses of a Windowing Application}

{\em Ted: Please give table and any other relevant parameters}

\section{Setting the Parameters}

Recall that the 2Q algorithm has a queue called Am for pages hit
at least two and possibly more times, a queue A1in that stores pages
that have been hit only once (in recent memory), 
and a queue A1out that stores records
of pages that have been hit only once but not the pages themselves. 
To gain intuition about these schemes, we performed the following 
experiments.

{\bf The Size of A1in}

For Zipf distributions, a large A1out helps and
a small/large A1in helps. 
{\em Ted: Please comment}

\begin{figure}
\vspace{3.8in}
\special{psfile=irlg5-2q.eps  hscale=60 vscale=60 hoffset=0 voffset=-40}
\caption{The Effect of the Size of A1in on the Hit Rate, assuming Zipf 0.5}
\label{fig6}
\end{figure}

\begin{figure}
\vspace{3.8in}
\special{psfile=irlg8-2q.eps  hscale=60 vscale=60 hoffset=0 voffset=-40}
\caption{The Effect of the Size of A1in on the Hit Rate, assuming Zipf 0.8}
\label{fig7}
\end{figure}

{\bf Responsiveness}

To investiate the responsiveness of this algorithm
to changes in locality, we ran the algorithms for
1,000,000 zipf references, then made a random permutation of the
probabilities assigned to the items (thus affecting a change in locality).
This chart shows hit rates as a function of time after the permutation.
The larger A1in is the better the responsiveness up to
|A1in| = |AM|/2.
{\em Ted: Was A1in or A1out big --- 
can we get responsiveness from A1out alone?}
We include LRU/2 as a benchmark against which to judge responsiveness
(LRU/2 is quite responsive).

\begin{figure}
\vspace{3.8in}
\special{psfile=lc5_20.eps  hscale=60 vscale=60 hoffset=0 voffset=-40}
\caption{Responsiveness and the Size of A1, with Zipf 0.5}
\label{fig8}
\end{figure}

\begin{figure}
\vspace{3.8in}
\special{psfile=lc8_20.eps  hscale=60 vscale=60 hoffset=0 voffset=-40}
\caption{Responsiveness and the Size of A1, with Zipf 0.8}
\label{fig9}
\end{figure}

\subsection{Theoretical Setting for 2Q Parameters}

On a static reference stream, the algorithm A0\cite{CD-73} is optimal.
That algorithm effectively locks the B-1 data items with the 
highest access probability into memory, and use the last buffer to service page
faults.
LRU works well because it tends to keep hot items near the front of
the queue, removing the cold ones.
However, LRU is too trusting.  
It will admit a cold item into the
buffer on the first hit
and kick out a hotter item to make room.
Like LRU/2,
we would like to filter the items that are admitted to the buffer,
in order to ensure that we do not remove a hot page to make room for a cold
page.

To do this, we can look at the inter-reference times.
If a data item has a short (but not too short)
inter-reference time, we can
feel confident that it is a hot item, and thus feel confident that
we will not remove a hot page from the buffer to make room for
a cold page.


The A1in queue acts as a filter.  An item will be admitted to the
{\em Ted: Can you integrate A1out into this discussion?}
LRU queue only if it receives a second reference before being
removed from the A1in queue.
Suppose that the miss rate is $m$, and there are $f$ spaces
available in the A1in area.
{\em Ted: I take it that the miss rate is 
the fraction of page accesses that are misses.
Please say so.}
We have observed that the A1in queue is usually full
(the miss rate is much greater than the A1in hit rate).
Thus, an item is admitted to the LRU buffer if it receives
a second reference within $f/m$ references.
Suppose that item $i$ is referenced with probability $p_{i}$.
The probability that item $i$ gains admission to the LRU buffer
on the $k^{\rm th}$ reference after entering A1in is 
$p_{i}(1-p_{i})^{k}$.
{\em Ted: should the exponent be k-1?}
Therefore,
\begin{eqnarray*}
p_{accept}=&\sum_{i=k}^{f/m}p_{i}(1-p_{i})^{k}
=&(1-p_{i})^(f/m)+1
\end{eqnarray*}
{\em Ted: is paccept defined anywhere (I assume
it is the probability that i will be accepted)? Also, still k-1 in exponent.
Also, shouldn't the sum start at 1, i.e. k=1 rather than i=k?}


The probability of admission is close to one for large values
of $p_{i}$, then drops off rapidly to zero when $p_{i}$ becomes small.
Thus, the A1in queue does indeed act as a filter, admitting hot
items into the queue and ejecting cold items.

We can identify the A1in filter's cutoff hotness as the reference probability
at which $p_{accept}=1/2$.
{\em Ted: say why this is a good definition}
So, we solve
\begin{eqnarray*}
(1-p_{i})^(f/m)+1=1/2
\end{eqnarray*}
for the value of interest.  Given $f$ and $m$, we can ask for the
access probability of the coldest item which has a 50\% chance of being
admitted to the LRU buffer.  Then
\begin{eqnarray*}
p_{cutoff} =&1-(1/2)^{m/f} \\
\approx & m \ln(2)/f
\end{eqnarray*}
(The approximation is by taking a Taylor series.)

We note that the A1in filter is somewhat self-adjusting.
When the miss rate is high, $p_{cutoff}$ is relatively high,
so the queue will admit only the hottest items.
When the miss rate is low, $p_{cutoff}$ is relatively small,
so that the only moderately hot items that should be admitted
to the queue have a chance of gaining admission.

Next, given $p$ and $m$, we can ask what $f$ gives
$p_{accept}=.5$.
We find that
\begin{eqnarray*}
f_{crit}=&-\frac{m\ln(2)}{\ln(1-p)} \\
&\approx m\ln(2)/p
\end{eqnarray*}

The approximation follows because $\ln(1-p) \approx -p$.
If we know the access probability of the coldest item that
should be in the buffer, we can solve for $f$.
However, we typically do not know the access probabilities ahead of
time (otherwise we'd use the $A_{0}$ algorithm).
For a rough estimate of $f$, let us find $f_{crit}$ that will
admit an item of average hotness to the buffer.
If the miss rate is $m$ and there are $B$ page slots,
the average access probability for an item in the buffer
is $(1-m)/B$.  Substituting for $p$ in the formula for $f_{crit}$,
we find that
\begin{eqnarray*}
f_{approx}=\frac{\ln(2) m B}{1-m}
\end{eqnarray*}

Since this formula requires an a-priori estimate of the miss rate,
it is of little use in practical tuning.
However, it delivers an intuition about determining the
proper size of A1, namely that the size of A1 should be a fixed
fraction of the size of the buffer, $B$.
In this paper, we always discuss the size of A1 as a fraction
of the size of $B$,
and we run simulation experiments to determine
the fraction.
{\em Ted: We'd now like to say something like.
"Over a wide variety of applications, the following value of A1in
performs well."

Also, we've said nothing about A1out so far.
We know it can't be infinite because then pages will
instantly get promoted.
}




\section{Conclusion}

2Q is a good buffering algorithm (giving a 5-20\% improvement
over LRU for a wide variety of applications
and buffer sizes), having constant time  overhead,
and requiring little or no tuning.
It works well for the same intuitive reason that LRU/2 works well:
it bases buffer priority on sustained popularity rather than on a  single
access.
We have given some analytic reasons for its good behavior.


\section{Acknowledgments}

Many thanks to
Ted Messinger of IBM and Steve Pendergrast of UNIX System
Laboratories for supplying us with real data.
Thanks also to Gerhard Weikum, Pat and Betty O'Neil for friendly
discussions and program code --- would that all algorithmic
competitions were so civil.



\newcommand{\etalchar}[1]{$^{#1}$}
\bibliographystyle{alpha}
\begin{thebibliography}{110}

\bibitem{CD-73}
{\sc E.G. Coffamn and P.J. Denning}
\newblock{\bf Operating System Theory}
\newblock{\em Prentice-Hall}, 1973

\bibitem{OOW-93}
{\sc Elizabeth J. O'Neil, Patrick E. O'Neil, and Gerhard Weikum}
\newblock{The LRU-K Page Replacement Algorithm for Database Disk Buffering}
\newblock{Proceedings of the 1993 ACM Sigmod International Conference
on Management of Data, June 1993 pp. 297-306}

\bibitem{ST-85}
{\sc Daniel D. Sleator and Rober T. Tarjan}
\newblock{Amortized Efficiency of List Update and Paging Rules}
\newblock{\em Communications of the ACM}, Feb. 1985, vol. 28, no. 2, pp. 202-208

\bibitem{S-81}
{\sc Michael Stonebraker} 
\newblock{Operating System Support for Database Management}
\newblock{\em Communications of the ACM}, vo. 24, no. 7, July 1981, pp. 412-418.
\end{thebibliography}


\end{document}
