CSE202 Database Management Systems Lecture #10 Lecture Slides

CSE202 Database Management Systems Lecture #10 Lecture Slides

CSE202 Database Management Systems Lecture #10 Lecture Slides of Elmasri & Gillenson (without revision) Part 1 Query Processing & Optimization 2 0. Introduction to Query Processing (1) Query optimization: The process of choosing a suitable execution strategy for processing a query. Two internal representations of a query: Query Tree Query Graph Introduction to Query Processing (2)

1. Translating SQL Queries into Relational Algebra (1) Query block: The basic unit that can be translated into the algebraic operators and optimized. A query block contains a single SELECT- FROM-WHERE expression, as well as GROUP BY and HAVING clause if these are part of the block. Nested queries within a query are identified as separate query blocks. Aggregate operators in SQL must be included in the extended algebra. Translating SQL Queries into Relational Algebra (2) SELECT

FROM WHERE SELECT FROM WHERE LNAME, FNAME EMPLOYEE SALARY > (SELECT MAX (SALARY) FROM EMPLOYEE WHERE DNO = 5); LNAME, FNAME EMPLOYEE SALARY > C

LNAME, FNAME (SALARY>C(EMPLOYEE)) SELECT FROM WHERE MAX (SALARY) EMPLOYEE DNO = 5 MAX SALARY (DNO=5 (EMPLOYEE)) 2. Algorithms for External Sorting (1) External sorting: Refers to sorting algorithms that are suitable for large files of records stored on disk that do not fit entirely in main memory, such as most database files. Sort-Merge strategy:

Starts by sorting small subfiles (runs) of the main file and then merges the sorted runs, creating larger sorted subfiles that are merged in turn. Sorting phase: n = (b/n ) R B Merging phase: d = Min (n -1, n ); n = M B R P (logdM(nR)) n : number of initial runs; b: number of file blocks; R n : available buffer space; d : degree of merging; B M n : number of passes. P

Algorithms for External Sorting (2) 3. Algorithms for SELECT and JOIN Operations (1) Implementing the SELECT Operation Examples: (OP1): s SSN='123456789' (EMPLOYEE) (OP2): s DNUMBER>5

(OP3): s DNO=5 (OP4): s DNO=5 AND SALARY>30000 AND SEX=F (OP5): s ESSN=123456789 AND PNO=10 (DEPARTMENT) (EMPLOYEE) (EMPLOYEE) (WORKS_ON)

Algorithms for SELECT and JOIN Operations (2) Implementing the SELECT Operation (contd.): Search Methods for Simple Selection: S1 Linear search (brute force): Retrieve every record in the file, and test whether its attribute values satisfy the selection condition. S2 Binary search: If the selection condition involves an equality comparison on a key attribute on which the file is ordered, binary search (which is more efficient than linear search) can be used. (See OP1). S3 Using a primary index or hash key to

retrieve a single record: If the selection condition involves an equality comparison on a key attribute with a primary index (or a hash key), use the primary index (or the hash key) to retrieve the record. Algorithms for SELECT and JOIN Operations (3) Implementing the SELECT Operation (contd.): Search Methods for Simple Selection: S4 Using a primary index to retrieve multiple records: If the comparison condition is >, , <, or on a key field

with a primary index, use the index to find the record satisfying the corresponding equality condition, then retrieve all subsequent records in the (ordered) file. S5 Using a clustering index to retrieve multiple records: If the selection condition involves an equality comparison on a non-key attribute with a clustering index, use the clustering index to retrieve all the records satisfying the selection condition. S6 Using a secondary (B+-tree) index:

On an equality comparison, this search method can be used to retrieve a single record if the indexing field has unique values (is a key) or to retrieve multiple records if the indexing field is not a key. Algorithms for SELECT and JOIN Operations (4) Implementing the SELECT Operation (contd.): Search Methods for Simple Selection: S7 Conjunctive selection: If an attribute involved in any single simple condition in the conjunctive condition has an access path that permits the use of one of the methods S2 to S6, use that condition to retrieve the records and then check whether each retrieved record satisfies the remaining simple conditions in the conjunctive condition.

S8 Conjunctive selection using a composite index If two or more attributes are involved in equality conditions in the conjunctive condition and a composite index (or hash structure) exists on the combined field, we can use the index directly. Algorithms for SELECT and JOIN Operations (5) Implementing the SELECT Operation (contd.): Search Methods for Complex Selection: S9 Conjunctive selection by intersection of record pointers: This method is possible if secondary indexes are available on all (or some of) the fields involved in equality comparison conditions in the conjunctive

condition and if the indexes include record pointers (rather than block pointers). Each index can be used to retrieve the record pointers that satisfy the individual condition. The intersection of these sets of record pointers gives the record pointers that satisfy the conjunctive condition, which are then used to retrieve those records directly. If only some of the conditions have secondary indexes, each retrieved record is further tested to determine whether it satisfies the remaining conditions. Algorithms for SELECT and JOIN Operations (7) Implementing the SELECT Operation (contd.): Whenever a single condition specifies the selection, we can only check whether an access path exists on the attribute involved in that

condition. If an access path exists, the method corresponding to that access path is used; otherwise, the brute force linear search approach of method S1 is used. (See OP1, OP2 and OP3) For conjunctive selection conditions, whenever more than one of the attributes involved in the conditions have an access path, query optimization should be done to choose the access path that retrieves the fewest records in the most efficient way. Algorithms for SELECT and JOIN Operations (8)

Implementing the JOIN Operation: Join (EQUIJOIN, NATURAL JOIN) twoway join: a join on two files e.g. R A=B S multi-way joins: joins involving more than two files. e.g. R S C=D T A=B Examples (OP6): EMPLOYEE DEPARTMENT (OP7): DEPARTMENT

DNO=DNUMBER MGRSSN=SSN EMPLOYEE Algorithms for SELECT and JOIN Operations (9) Implementing the JOIN Operation (contd.): Methods for implementing joins: J1 Nested-loop join (brute force): For each record t in R (outer loop), retrieve every record s from S (inner loop) and test whether the two records satisfy the join condition t[A] = s[B]. J2 Single-loop join (Using an access structure to

retrieve the matching records): If an index (or hash key) exists for one of the two join attributes say, B of S retrieve each record t in R, one at a time, and then use the access structure to retrieve directly all matching records s from S that satisfy s[B] = t[A]. Algorithms for SELECT and JOIN Operations (10) Implementing the JOIN Operation (contd.): Methods for implementing joins: J3 Sort-merge join: If the records of R and S are physically sorted (ordered) by value of the join attributes A and B, respectively, we can implement the join in the most

efficient way possible. Both files are scanned in order of the join attributes, matching the records that have the same values for A and B. In this method, the records of each file are scanned only once each for matching with the other file unless both A and B are non-key attributes, in which case the method needs to be modified slightly. Algorithms for SELECT and JOIN Operations (11) Implementing the JOIN Operation (contd.): Methods for implementing joins: J4 Hash-join: The records of files R and S are both hashed to the same hash file, using the same hashing function on the join attributes A of R and B of S as hash keys. A single pass through the file with fewer records

(say, R) hashes its records to the hash file buckets. A single pass through the other file (S) then hashes each of its records to the appropriate bucket, where the record is combined with all matching records from R. Algorithms for SELECT and JOIN Operations (12) Algorithms for SELECT and JOIN Operations (13) Algorithms for SELECT and JOIN Operations (cont.)

Algorithms for SELECT and JOIN Operations (14) Implementing the JOIN Operation (contd.): Factors affecting JOIN performance Available buffer space Join selection factor Choice of inner VS outer relation Algorithms for SELECT and JOIN Operations (15) Implementing the JOIN Operation (contd.): Other types of JOIN algorithms Partition hash join Partitioning phase: Each file (R and S) is first partitioned into M partitions using a partitioning hash function on the join attributes:

R1 , R2 , R3 , ...... Rm and S1 , S2 , S3 , ...... Sm Minimum number of in-memory buffers needed for the partitioning phase: M+1. A disk sub-file is created per partition to store the tuples for that partition. Joining or probing phase: Involves M iterations, one per partitioned file. Iteration i involves joining partitions Ri and Si. Algorithms for SELECT and JOIN Operations (16) Implementing the JOIN Operation (contd.):

Partitioned Hash Join Procedure: Assume Ri is smaller than Si. 1. Copy records from Ri into memory buffers. 2. Read all blocks from Si, one at a time and each record from Si is used to probe for a matching record(s) from partition Si. 3. Write matching record from Ri after joining to the record from Si into the result file. Algorithms for SELECT and JOIN Operations (17) Implementing the JOIN Operation (contd.): Cost analysis of partition hash join: 1. Reading and writing each record from R and S during the partitioning phase: (bR + bS), (bR + bS) 2. Reading each record during the joining phase: (bR + bS) 3. Writing the result of join:

bRES Total Cost: 3* (bR + bS) + bRES Algorithms for SELECT and JOIN Operations (18) Implementing the JOIN Operation (contd.): Hybrid hash join: Same as partitioned hash join except: Joining phase of one of the partitions is included during the partitioning phase. Partitioning phase: Allocate buffers for smaller relation- one block for each of the M-1 partitions, remaining blocks to

partition 1. Repeat for the larger relation in the pass through S.) Joining phase: M-1 iterations are needed for the partitions R2 , R3 , R4 , ......Rm and S2 , S3 , S4 , ......Sm. R1 and S1 are joined during the partitioning of S1, and results of joining R1 and S1 are already written to the disk by the end of partitioning phase. 4. Algorithms for PROJECT and SET Operations (1) Algorithm for PROJECT operations (Figure 15.3b)

(R) 1. If has a key of relation R, extract all tuples from R with only the values for the attributes in . 2. If does NOT include a key of relation R, duplicated tuples must be removed from the results. Methods to remove duplicate tuples 1. Sorting 2. Hashing Algorithms for PROJECT and SET Operations (2) Algorithm for SET operations Set operations: UNION, INTERSECTION, SET DIFFERENCE and CARTESIAN PRODUCT CARTESIAN PRODUCT of relations R and S

include all possible combinations of records from R and S. The attribute of the result include all attributes of R and S. Cost analysis of CARTESIAN PRODUCT If R has n records and j attributes and S has m records and k attributes, the result relation will have n*m records and j+k attributes. CARTESIAN PRODUCT operation is very expensive and should be avoided if possible. Algorithms for PROJECT and SET Operations (3) Algorithm for SET operations (contd.) UNION (See Figure 19.3c) Sort the two relations on the same attributes. Scan and merge both sorted files concurrently, whenever the same tuple exists in both relations,

only one is kept in the merged results. INTERSECTION (See Figure 19.3d) Sort the two relations on the same attributes. Scan and merge both sorted files concurrently, keep in the merged results only those tuples that appear in both relations. SET DIFFERENCE R-S (See Figure 19.3e) Keep in the merged results only those tuples that appear in relation R but not in relation S. 5. Implementing Aggregate Operations and Outer Joins (1) Implementing Aggregate Operations: Aggregate operators: MIN, MAX, SUM, COUNT and AVG Options to implement aggregate operators: Table Scan Index

Example SELECT MAX (SALARY) FROM EMPLOYEE; If an (ascending) index on SALARY exists for the employee relation, then the optimizer could decide on traversing the index for the largest value, which would entail following the right most pointer in each index node from the root to a leaf. Implementing Aggregate Operations and Outer Joins (2) Implementing Aggregate Operations (contd.): SUM, COUNT and AVG For a dense index (each record has one index entry): Apply the associated computation to the values in the

index. For a non-dense index: Actual number of records associated with each index entry must be accounted for With GROUP BY: the aggregate operator must be applied separately to each group of tuples. Use sorting or hashing on the group attributes to partition the file into the appropriate groups; Computes the aggregate function for the tuples in each group. What if we have Clustering index on the grouping attributes? Implementing Aggregate Operations and Outer Joins (3) Implementing Outer Join: Outer Join Operators: LEFT OUTER JOIN

RIGHT OUTER JOIN FULL OUTER JOIN. The full outer join produces a result which is equivalent to the union of the results of the left and right outer joins. Example: SELECT FNAME, DNAME FROM (EMPLOYEE LEFT OUTER JOIN DEPARTMENT ON DNO = DNUMBER); Note: The result of this query is a table of employee names and their associated departments. It is similar to a regular join result, with the exception that if an employee does not have an associated department, the employee's name will still appear in the resulting table, although the department name would be indicated as null.

