1、不連續(xù)及不穩(wěn)定數(shù)據(jù)管理英文課件Efficient Management of Inconsistent and Uncertain DataRene J. MillerUniversity of Toronto不連續(xù)及不穩(wěn)定數(shù)據(jù)管理英文課件ContributorslAriel Fuxman, PhD ThesislMicrosoft Search LabslJim Gray SIGMOD 2008 Dissertation AwardlPeriklis Andritsos, PhDlJiang Du, MSlElham Fazli, MSlDiego Fuxman, Undergrad不連續(xù)及

2、不穩(wěn)定數(shù)據(jù)管理英文課件3Dirty DatabaseslThe presence of dirty data is a major problem in enterpriseslTraditional solution: data cleaningNo. I dont see Any problem with the data不連續(xù)及不穩(wěn)定數(shù)據(jù)管理英文課件Limitations of Data CleaninglSemi-automatic processlRequires highly-qualified domain experts lTime consuminglMay not be p

3、ossible to wait until the database is cleanlOperational systems answer queries assuming clean data不連續(xù)及不穩(wěn)定數(shù)據(jù)管理英文課件5Our WorkIdentify classes of queries for which we can obtain meaningful answers from potentially dirty databasesShow how to do it efficiently and reusing existing database technology不連續(xù)及不

4、穩(wěn)定數(shù)據(jù)管理英文課件Why is this Business Intelligence?lBusiness intelligence (BI) refers to technologies, applications and practices for the collection, integration, analysis, and presentation of information.lThe goal of BI is to support better decision making, based on information.lDBMS should provide meanin

5、gful query answers even over data that is dirty不連續(xù)及不穩(wěn)定數(shù)據(jù)管理英文課件7Outline Introductionq Semantics for dirty databasesq Contributionsq Conclusions不連續(xù)及不穩(wěn)定數(shù)據(jù)管理英文課件8Outline Introductionq Semantics for dirty databasesq Contributionsq Conclusions不連續(xù)及不穩(wěn)定數(shù)據(jù)管理英文課件9A Data Integration ExampleIntegrating customer

6、data不連續(xù)及不穩(wěn)定數(shù)據(jù)管理英文課件10Matching and MergingCustidPeterPeterNameAddressIncomePeter Yarrow276 College Street40KPaul Stookey100 Bloor Street400KMary Travers20 Union Street110KNameAddressIncomePeter Peter YarrowYarrow276 College 276 College StreetStreet40K40KPaul Stookey100 Bloor Street400KMary Travers20

7、Union Street110KCustidPeterPeterNameAddressIncomePeter Yarrow276 College St.200KPaul Stookey100 Bloor St.400KMary Travers20 Union St.130KNameAddressIncomePeter Peter YarrowYarrow276 College St.276 College St.200K200KPaul Stookey100 Bloor St.400KMary Travers20 Union St.130KWebSalesMatching and mergin

8、g are two fundamental tasks in data integration 不連續(xù)及不穩(wěn)定數(shù)據(jù)管理英文課件11NameAddressIncomePeter Peter YarrowYarrow276 College 276 College StreetStreet200K200KPaul Stookey100 Bloor St.400KMary Travers20 Union St.130KNameAddressIncomePeter Peter YarrowYarrow276 College 276 College StreetStreet40K40KPaul Stook

9、ey100 Bloor Street400KMary Travers20 Union Street110KTrue Disagreement Between SourcesCustidPeterPeterWebSalesWhats Peters salary?CustidPeterPeter不連續(xù)及不穩(wěn)定數(shù)據(jù)管理英文課件12Inconsistent Integrated DatabasesIn the absence of complete resolution rulesSATISFY custid KEYVIOLATES custid KEYconsistent Integrated Da

10、tabase不連續(xù)及不穩(wěn)定數(shù)據(jù)管理英文課件13CustidincomePeter40KPeterPeter200KPaulPaul400KMaryMary110KMaryMary130KCustidincomePeter40KPeter200KPaul400KMary110KMary130KCustidincomePeterPeter40K40KPeter200KPaul400KMary110KMary130KQuery: “Get customers who make more than 100K”Peter,Paul,MaryAre we sure that we want to offe

11、r a card to Peter?Example: Offering a Platinum credit cardQuerying Inconsistent Databases不連續(xù)及不穩(wěn)定數(shù)據(jù)管理英文課件14lAggressive: Get customers who possibly make more than 100KlPeter, Paul, Mary lConservative: Get customers who certainly make more than 100KlPaul, MaryQuerying Inconsistent Databases不連續(xù)及不穩(wěn)定數(shù)據(jù)管理英

12、文課件15Formal SemanticslRelated to semantics for querying incomplete data Imielinski Lipski 84, Abiteboul Duschka 98lPossible world: “complete” databaseslConsistent answerslProposed by Arenas, Bertossi, and Chomicki in 1999lCorresponds to conservative semanticslPossible world: “consistent” databases不連

13、續(xù)及不穩(wěn)定數(shù)據(jù)管理英文課件16custidincomePeter40KPeter200KPaul400KMary110KMary130KcustidincomePeter40KPeter200KPaul400KMary110KMary130KcustidincomePeter40KPeter200KPaul400KMary110KMary130KcustidincomePeter40KPeter200KPaul400KMary110KMary130KcustidincomePeter40KPeter200KPaul400KMary110KMary130KInconsistent databas

