LessonsfromtheTSIMMISProject

,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,49,Lessons from the TSIMMIS Project,Yannis Papakonstantinou,Department of Computer Science & Engineering,University of California, San Diego,1,Overview,TSIMMIS goals, technical challenges, and solutions,Insufficiencies of the TSIMMIS framework,Going forward,2,Information Resides on Heterogeneous Information Sources,different interfaces,different data representations,redundant and conflicting information,WWW,Ticker,Tape,Personal,database,Dialog,3,Goal: System Providing Integrated View of Heterogeneous Data,Integration System,WWW,Personal,database,collects and combines information,provides integrated view, uniform user interface,Ticker,Tape,Dialog,4,The Wrapper and Mediator Architecture,Mediator,Wrapper,Wrapper,Client,business reports,portfolios for each company,stock market prices,Ticker,Tape,Dialog,Common,Data,Model,5,The Data Warehousing Approach to Integration,Mediator,Wrapper,Wrapper,Client,Ticker,Tape,Dialog,Stored,Integrated,View,6,The Lazy Integration Approach,Mediator,Wrapper,Wrapper,Client,IBM portfolio,IBM price,IBM related reports,(in common model),IBM related reports,Ticker,Tape,Dialog,Query Decomposition,Translation and,Result Fusion,7,Mediator,Client,Wrapper,Wrappers & Mediators from High-Level Specifications,Mediator Specification,Interpreter,Wrapper,Generator,Wrapper,Wrapper,Specification,Mediator,Specification,Source,Source,8,Challenge: Sources Without a Well-Structured Schema,semistructured,irregular,deeply nested,cross-referenced,incomplete schema knowledge,autonomous,dynamic,HTML pages,SGML documents,genome data,chemical structures,bibliographic information,results of the integration process,Examples,9,Challenge: Different and Limited Source Capabilities,Client,Wrapper,(,A,),Wrapper,(,B,),Mediator,(U = A + B),retrieve IBM data,retrieve IBM data,retrieve IBM data,10,Mediator has to Adapt to Query Capabilities of Sources,Client,Wrapper,(,A,),Wrapper,(,B,),Mediator,(U = A + B),retrieve everything,retrieve IBM data,retrieve IBM data,retrieve IBM data,(A),does not,allow selection,11,Part B,Semistructured Data Representation,Mediator Generation,Wrapper Generation,Capabilities-Based Rewriting,12,Representation of Semistructured Information using OEM,semantic,object-id,label,Atomic Value,Set Value,structural,object-id,13,Graph Representation of OEM Data,faculty,first_name,“John”,last_name,“Doe”,rank,“professor”,14,OEM Structures Represent Arbitrary Labeled Graphs,faculty,first_name,“John”,last_name,“Doe”,rank,“professor”,faculty,name,“Mary Smith”,project,“Air DB”,paper,author,name,“John Doe”,author,name,“,Mary Smith,”,title,“Thin Air DB”,15,Overview,Semistructured Data Representation,Mediator Generation,Example of mediator specification,Language expressiveness,Implementation and performance,Wrapper Generation,Capabilities-Based Rewriting,16,Merge Information Relating to a Faculty,person,name “John Doe”,birthday “April 1”,s2,faculty,name “John Doe”,rank “professor”,papers,.,s1,faculty,name “John Doe”,rank “professor”,birthday “April 1”,papers,.,17,Mediator Specification Example,person,name “John Doe”,birthday “April 1”,s2, :- s1, :- s2,faculty,name “John Doe”,rank “professor”,papers,.,s1,faculty,name “John Doe”,rank “professor”,birthday “April 1”,papers,.,18,Mediator Specification Example: Semantics of Rule Bodies, :-,faculty s1, :- s2,person,name “John Doe”,birthday “April 1”,s2,faculty,name “John Doe”,rank “professor”,birthday “April 1”,papers,.,faculty,name,“John Doe”,rank,“professor”,papers,.,s1,19,Mediator Specification Example: Semantics of Rule Heads,N,faculty :- faculty s1, :- s2,person,name “John Doe”,birthday “April 1”,s2,“John Doe”,faculty,name “John Doe”,rank,“professor”,birthday “April 1”,papers,.,faculty,name,“John Doe”,rank,“professor”,papers,.,s1,20,Incrementally Add to Semantically Identified Object,N,faculty :- faculty s1, :- s2,faculty,name,“John Doe”,rank “professor”,papers,.,s1,person,name “John Doe”,birthday “April 1”,s2,“John Doe”,faculty,name,“John Doe”,rank “professor”,birthday “April 1”,papers,.,21,Irregularities & Incomplete Schema Knowledge,N faculty :- s1,faculty,name “John Doe”,rank,“professor”,papers,faculty,name “Mary Smith”,project,“Air DB”,s1,person,name “John Doe”,birthday “April 1”,s2,faculty,name “John Doe”,rank,“professor”,birthday “April 1”,papers,faculty,name “Mary Smith”,project,“Air DB”,“John Doe”,“Mary Smith”,22,Second Rule Attaches More Subobjects to View Objects, :- s1,N,faculty :- person s2,faculty,name “John Doe”,rank “professor”,papers,.,s1,“John Doe”,faculty,name “John Doe”,rank “professor”,birthday,“April 1”,papers,.,person,name,“John Doe”,birthday,“April 1”,s2,23,Language Expressiveness,Information fusion problems solved by MSL,Irregularities,Incomplete knowledge of source structure,Transformation of cross-referenced structures,Inconsistent and redundant data,Use of arbitrary matching criteria,Theoretical analysis of expressiveness,Consider the relational representation of OEM graphs. Then MSL is equivalent to “SQL + special form of transitive closure”,24,faculty,name “John Doe”,rank,“associate”,Inconsistent and Redundant Information, :- s1, :- s2,AND NOT s1,person,name “John Doe”,rank,“assistant”,s1,s2,“John Doe”,faculty,name “John Doe”,rank,“associate”,rank,“assistant”,25,Overview,Semistructured Data Representation,Mediator Generation,Example of mediator specification,Language expressiveness,Implementation and performance,Wrapper Generation,Capabilities-Based Rewriting,26,Mediator Specification Interpreter Architecture,Query Rewriter,Cost-Based Optimizer,Datamerge Engine,Mediator,Specification,Query,logical datamerge,program,plan,Result,Queries to,Wrappers,Results,27,Query,Rewriting When Known Origins of Information,N faculty , :-:- ,s1, :- ,s2, :- N faculty , AND,X,65000,28,Query Rewriter Pushes,Conditions to Sources,N faculty , :-:- ,s1, :- ,s2, :- N faculty , AND,X,65000,logical datamerge program, ,:-,(,AND,X,65000),s1,AND ,s2,29, :- ,Passing Bindings,&,Local Join,Plans,Passing Bindings,Local Join, :-,faculty ,AND X65000, :- , :-,faculty ,AND X65000,N,s1,s2,s1,s2,30,Query,Decomposition When,Unknown,Origins of Information, :- , :- s1, :- s2,31,Plan Considers All Possible Sources of,birthday, :- X faculty , :- ,s1, :- ,s2,name,s2,s1,name,birthday,birthday,32,Overview,Semistructured-Data Representation,Mediator Generation,Wrapper Generation,Capabilities-Based Rewriting,33,Query Translation in Wrappers,Source,SELECT * FROM person,SELECT * FROM person,WHERE name=“Smith”,find -all,find -n Smith,Query Translator,Result,Translator,Wrapper,34,Rapid Query Translation Using Templates and,Actions,Source,SELECT * FROM person,SELECT * FROM person,WHERE name=“Smith”,find -all,find -n Smith,Template,Interpreter,Result,Translator,SELECT * FROM person,emit “find -all” ,SELECT * FROM person,WHERE name=$N,emit “find -n $N”,35,Description of Infinite Sets of Supported Queries,uses,recursive,nonterminals,Example:,job description contains word w1 and word w2 and .,SELECT,subset(,person,),FROM personWHERE,CJob,CJob,: job LIKE $W AND ,CJob,CJob,: TRUE,36,Overview,Semistructured-Data Representation,Mediator Generation,Wrapper Generation,Capabilities-Based Rewriting,37,Wrapper,Supported Queries,Description,Capabilities-Based Rewriter in Mediator Architecture,Capabilities-,Based,Rewriter,Query,Rewriter,Cost-Based,Optimizer,Datamerge,Engine,logical datamerge program,supported,plans,optimal plan,Mediator,Specification,Wrapper,Supported Queries,Description,Query,38,Capabilities-Based Rewriter Finds Supported Plans,Supported Queries,SELECT * FROM A,WHERE salary65000,SELECT * FROM A,39,Capabilities-Based Rewriter Finds,Most-Selective,Supported Plans,Supported Queries,SELECT * FROM B,WHERE salary65000,SELECT * FROM B,SELECT * FROM B,WHERE salary 65000,40,Capabilities-Based Rewriter Architecture,Component SubQuery,Discovery,Plan Construction,Plan Refinement,Query Capabilities,Description,Component SubQueries,Plans (not fully optimized),Query,Algebraically optimal plans,41,What TSIMMIS Achieved,system for integration of heterogeneous sources,challenges,and,solutions,semistructured data & incomplete schema knowledge,appropriate specification language and query processing algorithms,limited and different query capabilities,query translation algorithm,capabilities-based query rewriting algorithm,42,Overview,TSIMMIS goals, technical challenges, and solutions,Insufficiencies of the TSIMMIS framework,Going forward,43,Insufficiencies of the TSIMMIS framework,OEM was really,un,structured data,some loose and partial schematic info may pay off tremendously,too “databasy” user/mediator/source interaction,44,Overview,TSIMMIS goals, technical challenges, and solutions,Insufficiencies of the TSIMMIS framework,Going forward,45,Web emerges as a Distributed DB and XML as its Data Model,Data,Source,Native XML,Database,XML View,Document(s),XML View,Document(s),XML View,Document(s),Also export:,1. Schemas & Metadata,(XML-Data, RDF,),2. Description of,supported queries,Wrapper,Legacy,Source,XMAS Query,Language,46,Definition of Integrated Views,Data,Source,Data,Source,Data,Source,Mediator,XML View,Document(s),Integrated,XML View,XML View,Document(s),XML View,Document(s),View Definition in,XMAS,47,Non-Materialized Views in the MIX mediator system,B,lended,B,rowsing &,Q,uerying (,BBQ,) GUI,Application,DOM for Virtual XML Docs,MIX Mediator,XMAS query,XML document,DTD,Inference,Integrated,View DTD,XML Source,XML Source,Query,Processor,View Definition in,XMAS,Source DTD,48,RDB,RDB2XML,Wrapper,DTD,Inference,Resolution,Simplification,Execution,Unfolded Query,Blended Browsing &,Querying (BBQ) GUI,MIX Mediator,XMAS Mediator,View Definition,View DTD,Translation to Algebra,Optimization,XML Document,Fragments,XMAS,Query,XML,Source 1,XML,Source 2,DTD,XMAS,Query,XML,Document,Fragments,DOM (VXD),Client API,Application,49,