Explore topic-wise InterviewSolutions in Current Affairs.

The centralized approach has the problem of a possible BOTTLENECK at the central site and the problem of electing a new central site if it goes down. The distributed approach has the problem that many messages must be exchanges to KEEP the system fair, or ONE site can get ahead of all other sites and DOMINATE the DATABASE.

The centralized approach has the problem of a possible bottleneck at the central site and the problem of electing a new central site if it goes down. The distributed approach has the problem that many messages must be exchanges to keep the system fair, or one site can get ahead of all other sites and dominate the database.

Consider the balance in an account, replicated at N sites. Let the current balance be $100 – consistent across all sites. Consider TWO transactions T1 and T2 each depositing $10 in the account. Thus the balance would be $120 after both these transactions are EXECUTED. Let the transactions execute in sequence: T1 first and then T2. Suppose the copy of the balance at one of the sites, say s, is not consistent – due to lazy replication strategy – with the primary copy after transaction T1 is executed and let transaction T2 read this copy of the balance. One can see that the balance at the primary SITE would be $110 at the END.

Consider the balance in an account, replicated at N sites. Let the current balance be $100 – consistent across all sites. Consider two transactions T1 and T2 each depositing $10 in the account. Thus the balance would be $120 after both these transactions are executed. Let the transactions execute in sequence: T1 first and then T2. Suppose the copy of the balance at one of the sites, say s, is not consistent – due to lazy replication strategy – with the primary copy after transaction T1 is executed and let transaction T2 read this copy of the balance. One can see that the balance at the primary site would be $110 at the end.

In remote backup systems all TRANSACTIONS are performed at the primary site and the data is replicated at the remote backup site. The remote backup site is kept synchronized with the updates at the primary site by sending all LOG records. Whenever the primary site fails, the remote backup site takes over processing.

The distributed systems OFFER GREATER availability by having multiple copies of the data at different sites whereas the remote backup systems offer lesser availability at lower cost and execution overhead.

In a distributed system, TRANSACTION code runs at all the sites whereas in a remote backup system it runs only at the primary site. The distributed system transactions follow two-phase commit to have the data in consistent state whereas a remote backup system does not followtwo-phase commit and avoids related overhead.

In remote backup systems all transactions are performed at the primary site and the data is replicated at the remote backup site. The remote backup site is kept synchronized with the updates at the primary site by sending all log records. Whenever the primary site fails, the remote backup site takes over processing.

The distributed systems offer greater availability by having multiple copies of the data at different sites whereas the remote backup systems offer lesser availability at lower cost and execution overhead.

In a distributed system, transaction code runs at all the sites whereas in a remote backup system it runs only at the primary site. The distributed system transactions follow two-phase commit to have the data in consistent state whereas a remote backup system does not followtwo-phase commit and avoids related overhead.

Autonomy is the AMOUNT of CONTROL a single site has over the local database. It is important because users at that site want quick and correct access to local data items. This is especially true when one considers that local data will be most frequently accessed in a database. Transparency hides the distributed NATURE of the database. This is important because users should not be required to know about LOCATION, replication, fragmentation or other implementation aspects of the database.

Autonomy is the amount of control a single site has over the local database. It is important because users at that site want quick and correct access to local data items. This is especially true when one considers that local data will be most frequently accessed in a database. Transparency hides the distributed nature of the database. This is important because users should not be required to know about location, replication, fragmentation or other implementation aspects of the database.

REPLICATION is USEFUL when there are MANY read-only transactions at different SITES wanting access to the same data. They can all execute QUICKLY in parallel, accessing local data. But updates become difficult with replication. Fragmentation is useful if transactions on different sites tend to access different parts of the database.

Replication is useful when there are many read-only transactions at different sites wanting access to the same data. They can all execute quickly in parallel, accessing local data. But updates become difficult with replication. Fragmentation is useful if transactions on different sites tend to access different parts of the database.

Data transfer on a local-area NETWORK (LAN) is much faster than on a wide-area network (WAN). Thus replication and fragmentation will not increase THROUGHPUT and speed-up on a LAN, as much as in a WAN. But EVEN in a LAN, replication has its uses in increasing reliability and AVAILABILITY.