Implementing Aggregate Operations and Outer Joins (4) Implementing Outer Join (contd.): Modifying Join Algorithms: Nested Loop or Sort-Merge joins can be modified to implement outer join. E.g., For left outer join, use the left relation as outer relation and construct result from every tuple in the left relation. If there is a match, the concatenated tuple is saved in the result. However, if an outer tuple does not match, then the tuple is still included in the result but is padded with a null value(s). Implementing Aggregate Operations and Outer Joins (5)

Implementing Outer Join (contd.): Executing a combination of relational algebra operators. Implement the previous left outer join example {Compute the JOIN of the EMPLOYEE and DEPARTMENT tables} TEMP1 FNAME,DNAME(EMPLOYEE DEPARTMENT) DNO=DNUMBER {Find the EMPLOYEEs that do not appear in the JOIN} TEMP2 FNAME

(EMPLOYEE) - FNAME (Temp1) {Pad each tuple in TEMP2 with a null DNAME field} TEMP2 TEMP2 x 'null' {UNION the temporary tables to produce the LEFT OUTER JOIN} RESULT TEMP1 TEMP2 The cost of the outer join, as computed above, would include the cost of the associated steps (i.e., join, projections and union).

6. Combining Operations using Pipelining (1) Motivation A query is mapped into a sequence of operations. Each execution of an operation produces a temporary result. Generating and saving temporary files on disk is time consuming and expensive. Alternative: Avoid constructing temporary results as much as possible. Pipeline the data through multiple operations - pass the result of a previous operator to the next without waiting to complete the previous operation. Combining Operations using Pipelining (2)

Example: For a 2-way join, combine the 2 selections on the input and one projection on the output with the Join. Dynamic generation of code to allow for multiple operations to be pipelined. Results of a select operation are fed in a "Pipeline" to the join algorithm. Also known as stream-based processing. 7. Using Heuristics in Query Optimization (1) Process for heuristics optimization 1. The parser of a high-level query generates an initial internal representation; 2. Apply heuristics rules to optimize the internal representation.

3. A query execution plan is generated to execute groups of operations based on the access paths available on the files involved in the query. The main heuristic is to apply first the operations that reduce the size of intermediate results. E.g., Apply SELECT and PROJECT operations before applying the JOIN or other binary operations. Using Heuristics in Query Optimization (2) Query tree: A tree data structure that corresponds to a relational algebra expression. It represents the input relations of the query as leaf nodes of the tree, and represents the relational algebra operations as internal nodes.

An execution of the query tree consists of executing an internal node operation whenever its operands are available and then replacing that internal node by the relation that results from executing the operation. Query graph: A graph data structure that corresponds to a relational calculus expression. It does not indicate an order on which operations to perform first. There is only a single graph corresponding to each Using Heuristics in Query Optimization (3) Example: For every project located in Stafford, retrieve the project number, the controlling department number and

the department managers last name, address and birthdate. Relation algebra: PNUMBER, DNUM, LNAME, ADDRESS, BDATE (((sPLOCATION=STAFFORD(PROJECT)) DNUM=DNUMBER (EMPLOYEE)) SQL query: Q2: SELECT (DEPARTMENT)) MGRSSN=SSN P.NUMBER,P.DNUM,E.LNAME, E.ADDRESS, E.BDATE

FROM PROJECT AS P,DEPARTMENT AS D, EMPLOYEE AS E WHERE P.DNUM=D.DNUMBER AND D.MGRSSN=E.SSN AND P.PLOCATION=STAFFORD; Using Heuristics in Query Optimization (4) Using Heuristics in Query Optimization (5) Heuristic Optimization of Query Trees: The same query could correspond to many different relational algebra expressions and hence many different query trees. The task of heuristic optimization of query trees is to find a final query tree that is efficient to

execute. Example: Q: SELECT LNAME FROM EMPLOYEE, WORKS_ON, PROJECT WHERE PNAME = AQUARIUS AND PNMUBER=PNO AND ESSN=SSN AND BDATE > 1957-12-31; Using Heuristics in Query Optimization (6) Using Heuristics in Query Optimization (7)

Using Heuristics in Query Optimization (8) Using Heuristics in Query Optimization (9) General Transformation Rules for Relational Algebra Operations: 1. Cascade of s: A conjunctive selection condition can be broken up into a cascade (sequence) of individual s operations: s c1 AND c2 AND ... AND cn(R) = sc1 (sc2 (...(scn(R))...) ) 2. Commutativity of s: The s operation is commutative: s (s (R)) = s (s (R)) c1 c2

c2 c1 3. Cascade of : In a cascade (sequence) of operations, all but the last one can be ignored: List1 (List2 (...(Listn(R))...) ) = List1(R) 4. Commuting s with : If the selection condition c involves only the attributes A1, ..., An in the projection list, the two operations can be commuted: A1, A2, ..., An (sc (R)) = sc (A1, A2, ..., An (R)) Using Heuristics in Query Optimization (10) General Transformation Rules for Relational Algebra Operations (contd.): 5. Commutativity of ( and x ): The operation is

commutative as is the x operation: R C S = S C R; R x S = S x R 6. Commuting s with (or x ): If all the attributes in the selection condition c involve only the attributes of one of the relations being joinedsay, Rthe two operations can be commuted as follows: s ( R S ) = (s (R)) S c c Alternatively, if the selection condition c can be written as

(c1 and c2), where condition c1 involves only the attributes of R and condition c2 involves only the attributes of S, the operations commute as follows: s ( R S ) = (s (R)) (s (S)) c c1 c2 Using Heuristics in Query Optimization (11) General Transformation Rules for Relational Algebra Operations (contd.): 7. Commuting with (or x): Suppose that the projection list is L = {A1, ..., An, B1, ..., Bm}, where

A1, ..., An are attributes of R and B1, ..., Bm are attributes of S. If the join condition c involves only attributes in L, the two operations can be commuted as follows: L ( R C S ) = (A1, ..., An (R)) C ( B1, ..., Bm (S)) If the join condition C contains additional attributes not in L, these must be added to the projection list, and a final operation is needed. Using Heuristics in Query Optimization (12) General Transformation Rules for Relational Algebra Operations (contd.): 8. Commutativity of set operations: The set operations and are commutative but is not. 9. Associativity of , x, , and : These four

operations are individually associative; that is, if q stands for any one of these four operations (throughout the expression), we have ( R q S ) q T = R q ( S q T ) 10. Commuting s with set operations: The s operation commutes with , , and . If q stands for any one of these three operations, we have s ( R q S ) = (s (R)) q (s (S)) c c c Using Heuristics in Query Optimization (13) General Transformation Rules for Relational Algebra Operations (contd.): The operation commutes with . L ( R S ) =

(L (R)) (L (S)) Converting a (s, x) sequence into : If the condition c of a s that follows a x Corresponds to a join condition, convert the (s, x) sequence into a as follows: (sC (R x S)) = (R C S) Other transformations Using Heuristics in Query Optimization (14) Outline of a Heuristic Algebraic Optimization Algorithm: 1. Using rule 1, break up any select operations with conjunctive conditions into a cascade of select operations. 2. Using rules 2, 4, 6, and 10 concerning the commutativity of select with other operations, move each select operation as far down the query tree as is permitted by the attributes involved in the select condition.

3. Using rule 9 concerning associativity of binary operations, rearrange the leaf nodes of the tree so that the leaf node relations with the most restrictive select operations are executed first in the query tree representation. 4. Using Rule 12, combine a Cartesian product operation with a subsequent select operation in the tree into a join operation. 5. Using rules 3, 4, 7, and 11 concerning the cascading of project and the commuting of project with other operations, break down and move lists of projection attributes down the tree as far as possible by creating new project operations as needed. 6. Identify subtrees that represent groups of operations that can be executed by a single algorithm. Using Heuristics in Query Optimization (15) Summary of Heuristics for Algebraic

Optimization: 1. The main heuristic is to apply first the operations that reduce the size of intermediate results. 2. Perform select operations as early as possible to reduce the number of tuples and perform project operations as early as possible to reduce the number of attributes. (This is done by moving select and project operations as far down the tree as possible.) 3. The select and join operations that are most restrictive should be executed before other similar operations. (This is done by reordering the leaf nodes of the tree among themselves and adjusting the rest of the tree appropriately.) Using Heuristics in Query Optimization (16) Query Execution Plans

An execution plan for a relational algebra query consists of a combination of the relational algebra query tree and information about the access methods to be used for each relation as well as the methods to be used in computing the relational operators stored in the tree. Materialized evaluation: the result of an operation is stored as a temporary relation. Pipelined evaluation: as the result of an operator is produced, it is forwarded to the next operator in sequence. 8. Using Selectivity and Cost Estimates in Query Optimization (1) Cost-based query optimization: Estimate and compare the costs of executing a query using different execution strategies and choose the strategy with the lowest cost

estimate. (Compare to heuristic query optimization) Issues Cost function Number of execution strategies to be considered Using Selectivity and Cost Estimates in Query Optimization (2) Cost Components for Query Execution 1. Access cost to secondary storage 2. Storage cost 3. Computation cost 4. Memory usage cost 5. Communication cost Note: Different database systems may focus

on different cost components. Using Selectivity and Cost Estimates in Query Optimization (3) Catalog Information Used in Cost Functions Information about the size of a file number of records (tuples) (r), record size (R), number of blocks (b) blocking factor (bfr) Information about indexes and indexing attributes of a file Number of levels (x) of each multilevel index Number of first-level index blocks (bI1) Number of distinct values (d) of an attribute

Selectivity (sl) of an attribute Selection cardinality (s) of an attribute. (s = sl * r) Using Selectivity and Cost Estimates in Query Optimization (4) Examples of Cost Functions for SELECT S1. Linear search (brute force) approach C S1a = b; For an equality condition on a key, C S1a = (b/2) if the record is found; otherwise CS1a = b. S2. Binary search: C = log b + (s/bfr) 1 S2 2 For an equality condition on a unique (key)

attribute, CS2 =log2b S3. Using a primary index (S3a) or hash key (S3b) to retrieve a single record C = x + 1; CS3b = 1 for static or linear hashing; C S3b = 1 for extendible hashing; S3a Using Selectivity and Cost Estimates in Query Optimization (5) Examples of Cost Functions for SELECT (contd.) S4. Using an ordering index to retrieve multiple records: For the comparison condition on a key field with an

ordering index, CS4 = x + (b/2) S5. Using a clustering index to retrieve multiple records: CS5 = x + (s/bfr) S6. Using a secondary (B+-tree) index: For an equality comparison, CS6a = x + s; For an comparison condition such as >, <, >=, or <=, Using Selectivity and Cost Estimates in Query Optimization (6) Examples of Cost Functions for SELECT (contd.) S7. Conjunctive selection:

Use either S1 or one of the methods S2 to S6 to solve. For the latter case, use one condition to retrieve the records and then check in the memory buffer whether each retrieved record satisfies the remaining conditions in the conjunction. S8. Conjunctive selection using a composite index: Same as S3a, S5 or S6a, depending on the type of index. Using Selectivity and Cost Estimates in Query Optimization (7) Examples of Cost Functions for JOIN

Join selectivity (js) js = | (R C S) | / | R x S | = | (R C S) | / (|R| * |S |) If condition C does not exist, js = 1; If no tuples from the relations satisfy condition C, js = 0; Usually, 0 <= js <= 1; Size of the result file after join operation | (R C S) | = js * |R| * |S | Using Selectivity and Cost Estimates in Query Optimization (8) Examples of Cost Functions for JOIN (contd.)

J1. Nested-loop join: CJ1 = bR + (bR*bS) + ((js* |R|* |S|)/bfrRS) (Use R for outer loop) J2. Single-loop join (using an access structure to retrieve the matching record(s)) If an index exists for the join attribute B of S with index levels xB, we can retrieve each record s in R and then use the index to retrieve all the matching records t from S that satisfy t[B] = s[A]. The cost depends on the type of index. Using Selectivity and Cost Estimates in Query Optimization (9) Examples of Cost Functions for JOIN (contd.) J2. Single-loop join (contd.)

