1Principles of Information and Database Management198:336Week 11 – Apr 18Matthew StoneOutlineTransactions– Concepts– Implementation– ShortcutsWeb data– Hubs and authorities– Google PageRank2TransactionDefinition: an execution of a user program, seen by the DBMS as a series of read and write operations.ACID properties of transactionsAtomicConsistentIsolatedDurable3AtomicityEither all actions in a transaction execute or none of them do. – Needs to be guaranteed by DBMSConsistencyWhen run by itself – any transaction will leave the DB in a good state4IsolationEach transaction is protected from the effects of other transactions that might be running at the same time– No transaction can “tell” that other transactions are runningDurabilityOnce the DBMS informs the user that a transaction completed, its effects persist5Design choiceTransaction can be aborted by DBMS– Terminated unsuccessfully– May be bounced back• in this case none of it ever happened– May be retried• DBMS starts over and makes it workTransaction detailsOracle details– In SQLPLUS, everything you do is one xact– To end a transaction, use SQL commands• COMMIT• ROLLBACK6Transaction detailsIn MySQL command interface– Need InnoDB tables, and transaction mode• set autocommit=0;– Transactions have to be explicitly started• Start transaction;– Then finish transactions as usual• COMMIT• ROLLBACKTransaction detailsIn JDBC, part of the connection interface– Need to start up transaction mode• conn.setAutoCommit(false);– Like oracle, everything is in current xact– Just need to end xact• conn.commit();• conn.rollback();7How transactions helpActions by one process can put database in temporary, inconsistent state.– need to make sure other processes don’t use this inconsistent stateExample – “midnight bank transfer”Transfer $100 from account A to account B – read A– write A-$100– read B– write B+$100Halfway through is an inconsistent state– $100 has “gone missing”8“Midnight bank transfer”Suppose it’s time to pay interestAlgorithmread Awrite A * 1.05read Bwrite B * 1.05Bad soup!Suppose you pay interest in the moment when $100 is missing! Either A or B gets ripped off.9TransactionsLet DB program say what should happen–First• start transaction• r A, w A-$100, r B, w B+$100•commit– Second• start transaction• r A, w A*1.05, r B, w B*1.05•commitTransactionsUnderlying DBMS makes sure xacts are only interleaved correctly (if at all).10Kinds of things to worry aboutReading uncommitted data– “dirty read”– write-read conflictsUnrepeatable reads– T2 changes the value of A while– T1, in progress, has already read AKinds of things to worry aboutOverwriting uncommitted data– write-write conflicts– complementary writes leave DB in bad state11Asideselect … for update– required to say that you’re using information to compute a change to the database.– otherwise xact may retry with stale valuesShortcutsCreating IDs in Oraclecreate sequence my_id_sequence start with 1;insert into my_table values(my_id_sequence.nextval, 0);select my_id_sequence.currval from dual;12ShortcutsCreating IDs in MySQL– autoincrement feature– use null as primary key– select last_insert_id() from any_table;Page RankPR(A) = (1-d) +d * (PR(t1)/C(t1) + … + PR(tn)/C(tn))t1..tn are the pages that link to AC(ti) is the number of links out of page tid is a “fudge factor” (google’s is 0.85)13MetaphorPigeons randomly surfing the internet– random start point– click randomly on links– restart after 1/(1-d) clicks– what percentage of the time do they end up on each page?MetaphorPages vote for their neighbors– Like stockholders meeting– You get votes according to your importance– You can split your votes among any number of candidates14TrickyRequires an iterative calculationPR(A) = .15 + .85 * (PR(B)/C(B))PR(B) = .15 + .85 * (PR(A)/C(A))A BIn the endPR(A) = PR(B) = 1.Check by– pigeon metaphor– solution to equations15Other examplesA BCRankPR(A) ~ .77PR(B) ~ 1.46PR(C) ~ .7716Other examplesA BCRankPR(A) ~ 1PR(B) ~ 1.3PR(C) ~ 0.717Issues with real web sitesReachabilityAliasesSpamGoogle policeRequire pages to be different– identify spamPenalize links to