Data transfer on a local-area network (LAN) is much faster than on a wide-area network (WAN). Thus replication and fragmentation will not increase throughput and speed-up on a LAN, as much as in a WAN. But even in a LAN, replication has its uses in increasing reliability and availability.

1. With fragmentation transparency, the user of the system is unaware of any fragmentation the system has IMPLEMENTED. A user MAY formulate queries against global relations and the system will perform the necessary transformation to generate CORRECT output.
2. With replication transparency, the user is unaware of any replicated data. The systemmust prevent inconsistent operations on the data. This requires more complex concurrency control algorithms.
3. LOCATION transparencymeans the user is unaware of where data are stored. The system must route data REQUESTS to the appropriate sites.

• A distributed database allows a user convenient and transparent access to data which is not stored at the site, while allowing each site CONTROL over its own local data. A distributed database can be made more reliable than a centralized system because if one site fails, the database can CONTINUE FUNCTIONING, but if the centralized system fails, the database can no longer continue with its normal operation. Also, a distributed database allows PARALLEL execution of queries and possibly splitting one query into many parts to increase throughput.
• A centralized system is easier to design and implement. A centralized system is CHEAPER to operate because messages do not have to be sent.

With the central server, each SITE does not have to remember which site to contact when a particular data item is to be requested. The central server alone needs to remember this, so data items can be moved AROUND easily, depending on which sites access which items most frequently.Other house-keeping TASKS are also centralized rather than distributed, making the system easier to DEVELOP and maintain. Of course there is the disadvantage of a total shutdown in case the server becomes unavailable. Even if it is running, it may become a bottleneck because every request has to be routed via it.

With the central server, each site does not have to remember which site to contact when a particular data item is to be requested. The central server alone needs to remember this, so data items can be moved around easily, depending on which sites access which items most frequently.Other house-keeping tasks are also centralized rather than distributed, making the system easier to develop and maintain. Of course there is the disadvantage of a total shutdown in case the server becomes unavailable. Even if it is running, it may become a bottleneck because every request has to be routed via it.

In a distributed system, all the SITES TYPICALLY run the same database management software, and they share a global schema. Each site provides an ENVIRONMENT for EXECUTION of both global transactions INITIATED at remote sites and local transactions. The system described in the question does not have these properties, and hence it cannot qualify as a distributed database.

In a distributed system, all the sites typically run the same database management software, and they share a global schema. Each site provides an environment for execution of both global transactions initiated at remote sites and local transactions. The system described in the question does not have these properties, and hence it cannot qualify as a distributed database.

Increasing contention for shared resources prevents linear scale-up with increasing parallelism. In a shared MEMORY system, contention for memory (which implies bus contention) will result in falling scale-up with increasing parallelism. In a shared disk system, it is contention for disk and bus access which affects scale-up. In a shared-nothing system, inter-process COMMUNICATION overheads will be the MAIN impeding factor. Since there is no shared memory, acquiring locks, and other activities requiring message PASSING between processes will take more time with increased parallelism.

Increasing contention for shared resources prevents linear scale-up with increasing parallelism. In a shared memory system, contention for memory (which implies bus contention) will result in falling scale-up with increasing parallelism. In a shared disk system, it is contention for disk and bus access which affects scale-up. In a shared-nothing system, inter-process communication overheads will be the main impeding factor. Since there is no shared memory, acquiring locks, and other activities requiring message passing between processes will take more time with increased parallelism.

SINCE the part which cannot be parallelized takes 20% of the total RUNNING time, the best speed up we can HOPE for has to be less than 5.

Since the part which cannot be parallelized takes 20% of the total running time, the best speed up we can hope for has to be less than 5.

With increasing SCALE of operations, we expect that the number of transactions submitted per unit time increases. On the other hand, we wouldn’t expect most of the individual transactions to grow LONGER, nor would we require that a given TRANSACTION should execute more quickly now than it did before. Hence transaction scale-up is the most RELEVANT measure in this SCENARIO.

With increasing scale of operations, we expect that the number of transactions submitted per unit time increases. On the other hand, we wouldn’t expect most of the individual transactions to grow longer, nor would we require that a given transaction should execute more quickly now than it did before. Hence transaction scale-up is the most relevant measure in this scenario.