For a secondary index, CJ2a = bR + (|R| * (xB + sB)) + ((js* |R|* |S|)/bfrRS); For a clustering index, CJ2b = bR + (|R| * (xB + (sB/bfrB))) + ((js* |R|* |S|)/bfrRS); For a primary index, CJ2c = bR + (|R| * (xB + 1)) + ((js* |R|* |S|)/bfrRS); If a hash key exists for one of the two join attributes B of S

CJ2d = bR + (|R| * h) + ((js* |R|* |S|)/bfrRS); J3. Sort-merge join: CJ3a = CS + bR + bS + ((js* |R|* |S|)/bfrRS); (CS: Cost for sorting files) Using Selectivity and Cost Estimates in Query Optimization (10) Multiple Relation Queries and Join Ordering A query joining n relations will have n-1 join operations, and hence can have a large number of different join orders when we apply the algebraic transformation rules. Current query optimizers typically limit the structure of a (join) query tree to that of left-deep (or right-deep) trees. Left-deep tree:

A binary tree where the right child of each non-leaf node is always a base relation. Amenable to pipelining Could utilize any access paths on the base relation (the right child) when executing the join. 9. Overview of Query Optimization in Oracle Oracle DBMS V8 Rule-based query optimization: the optimizer chooses execution plans based on heuristically ranked operations. (Currently it is being phased out) Cost-based query optimization: the optimizer

examines alternative access paths and operator algorithms and chooses the execution plan with lowest estimate cost. The query cost is calculated based on the estimated usage of resources such as I/O, CPU and memory needed. Application developers could specify hints to the ORACLE query optimizer. The idea is that an application developer might 10. Semantic Query Optimization Semantic Query Optimization: Uses constraints specified on the database schema in

order to modify one query into another query that is more efficient to execute. Consider the following SQL query, SELECT E.LNAME, M.LNAME FROM EMPLOYEE E M WHERE E.SUPERSSN=M.SSN AND E.SALARY>M.SALARY Explanation: Suppose that we had a constraint on the database schema that stated that no employee can earn more than his or her direct supervisor. If the semantic query optimizer checks for the existence of this constraint, it need not execute the query at all because it knows that the result of the query will be empty. Techniques known as theorem proving can be used for this purpose. Part 2 DB Control Issues: Security, Backup and

Recovery, Concurrency 65 Chapter Objectives List the major data control issues handled by database management systems. List and describe the types of data security breaches. List and describe the types of data security measures. 11-66 Chapter Objectives

Describe the concept of backup and recovery. Describe the major backup and recovery techniques. Explain the problem of disaster recovery. 11-67 Chapter Objectives Describe the concept of concurrency control. Describe such concurrency control issues and measures as the lost update problem, locks and deadlock, and versioning. 11-68

Database Control Issues Different corporate resources have different management requirements. Money must be protected from theft Equipment must be secured against misuse Buildings may require security guards Data is a corporate resource and has its own peculiar concerns, which we call database control issues. Data security Backup and recovery Concurrency control 11-69

Database Control Issues Data Security - protecting the data from theft, from malicious destruction, from unauthorized updating, etc. Backup and Recovery - having procedures in place to recreate data that has been lost, for any reason. Concurrency Control - problems that can occur when two or more transactions or users attempt to update a piece of data simultaneously. 11-70

The Importance of Data Security Good data security is absolutely critical to every company and organization. A data security breach can dramatically affect a companys ability to continue normal functioning. Customer data, which, for example, can be financial, medical, or legal in nature, must be carefully guarded. 11-71 Types of Data Security Breaches Unauthorized Data Access - someone

obtains data that she is not authorized to see. Unauthorized Data or Program Modification - someone changes the value of stored data that they are not entitled to change. Malicious Mischief - someone can corrupt or even erase some of a companys data; hardware can be damaged, making data 11-72 Methods of Breaching Data Security

11-73 Methods of Breaching Data Security Unauthorized Computer Access Intercepting Data Communications Stealing Disks or Computers Computer Viruses Damaging Computer Hardware 11-74 Unauthorized Computer Access By hacking or gaining access from outside of the company. Some hackers are software experts. Some hackers have stolen identification names

and passwords and can enter a computer looking like legitimate users. Legitimate users, e.g., employees stealing data 11-75 Intercepting Data Communications Wiretapping Data can be stolen while it is being transmitted. Twisted-pair telephone wire or coaxial cable can be tapped. Data bounced off satellites may be intercepted. Light pulses with fiber-optic transmission cannot

be easily tapped. 11-76 Stealing Disks or Computers Flash Disks, and CDs all have the potential of being stolen. Laptop computers can be stolen. Even desktop computers have been stolen from company offices. 11-77 Computer Viruses A malicious piece of software that is capable

of copying itself and spreading from computer to computer on diskettes and through telecommunications lines. Computer viruses that travel along data communications lines are also called worms. 11-78 Damaging Computer Hardware Might be either deliberate or accidental. Fires Coffee spills Hurricanes Disgruntled or newly fired employees with hammers or whatever other hard objects were handy.

11-79 Types of Data Security Measures 11-80 Physical Security of Company Premises Dont put the computer in the basement because of the possibility of floods. Dont put the computer on the ground floor because of the possibility of a truck driving into the building, accidentally or on purpose. 11-81

Physical Security of Company Premises Dont put the computer above the eighth floor because thats as high as fire truck ladders can reach. Dont put the computer on the top floor of the building because it is subject to helicopter landing and attack. 11-82 Physical Security of Company Premises If you occupy at least three floors of the building, dont put the computer on your topmost floor because its ceiling is another

companys floor, and dont put the computer on your bottommost floor because its floor is another companys ceiling. 11-83 Physical Security of Company Premises Whatever floor you put the computer on, keep it in an interior space away from the windows. 11-84 Physical Security: Limit Access Access should be limited to those people who

have a legitimate need to be in the computer room. Control access to the room. 11-85 Physical Security: Access to Room Require something people know, such as a secret code to be punched in. Require people have something, such as a magnetic stripe card, possibly combined with a secret code. Use some human part that can be measured or

scanned. These biometric systems can be based on fingerprints, the dimensions and positions of facial features, retinal blood vessel patterns, or voice patterns. 11-86 Controlled Access to the Computer System First line of defense: Identification tag Password 11-87 Password Must be kept secret. Must be changed periodically. Must not be written down.

Should not appear on the terminal screen when typed. Should be user-created. 11-88 Access to the Database Restrict access to specific data so that only specific people can retrieve or modify it. Some systems have such controls in the operating system or in other utility software. An additional layer of passwords may also

be introduced. 11-89 Access to the Database At the DBMS level a user cannot simply access any data he wants to; users have to be given explicit authorization to access data. Use views (CREATE VIEW) Use SQL GRANT command. 11-90 The SQL GRANT Command GRANT privileges ON (view or table) TO users [ WITH GRANT OPTION].

GRANT SELECT ON SALESPERSON TO GLENN; 11-91 Data Encryption Data is changed, bit-by-bit or character-by- character, into a form that looks totally garbled. Data can be stored, transmitted, etc. encrypted. To be used, data must be decrypted. 11-92 Data Encryption

Encryption generally involves a data conversion algorithm and a secret key. The recipient must be aware of both the algorithm and the secret key so that it can work the algorithm in reverse and decrypt the data. 11-93 Data Encryption Techniques Symmetric or private key encryption Asymmetric or public key encryption 11-94 Symmetric Encryption

Require the same long bit-by-bit key for encrypting and decrypting the data. Transmitting the private key may compromise the key. 11-95 Asymmetric Encryption Uses two different keys: Public key - used for encrypting the data Private key - used for decrypting the data Process tends to be slower than symmetric encryption.

11-96 SSL Technology Secure Socket Layer A combination of private key and public key encryption. Used on the World Wide Web. 11-97 SSL - Usage Example A person at home who wants to buy something from an online store. Her PC and its WWW browser are the client. The online stores computer is the server.

11-98 SSL - Usage Example Both sides want to conduct the secure transaction using private key technology. They have the problem of one side picking a private key and getting it to the other side in a secure manner. How do they do it? 11-99 SSL - Usage Example The client contacts the server

The server sends the client its public key for its public key algorithm. No one cares if this public key is stolen. The client, using a random number generator, creates a session key. the key for the private key algorithm with which the secure transaction will be conducted 11-100 SSL - Usage Example The problem: How is the client going to

securely transmit the session key it generated to the server, since both must have it to use the private key algorithm for the transaction? 11-101 SSL - Usage Example The client is going to send the session key to the server securely, using a public key algorithm and the servers public key. The client encrypts the session key using the servers public key The client transmits the encrypted session key to the server with the public key algorithm.

11-102 SSL - Usage Example Once the session key has been securely transmitted to the server, both the client and the server have it and the secure transaction can proceed using the private key algorithm. 11-103 Antivirus Software Used to combat computer viruses. Two basic methods: Virus signatures - portions of the virus code that are considered to be unique to it. Monitoring - software constantly monitors the

computer environment to watch for requests or commands for any unusual activity. 11-104 Firewalls Software or a combination of hardware and software that protects a companys computer and its data against external attack via data communications lines. Different kinds of firewalls. 11-105 Firewall: Proxy Server

A firewall that is a combination of hardware and software. The proxy server takes apart the incoming message, extracts the legitimate pieces of data, reformats the data for the companys mainframe, and passes the data on to the companys main computer. 11-106 Training Employees in Good Security Practices Log off your computer or at least lock your office door when you leave your office. Dont write your computer password down anywhere.

Dont respond to any unusual requests for information about the computer system from anyone over the telephone. 11-107 Training Employees in Good Security Practices Dont leave flash disks or other storage media lying around your office. Dont take flash disks or other storage media out of the building. Dont assume that a stranger in the building

is there legitimately without checking. 11-108 Backup and Recovery We have to assume that from time to time something will go wrong with our data, and so we have to have the tools available to correct or reconstruct it. 11-109 Backup Copies and Journals Two basic but very important tasks: backing up the database maintaining a journal

11-110 Backup On a regularly scheduled basis, a companys databases must be backed up or copied. The backup copy must be put in a safe place, away from the original in the computer system. 11-111 Maintaining a Journal Tracks all changes that take place in the data. Updates to existing records Insertion of new records

Deletion of existing records Does not track read operations, because they do not change the data. 11-112 Database Log Started immediately after the data is backup up. Two types: Change log / before and after image log Records data value before and after a change Transaction log Keeps a record of the program that changed the data and all of the inputs that the program used. 11-113

(Roll) Forward Recovery Assume a database table has been lost. To recreate this table: Ready the last backup copy of the table. Ready the log Roll forward in the log, applying the changes that were made to the table since the last backup. 11-114 Forward Recovery 11-115 Change Log

Only the last one of the changes to the particular piece of data, which shows the value of this piece of data at the point that the table was destroyed, needs to be used in updating the database copy in the rollforward operation. 11-116 Backward Recovery or Rollback Suppose that in the midst of normal operation an error is discovered that involves a piece of recently updated data. The discovered error, and all other changes that were made to the database since the error was discovered, must be backed out.

11-117 Backward Recovery Start with the database in its current state. The log is positioned at the last entry. 11-118 Backward Recovery A recovery program proceeds

backwards through the log, resetting each updated data value in the database to its before image, until it reaches the point where the error was made. 11-119 Duplicate or Mirrored Databases Two copies of the entire database are maintained, and both are updated simultaneously.

11-120 Duplicate or Mirrored Databases Advantage: If one system is destroyed, the applications that use the database can just keep on running with the duplicate database. Disadvantage: This is a relatively expensive proposition. 11-121 Disaster Recovery

Rebuilding an entire information system or significant parts of one, after a catastrophic natural disaster such as: a hurricane a tornado a earthquake a building collapse a major fire 11-122 Being Prepared for Disaster Recovery Maintain totally mirrored systems (not just databases) in different cities. Contract with a company that maintains

hardware similar to yours (a hot site) so that you can be up and running again quickly after a disaster. Build a computer center that is relatively disaster proof. 11-123 Being Prepared for Disaster Recovery Maintain space (a cold site) with electrical connections, air conditioning, etc., into which new hardware can be moved if need be. Make a reciprocal arrangement with another

