{"id":20109,"date":"2024-02-07T09:30:22","date_gmt":"2024-02-07T08:30:22","guid":{"rendered":"https:\/\/complex-systems-ai.com\/?page_id=20109"},"modified":"2024-02-13T07:21:13","modified_gmt":"2024-02-13T06:21:13","slug":"exercices-concurrence","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/software-analysis\/competition-exercises\/","title":{"rendered":"3 Corrected Competition Exercises"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"20109\" class=\"elementor elementor-20109\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-4f33197 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4f33197\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-ca2fe64\" data-id=\"ca2fe64\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-5f10ea1 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"5f10ea1\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/en\/software-analysis\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Software Analysis<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-d3fc0d9\" data-id=\"d3fc0d9\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-716bcd1 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"716bcd1\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/en\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Home page<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-affc16f\" data-id=\"affc16f\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-f2ba715 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"f2ba715\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/fr.wikipedia.org\/wiki\/UML_(informatique)\" target=\"_blank\" rel=\"noopener\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Wiki<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-5d120fd elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"5d120fd\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-e942c7e\" data-id=\"e942c7e\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-bfcf550 elementor-widget elementor-widget-heading\" data-id=\"bfcf550\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_84 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contents<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewbox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewbox=\"0 0 24 24\" version=\"1.2\" baseprofile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/en\/software-analysis\/competition-exercises\/#Exercices-corriges-sur-les-controles-de-concurrence\" >Corrected exercises on concurrency controls<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/en\/software-analysis\/competition-exercises\/#Preambule\" >Preamble<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/complex-systems-ai.com\/en\/software-analysis\/competition-exercises\/#Exercice-1\" >Exercise 1<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/complex-systems-ai.com\/en\/software-analysis\/competition-exercises\/#Exercice-2\" >Exercise 2<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/complex-systems-ai.com\/en\/software-analysis\/competition-exercises\/#Exercice-3\" >Exercise 3<\/a><\/li><\/ul><\/nav><\/div>\n<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercices-corriges-sur-les-controles-de-concurrence\"><\/span>Corrected exercises on concurrency controls<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-82516d0 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"82516d0\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-32e4d41\" data-id=\"32e4d41\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-49e7088 elementor-widget elementor-widget-text-editor\" data-id=\"49e7088\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Concurrency problems are common in a database. Locking and stamping are two techniques to avoid them. Here are corrected exercises on this subject.<\/p><p><img decoding=\"async\" class=\"aligncenter wp-image-11096 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/cropped-Capture.png\" alt=\"competition\" width=\"97\" height=\"97\" title=\"\"><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-a36018f elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"a36018f\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-7303ce0\" data-id=\"7303ce0\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-a958fd3 elementor-widget elementor-widget-heading\" data-id=\"a958fd3\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Preambule\"><\/span>Preamble<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-2b6ef2f elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"2b6ef2f\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-452cd88\" data-id=\"452cd88\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-dad181c elementor-widget elementor-widget-text-editor\" data-id=\"dad181c\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Expression of constraints<br \/>\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014<\/p><p>0. PL\/SQL Preamble<br \/>SQL: <br \/>\u2013 Declarative therefore no control structures (loops, conditions, etc.)<br \/>\u2013 Data+set operations<br \/>=&gt; Few applications achievable by a simple sequence of SQL queries; need to enrich SQL with procedural capabilities.<br \/>3 possibilities<br \/>\u2013 Embedded SQL (PRO*C\u2026)<br \/>\u2013 Communication API (SQL-CLI\u2026)<br \/>\u2013 Dedicated language (PL\/SQL\u2026)<\/p><p>Advantage of dedicated languages: Procedures executed on the server side -&gt; Only results are returned to the client -&gt; Minimal network exchanges<\/p><p>Q0. PL\/SQL procedures<\/p><p>Q0.1 <br \/>CREATE OR REPLACE PROCEDURE D<br \/>(noc IN ACCOUNTS.Numero%TYPE, <br \/>credit IN NUMBER )<br \/>IS<br \/>BEGIN<br \/>UPDATE ACCOUNTS SET BALANCE = BALANCE \u2013 debit<br \/>WHERE Number = noc;<br \/>END;<br \/>\/<\/p><p>Q0.2 <br \/>CREATE OR REPLACE PROCEDURE C <br \/>(noc IN ACCOUNTS.Numero%TYPE, <br \/>credit IN ACCOUNTS.Balance%TYPE)<br \/>IS<br \/>BEGIN<br \/>UPDATE ACCOUNTS SET BALANCE = BALANCE + credit<br \/>WHERE Number = noc;<br \/>END;<br \/>\/<\/p><p>Q0.3 <br \/>CREATE OR REPLACE PROCEDURE S<br \/>(noc IN ACCOUNTS.Number%TYPE)<br \/>IS<br \/>theBalance ACCOUNTS.Balance%TYPE;<br \/>BEGIN<br \/>SELECT Balance INTO theBalance <br \/>FROM ACCOUNTS <br \/>WHERE Number = noc;<br \/>DBMS_OUTPUT.PUT_LINE(theBalance);<br \/>END;<br \/>\/<\/p><p>Q0.4 <br \/>CREATE OR REPLACE PROCEDURE V<br \/>(nofrom IN ACCOUNTS.Numero%TYPE,<br \/>noto IN ACCOUNTS.Numero%TYPE,<br \/>trans IN ACCOUNTS.Balance%TYPE)<br \/>IS<br \/>BEGIN<br \/>D (nofrom, trans);<br \/>C (noto, trans);<br \/>END;<br \/>\/<\/p><p>Q0.5 <br \/>CREATE OR REPLACE FUNCTION check <br \/>(noc IN ACCOUNTS.Numero%TYPE,<br \/>amount IN ACCOUNTS.Balance%TYPE)<br \/>RETURN BOOLEAN<br \/>IS<br \/>isSolvent BOOLEAN;<br \/>theBalance ACCOUNTS.Balance%TYPE;<br \/>BEGIN<br \/>SELECT Balance INTO theBalance<br \/>FROM ACCOUNTS<br \/>WHERE Number = noc;<br \/>IF Balance &gt;= amount THEN<br \/>isSolvent := TRUE;<br \/>ELSE<br \/>isSolvent := FALSE;<br \/>END IF;<br \/>RETURN is Solvent;<br \/>END check;<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-aa2c8fd elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"aa2c8fd\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-000bc1f\" data-id=\"000bc1f\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-0bf1753 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"0bf1753\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-e8ff244 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e8ff244\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-b4a79fc\" data-id=\"b4a79fc\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-96e84c3 elementor-widget elementor-widget-heading\" data-id=\"96e84c3\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-1\"><\/span>Exercise 1<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-22440a5 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"22440a5\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-e4dc3eb\" data-id=\"e4dc3eb\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-56cde00 elementor-widget elementor-widget-text-editor\" data-id=\"56cde00\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p><strong>Question 1<\/strong><\/p><p>To avoid possible concurrency issues, the administrator chooses to execute transactions serially. We consider the case of two simultaneous transactions on account X, the balance of which is initially 1000 Euros. Both are debits, the first is 400 Euros, the second is 800 Euros.<\/p><p>At the precise moment when T1 starts its flow, T2 starts.<\/p><p>What is going on ?<\/p><p>How can we speed up the execution of these transactions?<\/p><p><strong>Question 2<\/strong><\/p><p>Six bank account managers each carry out, in a transaction, and simultaneously, operations on 4 accounts A, B, C, and D. Let Ei(A) be a writing operation on account A by manager i, and Li( A) a reading operation of account A by manager i. Consider the following operation sequence: E2(A), L2(B), L6(D), E5(C), E3(A), L5(A), L1(C), L2(D), L3( C), E4(C), E3(D), L4(B), L1(B).<\/p><ol><li>Build it <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/\">graph<\/a> precedence of these transactions.<\/li><li>What execution issues might arise?<\/li><li>Is this execution serializable?<\/li><\/ol>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-39dbf6f elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"39dbf6f\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-b917ef2\" data-id=\"b917ef2\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-bb4e6a2 elementor-widget elementor-widget-toggle\" data-id=\"bb4e6a2\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1961\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1961\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1961\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1961\"><div>Q1. Constraints<\/div><div>Constraint reminders<\/div><div>\u00a0 has. When defining the schema (check)<\/div><div>\u00a0 b. By the CREATE ASSERTION command:<\/div><div>\u00a0 \u00a0 The programmer defines what must always be true\u00a0<\/div><div>\u00a0 \u00a0 The DBMS identifies database modifications that may affect constraints, and does not make them effective if they violate a constraint.<\/div><div>\u00a0 vs. By using Trigger (Event-Condition-Action rules):<\/div><div>\u00a0 \u00a0 The programmer defines DBMS reactions to database changes.<\/div><div>\u00a0 \u00a0 The DBMS applies these.<\/div><div>\u00a0<\/div><div>\u00a0 has. When defining the schema:<\/div><div>\u00a0 CREATE ACCOUNTS TABLE (<\/div><div>\u00a0 \u00a0 Number INT PRIMARY KEY,<\/div><div>\u00a0 \u00a0 \u2026,<\/div><div>\u00a0 \u00a0 Balance FLOAT CHECK (Balance&gt;=0 AND (TYPE &lt;&gt; &#039;Savings&#039; OR Balance &lt;= 2000))<\/div><div>\u00a0 )<\/div><div>\u00a0<\/div><div>\u00a0 b. Assertion<\/div><div>\u00a0 CREATE ASSERTION BonSoldeAssert CHECK\u00a0<\/div><div>\u00a0 (2000 &lt;= ALL(Select Balance FROM ACCOUNTS WHERE Type=&#039;Savings&#039;) AND 0&gt; (Select Balance FROM ACCOUNTS)<\/div><div>\u00a0\u00a0<\/div><div>\u00a0 vs. Trigger<\/div><div>\u00a0 CREATE TRIGGER BonSale<\/div><div>\u00a0 BEFORE INSERT OR UPDATE ON Accounts\u00a0<\/div><div>\u00a0 FOR EACH ROW<\/div><div>\u00a0 WHEN (:NEW.Balance&lt;0 OR (:NEW.Balance&gt;2000 AND :NEW.Type=&#039;Savings&#039;))<\/div><div>\u00a0 ABORT TRANSACTION;<\/div><div>\u00a0<\/div><div>Q2. Transaction observation<\/div><div>\u00a0<\/div><div>T1: A&lt;-1500<\/div><div>Displays: \u201cA&lt;-1500\u201d \u2014 TODO: Is the display really happening?<\/div><div>A&lt;-2100 ==&gt; Violates the constraint \u201csavings type balance implies balance &lt; 2000\u201d<\/div><div>==&gt; Abortion of the entire transaction (Roll Back)<\/div><div>==&gt; A&lt;-1000<\/div><div>\u00a0<\/div><div>T2: A&lt;-700<\/div><div>B&lt;-1300<\/div><div>COMMIT<\/div><div>\u00a0<\/div><div>T3: A&lt;- -900 ==&gt; Violates the \u201cbalance &gt;= 0\u201d constraint<\/div><div>==&gt; Abortion of the entire transaction<\/div><div>\u00a0<\/div><div>T4: Displays \u201cA&lt;-700\u201d<\/div><div>Poster \u201cB&lt;-1300\u201d<\/div><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-f98e9b6 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"f98e9b6\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-cf51c16\" data-id=\"cf51c16\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-2dfd144 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"2dfd144\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-9e7a474 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"9e7a474\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-cd76888\" data-id=\"cd76888\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-473fe0f elementor-widget elementor-widget-heading\" data-id=\"473fe0f\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-2\"><\/span>Exercise 2<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-8a1d7d7 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"8a1d7d7\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-26c68db\" data-id=\"26c68db\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-64f918c elementor-widget elementor-widget-text-editor\" data-id=\"64f918c\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p><strong>Question 3<\/strong><\/p><p>We place ourselves in the case of locking, with tuple level granule.<\/p><p>Show that the locking algorithm \u201cspots\u201d the problem of this execution. What would be the most suitable conflict resolution algorithm for this execution?<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-d332796 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"d332796\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-5a7d6d1\" data-id=\"5a7d6d1\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-f38fe62 elementor-widget elementor-widget-toggle\" data-id=\"f38fe62\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-2551\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-2551\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-2551\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-2551\"><div>Transaction: Sequence of operations (Read \u2013 Write) applying to a DB; four keywords: Starts with BEGIN, ends correctly with COMMIT, fails with ABORT, is undone with ROLLBACK.<\/div><div>\u00a0<\/div><div>Transaction properties:<\/div><div>Atomicity: A transaction is either fully executed or not at all<\/div><div>C oherence: A transaction moves the DB from a consistent state \u2013 where the constraints (integrity and others) are verified \u2013 to a consistent state.<\/div><div>Isolation: No interaction between transactions executed in parallel.<\/div><div>D urability: No loss of results of an executed transaction.<\/div><div>\u00a0<\/div><div>ACID ensured by: Fault tolerance (A, C, and D) + Concurrency control (mainly I, but I has repercussions on C and D)<\/div><div>\u00a0<\/div><div>Q3.<\/div><div>Trivial solution: 1 transaction at a time runs on the DB blocked for it.\u00a0<\/div><div>T1 then T2<\/div><div>\u00a0<\/div><div>Performance problems: Reading the same object, writing different objects, are actions which do not jeopardize isolation -&gt; Possibility of parallelizing transactions.<\/div><div>To improve performance: interleave execution by ensuring that interleaved execution is equivalent to serial execution.<\/div><div>\u00a0<\/div><div>Illustration of the problem of interleaving executions with Q4:<\/div><div><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-20115 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd54.png\" alt=\"competition control\" width=\"846\" height=\"441\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd54.png 846w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd54-300x156.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd54-768x400.png 768w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd54-18x9.png 18w\" sizes=\"(max-width: 846px) 100vw, 846px\" \/><\/div><div>Without concurrency control mechanism, executions are non-deterministic: the result depends on the order of inter-transaction operations (reads\/writes)<\/div><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-f0bc458 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"f0bc458\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-2c2df5a\" data-id=\"2c2df5a\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-d6fa99c elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"d6fa99c\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-885bcee elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"885bcee\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-81bb464\" data-id=\"81bb464\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-951995d elementor-widget elementor-widget-heading\" data-id=\"951995d\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-3\"><\/span>Exercise 3<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-9dbd58a elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"9dbd58a\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-0c67a19\" data-id=\"0c67a19\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-c83599e elementor-widget elementor-widget-text-editor\" data-id=\"c83599e\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p><strong>Question 4<\/strong><\/p><p>Suggest a <a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/\">algorithm<\/a> reading and a writing algorithm with stamping. Are we sure to make this execution serializable with the stamping system? Prove that this is true for any non-serializable execution.<\/p><p><strong>Question 5<\/strong><\/p><p>Compare the two families of techniques seen previously (locking and stamping). Is the simple stamping algorithm better suited for this execution than locking?<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-7572858 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"7572858\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-d9d4cba\" data-id=\"d9d4cba\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-31d666f elementor-widget elementor-widget-toggle\" data-id=\"31d666f\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-5221\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-5221\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-5221\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-5221\"><p>Q4. Precedence graph<\/p><p>The competition control mechanism must provide each transaction with the illusion that it is the only one executing on the DB, ie, the effective execution (therefore interleaved) of the transactions must be equivalent to a serial execution of these (execution: ordered sequence of read\/write operations).<br \/>Executions equivalent to a serial execution are called serializable. The concurrency mechanism must ensure that it only generates serializable executions.<\/p><p>Execution: ordered sequence of read\/write operations by different transactions.<br \/>Serial execution: Operations from different transactions do not interleave.<\/p><p><img decoding=\"async\" class=\"alignnone wp-image-20116 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd55.png\" alt=\"competition control\" width=\"417\" height=\"451\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd55.png 417w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd55-277x300.png 277w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd55-11x12.png 11w\" sizes=\"(max-width: 417px) 100vw, 417px\" \/><\/p><p>Is it possible to reorder the execution to make it serial?<\/p><div><p>No, because it is impossible to swap entries with any other operation -&gt; Induces a precedence relationship between transactions.<\/p><p>More formally:<br \/>Ti precedes Tj (\u201cTi &lt; Tj\u201d) if Ai occurs before<\/p><p>Aj in the execution Ai and Aj imply the same object of the BD<\/p><p>Ai or Aj is a writing action<\/p><p>This precedence relationship generates the precedence graph, in which a vertex is a transaction, and a directed edge is a precedence relationship.<\/p><p>Eg: Ti -&gt; Tj means Ti precedes Tj<\/p><p>View by object of operations (simpler than global view, but loses the order of operations within a transaction):<\/p><p>A: E2(A) E3(A) L5(A)<\/p><p>B: L2(B) L4(B) L1(B)<\/p><p>C: E5(C) L1(C) L3(C) E4(C)<\/p><p>D: L6(D) L2(D) E3(D)<\/p><p>Precedence graph:<\/p><p>T2 -&gt; T3 &lt;-&gt; T5 -&gt; T1 -&gt; T4<\/p><p>T6 -&gt;|<\/p><p>Precedence graph property:<\/p><p>Serializable execution iff absence of cycle (eg, above, T3 must be carried out before T5, which must be carried out before T3)<\/p><p>Problem: detecting cycles is NP Complete (Non-deterministic, Polynomial, difficult)<\/p><p>Noticed:<\/p><p>Isolation Property = Transactions must execute AS if they were alone on the database. Serializability ensures that the result of an interleaved execution is the same as that of a serial execution. But, serializability is not a sufficient condition to ensure that transactions execute in isolation.<\/p><p>Example of non-isolated serializable execution (cascaded ABORT):<\/p><p>T1 &lt; T2 &lt; \u2026 &lt; Tn<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-20117 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd56.png\" alt=\"competition control\" width=\"272\" height=\"251\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd56.png 272w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd56-13x12.png 13w\" sizes=\"(max-width: 272px) 100vw, 272px\" \/><\/p><p>Q5. Most used mechanism for isolation: lock and unlock<\/p><p>Most used locking protocol: 2 Phase lock<\/p><p>Phase 1: All locks are acquired, no unlock is performed<\/p><p>Phase 2: All unlocks are completed, no locks are acquired<\/p><p>Property: Ensures the serializability of the execution of a legal schedule (ie, lock1(X) cannot be followed by lock2(X) but by unlock1(X))<\/p><p>Four types of locks: Shared VS Exclusive \/ Short VS long (see compatibility matrix stated)<\/p><p>Two types of operation: Read and Write.<\/p><p>Different degrees of insulation:<\/p><p>* Degree 0 (Read uncommitted):<\/p><p>Installation of exclusive short write locks<\/p><p>-&gt; Reads even objects modified by transactions that have not committed<\/p><p>* Degree 1 (Read committed):<\/p><p>Installation of exclusive long write locks<\/p><p>Setting short shared read locks<\/p><p>-&gt; Only read objects modified by committed transactions<\/p><p>* Degree 2 (Repeatable Read):<\/p><p>Degree 1 + Installation of long shared read locks<\/p><p>-&gt; Repeatable reading<\/p><p>* Degree 3 (Serializable):<\/p><p>Level 2 + Eliminate ghosts<\/p><p>Locking \u201cspots\u201d the serializability problem: deadlocks<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-medium wp-image-20118\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd57-300x175.png\" alt=\"competition control\" width=\"300\" height=\"175\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd57-300x175.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd57-18x10.png 18w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd57.png 712w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/p><p>Several ways to manage deadlocks<\/p><p>* TimeOut: Kills transactions that take more than x seconds to execute<\/p><p>* Detection: Waiting graph<\/p><p>T5 &lt;-&gt; T3<\/p><p>\u00a0 \u00a0&lt;- T1<\/p><p>\u00a0 \u00a0&lt;- T4<\/p><p>\u00a0 \u00a0Graph Built as execution progresses<\/p><p>\u00a0 \u00a0Rollback any transaction that may cause a cycle to appear in the waiting graph<\/p><p>\u00a0 \u00a0Example: 1. T5 -&gt; T3 2. T1 -&gt; T5 -&gt; T3 3. T1 -&gt; T5 &lt;-&gt; T3 ==&gt; Rollback of T3<\/p><p>\u00a0 \u00a0Problem: Cycle detection always NP complete; can be long if the graph is wide<\/p><p>* Prevention: Timestamps<\/p><p>\u00a0 \u00a0Prioritizes old transactions to prevent deadlocks from occurring.<\/p><p>\u00a0 \u00a0Timestamp associated with each transaction.<\/p><p>\u00a0 \u00a0T1 wants to acquire a lock on an object locked by T2.<\/p><p>\u00a0 \u00a0Solution 1: Wait-Die<\/p><p>if T1 older than T2, T1 waits<\/p><p>otherwise T1 Rollback (and is restarted with the same timestamp)<\/p><p>\u00a0 \u00a0Solution 2: Wound-Wait (waits for old transactions)<\/p><p>if T1 older than T2, T2 must leave the lock and Rollback<\/p><p>otherwise T1 waits<\/p><p>\u00a0 \u00a0 -&gt; Never deadlock: T1 will end up being the oldest and therefore executed with priority.<\/p><p>\u00a0 \u00a0Wait-die VS Wound-wait:<\/p><p>\u00a0 \u00a0 \u00a0 Locks acquired at the start of a transaction -&gt; Old transactions are more likely to have their locks before young ones<\/p><p>\u00a0 \u00a0 \u00a0 -&gt; Wound-wait: causes little Rollback because see assumption<\/p><p>\u00a0 \u00a0 \u00a0 \u00a0 \u00a0Wait-die causes a lot of Rollback because see assumption; but each time at the beginning of young transactions<\/p><p>Stamps:<\/p><p>T2:1 T6:2T5:3T3:4T1:5T4:6<\/p><p>Wait-die:<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-20119 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd58.png\" alt=\"wait-die\" width=\"717\" height=\"784\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd58.png 717w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd58-274x300.png 274w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd58-11x12.png 11w\" sizes=\"(max-width: 717px) 100vw, 717px\" \/><\/p><p>Stamps:<\/p><p>T2:1 T6:2T5:3T3:4T1:5T4:6<\/p><p>Wound-wait:<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-20120 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd59.png\" alt=\"wound-wait\" width=\"725\" height=\"785\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd59.png 725w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd59-277x300.png 277w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd59-11x12.png 11w\" sizes=\"(max-width: 725px) 100vw, 725px\" \/><\/p><p>Q5.b.<br \/>Altruistic locking: A transaction releases its locks when it no longer needs them.<br \/>+: Effective<br \/>\u2013 : (i) Dirty read problem; (ii) Execution a priori not 2PL therefore a priori not serializable.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-20121 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd60.png\" alt=\"altruistic lock\" width=\"733\" height=\"200\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd60.png 733w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd60-300x82.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd60-18x5.png 18w\" sizes=\"(max-width: 733px) 100vw, 733px\" \/><\/p><p>Q6.<br \/>Stamping system: Assigns a stamp to each transaction (generally the timestamp of its creation), prevents access to objects contrary to the order of the stamps -&gt; Priority to young transactions. Transactions arriving late are Rollbacked and restarted with a new time stamp. Part of the family of optimistic protocols, ie, effective method when few conflicts because little overhead but potentially a lot of rollback.<\/p><p>Two rules:<\/p><p>Read too late: A transaction can only read data if it is younger than the last writer<\/p><p>Write too late: A transaction can only write data if it is younger than the last reader and writer<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-20122 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd61.png\" alt=\"stamping\" width=\"505\" height=\"246\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd61.png 505w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd61-300x146.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd61-18x9.png 18w\" sizes=\"(max-width: 505px) 100vw, 505px\" \/><\/p><p>Basic algorithm:<\/p><p>\u2013 Place stamp on each transaction<\/p><p>\u2013 Each object retains the stamp of the last reader as well as that of the last writer<\/p><p>\u2013 When Ti wants to read object O:<\/p><p>If stamp &lt; O.LastWriter: Read too late -&gt; Ti ROLLBACK then restarts with new stamp<\/p><p>Otherwise OK<\/p><p>\u2013 When Ti wants to write the object O:<\/p><p>If Ti.stamp &lt; O.LastReader || Ti.stamp &lt; O.LastWriter: Write too late -&gt; Ti ROLLBACK then restarts with new stamp<\/p><p>Otherwise OK<\/p><p>Example:<\/p><p>Stamps:<\/p><p>T2: 1-8 T6: 2T5: 3-7T3: 4T1: 5T4: 6<\/p><p>Objects:<\/p><p>A (L: ; E: 1) A (L: ; E: 4)<\/p><p>B (L: 1; E: )<\/p><p>C (L: 5; E: 3-6) C (L: 5; E: 6)<\/p><p>D (L: 2; E: 4)<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-20123 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd62.png\" alt=\"stamping\" width=\"377\" height=\"286\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd62.png 377w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd62-300x228.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd62-16x12.png 16w\" sizes=\"(max-width: 377px) 100vw, 377px\" \/><\/p><p>The precedence graphs of stamping executions never have a cycle.<\/p><p>Proof by absurdity:<\/p><p>Consider the cyclic precedence graph of an execution obtained by stamping:<\/p><p>T1 -&gt; \u2026 -&gt; Ti &lt;-&gt; Tj -&gt; \u2026 -&gt; Tn =&gt; Ti &lt; Tj &lt; Ti<\/p><p>&lt;=&gt; i &lt; j &lt; i<\/p><p>Contradiction<\/p><p>Q8.<\/p><p>Stamping good when few conflicts (no waiting); bad when a lot of conflicts (lots of rollback).<\/p><p>Good locking when lots of conflicts (less Rollback than stamping); bad when few conflicts (useless waits, lock management overhead).<\/p><p>Commercial systems attempt to combine the advantages of both: multiversion stamping (a variation of single stamping discussed above) for Read Only transactions, and 2PL locking for Read\/Write transactions. (see p. 978 of \u201cDB Systems: the complete book\u201d by Widom and Ullmann)<\/p><\/div><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>","protected":false},"excerpt":{"rendered":"<p>Software Analysis Wiki Home Page Corrected exercises on concurrency controls Concurrency problems are common in a database. Lockdown... <\/p>","protected":false},"author":1,"featured_media":0,"parent":4609,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-20109","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/20109","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/comments?post=20109"}],"version-history":[{"count":16,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/20109\/revisions"}],"predecessor-version":[{"id":20520,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/20109\/revisions\/20520"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/4609"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=20109"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}