In a client-server system with page shipping, when a client requests an item, the server typically grants a lock not on the requested item, but on the page having the item, thus implicitly granting locks on all the items in the page. The other items in the page are SAID to be prefetched. If some other client subsequently requests one of the prefetched items, the server may ask the OWNER of the page lock to transfer back the lock on this item. If the page lock owner doesn’t need this item, it de-escalates the page lock that it holds, to item locks on all the items that it is actually accessing, and then returns the locks on the unwanted items. The server can then grant the latter lock request. If the unit of data shipping is an item, there are no COARSER granularity locks; even if prefetching is used, it is typically implemented by granting individual locks on each of the prefetched items. Thus when the server asks for a return of a lock, there is no question of de-escalation, the requested lock is just RETURNED if the client has no USE for it.

In a client-server system with page shipping, when a client requests an item, the server typically grants a lock not on the requested item, but on the page having the item, thus implicitly granting locks on all the items in the page. The other items in the page are said to be prefetched. If some other client subsequently requests one of the prefetched items, the server may ask the owner of the page lock to transfer back the lock on this item. If the page lock owner doesn’t need this item, it de-escalates the page lock that it holds, to item locks on all the items that it is actually accessing, and then returns the locks on the unwanted items. The server can then grant the latter lock request. If the unit of data shipping is an item, there are no coarser granularity locks; even if prefetching is used, it is typically implemented by granting individual locks on each of the prefetched items. Thus when the server asks for a return of a lock, there is no question of de-escalation, the requested lock is just returned if the client has no use for it.

The DRAWBACKS would be that TWO interprocess messages would be required to acquire locks, ONE for the request and one to confirm grant. Interprocess communication is much more expensive than memory access, so the cost of locking would increase. The process storing the shared structures could ALSO become a bottleneck. The benefit of this alternative is that the LOCK table is protected better from erroneous updates since only one process can access it.

The drawbacks would be that two interprocess messages would be required to acquire locks, one for the request and one to confirm grant. Interprocess communication is much more expensive than memory access, so the cost of locking would increase. The process storing the shared structures could also become a bottleneck. The benefit of this alternative is that the lock table is protected better from erroneous updates since only one process can access it.

Porting is relatively easy to a shared memory multiprocessor machine. Databases DESIGNED for single-processor machines already provide multitasking, allowing multiple processes to run on the same processor in a time shared MANNER, giving a VIEW to the user of multiple processes running in parallel. Thus, coarse-granularity parallel machines logically appear to be identical to single-processor machines, MAKING the porting relatively easy. Porting a database to a shared disk or shared nothing multiprocessor architecture is a little harder.

Porting is relatively easy to a shared memory multiprocessor machine. Databases designed for single-processor machines already provide multitasking, allowing multiple processes to run on the same processor in a time shared manner, giving a view to the user of multiple processes running in parallel. Thus, coarse-granularity parallel machines logically appear to be identical to single-processor machines, making the porting relatively easy. Porting a database to a shared disk or shared nothing multiprocessor architecture is a little harder.

In a system crash, the CPU goes down, and disk may also crash. But STABLE-STORAGE at the site is assumed to survive system crashes. In a “DISASTER”, everything at a site is destroyed. Stable storage needs to be distributed to survive disasters.

In a system crash, the CPU goes down, and disk may also crash. But stable-storage at the site is assumed to survive system crashes. In a “disaster”, everything at a site is destroyed. Stable storage needs to be distributed to survive disasters.

The shadow-paging scheme is easy to implement for single-transaction systems, but difficult for multiple-transaction systems. In particular it is very HARD to allow multiple updates concurrently on the same page. Shadow paging COULD suffer from extra space overhead, but garbage collection can take care of that. The I/O overhead for shadow paging is typically HIGHER than the log based schemes, since the log based schemes need to write one record per UPDATE to the log, whereas the shadow paging scheme NEEDS to write one block per updated block.

The shadow-paging scheme is easy to implement for single-transaction systems, but difficult for multiple-transaction systems. In particular it is very hard to allow multiple updates concurrently on the same page. Shadow paging could suffer from extra space overhead, but garbage collection can take care of that. The I/O overhead for shadow paging is typically higher than the log based schemes, since the log based schemes need to write one record per update to the log, whereas the shadow paging scheme needs to write one block per updated block.

