All Matches
Solution Library
Expert Answer
Textbooks
Search Textbook questions, tutors and Books
Oops, something went wrong!
Change your search query and then try again
Toggle navigation
FREE Trial
S
Books
FREE
Tutors
Study Help
Expert Questions
Accounting
General Management
Mathematics
Finance
Organizational Behaviour
Law
Physics
Operating System
Management Leadership
Sociology
Programming
Marketing
Database
Computer Network
Economics
Textbooks Solutions
Accounting
Managerial Accounting
Management Leadership
Cost Accounting
Statistics
Business Law
Corporate Finance
Finance
Economics
Auditing
Ask a Question
Search
Search
Sign In
Register
study help
computer sciences
databases
Questions and Answers of
Databases
Design sorting based and hashing algorithms for computing the division operation.
Clustering indices may allow faster access to data than a nonclustering index affords. When must we create a nonclustering index, despite the advantages of a clustering index? Explain your answer.
Consider the relations r1 (A, B, C), r2 (C, D, E), and r3 (E, F), with primary keys A, C, and E, respectively. Assume that r1 has 1000 tuples, r2 has 1500 tuples, and r3 has 750 tuples. Estimate the
Consider the relations r1 (A, B, C), r2 (C, D, E), and r3 (E, F) of Exercise. Assume that there are no primary keys, except the entire schema. Let V (C, r1) be 900, V (C, r2) be 1100, V (E, r2) be
Suppose that a B+-tree index on branch-city is available on relation branch, and that no other index is available. What would be the best way to handle the following selections that involve
Suppose that a B+-tree index on (branch-name, branch-city) is available on relation branch. What would be the best way to handle the following selection?σ (branch-city<“Brooklyn”) ∧
Show that the following equivalences hold. Explain how you can apply then to improve the efficiency of certain queries:a. E1 Θθ (E2 − E3) = (E1 Θθ E2 − E1 Θθ E3).b. σθ (AGF (E)) = AGF
Show how to derive the following equivalences by a sequence of transformations using the equivalence rules in Section 14.3.1.a. σθ1 ∧ θ2 ∧ θ3 (E) = σθ1 (σθ2 (σθ3 (E)))b. σθ1
For each of the following pairs of expressions, give instances of relations that show the expressions are not equivalent.a. ΠA(R − S) and Π A (R) – ΠA (S)b. σB < 4(AGmax(B)(R)) and
SQL allows relations with duplicates.a. Define versions of the basic relational-algebra operations σ, Π, ×, Π, −, ∪, and ∩ that work on relationswith duplicates, in a way consistent with
Show that, with n relations, there are (2(n − 1))! / (n−1)! Different join orders. If you wish, you can derive the formula for the number of complete binary trees with n nodes from the formula
Show that the lowest-cost join order can be computed in time O(3n). Assume that you can store and look up information about a set of relations (such as the optimal join order for the set, and the
Show that, if only left-deep join trees are considered, as in the System R optimizer, the time taken to find themost efficient join order is around n2n.Assume that there is only one interesting sort
A set of equivalence rules is said to be complete if, whenever two expressions are equivalent, one can be derived from the other by a sequence of uses of the equivalence rules. Is the set of
Decorrelation:a. Write a nested query on the relation account to find for each branch with name starting with “B”, all accounts with the maximum balance at the branch.b. Rewrite the preceding
Describe how to incrementally maintain the results of the following operations, on both insertions and deletions.a. Union and set differenceb. Left outer join
Give an example of an expression defining a materialized view and two situations (sets of statistics for the input relations and the differentials) such that incremental view maintenance is better
List the ACID properties. Explain the usefulness of each.
Suppose that there is a database system that never fails. Is a recovery manager required for this system?
Consider a file system such as the one on your favorite operating system.a. What are the steps involved in creation and deletion of files, and in writing data to a file?b. Explain how the issues of
Database-system implementers have paid much more attention to the ACID properties than have file-system implementers. Why might this be the case?
During its execution, a transaction passes through several states, until it finally commits or aborts. List all possible sequences of states through which a transaction may pass. Explain why each
Justify the following statement: Concurrent execution of transactions is more important when data must be fetched from (slow) disk or when transactions are long, and is less important when data is in
Explain the distinction between the terms serial schedule and serializable schedule.
Consider the following two transactions:T1: read (A); read (B); if A = 0then B: = B + 1; write (B).T2: read (B); read (A); if B = 0 then A: = A + 1; write (A).Let the consistency requirement be A = 0
Since every conflict-serializable schedule is view serializable, why do we emphasize conflict serializability rather than view serializability?
Consider the precedence graph of Figure is the corresponding schedule conflict serializable? Explain your answer.
What is a recoverable schedule? Why is recoverability of schedules desirable? Are there any circumstances under which it would be desirable to allow nonrecoverable schedules? Explain your answer.
What is a cascade less schedule? Why is cascadelessness of schedules desirable? Are there any circumstances under which it would be desirable to allow non-cascadeless schedules? Explain your answer.
Consider the following two transactions:T31: read (A); read (B);If A = 0 then B: = B + 1; write (B).T32: read (B); read (A);If B = 0 then A: = A + 1; write (A).Add lock and unlock instructions to
What benefit does strict two-phase locking provide? What disadvantages result?
What benefit does rigorous two-phase locking provide? How does it compare with other forms of two-phase locking?
Most implementations of database systems use strict two-phase locking. Suggest three reasons for the popularity of this protocol.
Consider a database organized in the form of a rooted tree. Suppose that we insert a dummy vertex between each pair of vertices. Show that, if we follow the tree protocol on the new tree, we get
Show by example that there are schedules possible under the tree protocol that is not possible under the two-phase locking protocol, and vice versa.
Consider the following extension to the tree-locking protocol, which allows both shared and exclusive locks:• A transaction can be either a read-only transaction, in which case it can request only
Consider the following graph-based locking protocol, which allows only exclusive lock modes, and which operates on data graphs that are in the form of a rooted directed acyclic graph.• A
Consider the following graph-based locking protocol, which allows only exclusive lock modes, and which operates on data graphs that are in the form of a rooted directed acyclic graph.• A
Consider the following graph-based locking protocol that allows only exclusive lock modes, and that operates on data graphs that are in the form of a rooted directed acyclic graph.• A transaction
Consider a variant of the tree protocol called the forest protocol. The database is organized as a forest of rooted trees. Each transaction Ti must follow the following rules:• The first lock in
Locking is not done explicitly in persistent programming languages. Rather, objects (or the corresponding pages) must be locked when the objects are accessed. Most modern operating systems allow the
In timestamp ordering, W-timestamp (Q) denotes the largest timestamp of any transaction that executed write (Q) successfully. Suppose that, instead, we defined it to be the timestamp of the most
When a transaction is rolled back under timestamp ordering, it is assigned a new timestamp. Why can it not simply keep its old timestamp?
In multiple-granularity locking, what is the difference between implicit and explicit locking?
Although SIX mode is useful in multiple-granularity locking, an exclusive and intend-shared (XIS) mode is of no use. Why is it useless?
Use of multiple-granularity locking may require more or fewer locks than an equivalent system with a single lock granularity. Provide examples of both situations, and compare the relative amount of
Consider the validation-based concurrency-control scheme of Section 16.3. Show that by choosing Validation (Ti), rather than Start (Ti), as the timestamp of transaction Ti, we can expect better
Show that there are schedules that are possible under the two-phase locking protocol, but are not possible under the timestamp protocol, and vice versa.
For each of the following protocols, describe aspects of practical applications that would lead you to suggest using the protocol, and aspects that would suggest not using the protocol:• Two-phase
Under a modified version of the timestamp protocol, we require that a commit bit be tested to see whether a read request must wait. Explain how the commit bit can prevent cascading abort. Why is this
Under what conditions is it less expensive to avoid deadlock than to allow deadlocks to occur and then to detect them?
If deadlock is avoided by deadlock avoidance schemes, is starvation still possible? Explain your answer.
Explain the phantom phenomenon. Why may this phenomenon lead to an incorrect concurrent execution despite the use of the two-phase locking protocol?
Devise a timestamp-based protocol that avoids the phantom phenomenon.
Suppose that we use the tree protocol of Section 16.1.5 to manage concurrent access to a B+-tree. Since a split may occur on an insert that affects the root, it appears that an insert operation
Explain the difference between the three storage types—volatile, nonvolatile, and stable—in terms of I/O cost.
Stable storage cannot be implemented.a. Explain why it cannot be.b. Explain how database systems deal with this problem.
Compare the deferred- and immediate-modification versions of the log-based recovery scheme in terms of ease of implementation and overhead cost.
Assume that immediate modification is used in a system. Show, by an example, how an inconsistent database state could result if log records for a transaction are not output to stable storage prior to
Explain the purpose of the checkpoint mechanism. How often should checkpoints be performed? How does the frequency of checkpoints affect• System performance when no failure occurs• The time it
When the system recovers from a crash, it constructs an undo-list and a redo-list. Explainwhy log records for transactions on the undolist must be processed in reverse order, while those log records
Compare the shadow-paging recovery scheme with the log-based recovery schemes in terms of ease of implementation and overhead cost.
Consider a database consisting of 10 consecutive disk blocks (block 1, block 2, . . ., block 10). Show the buffer state and a possible physical ordering of the blocks after the following updates,
Explain how the buffer manager may cause the database to become inconsistent if some log records pertaining to a block are not output to stable storage before the block is output to disk.
Explain the benefits of logical logging. Give examples of one situation where logical logging is preferable to physical logging and one situation where physical logging is preferable to logical
Explain the reasons why recovery of interactive transactions is more difficult to deal with than is recovery of batch transactions. Is there a simple way to deal with this difficulty?
Sometimes a transaction has to be undone after it has commited, because it was erroneously executed, for example because of erroneous input by a bank teller.a. Give an example to show that using the
Logging of updates is not done explicitly in persistent programming languages. Describe how page access protections provided by modern operating systems can be used to create before and after images
Explain the difference between a system crash and a “disaster.”
For each of the following requirements, identify the best choice of degree of durability in a remote backup system:a. Data loss must be avoided but some loss of availability may be tolerated.b.
Why is it relatively easy to port a database from a single processor machine to a multiprocessor machine if individual queries need not be parallelized?
Transaction server architectures are popular for client-server relational databases, where transactions are short. On the other hand, data server architectures are popular for client-server
Instead of storing shared structures in shared memory, an alternative architecture would be to store them in the local memory of a special process, and access the shared data by interprocess
In typical client–server systems the server machine is much more powerful than the clients; that is, its processor is faster, it may have multiple processors, and it has more memory and disk
Consider an object-oriented database system based on a client-server architecture, with the server acting as a data server.a. What is the effect of the speed of the interconnection between the client
What is lock de-escalation, and under what conditions is it required why is it not required if the unit of data shipping is an item?
Suppose you were in charge of the database operations of a company whose main job is to process transactions. Suppose the company is growing rapidly each year, and has outgrown its current computer
Suppose a transaction is written in C with embedded SQL, and about 80 percent of the time is spent in the SQL code, with the remaining 20 percent spent in C code. How much speedup can one hope to
What are the factors that can work against linear scaleup in a transaction processing system? Which of the factors are likely to be themost important in each of the following architectures: shared
Consider a bank that has a collection of sites, each running a database system. Suppose the only way the databases interact is by electronic transfer of money between one another. Would such a system
Consider a network based on dial-up phone lines, where sites communicate periodically, such as every night. Such networks are often configured with a server site and multiple client sites. The client
Discuss the relative advantages of centralized and distributed databases.
Explain how the following differ: fragmentation transparency, replication transparency, and location transparency.
How might a distributed database designed for a local-area network differ from one designed for a wide-area network?
When is it useful to have replication or fragmentation of data? Explain your answer.
Explain the notions of transparency and autonomy. Why are these notions desirable from a human-factors stand point?
To build a highly available distributed system, you must know what kinds of failures can occur.a. List possible types of failure in a distributed system.b. Which items in your list from part a are
Consider a failure that occurs during 2PC for a transaction. For each possible failure that you listed in Exercise 19.6a, explain how 2PC ensures transaction atomicity despite the failure.
Consider a distributed system with two sites, A and B. Can site A distinguish among the following?• B goes down.• The link between A and B goes down.• B is extremely overloaded and response
Consider a distributed system with two sites, A and B. Can site A distinguish among the following?• B goes down.• The link between A and B goes down.• B is extremely overloaded and response
The persistent messaging scheme described in this chapter depends on timestamps combined with discarding of received messages if they are too old. Suggest an alternative scheme based on sequence
Give an example where the read one, write all available approach leads to an erroneous state.
If we apply a distributed version of the multiple-granularity protocol of Chapter to a distributed database, the site responsible for the root of the DAG may become a bottleneck. Suppose we modify
Explain the difference between data replication in a distributed system and the maintenance of a remote backup site.
Give an example where lazy replication can lead to an inconsistent database state even when updates get an exclusive lock on the primary (master) copy.
Discuss the advantages and disadvantages of the two methods that we presented in Section 19.5.2 for generating globally unique timestamps.
Consider the following deadlock-detection algorithm. When transaction Ti, at site S1, requests a resource from Tj, at site S3, a request message with timestamp n is sent. The edge (Ti, Tj, n) is
Consider a relation that is fragmented horizontally by plant-number:Employee (name, address, salary plant-number) assumes that each fragment has two replicas: one stored at the New York site and one
Consider the relations employee (name, address, salary plant-number) machine (machine-number, type plant-number) Assume that the employee relation is fragmented horizontally by plant-number, and that
For each of the strategies of Exercise 19.18, state how your choice of a strategy depends on:a. The site at which the querywas enteredb. The site at which the result is desired
Compute r x s for the relations as shown below.
Given that the LDAP functionality can be implemented on top of a database system, what is the need for the LDAP standard?
Showing 300 - 400
of 2962
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Last