SQL on integrity, views and confidentiality, each corrected exercise explores one of these concepts.
States
The example used is that of a “library” database managing readers, books identified by a number and belonging to a certain category of works (detective novel, adventure novel, etc.) and loans of books.
BOOK(Ctakes away,Title,Author,Category)
DRIVE(Number,Name,Address,Consumption)
READY(Rating,ReaderNum,LoanDate,ReturnDate,RestartDate)
Exercise 1
Define the following integrity constraints in SQL2:
- The consumption of a drive is High, Medium or Low (domain constraint)
- Any loan must be made to an existing reader in the database, concerning an existing book (referential constraint)
- Each author can only be classified in one category (functional division: author to category).
- ALTER TABLE Reader ADD (CONSTRAINT domain_conso CHECK (Consumption IN ('High', 'Medium', 'Low')));
- ALTER TABLE Loan ADD (CONSTRAINT fk_reader FOREYGN KEY ReaderNumber REFERENCES Reader); ALTER TABLE Loan ADD (CONSTRAINT fk_book FOREYGN KEY Cote REFERENCES Book);
- ALTER TABLE Book ADD (CONSTRAINT author_category CHECK (NOT EXISTS (SELECT Author FROM Book GROUP BY Author HAVING COUNT(Category) > 1)));
Exercise 2
Question 1: Definition of a view
Give the SQL commands to create the following views:
a) detective novels, view defined by the following diagram:
POLICE OFFICER (Rating, Title, Author)
b) readers of detective novels, view defined by the following diagram:
POLICE READER (Number, Name, Address, Rating, Borrowing Date, Return Date)
c) readers not authorized to borrow books in the event that they have forgotten to return some of their previous loans:
READER-PROHIBITED (Number, Name)
d) a STATS-DE-SPRETS relationship describing for each reader the number of borrowings since the date d.
Question 2 Using a view.
A user with the right to query from the previous POLICEMAN and POLICE-READER views asks the following questions:
a) list the names of readers who borrowed detective novels on the date d,
b) give the names of readers who borrowed more than three detective novels by Simenon on the same day.
Express these questions in SQL on the previous views. Also express these questions about the basic relationships READER, BOOK and READY.
Question 3: Processing a question relating to a view
Views define virtual relationships whose content is never actually calculated. When creating a view, only the view definition is stored in a metabase relationship. When a user asks a question about a view, the DBMS transforms it into a question about the corresponding relationships in the database.
This transformation is done either directly on the LMD formulation of the query [Stonebraker75], or by modifying the algebraic syntactic tree of the question [Astrahan76]. In both cases, the transformation consists of doing an AND between the user question and the view definition questions.
Describe the general algorithm for transforming a question asked on views into a question expressed on the basis by modifying the syntax tree of the question. Show how it works on question 2.b.
Question 4: Update through a view.
Updates across views pose different problems depending on the definition of the view: undefined values (e.g. insertion of a new tuple in READER-PROHIBITED), potential inconsistencies (e.g. insertion or deletion of a tuple of READER- DE-POLICIER), non-definition of the update (for example deletion of a tuple in STATS-DES-PRETS of reader no. 1347).
What type of view definition does each of these problems correspond to? Under what condition can an update on a view be passed on to the database without ambiguity?
Question 5: Concrete views or clichés
Some DBMS offer, in addition to the view mechanism, the notion of cliche Where concrete view [Adiba 80] or materialized view. As opposed to a view, the content of a materialized view is calculated at its definition and stored in the database. A materialized view reflects the state of the database at the moment t where it was calculated.
More specifically, we call a snapshot a concrete view which is recalculated periodically by the system. Updates in the database should be reflected in the snapshot when it is refreshed. How can we avoid systematically recalculating the entire snapshot each time it is refreshed?
a) Definition of the POLICE OFFICER view
create view POLICE OFFICER
ace select Rating, Title, Author
from BOOK
where Category = “detective novel”;
This view is an example of an external schema definition where the database subset is defined as an occurrence-level subset.
b) Definition of the POLICE READER view
create view POLICE READER
as select Number, Name, Address, Rating, Borrowing Date, Return Date
from BOOK L, READER E, READY P
where L.Cote = P.Cote and E.Number = P.ReaderNumber and L.Category = “detective novel”;
This view definition is an example of information restructuring. The user only sees one relationship in the view when in reality the base is made up of three relationships. This possibility makes it possible to simplify the work of users by presenting them with information in the format that suits them best, for example by avoiding the formulation of joins when querying the view.
c) Definition of the READER-PROHIBITED view
create view READER-PROHIBITED (Number, Name)
as select Number, Name
from READER E, READY P
where E.Number = P.ReaderNumber
and (LoanDate + 15) < SystemDate
and ReturnDate is NULL;
We assume that the system allows you to obtain today's date using the keyword "system-date". The view definition is dynamic, in the sense that its content varies every day automatically based on the date. This view definition also allows you to change attribute names to adapt to user habits.
d) Definition of the STATS-DES-READS view
create view LOAN-STATS(ReaderNum, LoanNumber, Name)
as select Number, count(*)
from READER E, READY P
where E.Number = P.Numlector
and LoanDate > “d”
group by ReaderNum;
The NumberLoans attribute is inferred information to the extent that it is not stored as such in the database, but calculated from the stored information.
Question 2: Using a view
a) The user question is
select distinct Last name
from POLICE READER
where LoanDate = “d”;
The same question asked about the base relationships would be:
select Last name
from BOOK L, READER E, READY P
where L.Cote = P.Cote
and E.Number=P.Numlector
and L.Category = “detective novel”
and LoanDate = “d”;
This question is much more complex to formulate because it has two joins, while the view question is very simple since it only has one restriction. This is one of the advantages of views: simplifying users' work.
b) The user's question expressed in SQL is:
select distinct Last name
from POLICEMAN READER E, POLICEMAN P
where E.Rating = P.Rating and Author = “SIMENON”
group by ReaderNumber, LoanDate
having count (BookNumber)>3;
The question as it should have been asked on the database is:
select distinct Last name
from READER E, BOOK L, READY P
where P.Cote=L.Cote and Author=”Simenon”
and L.Category=”detective novel”
and P.ReaderNum=E.Number
group by ReaderNumber, LoanDate
having count (BookNumber) > 3;
Question 3: Handling a question about a view
The algorithm for transforming a question asked on one or more views consists of “adding” the user question and the questions defining each of the views. The processing is iterative because a view can be built on other views.
As long as the question involves the use of views
- search the metabase for view definition trees
- construct the syntactic tree of the question asked
- change view attribute names to corresponding attribute names if there is re-naming of attributes in the view
- transform the trees into one by matching the result of a view with the view name in the question
- possibly simplify the tree by eliminating redundant operations
ftq
Passing the transformed question tree to the question optimizer
Application of the algorithm on the example:
1) The question tree is as follows:
2) The trees of the two views are as follows:
3) Adding trees by matching the result of a view and the name of the view:
4) In the definition of views there is no renaming of attributes.
5) Simplification of the tree.
We use the BOOK relation twice for a join on book number. There are also two identical restrictions with the criterion . We only keep each of these operations once.
Question 4: Update through a view
Updating through views is prohibited in the general case because it poses various problems:
(1) Attributes not defined in the view: any insertion of a tuple in the view results in the insertion of a tuple in the base having an undetermined value for attributes not visible in the view. For example, the insertion of a new tuple in the READER-PROHIBITED view implies the insertion of a READER tuple whose address is unknown. Any view that includes a projection in its definition causes this type of problem.
(2) Risks of inconsistency when a view relation is obtained by joining several real relations. For example, does inserting a tuple in POLICE-READER mean adding a loan for an existing reader, or inserting a loan and a new reader, or even the insertion of a loan, a book and a reader?
The ambiguity is the same for tuple deletions. The impact of an update depends on the semantics of the view and the application. It cannot be automatic. The semantics of the update operations should be described for each view.
(3) Loss of significance of the update: the deletion, for example, of the tuple (1347, 45) from the STATS-DES-PRETS view, cannot be passed on to the base relations level. This loss of meaning is characteristic of views constructed using aggregates and/or sum or average calculation functions.
In general, DBMS prohibit updates across views. Some allow them in the case where the semantics of updates can be defined unambiguously. This is the case if the view definition only uses the restriction operator of a relation (neither join, nor projection, nor aggregate, nor calculation function).
In this case a tuple of the view corresponds to a single tuple of the base. We can also authorize the projection operator if the DBMS manages indeterminate values.
Question 5: Concrete views or clichés
The time to calculate and store a snapshot can be significant if the corresponding subset of the database is large. To reduce this execution time, which for a snapshot is repetitive, the system can use a differential update mechanism. Only tuples inserted, deleted or modified in the database since the last calculation are in turn inserted, deleted or modified in the snapshot.
It is necessary for the DBMS to keep the tuples inserted or deleted from the database relations in a special relation. Tuple deletions pose a particular problem in the general case: a snapshot tuple can come from several base tuples and the deletion of only one of these tuples should not result in the deletion of the snapshot tuple.
This problem is studied in [Kerhervé 86]. The idea is to associate with each tuple in the view a counter indicating the number of reasons for its presence. When deleting a tuple from the base, the corresponding counter is decremented. When the counter becomes zero, the snapshot tuple is deleted.
Exercise 3
Question 1: Example of use
Write the command allowing reading and insertion rights on the BOOK relationship to be transmitted to the Dupont user, guaranteeing them the right to transmit their rights.
Question 2: Checking the allocation of rights
Describe the principles of the GRANT algorithm. Information regarding authorization management is stored in a metabase system relationship called RIGHT. Specify the schema of this relationship according to the GRANT algorithm.
Question 3: Verification of the withdrawal of a right
In a decentralized system, the procedure for withdrawing rights is delicate. It is in fact necessary to withdraw the right from the indicated user, but also recursively withdraw it from all the users to whom the latter had transmitted it. On the other hand, a user can receive the same right from several different donors. When one of them takes it away from him, he keeps the one coming from different sources. Specify the principles of the REVOKE algorithm. Indicate any modifications to the diagram of the RIGHT relationship.
Question 4: Verification of access rights during manipulations
Verification that a user has the right to perform a certain operation on a relationship must be carried out quickly. How can the system respond to this constraint?
Question 5: Rights to a view
When a user creates a view, what rights are automatically assigned to them on the virtual relationship?
Question 1: Example of use
grant select insert on BOOK
to dupont
with grant option
Question 2: Verification of the allocation of rights.
A GRANT request has the following parameters:
- the user who issued the GRANT, called the donor;
- the user to whom the rights are granted, called the beneficiary;
- the list of rights granted (a right being granted with or without a right of transmission), each of the two possibilities is identified as a different right;
- the relationship over which rights are granted called the object.
The RIGHT relationship allows you to store this information. Its diagram can be as follows:
RIGHT (object-relation, beneficiary-name, donor-name,
non-transferable-rights, transferable-rights)
This schema is not in first normal form because the attributes-transmissible-rights and non-transmissible-rights attributes contain multiple values, but it allows for more compact storage. Conversely, it requires processing to analyze the rights present.
The GRANT algorithm includes the following steps:
1) check that the donor has the rights he wants to grant with the right of transmission.
To do this, it is necessary to extract from the RIGHT relationship the rights that the author of the GRANT has on the 'object' relationship.
select transferable-rights
from right
where beneficiary-name = “donor”
and object-relation = “object”;
2) if the donor actually has the right to transmit 'list-rights', these must be stored in the RIGHT relationship by an INSERT query, either as transferable rights or as non-transferable rights depending on the presence or absence of the clause with grant option.
The algorithm of grant will generate the following query:
insert into RIGHT
values(“object”, “beneficiary”, “donor”, nil, “list-rights”)
Where
insert into RIGHT
values(“object”, “beneficiary”, “donor”, “list-rights”, nil)
Question 3: Verification of the withdrawal of a right
In a decentralized rights management system where rights are dynamically granted, verified and withdrawn, controlling the withdrawal of rights is not trivial. Verifying the origin of a user's rights in principle requires tracing the graph transmission of authorizations to verify the origin of each right and to ensure that a user has not retransmitted a right to himself through a circuitous route.
A simpler solution than constructing the graph was developed in [Lindsay79]. Each right is associated with a stamp indicating the date on which the right was granted. The stamp makes it possible to recognize the rights which remain to a user t disappears. All rights derived recursively from X and subsequent to t must also disappear. The format of the RIGHT relation becomes the following:
LAW (object-relation,
beneficiary-name,
donor-name,
non-transferable rights,
transferable-rights-stamps)
Each transferable right is no longer represented by a bit but by the time at which it was granted. A right not granted has a stamp of 0. An example of the content of the relationship (considering only transferable rights) is the following:
object relationship | beneficiary name | donor name | select | insert | delete | update |
BOOK | X | TO | 15 | 15 | 0 | 0 |
BOOK | X | B | 20 | 0 | 20 | 0 |
BOOK | Y | X | 25 | 25 | 25 | 0 |
BOOK | X | VS | 30 | 0 | 30 | 0 |
Suppose that at time t = 35, B withdraws all the rights it had granted to X at time t = 20. The tuple (BOOK, X, B, 20, 0, 20, 0) must disappear. The rights remaining at X are then (BOOK, X, (A,C), (15, 30), 15, 30, 0). The rights that X transmitted are (BOOK, Y, X, 25, 25, 25, 0).
The DELETE right given by X at time t = 25 must disappear since we now consider that of rights received by X before time 20. The algorithm is as follows:
proc REVOKE (b: beneficiary-name, da: access-right, r: object-relation, d: donor-name)
/* remove the privilege 'da' granted by 'd' to 'b' on 'r' */
update RIGHT
set da = 0
where beneficiary-name = b
and donor-name = d
and object-relation = r;
/* define the minimum stamp which remains at 'b' for the right 'da' on the relation 'r' */
select MIN(da) into min
from RIGHT
where beneficiary-name = b
and object-relation = r;
/* remove all 'da' rights granted by 'b' on 'r' before 'min' */
select beneficiary-name into withdrawal-list
from RIGHT
where donor-name='b'
and object-relation='r'
and da<'min';
Yes indent-list ¬ empty
so for each element 'l' of withdrawal-list
to do
REVOKE (l, da, r, b)
ffor
fsi
end of procedure
The algorithm is recursive and gradually withdraws the rights of all those to whom they can no longer have been granted.
Example :
If A withdraws his right from X, it must recursively withdraw it from all the others. The algorithm goes like this:
- 1st pass: REVOKE (X, da, r, A)
removes from X the right 'da' which comes to him from A
minimum of stamps remaining at X: 15
==> remove the right to Y given in t = 10 (therefore before 15): REVOKE (Y, da, r, Y)
- 2nd pass: REVOKE (Y, da, r, X)
Y no longer has the right 'da', so this right must be withdrawn from those to whom he transmitted it:
REVOKE (X, da, r, Y)
- 3rd pass: REVOKE (X, da, r, Y)
X no longer has the 'da' right, so it must be withdrawn from those to whom he transmitted it:
REVOKE (Z, da, r, X)
Question 4: Verification of access rights during manipulations
During each request from a user, the system verifies that this user actually has the right to execute this type of request on the relationships cited. This verification could be done by accessing the RIGHT relation, but this access then generates an input-output per request which is cumbersome.
A better solution is to only access the RIGHT relationship once at the start of the session for each user. When a user connects to the DBMS, after authentication (verification that he has the right to use the DBMS), the system reads from central memory the part of the RIGHT relationship that concerns him. This extract of the RIGHT relation for a user 'U' is defined by:
select * into RIGHTS-TM
from RIGHT
where beneficiary-name = 'U';
The RIGHTS-MC relationship must be stored in central memory in a location reserved for the system to which a user can never have access to avoid any fraudulent or accidental modification of this relationship.
Question 5: Access rights on a view
When a user creates a view, he cannot obtain rights on it greater than those he has on the relationships in the database used to construct the view. The rights that are automatically granted to the creator of a view are equal to all the rights that the user has on each of the relationships making up the view.
Rights acquired over sight are only transferable if they were for base relationships. To create the view, the user must have read (select) permission on the relationships used to compose the view. He will therefore have at least reading rights on the created view.
EN 
FR 
ES