Volatile storage is storage which fails when there is a power failure. Cache, MAIN memory, and REGISTERS are examples of volatile storage. Nonvolatile storage is storage which retains its content despite power FAILURES. An example is magnetic disk. Stable storage is storage which theoretically survives any kind of failure (short of a complete disaster!). This type of storage can only be approximated by replicating DATA.

In terms of I/O cost, volatile memory is the fastest and non-volatile storage is typically several times SLOWER. Stable storage is slower than non-volatile storage because of the cost of data replication.

Volatile storage is storage which fails when there is a power failure. Cache, main memory, and registers are examples of volatile storage. Nonvolatile storage is storage which retains its content despite power failures. An example is magnetic disk. Stable storage is storage which theoretically survives any kind of failure (short of a complete disaster!). This type of storage can only be approximated by replicating data.

In terms of I/O cost, volatile memory is the fastest and non-volatile storage is typically several times slower. Stable storage is slower than non-volatile storage because of the cost of data replication.

Answer :In the text, we CONSIDERED two approaches to dealing with the PHANTOM phenomenon by means of locking. The coarser granularity approach OBVIOUSLY works for time stamps as well. The B+-tree index based approach can be adapted to time stamping by treating index buckets as data items with time stamps associated with them, and requiring that all read accesses use an index. We now show that this simple method works. Suppose a transaction TI wants to access all tuples with a particular range of search-key values, using a B+- tree index on that search-key. Ti will need to read all the buckets in that index which have key values in that range. It can be seen that any delete or insert of a tuple with a key-value in the same range will need to WRITE one of the index buckets read by Ti. Thus the logical conflict is converted to a conflict on an index bucket, and the phantom phenomenon is avoided.

The phantom PHENOMENON ARISES when, due to an insertion or deletion, two transactions logically conflict despite not locking any data items in common. The insertion case is described in the book. Deletion can also lead to this phenomenon. Suppose Ti deletes a tuple from a relation while Tj scans the relation. If Ti deletes the tuple and then Tj reads the relation, Ti should be serialized before Tj . Yet there is no tuple that both Ti and Tj conflict on.

An interpretation of 2PL as just locking the accessed tuples in a relation is incorrect. There is also an index or a relation data that has information about the tuples in the relation. This information is READ by any TRANSACTION that scans the relation, and modified by transactions that update, or insert into, or delete from the relation. Hence locking MUST also be performed on the index or relation data, and this will avoid the phantom phenomenon.

The phantom phenomenon arises when, due to an insertion or deletion, two transactions logically conflict despite not locking any data items in common. The insertion case is described in the book. Deletion can also lead to this phenomenon. Suppose Ti deletes a tuple from a relation while Tj scans the relation. If Ti deletes the tuple and then Tj reads the relation, Ti should be serialized before Tj . Yet there is no tuple that both Ti and Tj conflict on.

An interpretation of 2PL as just locking the accessed tuples in a relation is incorrect. There is also an index or a relation data that has information about the tuples in the relation. This information is read by any transaction that scans the relation, and modified by transactions that update, or insert into, or delete from the relation. Hence locking must also be performed on the index or relation data, and this will avoid the phantom phenomenon.

Answer :A transaction MAY become the victim of deadlock-prevention rollback ARBITRARILY many times, THUS creating a potential starvation SITUATION.

Deadlock AVOIDANCE is PREFERABLE if the CONSEQUENCES of abort are SERIOUS (as in interactive transactions), and if there is high contention and a resulting high probability of deadlock.

Deadlock avoidance is preferable if the consequences of abort are serious (as in interactive transactions), and if there is high contention and a resulting high probability of deadlock.

Using the commit bit, a read request is made to wait if the transaction which wrote the data ITEM has not yet COMMITTED. Therefore, if the writing transaction fails before commit, we can abort that transaction alone. The waiting read will then ACCESS the EARLIER version in case of a multiversion system, or the restored value of the data item after abort in case of a single-version system. For writes, this commit bit checking is unnecessary. That is because either the write is a “blind” write and thus independent of the old value of the data item or there was a prior read, in which case the test was already applied.