company with hardware similar to yours to aid each other in case one suffers a disaster. 11-124 Concurrency Control Many people using todays applications systems will require access to the same data at the same time. Two or more users attempting to update some data simultaneously will conflict. 11-125 The Lost Update Problem

11-126 Locks and Deadlock When a user begins an update operation on a piece of data, the DBMS locks that data. Any attempt to begin another update operation on that same piece of data will be blocked, or locked out, until the first update operation is completed and its lock on the data is released. 11-127 Locks

Prevents the Lost Update Problem. Granularity of lock can vary. Entire table Record level Etc. 11-128 Deadlock Two or more transactions must each update the same, multiple pieces of data. They each wait endlessly for the other to release the data that each has already locked. Also called the deadly embrace.

11-129 Deadlock 11-130 Handling Deadlock Deadlock Prevention Difficult to accomplish Deadlock Detection Allow deadlock to occur Detect occurrence Abort one of the deadlocked transactions 11-131 Versioning

Does not involve locks at all. Each transaction is given a copy or version of the data that it needs for an update operation. Each transaction records its result in its own copy of the data. Then each transaction tries to update the actual database with its result. 11-132 Versioning Monitoring software checks to see if there is

a conflict between two or more transactions trying to update the same data at the same time. If there is, the software allows one of the transactions to update the database and makes the other(s) start over again. 11-133 Additional Material (Going Deeper) Security, Concurrency, Recovery 134 Chapter 24 Database

Security Copyright 2011 Pearson Education, Inc. Publishing as Pearson Addison-Wesley 1 Introduction to Database Security Issues Types of Security Legal and ethical issues Policy issues System-related issues The need to identify multiple security levels

Copyright 2011 Ramez Elmasri and Shamkant Navathe Introduction to Database Security Issues (2) Threats to databases Loss of integrity Loss of availability Loss of confidentiality To protect databases against these types of threats four kinds of countermeasures can be implemented:

Access control Inference control Flow control Encryption Copyright 2011 Ramez Elmasri and Shamkant Navathe Introduction to Database Security Issues (3) A DBMS typically includes a database security and authorization subsystem that is responsible for ensuring the security portions of a database

against unauthorized access. Two types of database security mechanisms: Discretionary security mechanisms Mandatory security mechanisms Copyright 2011 Ramez Elmasri and Shamkant Navathe Introduction to Database Security Issues (4) The security mechanism of a DBMS must include provisions for restricting access to the database

as a whole This function is called access control and is handled by creating user accounts and passwords to control login process by the DBMS. Copyright 2011 Ramez Elmasri and Shamkant Navathe Introduction to Database Security Issues (5) The security problem associated with databases is that of controlling the access to a statistical database, which is used to provide statistical information or summaries of values based on various criteria.

The countermeasures to statistical database security problem is called inference control measures. Copyright 2011 Ramez Elmasri and Shamkant Navathe Introduction to Database Security Issues (6) Another security is that of flow control, which prevents information from flowing in such a way that it reaches unauthorized users. Channels that are pathways for information to flow implicitly in ways that violate the security

policy of an organization are called covert channels. Copyright 2011 Ramez Elmasri and Shamkant Navathe Introduction to Database Security Issues (7) A final security issue is data encryption, which is used to protect sensitive data (such as credit card numbers) that is being transmitted via some type communication network. The data is encoded using some encoding algorithm.

An unauthorized user who access encoded data will have difficulty deciphering it, but authorized users are given decoding or decrypting algorithms (or keys) to decipher data. Copyright 2011 Ramez Elmasri and Shamkant Navathe 1.2 Database Security and the DBA The database administrator (DBA) is the central authority for managing a database system. The DBAs responsibilities include

granting privileges to users who need to use the system classifying users and data in accordance with the policy of the organization The DBA is responsible for the overall security of the database system. Copyright 2011 Ramez Elmasri and Shamkant Navathe 1.2 Database Security and the DBA (2) The DBA has a DBA account in the DBMS

Sometimes these are called a system or superuser account These accounts provide powerful capabilities such as: 1. Account creation 2. Privilege granting 3. Privilege revocation 4. Security level assignment Action 1 is access control, whereas 2 and 3 are discretionarym and 4 is used to control mandatory authorization Copyright 2011 Ramez Elmasri and Shamkant Navathe

1.3 Access Protection, User Accounts, and Database Audits Whenever a person or group of person s need to access a database system, the individual or group must first apply for a user account. The DBA will then create a new account id and password for the user if he/she deems there is a legitimate need to access the database The user must log in to the DBMS by entering account id and password whenever database access is needed.

Copyright 2011 Ramez Elmasri and Shamkant Navathe 1.3 Access Protection, User Accounts, and Database Audits(2) The database system must also keep track of all operations on the database that are applied by a certain user throughout each login session. To keep a record of all updates applied to the database and of the particular user who applied each update, we can modify system log, which includes an entry for each operation applied to the database that may be required for recovery from a transaction failure or system crash.

Copyright 2011 Ramez Elmasri and Shamkant Navathe 1.3 Access Protection, User Accounts, and Database Audits(3) If any tampering with the database is suspected, a database audit is performed A database audit consists of reviewing the log to examine all accesses and operations applied to the database during a certain time period. A database log that is used mainly for security purposes is sometimes called an audit trail.

Copyright 2011 Ramez Elmasri and Shamkant Navathe Discretionary Access Control Based on Granting and Revoking Privileges The typical method of enforcing discretionary access control in a database system is based on the granting and revoking privileges. Copyright 2011 Ramez Elmasri and Shamkant Navathe 2.1Types of Discretionary Privileges The account level:

At this level, the DBA specifies the particular privileges that each account holds independently of the relations in the database. The relation level (or table level): At this level, the DBA can control the privilege to access each individual relation or view in the database. Copyright 2011 Ramez Elmasri and Shamkant Navathe 2.1Types of Discretionary Privileges(2) The privileges at the account level apply to the capabilities provided to the account itself and can include

the CREATE SCHEMA or CREATE TABLE privilege, to create a schema or base relation; the CREATE VIEW privilege; the ALTER privilege, to apply schema changes such adding or removing attributes from relations; the DROP privilege, to delete relations or views; the MODIFY privilege, to insert, delete, or update tuples; and the SELECT privilege, to retrieve information from the database by using a SELECT query.

Copyright 2011 Ramez Elmasri and Shamkant Navathe 2.1Types of Discretionary Privileges(3) The second level of privileges applies to the relation level This includes base relations and virtual (view) relations. The granting and revoking of privileges generally follow an authorization model for discretionary privileges known as the access matrix model where

The rows of a matrix M represents subjects (users, accounts, programs) The columns represent objects (relations, records, columns, views, operations). Each position M(i,j) in the matrix represents the types of privileges (read, write, update) that subject i holds on object j. Copyright 2011 Ramez Elmasri and Shamkant Navathe 2.1Types of Discretionary Privileges(4) To control the granting and revoking of relation privileges, each relation R in a database is assigned and owner account, which is typically the account that was used when the relation was created in the first place.

The owner of a relation is given all privileges on that relation. In SQL2, the DBA can assign and owner to a whole schema by creating the schema and associating the appropriate authorization identifier with that schema, using the CREATE SCHEMA command. The owner account holder can pass privileges on any of the owned relation to other users by granting privileges to their accounts. Copyright 2011 Ramez Elmasri and Shamkant Navathe 2.1Types of Discretionary Privileges(5)

In SQL the following types of privileges can be granted on each individual relation R: SELECT (retrieval or read) privilege on R: Gives the account retrieval privilege. In SQL this gives the account the privilege to use the SELECT statement to retrieve tuples from R. MODIFY privileges on R:

This gives the account the capability to modify tuples of R. In SQL this privilege is further divided into UPDATE, DELETE, and INSERT privileges to apply the corresponding SQL command to R. In addition, both the INSERT and UPDATE privileges can specify that only certain attributes can be updated by the account. Copyright 2011 Ramez Elmasri and Shamkant Navathe 2.1Types of Discretionary Privileges(6) In SQL the following types of privileges can be granted on each individual relation R (contd.):

REFERENCES privilege on R: This gives the account the capability to reference relation R when specifying integrity constraints. The privilege can also be restricted to specific attributes of R. Notice that to create a view, the account must have SELECT privilege on all relations involved in the view definition. Copyright 2011 Ramez Elmasri and Shamkant Navathe 2.2 Specifying Privileges Using Views

The mechanism of views is an important discretionary authorization mechanism in its own right. For example, If the owner A of a relation R wants another account B to be able to retrieve only some fields of R, then A can create a view V of R that includes only those attributes and then grant SELECT on V to B. The same applies to limiting B to retrieving only certain tuples of R; a view V can be created by defining the view by means of a query that selects only those tuples from R that A wants to allow B to access. Copyright 2011 Ramez Elmasri and Shamkant Navathe

2.3 Revoking Privileges In some cases it is desirable to grant a privilege to a user temporarily. For example, The owner of a relation may want to grant the SELECT privilege to a user for a specific task and then revoke that privilege once the task is completed. Hence, a mechanism for revoking privileges is needed. In SQL, a REVOKE command is included for the purpose of canceling privileges. Copyright 2011 Ramez Elmasri and Shamkant Navathe

2.4 Propagation of Privileges using the GRANT OPTION Whenever the owner A of a relation R grants a privilege on R to another account B, privilege can be given to B with or without the GRANT OPTION. If the GRANT OPTION is given, this means that B can also grant that privilege on R to other accounts. Suppose that B is given the GRANT OPTION by A and that B then grants the privilege on R to a third account C, also with GRANT OPTION. In this way, privileges on R can propagate to other accounts without the knowledge of the

owner of R. If the owner account A now revokes the privilege granted to B, all the privileges that B propagated based on that privilege should automatically be revoked by the system. Copyright 2011 Ramez Elmasri and Shamkant Navathe 2.5 An Example Suppose that the DBA creates four accounts A1, A2, A3, A4 and wants only A1 to be able to create base relations. Then the DBA must issue the following GRANT command

in SQL GRANT CREATETAB TO A1; In SQL2 the same effect can be accomplished by having the DBA issue a CREATE SCHEMA command as follows: CREATE SCHAMA EXAMPLE AUTHORIZATION A1; Copyright 2011 Ramez Elmasri and Shamkant Navathe 2.5 An Example (2) User account A1 can create tables under the schema called EXAMPLE.

Suppose that A1 creates the two base relations EMPLOYEE and DEPARTMENT A1 is then owner of these two relations and hence all the relation privileges on each of them. Suppose that A1 wants to grant A2 the privilege to insert and delete tuples in both of these relations, but A1 does not want A2 to be able to propagate these privileges to additional accounts: GRANT INSERT, DELETE ON EMPLOYEE, DEPARTMENT TO A2; Copyright 2011 Ramez Elmasri and Shamkant Navathe 2.5 An Example (3)

Copyright 2011 Ramez Elmasri and Shamkant Navathe 2.5 An Example (4) Suppose that A1 wants to allow A3 to retrieve information from either of the two tables and also to be able to propagate the SELECT privilege to other accounts. A1 can issue the command: GRANT SELECT ON EMPLOYEE, DEPARTMENT TO A3 WITH GRANT OPTION; A3 can grant the SELECT privilege on the EMPLOYEE relation to A4 by issuing:

GRANT SELECT ON EMPLOYEE TO A4; Notice that A4 cant propagate the SELECT privilege because GRANT OPTION was not given to A4 Copyright 2011 Ramez Elmasri and Shamkant Navathe 2.5 An Example (5) Suppose that A1 decides to revoke the SELECT privilege on the EMPLOYEE relation from A3; A1 can issue: REVOKE SELECT ON EMPLOYEE FROM A3;

The DBMS must now automatically revoke the SELECT privilege on EMPLOYEE from A4, too, because A3 granted that privilege to A4 and A3 does not have the privilege any more. Copyright 2011 Ramez Elmasri and Shamkant Navathe 2.5 An Example (6) Suppose that A1 wants to give back to A3 a limited capability to SELECT from the EMPLOYEE relation and wants to allow A3 to be able to propagate the privilege. The limitation is to retrieve only the NAME, BDATE, and ADDRESS attributes and only for the tuples with DNO=5. A1 then create the view:

CREATE VIEW A3EMPLOYEE AS SELECT NAME, BDATE, ADDRESS FROM EMPLOYEE WHERE DNO = 5; After the view is created, A1 can grant SELECT on the view A3EMPLOYEE to A3 as follows: GRANT SELECT ON A3EMPLOYEE TO A3 WITH GRANT OPTION; Copyright 2011 Ramez Elmasri and Shamkant Navathe 2.5 An Example (7)

Finally, suppose that A1 wants to allow A4 to update only the SALARY attribute of EMPLOYEE; A1 can issue: GRANT UPDATE ON EMPLOYEE (SALARY) TO A4; The UPDATE or INSERT privilege can specify particular attributes that may be updated or inserted in a relation. Other privileges (SELECT, DELETE) are not attribute specific. Copyright 2011 Ramez Elmasri and Shamkant Navathe 2.6 Specifying Limits on Propagation of

Privileges Techniques to limit the propagation of privileges have been developed, although they have not yet been implemented in most DBMSs and are not a part of SQL. Limiting horizontal propagation to an integer number i means that an account B given the GRANT OPTION can grant the privilege to at most i other accounts. Vertical propagation is more complicated; it limits the depth of the granting of privileges. Copyright 2011 Ramez Elmasri and Shamkant Navathe

3 Mandatory Access Control and Role-Based Access Control for Multilevel Security The discretionary access control techniques of granting and revoking privileges on relations has traditionally been the main security mechanism for relational database systems. This is an all-or-nothing method: A user either has or does not have a certain privilege. In many applications, and additional security policy is

needed that classifies data and users based on security classes. This approach as mandatory access control, would typically be combined with the discretionary access control mechanisms. Copyright 2011 Ramez Elmasri and Shamkant Navathe 3 Mandatory Access Control and Role-Based Access Control for Multilevel Security (2) Typical security classes are top secret (TS), secret (S), confidential (C), and unclassified (U), where TS is the highest level and U the lowest: TS S C U

The commonly used model for multilevel security, known as the Bell-LaPadula model, classifies each subject (user, account, program) and object (relation, tuple, column, view, operation) into one of the security classifications, T, S, C, or U: Clearance (classification) of a subject S as class(S) and to the classification of an object O as class(O). Copyright 2011 Ramez Elmasri and Shamkant Navathe 3 Mandatory Access Control and Role-Based Access Control for Multilevel Security (3) Two restrictions are enforced on data access based on the subject/object classifications:

Simple security property: A subject S is not allowed read access to an object O unless class(S) class(O). A subject S is not allowed to write an object O unless class(S) class(O). This known as the star property (or * property). Copyright 2011 Ramez Elmasri and Shamkant Navathe 3 Mandatory Access Control and Role-Based Access Control for Multilevel Security (4)

To incorporate multilevel security notions into the relational database model, it is common to consider attribute values and tuples as data objects. Hence, each attribute A is associated with a classification attribute C in the schema, and each attribute value in a tuple is associated with a corresponding security classification. In addition, in some models, a tuple classification attribute TC is added to the relation attributes to provide a classification for each tuple as a whole. Hence, a multilevel relation schema R with n attributes would be represented as R(A1,C1,A2,C2, , An,Cn,TC)

where each Ci represents the classification attribute associated with attribute Ai. Copyright 2011 Ramez Elmasri and Shamkant Navathe 3 Mandatory Access Control and Role-Based Access Control for Multilevel Security (5) The value of the TC attribute in each tuple t which is the highest of all attribute classification values within t provides a general classification for the tuple itself, whereas each Ci provides a finer security classification for each attribute value within the tuple. The apparent key of a multilevel relation is the set of attributes that would have formed the primary

key in a regular (single-level) relation. Copyright 2011 Ramez Elmasri and Shamkant Navathe 3 Mandatory Access Control and Role-Based Access Control for Multilevel Security (6) A multilevel relation will appear to contain different data to subjects (users) with different clearance levels. In some cases, it is possible to store a single tuple in the relation at a higher classification level and produce the corresponding tuples at a lower-level classification through

a process known as filtering. In other cases, it is necessary to store two or more tuples at different classification levels with the same value for the apparent key. This leads to the concept of polyinstantiation where several tuples can have the same apparent key value but have different attribute values for users at different classification levels. Copyright 2011 Ramez Elmasri and Shamkant Navathe 3 Mandatory Access Control and Role-Based Access Control for Multilevel Security (7) In general, the entity integrity rule for multilevel

relations states that all attributes that are members of the apparent key must not be null and must have the same security classification within each individual tuple. In addition, all other attribute values in the tuple must have a security classification greater than or equal to that of the apparent key. This constraint ensures that a user can see the key if the user is permitted to see any part of the tuple at all. Copyright 2011 Ramez Elmasri and Shamkant Navathe 3 Mandatory Access Control and Role-Based Access Control for Multilevel Security (8)

Other integrity rules, called null integrity and interinstance integrity, informally ensure that if a tuple value at some security level can be filtered (derived) from a higher-classified tuple, then it is sufficient to store the higher-classified tuple in the multilevel relation. Copyright 2011 Ramez Elmasri and Shamkant Navathe 3.1 Comparing Discretionary Access Control and Mandatory Access Control Discretionary Access Control (DAC) policies are characterized by a high degree of flexibility, which makes them suitable for a large variety of application domains.

The main drawback of DAC models is their vulnerability to malicious attacks, such as Trojan horses embedded in application programs. Copyright 2011 Ramez Elmasri and Shamkant Navathe 3.1 Comparing Discretionary Access Control and Mandatory Access Control(2) By contrast, mandatory policies ensure a high degree of protection in a way, they prevent any illegal flow of information. Mandatory policies have the drawback of being too rigid and they are only applicable in limited

environments. In many practical situations, discretionary policies are preferred because they offer a better trade-off between security and applicability. Copyright 2011 Ramez Elmasri and Shamkant Navathe 3.2 Role-Based Access Control Role-based access control (RBAC) emerged rapidly in the 1990s as a proven technology for managing and enforcing security in large-scale enterprisewide systems. Its basic notion is that permissions are associated with roles, and users are assigned to appropriate roles.

Roles can be created using the CREATE ROLE and DESTROY ROLE commands. The GRANT and REVOKE commands discussed under DAC can then be used to assign and revoke privileges from roles. Copyright 2011 Ramez Elmasri and Shamkant Navathe 3.2 Role-Based Access Control (2) RBAC appears to be a viable alternative to traditional discretionary and mandatory access

controls; it ensures that only authorized users are given access to certain data or resources. Many DBMSs have allowed the concept of roles, where privileges can be assigned to roles. Role hierarchy in RBAC is a natural way of organizing roles to reflect the organizations lines of authority and responsibility. Copyright 2011 Ramez Elmasri and Shamkant Navathe 3.2 Role-Based Access Control (3) Another important consideration in RBAC systems is the possible temporal constraints that may exist on roles,

such as time and duration of role activations, and timed triggering of a role by an activation of another role. Using an RBAC model is highly desirable goal for addressing the key security requirements of Web-based applications. In contrast, discretionary access control (DAC) and mandatory access control (MAC) models lack capabilities needed to support the security requirements emerging enterprises and Web-based applications. Copyright 2011 Ramez Elmasri and Shamkant Navathe 3.3 Access Control Policies for E-Commerce and the Web E-Commerce environments require elaborate policies that go beyond traditional DBMSs.

In an e-commerce environment the resources to be protected are not only traditional data but also knowledge and experience. The access control mechanism should be flexible enough to support a wide spectrum of heterogeneous protection objects. A related requirement is the support for contentbased access-control. Copyright 2011 Ramez Elmasri and Shamkant Navathe 3.3 Access Control Policies for E-Commerce and the Web (2)

Another requirement is related to the heterogeneity of subjects, which requires access control policies based on user characteristics and qualifications. A possible solution, to better take into account user profiles in the formulation of access control policies, is to support the notion of credentials. A credential is a set of properties concerning a user that are relevant for security purposes For example, age, position within an organization It is believed that the XML language can play a key role in

access control for e-commerce applications. Copyright 2011 Ramez Elmasri and Shamkant Navathe 4 Introduction to Statistical Database Security Statistical databases are used mainly to produce statistics on various populations. The database may contain confidential data on individuals, which should be protected from user access. Users are permitted to retrieve statistical information on the populations, such as

averages, sums, counts, maximums, minimums, and standard deviations. Copyright 2011 Ramez Elmasri and Shamkant Navathe 4 Introduction to Statistical Database Security (2) A population is a set of tuples of a relation (table) that satisfy some selection condition. Statistical queries involve applying statistical functions to a population of tuples. Copyright 2011 Ramez Elmasri and Shamkant Navathe 4 Introduction to Statistical

Database Security (3) For example, we may want to retrieve the number of individuals in a population or the average income in the population. However, statistical users are not allowed to retrieve individual data, such as the income of a specific person. Statistical database security techniques must prohibit the retrieval of individual data. This can be achieved by prohibiting queries that retrieve attribute values and by allowing only queries that involve

statistical aggregate functions such as COUNT, SUM, MIN, MAX, AVERAGE, and STANDARD DEVIATION. Such queries are sometimes called statistical queries. Copyright 2011 Ramez Elmasri and Shamkant Navathe 4 Introduction to Statistical Database Security (4) It is DBMSs responsibility to ensure confidentiality of information about individuals, while still providing useful statistical summaries of data about those individuals to users. Provision of privacy protection of users in a statistical database is paramount.

In some cases it is possible to infer the values of individual tuples from a sequence statistical queries. This is particularly true when the conditions result in a population consisting of a small number of tuples. Copyright 2011 Ramez Elmasri and Shamkant Navathe 5 Introduction to Flow Control Flow control regulates the distribution or flow of information among accessible objects. A flow between object X and object Y occurs when a program reads values from X and writes values into Y.

Flow controls check that information contained in some objects does not flow explicitly or implicitly into less protected objects. A flow policy specifies the channels along which information is allowed to move. The simplest flow policy specifies just two classes of information: confidential (C) and nonconfidential (N)

and allows all flows except those from class C to class N. Copyright 2011 Ramez Elmasri and Shamkant Navathe 5.1 Covert Channels A covert channel allows a transfer of information that violates the security or the policy. A covert channel allows information to pass from a higher classification level to a lower classification level through improper means. Copyright 2011 Ramez Elmasri and Shamkant Navathe 5.1 Covert Channels (2)

Covert channels can be classified into two broad categories: Storage channels do not require any temporal synchronization, in that information is conveyed by accessing system information or what is otherwise inaccessible to the user. Timing channel allow the information to be conveyed by the timing of events or processes. Some security experts believe that one way to avoid covert channels is for programmers to not actually gain

access to sensitive data that a program is supposed to process after the program has been put into operation. Copyright 2011 Ramez Elmasri and Shamkant Navathe 6 Encryption and Public Key Infrastructures Encryption is a means of maintaining secure data in an insecure environment. Encryption consists of applying an encryption algorithm to data using some prespecified encryption key. The resulting data has to be decrypted using a decryption key to recover the original data.

Copyright 2011 Ramez Elmasri and Shamkant Navathe 6.1 The Data and Advanced Encryption Standards The Data Encryption Standard (DES) is a system developed by the U.S. government for use by the general public. It has been widely accepted as a cryptographic standard both in the United States and abroad. DES can provide end-to-end encryption on the channel between the sender A and receiver B.

Copyright 2011 Ramez Elmasri and Shamkant Navathe 6.1 The Data and Advanced Encryption Standards (2) DES algorithm is a careful and complex combination of two of the fundamental building blocks of encryption: substitution and permutation (transposition). The DES algorithm derives its strength from repeated application of these two techniques for a total of 16 cycles.

Plaintext (the original form of the message) is encrypted as blocks of 64 bits. Copyright 2011 Ramez Elmasri and Shamkant Navathe 6.1 The Data and Advanced Encryption Standards(3) After questioning the adequacy of DES, the National Institute of Standards (NIST) introduced the Advanced Encryption Standards (AES). This algorithm has a block size of 128 bits and thus takes longer time to crack.