14、eRepairsConsistent Answers不連續(xù)及不穩(wěn)定數(shù)據(jù)管理英文課件17CONSISTENT ANSWERSAnswers obtainedno matter which repair we chooseCONSISTENT ANSWER=Paul,MaryConsistent AnswersPaulMaryPaulMaryPeterPaulMaryPeterPaulMaryPaulPaulMaryMaryPaulPaulMaryMaryPeterPaulPaulMaryMaryPeterPaulPaulMaryMary不連續(xù)及不穩(wěn)定數(shù)據(jù)管理英文課件18Outline Intro

15、duction Semantics for dirty databasesq Contributionsq Conclusions不連續(xù)及不穩(wěn)定數(shù)據(jù)管理英文課件19When We StartedlSemantics well understoodlProblemlPotentially HUGE number of repairs!lNegative results Chomicki et al 02, Arenas et al. 01, Cali et al 04 lFew tractability results Arenas et al. 99, Arenas et al. 01lLog

16、ic programming approaches Bravo and Bertossi 03, Eiter et al. 03lExpressive queries and constraintslComputationally expensivelApplicable only to small databases with small number of inconsistencies不連續(xù)及不穩(wěn)定數(shù)據(jù)管理英文課件20Our Proposal: ConQuerCommercial databaseengineSQL query q KeysRewrittenSQL query Q*Mac

17、intosh PICTimage formatis not supported不連續(xù)及不穩(wěn)定數(shù)據(jù)管理英文課件21Class of Rewritable QuerieslConQuer handles a broad class of SPJ queries withlSet semanticslBag semantics, grouping, and aggregationlNo restrictions onlNumber of relationslNumber of joinslConditions or built-in predicateslKey-to-key joinslThe c

18、lass is “maximal”不連續(xù)及不穩(wěn)定數(shù)據(jù)管理英文課件22Why not all SPJ queries?lSome SPJ queries cannot be rewritten into SQLlConsistent query answering is coNP-complete even for some SPJ queries and key constraintslMaximality of ConQuers classlMinimal relaxations lead to intractabilitylRestrictions only onlNonkey-to-no

19、nkey joinslSelf joinslNonkey-to-key joins that form a cycle不連續(xù)及不穩(wěn)定數(shù)據(jù)管理英文課件23Example: A Rewritable QuerySELECT c_custkey, c_name, sum(l_extendedprice * (1 - l_discount) as revenue, c_acctbal, n_name, c_address, c_phone, c_commentFROM customer, orders, lineitem, nationWHERE c_custkey = o_custkey and l

20、_orderkey = o_orderkey and o_orderdate = 1993-10-01 and o_orderdate date(1993-10-01) + 3 MONTHS and l_returnflag = R and c_nationkey = n_nationkeyGROUP BY c_custkey, c_name, c_acctbal, c_phone, n_name, c_address, c_commentORDER BY revenue desc TPC-H Query 10不連續(xù)及不穩(wěn)定數(shù)據(jù)管理英文課件Rewritings Can Get Quite Co

21、mplexRewriting of TPC-H Query 10Can this rewriting be executed efficiently?1.7 overhead20 GB database, 5% inconsistency 不連續(xù)及不穩(wěn)定數(shù)據(jù)管理英文課件25Experimental EvaluationlGoalslQuantify the overhead of the rewritingslAssess the scalability of the approach lDetermine sensitivity of the rewritten queries to lev

22、el of inconsistency of the instancelQueries and databaseslRepresentative decision support queries (TPC-H benchmark)lTPC-H databases, altered to introduce inconsistencieslDatabase parametersldatabase sizelpercentage of the database that is inconsistentlconflicts per key value (in inconsistent portion

23、)不連續(xù)及不穩(wěn)定數(shù)據(jù)管理英文課件26Worst Case5.8 overheadSelectivity 98.56 %Size (GB)Maci nt osh PI CTi mage f or mati s not suppor t ed5 % inconsistent tuples2 conflicts per inconsistent key valueScalabilityBest Case1.2 overheadSelectivity 0.001 %不連續(xù)及不穩(wěn)定數(shù)據(jù)管理英文課件27Contributions TheorylFormal characterization of a br

24、oad class of queries lFor which computing consistent answers is tractable under key constraintslThat can be rewritten into first-order/SQLlQuery rewriting algorithms for a class of Select-Project-Join queries lWith set semanticslWith bag semantics, grouping, and aggregationlMaximality of the class o

25、f queries不連續(xù)及不穩(wěn)定數(shù)據(jù)管理英文課件28Contributions PracticelImplementation of ConQuerl Designed to compute consistent answers efficientlylMultiple rewriting strategieslExperimental validation of efficiency and scalability lRepresentative queries from TPC-HlLarge databases不連續(xù)及不穩(wěn)定數(shù)據(jù)管理英文課件Uncertain DatacustidincomePeter40KPaul 400KMary110KcustidincomePeter 200KPaul400KMary130KcustidincomePeter40KPeter200KPaul400KMary110KMary130K不連續(xù)及不穩(wěn)定數(shù)據(jù)管理英文課