Using the commit bit, a read request is made to wait if the transaction which wrote the data item has not yet committed. Therefore, if the writing transaction fails before commit, we can abort that transaction alone. The waiting read will then access the earlier version in case of a multiversion system, or the restored value of the data item after abort in case of a single-version system. For writes, this commit bit checking is unnecessary. That is because either the write is a “blind” write and thus independent of the old value of the data item or there was a prior read, in which case the test was already applied.

In the concurrency control SCHEME choosing Start(Ti) as the time stamp of Ti gives a subset of the schedules ALLOWED by choosing Validation(Ti) as the time stamp. USING Start(Ti) means that whoever started FIRST must finish first. Clearly transactions could enter the validation phase in the same order in which they began executing, but this is overly restrictive. Since choosing Validation(Ti) causes fewer non conflicting transactions to restart, it gives the better response TIMES.

In the concurrency control scheme choosing Start(Ti) as the time stamp of Ti gives a subset of the schedules allowed by choosing Validation(Ti) as the time stamp. Using Start(Ti) means that whoever started first must finish first. Clearly transactions could enter the validation phase in the same order in which they began executing, but this is overly restrictive. Since choosing Validation(Ti) causes fewer non conflicting transactions to restart, it gives the better response times.

If a transaction needs to access a large a set of items, multiple granularity locking requires FEWER locks, whereas if only ONE ITEM needs to be ACCESSED, the single lock granularity system allows this with just one lock. Because all the desired data items are locked and unlocked together in the multiple granularity SCHEME, the locking overhead is low, but concurrency is also reduced.

If a transaction needs to access a large a set of items, multiple granularity locking requires fewer locks, whereas if only one item needs to be accessed, the single lock granularity system allows this with just one lock. Because all the desired data items are locked and unlocked together in the multiple granularity scheme, the locking overhead is low, but concurrency is also reduced.

An EXCLUSIVE lock is incompatible with any other lock kind. Once a node is locked in exclusive mode, NONE of the descendents can be SIMULTANEOUSLY accessed by any other transaction in any mode. Therefore an exclusive and intend-shared declaration has no MEANING.

An exclusive lock is incompatible with any other lock kind. Once a node is locked in exclusive mode, none of the descendents can be simultaneously accessed by any other transaction in any mode. Therefore an exclusive and intend-shared declaration has no meaning.

When a TRANSACTION explicitly locks a NODE in SHARED or exclusive mode, it implicitly locks all the DESCENDENTS of that node in the same mode. The transaction need not explicitly lock the descendent nodes. There is no DIFFERENCE in the functionalities of these locks, the only difference is in the way they are acquired, and their presence tested.

When a transaction explicitly locks a node in shared or exclusive mode, it implicitly locks all the descendents of that node in the same mode. The transaction need not explicitly lock the descendent nodes. There is no difference in the functionalities of these locks, the only difference is in the way they are acquired, and their presence tested.

A transaction is rolled back because a newer transaction has read or written the data which it was supposed to WRITE. If the rolled back transaction is re-introduced with the same TIME stamp, the same reason for ROLLBACK is STILL VALID, and the transaction will have be rolled back again. This will continue indefinitely.

A transaction is rolled back because a newer transaction has read or written the data which it was supposed to write. If the rolled back transaction is re-introduced with the same time stamp, the same reason for rollback is still valid, and the transaction will have be rolled back again. This will continue indefinitely.

It WOULD make no difference. The write protocol is such that the most RECENT TRANSACTION to write an item is also the one with the largest time stamp to have DONE so.

It would make no difference. The write protocol is such that the most recent transaction to write an item is also the one with the largest time stamp to have done so.

The proof is in Buckley and Silberschatz, “Concurrency Control in Graph Protocols by USING Edge Locks,” PROC. ACM SIGACT-SIGMOD SYMPOSIUM on the Principles of DATABASE Systems, 1984.

The proof is in Buckley and Silberschatz, “Concurrency Control in Graph Protocols by Using Edge Locks,” Proc. ACM SIGACT-SIGMOD Symposium on the Principles of Database Systems, 1984.

It is relatively simple to implement, imposes low ROLLBACK overhead because of cascadeless SCHEDULES, and usually ALLOWS an ACCEPTABLE LEVEL of concurrency.