Copyright 2011 Ramez Elmasri and Shamkant Navathe 6.2 Public Key Encryption In 1976 Diffie and Hellman proposed a new kind of cryptosystem, which they called public key encryption. Public key algorithms are based on mathematical functions rather than operations on bit patterns. They also involve the use of two separate keys in contrast to conventional encryption, which uses only one

key. The use of two keys can have profound consequences in the areas of confidentiality, key distribution, and authentication. Copyright 2011 Ramez Elmasri and Shamkant Navathe 6.2 Public Key Encryption (2) The two keys used for public key encryption are referred to as the public key and the private key. the private key is kept secret, but it is referred to as private key rather than a secret key (the word used in conventional encryption to avoid confusion

with conventional encryption). Copyright 2011 Ramez Elmasri and Shamkant Navathe 6.2 Public Key Encryption (3) A public key encryption scheme, or infrastructure, has six ingredients: Plaintext: This is the data or readable message that is fed into the algorithm as input. Encryption algorithm: The encryption algorithm performs various transformations on the plaintext.

Public and private keys: These are pair of keys that have been selected so that if one is used for encryption, the other is used for decryption. The exec transformations performed by the encryption algorithm depend on the public or private key that is provided as input. Copyright 2011 Ramez Elmasri and Shamkant Navathe 6.2 Public Key Encryption (4) A public key encryption scheme, or infrastructure, has six ingredients (contd.): Ciphertext:

This is the scrambled message produced as output. It depends on the plaintext and the key. For a given message, two different keys will produce two different ciphertexts. Decryption algorithm: This algorithm accepts the ciphertext and the matching key and produces the original plaintext. Copyright 2011 Ramez Elmasri and Shamkant Navathe

6.2 Public Key Encryption (5) Public key is made for public and private key is known only by owner. A general-purpose public key cryptographic algorithm relies on one key for encryption and a different but related key for decryption. Copyright 2011 Ramez Elmasri and Shamkant Navathe 6.2 Public Key Encryption (6)

The essential steps are as follows: Each user generates a pair of keys to be used for the encryption and decryption of messages. Each user places one of the two keys in a public register or other accessible file. This is the public key. The companion key is kept private (private key). If a sender wishes to send a private message to a receiver, the sender encrypts the message using the receivers public key. When the receiver receives the message, he or she

decrypts it using the receivers private key. No other recipient can decrypt the message because only the receiver knows his or her private key. Copyright 2011 Ramez Elmasri and Shamkant Navathe 6.2 Public Key Encryption (7) The RSA Public Key Encryption algorithm, one of the first public key schemes was introduced in 1978 by Ron Rivest (R), Adi Shamir (S), and Len Adleman (A) at MIT and is named after them.

The RSA encryption algorithm incorporates results from number theory, such as the difficulty of determining the large prime factors of a large number. The RSA algorithm also operates with modular arithmetic mod n, where n is the product of two large prime numbers. Copyright 2011 Ramez Elmasri and Shamkant Navathe 6.2 Public Key Encryption (8) Two keys, d and e, are used for decryption and encryption. An important property is that d and e can be interchanged. n is chosen as a large integer that is a product of two large distinct prime numbers, a and b. The encryption key e is a randomly chosen number between 1 and n that is relatively prime to (a-1) x (b-1).

The plaintext block P is encrypted as Pe mod n. Because the exponentiation is performed mod n, factoring Pe to uncover the encrypted plaintext is difficult. However, the decryption key d is carefully chosen so that (Pe)d mod n = P. The decryption key d can be computed from the condition that d x e= 1 mod ((a-1)x(b-1)). Thus, the legitimate receiver who knows d simply computes (Pe)d mod n = P and recovers P without having to factor Pe . Copyright 2011 Ramez Elmasri and Shamkant Navathe 6.3 Digital Signatures

A digital signature is an example of using encryption techniques to provide authentication services in e-commerce applications. A digital signature is a means of associating a mark unique to an individual with a body of text. The mark should be unforgettable, meaning that others should be able to check that the signature does come from the originator. A digital signature consists of a string of symbols. Signature must be different for each use. This can be achieved by making each digital signature a function of the message that it is signing, together with a time stamp. Public key techniques are the means creating digital signatures.

Copyright 2011 Ramez Elmasri and Shamkant Navathe Summary 1 Database Security and Authorization 2 Discretionary Access Control 3 Mandatory Access Control and Role-Based Access Control for Multilevel Security 4 Statistical Database Security 5 Flow Control 6 Encryption and Public Key Infrastructures

Copyright 2011 Ramez Elmasri and Shamkant Navathe Chapter 22 Concurrency Control Techniques Copyright 2011 Pearson Education, Inc. Publishing as Pearson Addison-Wesley Database Concurrency Control 1 Purpose of Concurrency Control

To enforce Isolation (through mutual exclusion) among conflicting transactions. To preserve database consistency through consistency preserving execution of transactions. To resolve read-write and write-write conflicts. Example: In concurrent execution environment if T1 conflicts with T2 over a data item A, then the existing concurrency control decides if T1 or T2 should get the A and if the other transaction is rolled-back or waits. Copyright 2011 Ramez Elmasri and Shamkant Navathe

Database Concurrency Control Two-Phase Locking Techniques Locking is an operation which secures Example: Lock (X). Data item X is locked in behalf of the requesting transaction.

Unlocking is an operation which removes these permissions from the data item. Example: (a) permission to Read (b) permission to Write a data item for a transaction. Unlock (X): Data item X is made available to all other transactions. Lock and Unlock are Atomic operations. Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control

Two-Phase Locking Techniques: Essential components Two locks modes: More than one transaction can apply share lock on X for reading its value but no write lock can be applied on X by any other transaction. Exclusive mode: Write lock (X) (b) exclusive (write).

Shared mode: shared lock (X) (a) shared (read) Only one write lock on X can exist at any time and no shared lock can be applied by any other transaction on X. Read Write Read Y N

Write Conflict matrix N N Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Two-Phase Locking Techniques: Essential components Lock Manager:

Managing locks on data items. Lock table: Lock manager uses it to store the identify of transaction locking a data item, the data item, lock mode and pointer to the next data item locked. One simple way to implement a lock table is through linked list. Transaction ID Data item id lock mode Ptr to next data item T1 X1 Read Next Copyright 2011 Ramez Elmasri and Shamkant Navathe

Database Concurrency Control Two-Phase Locking Techniques: Essential components Database requires that all transactions should be well-formed. A transaction is well-formed if: It must lock the data item before it reads or writes to it. It must not lock an already locked data items and it must not try to unlock a free data item. Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control

Two-Phase Locking Techniques: Essential components The following code performs the lock operation: B:if LOCK (X) = 0 (*item is unlocked*) then LOCK (X) 1 (*lock the item*) else begin wait (until lock (X) = 0) and the lock manager wakes up the transaction); goto B end; Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Two-Phase Locking Techniques: Essential components

The following code performs the unlock operation: LOCK (X) 0 (*unlock the item*) if any transactions are waiting then wake up one of the waiting the transactions; Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Two-Phase Locking Techniques: Essential components The following code performs the read operation: B: if LOCK (X) = unlocked then begin LOCK (X) read-locked; no_of_reads (X) 1; end

else if LOCK (X) read-locked then no_of_reads (X) no_of_reads (X) +1 else begin wait (until LOCK (X) = unlocked and the lock manager wakes up the transaction); go to B end; Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Two-Phase Locking Techniques: Essential components The following code performs the write lock operation: B: if LOCK (X) = unlocked then begin LOCK (X) read-locked; no_of_reads (X) 1;

end else if LOCK (X) read-locked then no_of_reads (X) no_of_reads (X) +1 else begin wait (until LOCK (X) = unlocked and the lock manager wakes up the transaction); go to B end; Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Two-Phase Locking Techniques: Essential components The following code performs the unlock operation: if LOCK (X) = write-locked then begin LOCK (X) unlocked;

wakes up one of the transactions, if any end else if LOCK (X) read-locked then begin no_of_reads (X) no_of_reads (X) -1 if no_of_reads (X) = 0 then begin LOCK (X) = unlocked; wake up one of the transactions, if any end end; Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Two-Phase Locking Techniques: Essential components Lock conversion

Lock upgrade: existing read lock to write lock if Ti has a read-lock (X) and Tj has no read-lock (X) (i j) then convert read-lock (X) to write-lock (X) else force Ti to wait until Tj unlocks X Lock downgrade: existing write lock to read lock Ti has a write-lock (X) (*no transaction can have any lock on X*) convert write-lock (X) to read-lock (X) Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Two-Phase Locking Techniques: The algorithm Two Phases: (a) Locking (Growing) (b) Unlocking (Shrinking).

Locking (Growing) Phase: A transaction applies locks (read or write) on desired data items one at a time. Unlocking (Shrinking) Phase: A transaction unlocks its locked data items one at a time. Requirement: For a transaction these two phases must be mutually exclusively, that is, during locking phase unlocking phase must not start and during unlocking phase locking phase must not begin. Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Two-Phase Locking Techniques: The algorithm T1 T2 Result

read_lock (Y); read_lock (X); Initial values: X=20; Y=30 read_item (Y); read_item (X); Result of serial execution unlock (Y); unlock (X); T1 followed by T2 write_lock (X); Write_lock (Y); X=50, Y=80. read_item (X); read_item (Y); Result of serial execution X:=X+Y; Y:=X+Y; T2 followed by T1

write_item (X); write_item (Y); X=70, Y=50 unlock (X); unlock (Y); Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Two-Phase Locking Techniques: The algorithm T1 T2 read_lock (Y); read_item (Y); unlock (Y); read_lock (X); read_item (X); unlock (X); Time

write_lock (Y); read_item (Y); Y:=X+Y; write_item (Y); unlock (Y); write_lock (X); read_item (X); X:=X+Y; write_item (X); unlock (X); Result X=50; Y=50 Nonserializable because it. violated two-phase policy. Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control

Two-Phase Locking Techniques: The algorithm T1 T2 read_lock (Y); read_lock (X); T1 and T2 follow two-phase read_item (Y); read_item (X); policy but they are subject to write_lock (X); Write_lock (Y); deadlock, which must be unlock (Y); unlock (X); dealt with. read_item (X); read_item (Y); X:=X+Y; Y:=X+Y;

write_item (X); write_item (Y); unlock (X); unlock (Y); Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Two-Phase Locking Techniques: The algorithm Two-phase policy generates two locking algorithms (a) Basic (b) Conservative Conservative: Prevents deadlock by locking all desired data items before transaction begins execution. Basic: Transaction locks data items incrementally. This may cause deadlock which is dealt with.

Strict: A more stricter version of Basic algorithm where unlocking is performed after a transaction terminates (commits or aborts and rolled-back). This is the most commonly used two-phase locking algorithm. Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Dealing with Deadlock and Starvation T1 Deadlock T2 read_lock (Y); T1 and T2 did follow two-phase

read_item (Y); policy but they are deadlock read_lock (X); read_item (Y); write_lock (X); (waits for X) write_lock (Y); (waits for Y) Deadlock (T1 and T2) Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Dealing with Deadlock and Starvation Deadlock prevention

A transaction locks all data items it refers to before it begins execution. This way of locking prevents deadlock since a transaction never waits for a data item. The conservative two-phase locking uses this approach. Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Dealing with Deadlock and Starvation Deadlock detection and resolution

In this approach, deadlocks are allowed to happen. The scheduler maintains a wait-for-graph for detecting cycle. If a cycle exists, then one transaction involved in the cycle is selected (victim) and rolled-back. A wait-for-graph is created using the lock table. As soon as a transaction is blocked, it is added to the graph. When a chain like: Ti waits for Tj waits for Tk waits for Ti or Tj occurs, then this creates a cycle. One of the transaction o Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Dealing with Deadlock and Starvation Deadlock avoidance

There are many variations of two-phase locking algorithm. Some avoid deadlock by not letting the cycle to complete. That is as soon as the algorithm discovers that blocking a transaction is likely to create a cycle, it rolls back the transaction. Wound-Wait and Wait-Die algorithms use timestamps to avoid deadlocks by rolling-back victim. Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Dealing with Deadlock and Starvation Starvation

Starvation occurs when a particular transaction consistently waits or restarted and never gets a chance to proceed further. In a deadlock resolution it is possible that the same transaction may consistently be selected as victim and rolled-back. This limitation is inherent in all priority based scheduling mechanisms. In Wound-Wait scheme a younger transaction may always be wounded (aborted) by a long running older transaction which may create starvation. Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control