It is relatively simple to implement, imposes low rollback overhead because of cascadeless schedules, and usually allows an acceptable level of concurrency.

Rigorous two-phase locking has the advantages of strict 2PL. In addition it has the property that for two conflicting transactions, their COMMIT order is their serializability order. In some SYSTEMS USERS MIGHT expect this behavior.

Rigorous two-phase locking has the advantages of strict 2PL. In addition it has the property that for two conflicting transactions, their commit order is their serializability order. In some systems users might expect this behavior.

Because it produces only cascadeless schedules, RECOVERY is very easy. But the SET of schedules obtainable is a subset of those obtainable from PLAIN TWO phase locking, thus concurrency is reduced.

Because it produces only cascadeless schedules, recovery is very easy. But the set of schedules obtainable is a subset of those obtainable from plain two phase locking, thus concurrency is reduced.

A cascadeless schedule is ONE where, for each pair of transactions Ti and TJ such that Tj reads data ITEMS previously written by Ti, the commit operation of Ti appears before the read operation of Tj. Cascadeless SCHEDULES are desirable because the failure of a transaction does not LEAD to the aborting of any other transaction. Of course this comes at the cost of less concurrency. If failures occur rarely, so that we can pay the price of cascading aborts for the increased concurrency, noncascadeless schedules might be desirable.

A cascadeless schedule is one where, for each pair of transactions Ti and Tj such that Tj reads data items previously written by Ti, the commit operation of Ti appears before the read operation of Tj. Cascadeless schedules are desirable because the failure of a transaction does not lead to the aborting of any other transaction. Of course this comes at the cost of less concurrency. If failures occur rarely, so that we can pay the price of cascading aborts for the increased concurrency, noncascadeless schedules might be desirable.

A recoverable schedule is one where, for each pair of transactions Ti and Tj such that Tj reads data items PREVIOUSLY written by Ti, the COMMIT operation of Ti appears before the commit operation of Tj. Recoverable schedules are desirable because failure of a transaction might otherwise BRING the system into an irreversibly INCONSISTENT state. Nonrecoverable schedules may sometimes be needed when updates must be made visible early due to time constraints, even if they have not yet been COMMITTED, which may be required for very long duration transactions.

A recoverable schedule is one where, for each pair of transactions Ti and Tj such that Tj reads data items previously written by Ti, the commit operation of Ti appears before the commit operation of Tj. Recoverable schedules are desirable because failure of a transaction might otherwise bring the system into an irreversibly inconsistent state. Nonrecoverable schedules may sometimes be needed when updates must be made visible early due to time constraints, even if they have not yet been committed, which may be required for very long duration transactions.

Most of the concurrency control protocols (protocols for ensuring that only SERIALIZABLE SCHEDULES are generated) used in practice are based on conflict serializability—they actually permit only a SUBSET of conflict serializable schedules. The GENERAL FORM of view serializability is very expensive to test, and only a very restricted form of it is used for concurrency control.

Most of the concurrency control protocols (protocols for ensuring that only serializable schedules are generated) used in practice are based on conflict serializability—they actually permit only a subset of conflict serializable schedules. The general form of view serializability is very expensive to test, and only a very restricted form of it is used for concurrency control.

A schedule in which all the INSTRUCTIONS belonging to one single transaction appear together is CALLED a SERIAL schedule. A serializable schedule has a weaker restriction that it should be equivalent to some serial schedule. There are two definitions of schedule EQUIVALENCE – conflict equivalence and VIEW equivalence. Both of these are described in the chapter.

A schedule in which all the instructions belonging to one single transaction appear together is called a serial schedule. A serializable schedule has a weaker restriction that it should be equivalent to some serial schedule. There are two definitions of schedule equivalence – conflict equivalence and view equivalence. Both of these are described in the chapter.

If a transaction is very long or when it fetches data from a slow disk, it takes a long TIME to COMPLETE. In absence of CONCURRENCY, other transactions will have to wait for longer period of time. Average response time will increase. Also when the transaction is reading data from disk, CPU is idle. So resources are not properly utilized. Hence concurrent execution becomes important in this case. However, when the transactions are short or the data is available in memory, these problems do not OCCUR.

If a transaction is very long or when it fetches data from a slow disk, it takes a long time to complete. In absence of concurrency, other transactions will have to wait for longer period of time. Average response time will increase. Also when the transaction is reading data from disk, CPU is idle. So resources are not properly utilized. Hence concurrent execution becomes important in this case. However, when the transactions are short or the data is available in memory, these problems do not occur.

The possible sequences of states are:-

1. active→PARTIALLY COMMITTED→committed. This is the normal sequence a SUCCESSFUL transaction will follow. After executing all its statements it enters the partially committed state. After enough recovery information has been written to disk, the transaction finally enters the committed state.
2. active → partially committed → aborted. After executing the last statement of the transaction, it enters the partially committed state. But before enough recovery information is written to disk, a hardware failure may occur destroying the memory contents. In this case the changes which it made to the database are undone, and the transaction enters the aborted state.
3. active → failed → aborted. After the transaction starts, if it is discovered at some point that normal execution cannot continue (EITHER DUE to internal program errors or external errors), it enters the failed state. It is then rolled back, after which it enters the aborted state.

The possible sequences of states are:-

Database systems usually perform crucial tasks whose effects need to be ATOMIC and durable, and whose outcome affects the real world in a permanent manner. EXAMPLES of such tasks are monetary transactions, SEAT BOOKINGS etc. Hence the ACID PROPERTIES have to be ensured. In contrast, most users of file systems would not be willing to pay the price (monetary, disk space, time) of supporting ACID properties.

Database systems usually perform crucial tasks whose effects need to be atomic and durable, and whose outcome affects the real world in a permanent manner. Examples of such tasks are monetary transactions, seat bookings etc. Hence the ACID properties have to be ensured. In contrast, most users of file systems would not be willing to pay the price (monetary, disk space, time) of supporting ACID properties.

There are several STEPS in the creation of a FILE. A storage area is assigned to the file in the file system, a unique i-number is given to the file and an i-node entry is inserted into the i-list. Deletion of file involves EXACTLY opposite steps.

For the file system user in UNIX, durability is important for obvious REASONS, but atomicity is not relevant generally as the file system doesn’t support transactions. To the file system implementor though, many of the internal file system ACTIONS need to have transaction semantics. All the steps involved in creation/deletion of the file must be atomic, otherwise there will be unreferenceable files or unusable areas in the file system.

There are several steps in the creation of a file. A storage area is assigned to the file in the file system, a unique i-number is given to the file and an i-node entry is inserted into the i-list. Deletion of file involves exactly opposite steps.

For the file system user in UNIX, durability is important for obvious reasons, but atomicity is not relevant generally as the file system doesn’t support transactions. To the file system implementor though, many of the internal file system actions need to have transaction semantics. All the steps involved in creation/deletion of the file must be atomic, otherwise there will be unreferenceable files or unusable areas in the file system.

Even in this case the recovery MANAGER is NEEDED to PERFORM roll-back of ABORTED transactions.

Even in this case the recovery manager is needed to perform roll-back of aborted transactions.

The ACID properties, and the need for each of them are:-

• Consistency: Execution of a TRANSACTION in isolation (that is, with no other transaction EXECUTING concurrently) PRESERVES the consistency of the database. This is typically the responsibility of the application programmer who codes the transactions.
• Atomicity: Either all OPERATIONS of the transaction are reflected properly in the database, or none are. Clearly lack of atomicity will lead to inconsistency in the database.
• Isolation: When multiple transactions execute concurrently, it should be the case that, for every pair of transactions Ti and Tj , it appears to Ti that either Tj finished execution before Ti started, or Tj started execution after Ti finished. Thus, each transaction is unaware of other transactions executing concurrently with it. The user VIEW of a transaction system requires the isolation property, and the property that concurrent schedules take the system from one consistent state to another. These requirements are satisfied by ensuring that only serializable schedules of individually consistency preserving transactions are allowed.
• Durability: After a transaction completes successfully, the changes it has made to the database persist, even if there are system failures.

The ACID properties, and the need for each of them are:-

If there are multiple tuples in the inner relation with the same value for the join attributes, we MAY have to access that many blocks of the inner relation for each tuple of the outer relation. That is why it is inefficient. To reduce this cost we can perform a join of the outer relation tuples with just the secondary index LEAF entries, postponing the inner relation tuple retrieval. The result file obtained is then sorted on the inner relation addresses, allowing an EFFICIENT physical order scan to complete the join.