Timestamp based concurrency control algorithm Timestamp A monotonically increasing variable (integer) indicating the age of an operation or a transaction. A larger timestamp value indicates a more recent event or operation. Timestamp based algorithm uses timestamp to serialize the execution of concurrent transactions. Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Timestamp based concurrency control algorithm Basic Timestamp Ordering

1. Transaction T issues a write_item(X) operation: If read_TS(X) > TS(T) or if write_TS(X) > TS(T), then an younger transaction has already read the data item so abort and roll-back T and reject the operation. If the condition in part (a) does not exist, then execute write_item(X) of T and set write_TS(X) to TS(T). 2. Transaction T issues a read_item(X) operation:

If write_TS(X) > TS(T), then an younger transaction has already written to the data item so abort and roll-back T and reject the operation. If write_TS(X) TS(T), then execute read_item(X) of T and set read_TS(X) to the larger of TS(T) and the current read_TS(X). Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Timestamp based concurrency control algorithm Strict Timestamp Ordering 1. Transaction T issues a write_item(X) operation:

If TS(T) > read_TS(X), then delay T until the transaction T that wrote or read X has terminated (committed or aborted). 2. Transaction T issues a read_item(X) operation: If TS(T) > write_TS(X), then delay T until the transaction T that wrote or read X has terminated (committed or aborted). Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Timestamp based concurrency control algorithm Thomass Write Rule

If read_TS(X) > TS(T) then abort and roll-back T and reject the operation. If write_TS(X) > TS(T), then just ignore the write operation and continue execution. This is because the most recent writes counts in case of two consecutive writes. If the conditions given in 1 and 2 above do not occur, then execute write_item(X) of T and set write_TS(X) to TS(T). Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Multiversion concurrency control techniques

This approach maintains a number of versions of a data item and allocates the right version to a read operation of a transaction. Thus unlike other mechanisms a read operation in this mechanism is never rejected. Side effect: Significantly more storage (RAM and disk) is required to maintain multiple versions. To check unlimited growth of versions, a garbage collection is run when some criteria is satisfied. Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Multiversion technique based on timestamp

ordering This approach maintains a number of versions of a data item and allocates the right version to a read operation of a transaction. Thus unlike other mechanisms a read operation in this mechanism is never rejected. Side effects: Significantly more storage (RAM and disk) is required to maintain multiple versions. To check unlimited growth of versions, a garbage collection is run when some criteria is satisfied. Copyright 2011 Ramez Elmasri and Shamkant Navathe

Database Concurrency Control Multiversion technique based on timestamp ordering Assume X1, X2, , Xn are the version of a data item X created by a write operation of transactions. With each Xi a read_TS (read timestamp) and a write_TS (write timestamp) are associated. read_TS(Xi): The read timestamp of Xi is the largest of all the timestamps of transactions that have successfully read version Xi. write_TS(Xi): The write timestamp of Xi that wrote the

value of version Xi. A new version of Xi is created only by a write operation. Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Multiversion technique based on timestamp ordering To ensure serializability, the following two rules are used. If transaction T issues write_item (X) and version i of X has the highest write_TS(Xi) of all versions of X that is also less than or equal to TS(T), and read _TS(Xi) > TS(T), then abort and roll-back T; otherwise create a new version Xi and read_TS(X) = write_TS(Xj) = TS(T). If transaction T issues read_item (X), find the version i of X

that has the highest write_TS(Xi) of all versions of X that is also less than or equal to TS(T), then return the value of Xi to T, and set the value of read _TS(Xi) to the largest of TS(T) and the current read_TS(Xi). Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Multiversion technique based on timestamp ordering To ensure serializability, the following two rules are used. If transaction T issues write_item (X) and version i of X has the

highest write_TS(Xi) of all versions of X that is also less than or equal to TS(T), and read _TS(Xi) > TS(T), then abort and roll-back T; otherwise create a new version Xi and read_TS(X) = write_TS(Xj) = TS(T). If transaction T issues read_item (X), find the version i of X that has the highest write_TS(Xi) of all versions of X that is also less than or equal to TS(T), then return the value of Xi to T, and set the value of read _TS(Xi) to the largest of TS(T) and the current read_TS(Xi). Rule 2 guarantees that a read will never be rejected. Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Multiversion Two-Phase Locking Using Certify Locks Concept

Allow a transaction T to read a data item X while it is write locked by a conflicting transaction T. This is accomplished by maintaining two versions of each data item X where one version must always have been written by some committed transaction. This means a write operation always creates a new version of X. Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Multiversion Two-Phase Locking Using Certify Locks Steps 1. X is the committed version of a data item. 2. T creates a second version X after obtaining a write lock on X.

3. Other transactions continue to read X. 4. T is ready to commit so it obtains a certify lock on X. 5. The committed version X becomes X. 6. T releases its certify lock on X, which is X now. Compatibility tables for Read Write Certify no no Read yes no no Write no no no Certify no Read Write Read yes

no Write no no read/write locking scheme read/write/certify locking scheme Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Multiversion Two-Phase Locking Using Certify Locks Note: In multiversion 2PL read and write operations from conflicting transactions can be processed

concurrently. This improves concurrency but it may delay transaction commit because of obtaining certify locks on all its writes. It avoids cascading abort but like strict two phase locking scheme conflicting transactions may get deadlocked. Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Validation (Optimistic) Concurrency Control Schemes In this technique only at the time of commit serializability is checked and transactions are aborted in case of nonserializable schedules. Three phases: 1. Read phase 2. Validation phase 3. Write phase

1. Read phase: A transaction can read values of committed data items. However, updates are applied only to local copies (versions) of the data items (in database cache). Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Validation (Optimistic) Concurrency Control Schemes 2. Validation phase: Serializability is checked before transactions write their updates to the database. This phase for Ti checks that, for each transaction Tj that is either committed or is in its validation phase, one of the following conditions holds:

Tj completes its write phase before Ti starts its read phase. Ti starts its write phase after Tj completes its write phase, and the read_set of Ti has no items in common with the write_set of Tj Both the read_set and write_set of Ti have no items in common with the write_set of Tj, and Tj completes its read phase. When validating Ti, the first condition is checked first for each transaction Tj, since (1) is the simplest condition to check. If (1) is false then (2) is checked and if (2) is false then (3 ) is checked. If none of these conditions holds, the validation fails and Ti is aborted. Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Validation (Optimistic) Concurrency Control

Schemes 3. Write phase: On a successful validation transactions updates are applied to the database; otherwise, transactions are restarted. Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Granularity of data items and Multiple Granularity Locking A lockable unit of data defines its granularity. Granularity can be coarse (entire database) or it can be fine (a tuple or an attribute of a relation). Data item granularity significantly affects concurrency control performance. Thus, the degree of concurrency is low for coarse granularity and high for fine granularity. Example of data item granularity:

1. 2. 3. 4. 5. A field of a database record (an attribute of a tuple) A database record (a tuple or a relation) A disk block An entire file The entire database Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Granularity of data items and Multiple Granularity Locking The following diagram illustrates a hierarchy of granularity from coarse (database) to fine

(record). DB f1 p11 p12 r111 ... r11j r111 ... r11j f2 ... p1n p11 p12

... r111 ... r11j r111 ... r11j r111 ... r11j Copyright 2011 Ramez Elmasri and Shamkant Navathe p1n r111 ... r11j Database Concurrency Control Granularity of data items and Multiple Granularity Locking To manage such hierarchy, in addition to read and write, three additional locking modes, called intention lock modes are defined:

Intention-shared (IS): indicates that a shared lock(s) will be requested on some descendent nodes(s). Intention-exclusive (IX): indicates that an exclusive lock(s) will be requested on some descendent node(s). Shared-intention-exclusive (SIX): indicates that the current node is locked in shared mode but an exclusive lock(s) will be requested on some descendent nodes(s). Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Granularity of data items and Multiple Granularity Locking These locks are applied using the following Intention-shared (IS compatibility matrix: IS IS yes

IX yes yes S SIX yes X no IX yes yes no no no S SIX yes yes no no yes no no no

no no Copyright 2011 Ramez Elmasri and Shamkant Navathe X no no no no no Intention-exclusive (IX) Shared-intention-exclusive (SIX) Database Concurrency Control Granularity of data items and Multiple Granularity Locking The set of rules which must be followed for producing serializable

schedule are 1. The lock compatibility must adhered to. 2. The root of the tree must be locked first, in any mode.. 3. A node N can be locked by a transaction T in S or IX mode only if the parent node is already locked by T in either IS or IX mode. 4. A node N can be locked by T in X, IX, or SIX mode only if the parent of N is already locked by T in either IX or SIX mode. 5. T can lock a node only if it has not unlocked any node (to enforce 2PL policy). 6. T can unlock a node, N, only if none of the children of N are currently locked by T. Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Granularity of data items and Multiple Granularity Locking: An example of a serializable execution: T1 IX(db)

IX(f1) T2 T3 IX(db) IS(db) IS(f1) IS(p11) IX(p11) X(r111) IX(f1) X(p12) S(r11j) IX(f2) IX(p21) IX(r211) Unlock (r211)

Unlock (p21) Unlock (f2) S(f2) Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Granularity of data items and Multiple Granularity Locking: An example of a serializable execution (continued): T1 T2 T3 unlock(p12) unlock(f1) unlock(db) unlock(r111) unlock(p11)

unlock(f1) unlock(db) unlock (r111j) unlock (p11) unlock (f1) unlock(f2) unlock(db) Copyright 2011 Ramez Elmasri and Shamkant Navathe Summary Databases Concurrency Control 1. 2. 3. 4. 5. 6.

Purpose of Concurrency Control Two-Phase locking Limitations of CCMs Index Locking Lock Compatibility Matrix Lock Granularity Copyright 2011 Ramez Elmasri and Shamkant Navathe Chapter 23 Database Recovery Techniques Copyright 2011 Pearson Education, Inc. Publishing as Pearson Addison-Wesley Database Recovery

1 Purpose of Database Recovery To bring the database into the last consistent state, which existed prior to the failure. To preserve transaction properties (Atomicity, Consistency, Isolation and Durability). Example: If the system crashes before a fund transfer transaction completes its execution, then either one or both accounts may have incorrect value. Thus, the database must be restored to the state before the transaction modified any of the accounts. Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Recovery 2 Types of Failure The database may become unavailable for use

due to Transaction failure: Transactions may fail because of incorrect input, deadlock, incorrect synchronization. System failure: System may fail because of addressing error, application error, operating system fault, RAM failure, etc. Media failure: Disk head crash, power disruption, etc. Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Recovery

3 Transaction Log For recovery from any type of failure data values prior to modification (BFIM - BeFore Image) and the new value after modification (AFIM AFter Image) are required. These values and other information is stored in a sequential file called Transaction log. A sample log is given below. Back P and Next P point to the previous and next log records of the same transaction. T ID Back P Next P Operation Data item Begin T1 0 1 T1 1

4 Write X Begin T2 0 8 T1 2 5 W Y T1 4 7 R M T3 0

9 R N T1 5 nil End Copyright 2011 Ramez Elmasri and Shamkant Navathe BFIM AFIM X = 100 X = 200 Y = 50 Y = 100

M = 200 M = 200 N = 400 N = 400 Database Recovery 4 Data Update Immediate Update: As soon as a data item is modified in cache, the disk copy is updated. Deferred Update: All modified data items in the cache is written either after a transaction ends its execution or after a fixed number of transactions have completed their execution.

Shadow update: The modified version of a data item does not overwrite its disk copy but is written at a separate disk location. In-place update: The disk version of the data item is overwritten by the cache version. Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Recovery 5 Data Caching Data items to be modified are first stored into database cache by the Cache Manager (CM) and after modification they are flushed (written) to the disk. The flushing is controlled by Modified and PinUnpin bits.

Pin-Unpin: Instructs the operating system not to flush the data item. Modified: Indicates the AFIM of the data item. Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Recovery 6 Transaction Roll-back (Undo) and RollForward (Redo) To maintain atomicity, a transactions operations are redone or undone.

Undo: Restore all BFIMs on to disk (Remove all AFIMs). Redo: Restore all AFIMs on to disk. Database recovery is achieved either by performing only Undos or only Redos or by a combination of the two. These operations are recorded in the log as they happen. Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Recovery Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Recovery

Roll-back: One execution of T1, T2 and T3 as recorded in the log. Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Recovery Write-Ahead Logging When in-place update (immediate or deferred) is used then log is necessary for recovery and it must be available to recovery manager. This is achieved by Write-Ahead Logging (WAL) protocol. WAL states that For Undo: Before a data items AFIM is flushed to the database disk (overwriting the BFIM) its BFIM must be written to the log and the log must be saved on a stable store (log disk).

For Redo: Before a transaction executes its commit operation, all its AFIMs must be written to the log and the log must be saved on a stable store. Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Recovery 7 Checkpointing Time to time (randomly or under some criteria) the database flushes its buffer to database disk to minimize the task of recovery. The following steps defines a checkpoint operation: 1. 2. 3. 4.

Suspend execution of transactions temporarily. Force write modified buffer data to disk. Write a [checkpoint] record to the log, save the log to disk. Resume normal transaction execution. During recovery redo or undo is required to transactions appearing after [checkpoint] record. Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Recovery Steal/No-Steal and Force/No-Force Possible ways for flushing database cache to database disk: 1. Steal: Cache can be flushed before transaction commits.

2. No-Steal: Cache cannot be flushed before transaction commit. 3. Force: Cache is immediately flushed (forced) to disk. 4. No-Force: Cache is deferred until transaction commits These give rise to four different ways for handling recovery: Steal/No-Force (Undo/Redo) Steal/Force (Undo/No-redo) No-Steal/No-Force (Redo/No-undo) No-Steal/Force (No-undo/No-redo)

Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Recovery 8 Recovery Scheme Deferred Update (No Undo/Redo) The data update goes as follows: A set of transactions records their updates in the log. At commit point under WAL scheme these updates are saved on database disk. After reboot from a failure the log is used to redo all the transactions affected by this failure. No

undo is required because no AFIM is flushed to the disk before a transaction commits. Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Recovery Deferred Update in a single-user system There is no concurrent data sharing in a single user system. The data update goes as follows: A set of transactions records their updates in the log. At commit point under WAL scheme these updates are saved on database disk.

After reboot from a failure the log is used to redo all the transactions affected by this failure. No undo is required because no AFIM is flushed to the disk before a transaction commits. Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Recovery Deferred Update with concurrent users This environment requires some concurrency control mechanism to guarantee isolation property of transactions. In a system recovery transactions which were recorded in the log after the last checkpoint were redone. The recovery manager may scan some of the transactions recorded before the checkpoint to get the AFIMs. Copyright 2011 Ramez Elmasri and Shamkant Navathe

Database Recovery Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Recovery Deferred Update with concurrent users Two tables are required for implementing this protocol: Active table: All active transactions are entered in this table. Commit table: Transactions to be committed are entered in this table. During recovery, all transactions of the commit table are

redone and all transactions of active tables are ignored since none of their AFIMs reached the database. It is possible that a commit table transaction may be redone twice but this does not create any inconsistency because of a redone is idempotent, that is, one redone for an AFIM is equivalent to multiple redone for the same AFIM. Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Recovery Recovery Techniques Based on Immediate Update Undo/No-redo Algorithm In this algorithm AFIMs of a transaction are flushed

to the database disk under WAL before it commits. For this reason the recovery manager undoes all transactions during recovery. No transaction is redone. It is possible that a transaction might have completed execution and ready to commit but this transaction is also undone. Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Recovery Recovery Techniques Based on Immediate Update Undo/Redo Algorithm (Single-user environment)

Recovery schemes of this category apply undo and also redo for recovery. In a single-user environment no concurrency control is required but a log is maintained under WAL. Note that at any time there will be one transaction in the system and it will be either in the commit table or in the active table. The recovery manager performs: Undo of a transaction if it is in the active table. Redo of a transaction if it is in the commit table. Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Recovery

Recovery Techniques Based on Immediate Update Undo/Redo Algorithm (Concurrent execution) Recovery schemes of this category applies undo and also redo to recover the database from failure. In concurrent execution environment a concurrency control is required and log is maintained under WAL. Commit table records transactions to be committed and active table records active transactions. To minimize the work of the recovery manager checkpointing is used. The recovery performs: Undo of a transaction if it is in the active table. Redo of a transaction if it is in the commit table. Copyright 2011 Ramez Elmasri and Shamkant Navathe

Database Recovery Shadow Paging The AFIM does not overwrite its BFIM but recorded at another place on the disk. Thus, at any time a data item has AFIM and BFIM (Shadow copy of the data item) at two different places on the disk. X Y X' Y' Database X and Y: Shadow copies of data items X' and Y': Current copies of data items Copyright 2011 Ramez Elmasri and Shamkant Navathe

Database Recovery Shadow Paging To manage access of data items by concurrent transactions two directories (current and shadow) are used. The directory arrangement is illustrated below. Here a page is a data item. Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Recovery The ARIES Recovery Algorithm The ARIES Recovery Algorithm is based on: WAL (Write Ahead Logging)

Repeating history during redo: ARIES will retrace all actions of the database system prior to the crash to reconstruct the database state when the crash occurred. Logging changes during undo: It will prevent ARIES from repeating the completed undo operations if a failure occurs during recovery, which causes a restart of the recovery process. Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Recovery

The ARIES Recovery Algorithm (cont.) The ARIES recovery algorithm consists of three steps: 1. Analysis: step identifies the dirty (updated) pages in the buffer and the set of transactions active at the time of crash. The appropriate point in the log where redo is to start is also determined. 2. Redo: necessary redo operations are applied. 3. Undo: log is scanned backwards and the operations of transactions active at the time of crash are undone in reverse order. Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Recovery The ARIES Recovery Algorithm (cont.) The Log and Log Sequence Number (LSN)

A log record is written for: (a) data update (b) transaction commit (c) transaction abort (d) undo (e) transaction end In the case of undo a compensating log record is written. Copyright 2011 Ramez Elmasri and Shamkant Navathe

Database Recovery The ARIES Recovery Algorithm (cont.) The Log and Log Sequence Number (LSN) (cont.) A unique LSN is associated with every log record. LSN increases monotonically and indicates the disk address of the log record it is associated with. In addition, each data page stores the LSN of the latest log record corresponding to a change for that page. A log record stores

(a) the previous LSN of that transaction (b) the transaction ID (c) the type of log record. Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Recovery The ARIES Recovery Algorithm (cont.) The Log and Log Sequence Number (LSN) (cont.) A log record stores: 1. Previous LSN of that transaction: It links the log record of each transaction. It is like a back pointer points to the previous record of the same transaction

2. Transaction ID 3. Type of log record For a write operation the following additional information is logged: 1. Page ID for the page that includes the item 2. Length of the updated item 3. Its offset from the beginning of the page 4. BFIM of the item 5. AFIM of the item Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Recovery The ARIES Recovery Algorithm (cont.) The Transaction table and the Dirty Page table For efficient recovery following tables are also stored in the log during checkpointing:

Transaction table: Contains an entry for each active transaction, with information such as transaction ID, transaction status and the LSN of the most recent log record for the transaction. Dirty Page table: Contains an entry for each dirty page in the buffer, which includes the page ID and the LSN corresponding to the earliest update to that page. Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Recovery The ARIES Recovery Algorithm (cont.) Checkpointing

A checkpointing does the following: Writes a begin_checkpoint record in the log Writes an end_checkpoint record in the log. With this record the contents of transaction table and dirty page table are appended to the end of the log. Writes the LSN of the begin_checkpoint record to a special file. This special file is accessed during recovery to locate the last checkpoint information. To reduce the cost of checkpointing and allow the system to continue to execute transactions, ARIES uses fuzzy

checkpointing. Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Recovery The ARIES Recovery Algorithm (cont.) The following steps are performed for recovery Analysis phase: Start at the begin_checkpoint record and proceed to the end_checkpoint record. Access transaction table and dirty page table are appended to the end of the log. Note that during this phase some other log records may be written to the log and transaction table may be modified. The analysis phase compiles the set of redo and undo to be performed and ends. Redo phase: Starts from the point in the log up to where all dirty pages have been flushed, and move forward to the end of the log. Any change that appears in the dirty page table is redone. Undo phase: Starts from the end of the log and proceeds backward while performing appropriate undo. For each undo it writes a compensating record in the log.

The recovery completes at the end of undo phase. Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Recovery Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Recovery 10 Recovery in multidatabase system A multidatabase system is a special distributed database system where one node may be running relational database system under UNIX, another may be running object-oriented system under Windows and so on. A transaction may run in a distributed fashion at multiple nodes. In this execution scenario the transaction commits only when all these multiple nodes agree to commit individually the part of the transaction they were executing.

This commit scheme is referred to as two-phase commit (2PC). If any one of these nodes fails or cannot commit the part of the transaction, then the transaction is aborted. Each node recovers the transaction under its own recovery protocol. Copyright 2011 Ramez Elmasri and Shamkant Navathe Summary Databases Recovery

Types of Failure Transaction Log Data Updates Data Caching Transaction Roll-back (Undo) and Roll-Forward Checkpointing Recovery schemes ARIES Recovery Scheme Recovery in Multidatabase System Copyright 2011 Ramez Elmasri and Shamkant Navathe References Ramez Elmasri, Shamkant Navathe; Fundamentals of Database Systems, 6th Ed., Pearson, 2014

Mark L. Gillenson; Fundamentals of Database Management Systems, 2nd Ed., John Wiley, 2012 Universitt Hamburg, Fachbereich Informatik, Einfhrung in Datenbanksysteme, Lecture Notes, 1999 280

Recently Viewed Presentations

  • Présentation PowerPoint

    Présentation PowerPoint

    With Interpoles specificitieseg fragments. Only data sets and collections. At Data center level. Assigning several DOI (with different prefixes) for the same data sets is forbidden. ENVRI FAIR ? GO FAIR ? DIrection du Numérique, de l'exploitation et des Opérations.
  • Petition: Exercise of the Police Power of the State of Maryland?

    Petition: Exercise of the Police Power of the State of Maryland?

    Trial judges throughout Maryland recount a pattern of endorsing emergency evaluation orders repeatedly for seriously ill individuals only to see the same individuals on criminal dockets. The downsizing of state mental hospitals has resulted in the remaining state beds serving...
  • Automatic signature Generation of Vulnerability-Based Signature

    Automatic signature Generation of Vulnerability-Based Signature

    At a high level, our main contribution is a new class of signature, that is not specific to details such as whether an exploit successfully hijacks control of the program, but instead whether executing an input will (potentially) result in...
  • TRAJNIM: Si nxn adoleshentet? Mirazhe 1 OBJEKTIVA  T

    TRAJNIM: Si nxn adoleshentet? Mirazhe 1 OBJEKTIVA T

    robert mager: cili eshte destinacioni i nderhyrjes? specifiko repertorin e sjelljes se deshiruar! (objektiv i arritjes) specifiko masen e suksesit! specifiko kohen e kryerjes se sjelljes! * mirazhe si i nderton mesuesi objektivat specifike? norman gronlund: gjej elementet e sjelljes...
  • Apresentação do PowerPoint

    Apresentação do PowerPoint

    Communication and Management - a crucial relationship Communication touches everything that takes place in an organization and is so intermingled with all other functions and processes that separating it from management is difficult.
  • Chapter 9: Alkynes 9.1: Sources of Alkynes (please

    Chapter 9: Alkynes 9.1: Sources of Alkynes (please

    Many of the same rules for alkenes apply to alkynes Number the carbon chain from the end of the carbon nearest the triple bond The alkyne position is indicated by the number of the alkyne carbon in the chain Compounds...
  • So Jesus said to the Jews who had

    So Jesus said to the Jews who had

    The slave does not remain in the house forever; the son remains forever. So if the Son sets you free, you will be free indeed. ... scarcely die for a righteous person—though perhaps for a good person one would dare...
  • The Fur Trade Phase 5 - Weebly

    The Fur Trade Phase 5 - Weebly

    HBC + NWC. Competition between the two companies had turned ugly. Shootings, fighting, hostage taking amongst other things was occurring. Britain ended the conflict in 1821 by merging the company under one name, The Hudson's Bay Company