HYBRID merge–join requires the outer relation to be sorted. The above algorithm does not have this REQUIREMENT, but for each tuple in the outer relation it needs to perform an index lookup on the inner relation. If the outer relation is much larger than the inner relation, this index lookup cost will be less than the sorting cost, thus this algorithm will be more efficient.

If there are multiple tuples in the inner relation with the same value for the join attributes, we may have to access that many blocks of the inner relation for each tuple of the outer relation. That is why it is inefficient. To reduce this cost we can perform a join of the outer relation tuples with just the secondary index leaf entries, postponing the inner relation tuple retrieval. The result file obtained is then sorted on the inner relation addresses, allowing an efficient physical order scan to complete the join.

Hybrid merge–join requires the outer relation to be sorted. The above algorithm does not have this requirement, but for each tuple in the outer relation it needs to perform an index lookup on the inner relation. If the outer relation is much larger than the inner relation, this index lookup cost will be less than the sorting cost, thus this algorithm will be more efficient.

We merge the LEAF entries of the first sorted secondary index with the leaf entries of the second sorted secondary index. The result FILE contains pairs of addresses, the first address in each pair POINTING to a tuple in the first relation, and the second address pointing to a tuple in the second relation. This result file is first sorted on the first relation’s addresses. The relation is then scanned in physical storage order, and addresses in the result file are replaced by the actual tuple values. Then the result file is sorted on the second relation’s addresses, allowing a SCAN of the second relation in physical storage order to complete the JOIN.

We merge the leaf entries of the first sorted secondary index with the leaf entries of the second sorted secondary index. The result file contains pairs of addresses, the first address in each pair pointing to a tuple in the first relation, and the second address pointing to a tuple in the second relation. This result file is first sorted on the first relation’s addresses. The relation is then scanned in physical storage order, and addresses in the result file are replaced by the actual tuple values. Then the result file is sorted on the second relation’s addresses, allowing a scan of the second relation in physical storage order to complete the join.

Hash indices enable US to perform point LOOK up (eg. σA=r(relation)) operations very fast, but for range searches the B+-tree INDEX would be much more efficient. If there is a range query to be evaluated, and only a hash index is available, the better STRATEGY might be to perform a file scan rather than using that index.

Hash indices enable us to perform point look up (eg. σA=r(relation)) operations very fast, but for range searches the B+-tree index would be much more efficient. If there is a range query to be evaluated, and only a hash index is available, the better strategy might be to perform a file scan rather than using that index.

In general it is not desirable to force users to choose a query processing strategy because naive users might select an inefficient strategy. The reason users WOULD make poor CHOICES about processing queries is that they would not know how a RELATION is stored, nor about its indices. It is unreasonable to force users to be aware of these details since ease of use is a MAJOR OBJECT of database query languages. If users are aware of the costs of different strategies they could write queries efficiently, thus helping performance. This could happen if experts were using the system.

In general it is not desirable to force users to choose a query processing strategy because naive users might select an inefficient strategy. The reason users would make poor choices about processing queries is that they would not know how a relation is stored, nor about its indices. It is unreasonable to force users to be aware of these details since ease of use is a major object of database query languages. If users are aware of the costs of different strategies they could write queries efficiently, thus helping performance. This could happen if experts were using the system.

Note that indices must OPERATE on the encrypted data or someone could gain access to the index to interpret the data.Otherwise, the index would have to be RESTRICTED so that only CERTAIN users could access it. To KEEP the data in sorted order, the index scheme would have to decrypt the data at each level in a tree. Note that hash systems would not be AFFECTED.

Note that indices must operate on the encrypted data or someone could gain access to the index to interpret the data.Otherwise, the index would have to be restricted so that only certain users could access it. To keep the data in sorted order, the index scheme would have to decrypt the data at each level in a tree. Note that hash systems would not be affected.

The existence BITMAP for a relation can be calculated by taking the union (logical-or) of all the BITMAPS on that attribute, INCLUDING the bitmap for value NULL.

The existence bitmap for a relation can be calculated by taking the union (logical-or) of all the bitmaps on that attribute, including the bitmap for value null.