Inhalt

•  
   List of Figures
•  
   List of Definitions
•  
  CHAPTER 1 Introduction
•  
   1.1 Background: the dilemma of software legacies
•  
   role of information management
•  
  legacy systems characteristics
•  
   Definition 1.1 Legacy software system
•  
   dealing with legacy systems cold turkey
•  
  reengineering
•  
   Definition 1.2 Software reengineering
•  
  reengineering process
•  
  Definition 1.3 Reverse engineering
•  
   Reverse engineering is the process of analyzing a ...
•  
   Figure 1.1. Reengineering process
•  
   1.2 Database reengineering
•  
   mass changes w.r.t. data representation
•  
   importance of data structures
•  
   database reengineering
•  
  Definition 1.4 Database reengineering
•  
   Figure 1.2. Conceptual schema as a starting point ...
•  
   1.3 Problem definition
•  
   tool support
•  
   customizability
•  
   human-awareness
•  
   role of human knowledge
•  
   Figure 1.3. CARE tool classification according to ...
•  
   representation of human knowledge
•  
  iterations
•  
   1.4 The approach
•  
   GFRN to achieve customizability
•  
   Figure 1.4. Proposed DBRE approach
•  
   analysis guided by possibilistic inference engine
•  
   user interaction
•  
   iterations between analysis and migration
•  
   1.5 Dissertation outline
•  
   Chapter 2
•  
   Chapter 3
•  
   Chapter 4
•  
   Chapter 5
•  
   Chapters 6
•  
  CHAPTER 2 Database Reengineering- A Case Study
•  
   2.1 A legacy product and document information syst...
•  
   PDIS overview
•  
  PDIS problems
•  
   2.2 Migration target: a distributed marketing info...
•  
   migration objectives
•  
   Figure 2.1. Existing Product and Document Informat...
•  
   2.2.1 Functional requirements
•  
  2.2.2 Technical requirements
•  
   Figure 2.2. Planned Marketing Information System (...
•  
   2.3 Migration strategy
•  
   Figure 2.3. Gradual migration strategy
•  
   2.4 The reengineering process
•  
  problem of inconsistency
•  
   Figure 2.4. The planned reengineering process
•  
   2.4.1 Legacy schema analysis
•  
   activity overview
•  
   PDIS example
•  
  Structural completion
•  
   Figure 2.5. Constraints resulting from the schema ...
•  
   heuristics as indicators
•  
  naming conventions
•  
   Figure 2.6. Potential constraints indicated by nam...
•  
   Figure 2.7. Detail of PDIS
•  
   code patterns
•  
   code segment 1: cyclic join pattern
•  
  code segment 2: select distinct pattern
•  
   Figure 2.8. Contradicting indicators for key const...
•  
  code segment 3: join pattern
•  
   Figure 2.9. Potential foreign keys indicated by jo...
•  
   data analysis
•  
   Figure 2.10. Result of the structural completion
•  
   Semantical enrichment
•  
   inheritance structures
•  
  variant records
•  
   Figure 2.11. Assumed hidden common domain relation...
•  
   Figure 2.12. Labeled variants and additional forei...
•  
   Figure 2.13. Variants of table PRODREF
•  
   optimization structures code segment 4
•  
   artificial keys
•  
  aggregations
•  
   Figure 2.14. Detected optimization and aggregation...
•  
   cardinality constraints
•  
   Figure 2.15. Implication of relational constraints...
•  
   problems of scale: completeness and consistency
•  
   iterative process
•  
   Figure 2.16. Summary of analysis results
•  
  Observations
•  
   O1. involves heuristics and imprecise facts, i.e.,...
•  
   O2. deals with idiosyncratic coding concepts and o...
•  
   O3. involves heuristics with credibilities that de...
•  
   O4. combines contradicting indicators and assumpti...
•  
   O5. deals with incomplete information and non-mono...
•  
   O6. is a human-intensive process that can be suppo...
•  
   O7. produces abstract information about the LDB by...
•  
   2.4.2 Conceptual schema migration and redesign
•  
   conceptual migration
•  
   conceptual redesign
•  
   iteration
•  
   Figure 2.17. Conceptual schema for PDIS (detail)
•  
   update of conceptual schema
•  
   problems of scale: correctness and consistency
•  
   Figure 2.18. Extended conceptual schema for MIS (d...
•  
   2.4.3 Implementation of changes and a middleware f...
•  
   Figure 2.19. Extended conceptual schema for MIS af...
•  
   implementation alternatives
•  
   Figure 2.20. Implemented extensions of the logical...
•  
   MIS architecture and rationales
•  
  middleware design
•  
   Figure 2.21. MIS architecture
•  
   Figure 2.22. Design of the middleware layer (detai...
•  
  Observations
•  
   O8. Conceptual abstraction (and redesign) of a log...
•  
   O9. Conceptual translation of complex schemas is e...
•  
   O10. Increasing conceptual knowledge about LDBs of...
•  
   O11. Iterations cause inconsistencies between the ...
•  
   O12. Modifications to the original schema can be p...
•  
   2.5 Summary and concluding remarks
•  
   relevance of the scenario
•  
   migration strategy
•  
   DBRE process
•  
   role of the scenario
•  
  CHAPTER 3 A Theory to Manage Imperfect Knowledge
•  
  knowledge-based system
•  
   3.1 Requirements on formalisms to manage DBRE know...
•  
   Figure 3.1. Reference architecture of KBS
•  
   3.1.1 Quantitative representation of uncertainty
•  
  quantitative vs. qualitative approaches
•  
   R1. A formalism to specify DBRE expert knowledge h...
•  
  3.1.2 Representation and indication of contradicti...
•  
   R2. A formalism to manage DBRE knowledge has to al...
•  
   R3. A formalism to manage DBRE knowledge has to be...
•  
  3.1.3 Reasoning about incomplete knowledge
•  
   R4. A formalism to manage DBRE knowledge has to be...
•  
   3.1.4 Representation of ignorance
•  
   R5. A formalism to manage DBRE knowledge has to be...
•  
  3.1.5 Computational tractability
•  
   R6. A formalism to manage DBRE knowledge should sc...
•  
  3.2 Evaluation of theories
•  
  Notation and basic definitions
•  
   Definition 3.1 Data model
•  
   Definition 3.2 Database
•  
   Definition 3.3 Relational database
•  
   Definition 3.4 (Notation)
•  
  Definition 3.5 Flattening
•  
   We define a function that transitively flattens ne...
•  
   3.2.1 Production systems with confidence factors
•  
   CF(u3Ÿu4)=min(CF(u3),CF(u4)) (EQ 1)
•  
   CF(u3⁄u4)=max(CF(u3),CF(u4)) (EQ 2)
•  
   CF(Øu3)=-1*CF(u3) (EQ 3)
•  
   (EQ 4)
•  
   Evaluation
•  
   only monotonic reasoning (R4)
•  
   3.2.2 Probabilistic reasoning
•  
  semantics
•  
   (EQ 5)
•  
  subjective probability
•  
   (EQ 6)
•  
   (EQ 7)
•  
   Evaluation
•  
   limited support for contradiction (R3): error mode...
•  
   no representation of ignorance (R5)
•  
   computational intractable for DBRE (R6)
•  
  3.2.3 Credibilistic reasoning
•  
  Definition 3.6 Basic probability assignment, focal...
•  
  Let U denote the set of all relevant propositions ...
•  
   (EQ 8)
•  
   difference to probabilistic logic
•  
  Definition 3.7 Combination of evidences
•  
  For a proposition uŒU and a set of pieces of evide...
•  
   (EQ 9)
•  
   The combination of n+1 pieces of evidences is recu...
•  
  Definition 3.8 Belief function
•  
  Let m:UÆ[0,1] be the mass function that is obtaine...
•  
   (EQ 10)
•  
   semantics of belief and plausibility
•  
  Definition 3.9 Plausibility function
•  
  Let m:UÆ[0,1] be the mass function that is obtaine...
•  
   (EQ 11)
•  
   pl(u)=bel()-bel(Øu)=1-m()-bel(Øu) (EQ 12)
•  
   Evaluation
•  
   limited support for non-monotonic reasoning (R4)
•  
  computational intractable (R6)
•  
   3.2.4 Fuzzy reasoning
•  
  fuzzy sets
•  
   mS: UÆ{0,1}, with . (EQ 13)
•  
  Definition 3.10 Fuzzy set
•  
  A set of pairs F:={(u,m(u)) | uŒU} is called fuzzy...
•  
   Figure 3.2. Sample fuzzy sets with continous and d...
•  
   a-cut
•  
  operations on fuzzy sets
•  
   Definition 3.11 t-norm and t-conorm
•  
  t-norm/t-conorm
•  
  Two binary functions T,^:[0,1]¥[0,1]Æ[0,1] are cal...
•  
   Union, A»B := {(x, max(mA(x), mB(x))) | xŒU} (EQ 1...
•  
   Intersection, A«B := {(x, min(mA(x), mB(x))) | xŒU...
•  
   Equality, A=B := ("xŒU) (mA(x)=mB(x)) (EQ 16)
•  
   Complement, ØA := {(x, 1-mA(x)) | xŒU} (EQ 17)
•  
  fuzzy rules and inference
•  
   Example 3.1 Fuzzy rule
•  
   Figure 3.3. Sample fuzzy sets for fuzzy predicates...
•  
  fuzzy relations
•  
  Definition 3.12 Fuzzy relation
•  
   Let F1,..,Fn be n fuzzy sets over objects of the u...
•  
   AÆB := {((a,b),min(mA(a),mB(b)))|aŒUA, bŒUB} (EQ 1...
•  
  Definition 3.13 Fuzzy logical operators
•  
   Conjunction, AŸB := {(x, min(mA(x), mB(x))) | xŒU}...
•  
   Disjunction, A⁄B := {(x, max(mA(x), mB(x))) | xŒU}...
•  
  MAX-MIN composition
•  
   (R1·R2)(A,C)={((a,c),max{min(mR1(a,b),mR2(b,c)) | ...
•  
   Definition 3.14 Fuzzy inference
•  
   3.2.4.1 Evaluation
•  
   limited support for uncertainty (R1)
•  
  limited support for contradiction and ignorance (R...
•  
   3.2.5 Possibilistic reasoning
•  
  possibility and necessity
•  
   P()=0; P()=1; N()=0; N()=1; (EQ 20)
•  
   N(f1Ÿf2)=min(N(f1),N(f2)); P(f1Ÿf2)=max(P(f1),P(f2...
•  
   N(f1⁄f2)³max(N(f1),N(f2)); P(f1Ÿf2)£min(P(f1),P(f2...
•  
   min(N(f),N(Øf))=0; max(P(f),P(Øf))=1 (EQ 23)
•  
  necessity-valued formulae
•  
   Definition 3.15 Necessity-valued formula
•  
   Definition 3.16 Classical projection
•  
   Definition 3.17 a-cut
•  
  semantics
•  
   P:L{L1}Æ[0,1], with P(f)=sup{p(w),wf}, wŒW. (EQ 24...
•  
   N:L{L1}Æ[0,1], with N(f)=inf{1-p(w),wØf}, wŒW. (EQ...
•  
   "p (pF) fi(pfn+1)) (EQ 26)
•  
  partial contradiction
•  
   N()=1 (EQ 27)
•  
   N(f1Ÿf2)=min(N(f1),N(f2)) (EQ 28)
•  
   N(f1⁄f2)³max(N(f1),N(f2)) (EQ 29)
•  
   (f1f2) fi N(f2)³N(f1) (EQ 30)
•  
  Definition 3.18 Partial contradicting set of formu...
•  
  A set of formulae F={f1,..,fn}ÕL{NPL1} is said to ...
•  
   Cons(F)=suppFsupwŒWp(w)<1 (EQ 31)
•  
   deduction problem
•  
   least specific poss. distribution
•  
  best model
•  
   Definition 3.19 Best model
•  
  inference
•  
  Definition 3.20 Formal system for NPL1
•  
   Axioms:
•  
   Inference rules:
•  
  3.2.5.1 Evaluation
•  
   f(f,b) iff f(f,b) and b>Incons(f). (EQ 32)
•  
   3.3 Summary and conclusion
•  
   Figure 3.4. Evaluation summary
•  
  CHAPTER 4 GFRN as a Basis for Legacy Schema Analys...
•  
   4.1 Supporting human-centered schema analysis proc...
•  
   customization process
•  
  analysis process
•  
   Figure 4.1. The proposed schema analysis process
•  
   user interaction
•  
  role of the GFRN
•  
  4.2 Specification of database reengineering knowle...
•  
   Basic definitions
•  
  Definition 4.1 Signature of an analyzed logical sc...
•  
   An (analyzed) logical schema for a relational DB i...
•  
   4.2.1 Informal introduction to GFRNs
•  
   Figure 4.2. Simple GFRN
•  
  constraints and negation
•  
   Figure 4.3. Implication with constraint and negati...
•  
  conjunction
•  
   Figure 4.4. Implication with conjunction
•  
  thresholds
•  
   Figure 4.5. Similarity measures for the seven samp...
•  
   Figure 4.6. Implication with threshold
•  
  premise with inner universal quantifier
•  
   Figure 4.7. Premise with universal quantifier
•  
   variable aggregation and composition
•  
   Figure 4.8. Variable aggregation and composition
•  
   Figure 4.9. Combination of heuristics in a single ...
•  
   4.2.2 Integration of automatic analysis operations...
•  
   existing operations
•  
   data- and goal-driven operations
•  
   Figure 4.10. Characteristics for classifying autom...
•  
  different types of predicates
•  
   Figure 4.11. GFRN with data- and goal-driven predi...
•  
   Figure 4.12. Goal-driven analysis operation valida...
•  
   Figure 4.13. N(validIND2(i,v)) for the case of no ...
•  
   4.2.3 Formal definition
•  
  4.2.3.1 Syntax of GFRN
•  
  Definition 4.2 Signature of a GFRN
•  
   A generic fuzzy reasoning net is defined by a 9-tu...
•  
  Definition 4.3 Context sensitive syntax
•  
   A GFRN ((Pd,Pg,Pt),Fr,Fb,I,E,cf,th,W,w) is called ...
•  
   Example 4.1 Syntax of a GFRN
•  
   Figure 4.14. GFRN to illustrate the formalization
•  
  4.2.3.2 Declarative semantics
•  
   Definition 4.4 Declarative semantics of GFRNs
•  
   1) input G:(P, Fr, Fb, I, E, cf, th, W, w) ŒL{GFRN...
•  
   2) output F ŒL{NPL1}
•  
   3) local variables F ŒL{NPL1}, i ŒI
•  
   4) begin
•  
   5) let F = „“
•  
   6) for each i ŒI do
•  
   7) let F= F „Ÿ“ Impl2NPL1(G, i)
•  
   8) od
•  
   9) return F
•  
  10) end
•  
   Figure 4.15. Translation algorithm GFRN2NPL1
•  
   algorithm explanation
•  
   11) input G:=(P, Fr, Fb, I, E, cf, th, W, w) ŒL{GF...
•  
   12) output F ŒL{NPL1}
•  
   13) local variables F1,F2,F3,F4,F5 ŒString; e ŒE; ...
•  
   14) begin
•  
   15) let F1 = F2 = F5 = „“
•  
   16) let F3 =F4 =„“
•  
   18) // create „inner“ univ. quantifier (IQ)
•  
   19) if $(c,l, s, premise_quantified, vi)ŒE
•  
   20) then let F2 = F2 „"“ vi
•  
   21) let V=V\vi
•  
   22) fi
•  
   24) // create „outer“ univ. quantifiers for all re...
•  
   25) for each v ŒV do
•  
   26) let F1 = F1 „"“ v
•  
   27) od
•  
   29) // create constraints
•  
   30) for each (w,fu, <w1,..,wu>) ŒK do
•  
   31) if w=e then
•  
   32) let F3= F3 „Ÿ“ fu„(“w1,..,wu „)“
•  
   33) else
•  
   34) let F3 = F3 „Ÿ“ w „=“ fu„(“w1,..,wu „)“
•  
   35) fi
•  
   36) od
•  
   38) // create predicates in premise
•  
   39) for each ((pm,i),s,t,A)ŒE with t=’premise’ or ...
•  
   40) let F4 = F4 „Ÿ“ s pm „(“ A „)“
•  
   41) od
•  
   43) // create predicate in conclusion
•  
   44) let ((pm,i),s,conclusion, A)ŒE
•  
   45) let F5 = s pm „(“ A „)“
•  
   47) let F = „(“ F1 „(“ F2 „(“ F3 „Æ“F4 „ŸN( “F4 „)...
•  
   48) return F
•  
  49) end
•  
   Figure 4.16. Translation algorithm Impl2NPL1
•  
   Example 4.2 Translation of GFRN to NPL1
•  
  semantics of analysis operations
•  
   Definition 4.5 Extent of a predicate
•  
   Definition 4.6 Data-driven analysis operation
•  
   Definition 4.7 Goal-driven analysis operation
•  
   Definition 4.8 Application context
•  
  Definition 4.9 Expansion of formulae over a finite...
•  
   Let FÃL{NPL1} be a set of closed formulae where al...
•  
   FflU={(gi,b)| ($g1,..,gnŒL{NPL0})(f ºg1Ÿ,..,Ÿgn in ...
•  
   Definition 4.10 Occurrence of literals
•  
   Definition 4.11 Semantics of automatic analysis op...
•  
   algorithm explanation
•  
   1) input G:=((Pd,Pg,Pt),Fr,Fb,I,E,cf,th,W,w) ŒL{GF...
•  
   2) output F ÃL{L0}
•  
   3) local variables F ÃL{NPL1}, exec[pŒPg,uŒU(B)]:B...
•  
   4) begin
•  
   5) let F = GFRN2NPL1(G)
•  
   6) // execute data-driven analysis operations
•  
   7) for each pŒPd do
•  
   8) let F =F »W(p)(B)
•  
   9) end
•  
   11) loop
•  
   12) let F=FflU(B)
•  
   13) if ($(f1Æi f2,b)ŒF) ($pŒPg) ($uŒU(B)) ($gŒ[th(...
•  
   14) (occ(f1,p(u)))ŸF(f2,g)) // p(u) in the anteced...
•  
   15) then
•  
   16) if exec[p,u]=FALSE
•  
   17) then
•  
   18) // execute goal-driven analysis operations
•  
   19) let F =F »w(p)(B,p(u))
•  
   20) let exec[p,u]=TRUE
•  
   21) fi
•  
   22) fi
•  
   23) if exists user input jÃL{NPL0}
•  
   24) then
•  
   25) let F =F »j
•  
   26) fi
•  
   27) until a definite analysis results is obtained,...
•  
   28) Ø($pŒPt)($uŒU(B))
•  
   29) ((F(p(u),g)ŸgŒ(0,1)ŸF(Øp(u),g)Ÿg¹1)⁄(F(p(u),g)...
•  
   30) return {f | (f,1)ŒF Ÿ fŒL{L0}}
•  
  31) end
•  
   Figure 4.17. Algorithm OperateGFRN
•  
  Example 4.3 Semantics of automatic analysis operat...
•  
   Fs={ ...
•  
   (ANameIsRSName+ID1(usrid),0.8), (EQ 34)
•  
   ({sname}Õ{sname,dpt} ÆselectDist1({sname,dpt})) Æ1...
•  
   ({sname,dpt}Õ{sname,dpt} ÆselectDist1({sname,dpt})...
•  
   (ANameIsRSName+ID1(usrid)ŸN(ANameIsRSName+ID1(usri...
•  
   (ØvalidKey1(usrid)ŸN(ØvalidKey1(usrid)) ³ 0.2) Æ3 ...
•  
   (ØvalidKey1(sname)ŸN(ØvalidKey1(sname)) ³ 0.2) Æ3 ...
•  
   usrid
•  
   name
•  
   dpt
•  
   sname
•  
   addr
•  
   telo
•  
   telp
•  
   3
•  
   John Best
•  
   MRD
•  
   bes01
•  
   MLab 340
•  
   6020
•  
   NULL
•  
   10
•  
   Manfred Schmitz
•  
   PCD
•  
   sch02
•  
   OfficeW 450
•  
   3530
•  
   58787
•  
   8
•  
   Heinrich Muller
•  
   CRD
•  
   mul08
•  
   ChemB A350
•  
   8331
•  
  52718
•  
   Figure 4.18. Excerpt of case study
•  
   Figure 4.19. Necessity degrees for the facts produ...
•  
   Figure 4.20. Necessity degrees for the facts produ...
•  
   4.3 Knowledge inference with GFRN specifications
•  
   forwards and backwards reasoning
•  
  incremental reasoning
•  
   4.3.1 A fuzzy Petri net model for non-monotonic re...
•  
  Definition 4.12 Fuzzy Petri net
•  
   A fuzzy Petri net (FPN) is a tuple FPN:=(S, T, F; ...
•  
   belief revision
•  
   (EQ 40)
•  
   (EQ 41)
•  
  Figure 4.21. Belief revision phase 1: computation ...
•  
   (EQ 42)
•  
   Figure 4.22. Belief revision phase 2: Computation ...
•  
  termination and stability of belief revision
•  
   Definition 4.13 Stability
•  
   Theorem 4.1 Equilibrium time
•  
   Definition 4.14 Predecessor
•  
   Definition 4.15 Axiom
•  
   Definition 4.16 Axiom-based marking
•  
  Theorem 4.2 Stability of FPN with axiom-based mark...
•  
   An FPN N:(S,T,F;D,b,v,c,t,m0) with an axiom-based ...
•  
  Proof: If N is not stable there has to be at least...
•  
   ("xŒ[xlc,•))(mx(s)=mx+p(s)Ÿmx(s)¹mx+r(s)) (EQ 43)
•  
  with a period pŒ[2,•) and rŒ[1,p-1]. In the follow...
•  
   ("xŒ[0,•])("sŒS)(mx+1(s)³mx(s)) (EQ 44)
•  
  which can easily be proved: EQ44 is trivially fulf...
•  
   ("sŒS)(m1(s)³m0(s)). (EQ 45)
•  
  From EQ40-EQ42 follows that for any non-axiom plac...
•  
   ("zŒpre(s))(mx+1(z)³mx(z))fimx+2(s)³mx+1(s) (EQ 46)...
•  
   Corollary 4.1
•  
   4.3.2 The inference process
•  
   4.3.2.1 Informal introduction
•  
  data-driven analysis
•  
   Figure 4.23. The proposed iterative and interactiv...
•  
  expansion
•  
   Figure 4.24. Representation of an expanded GFRN im...
•  
   goal-driven analysis
•  
   evaluation
•  
   grounding
•  
  automatic expansion and evaluation cycles
•  
   Figure 4.25. Forward and backward expansion (sampl...
•  
  user dialog
•  
   Example 4.4 Inference process
•  
   Figure 4.26. Information sources for inference exa...
•  
   first expansion/ evaluation cycle
•  
   Figure 4.27. GFRN to exemplify the inference proce...
•  
   Figure 4.28. FPN after the first expansion/evaluat...
•  
  second expansion/ evaluation cycle
•  
   Figure 4.29. FPN after second expansion/evaluation...
•  
   third expansion/ evaluation cycle
•  
  human interaction
•  
   Figure 4.30. FPN after third expansion/evaluation ...
•  
   Figure 4.31. Additional implications to specify ne...
•  
   Figure 4.32. FPN after considering human input
•  
   Figure 4.33. Final analsysis result
•  
  representing human assumptions
•  
   Figure 4.34. Representation of human assumptions
•  
   4.3.2.2 Formal definition
•  
   1) algorithm GFRNInference(G, B)
•  
   2) input G:=((Pd,Pg,Pt),Fr,Fb,I,E,cf,th,W,w)ŒL{GFR...
•  
   3) output R ÃL{L0}
•  
   4) local variables N:(S,T,F;D,b,v,c,t,mx)ŒL{FPN} /...
•  
   5) N:(S,T,F;D,b,v,c,t,mx)ŒL{FPN} // result of the ...
•  
   6) XÕS // places that are going to be axioms
•  
   7) begin
•  
   8) let N:(S,T,F;D,b,v,c,t,mx)=CreateEmptyFPN()
•  
   10) for each pŒPd do // data-driven analysis
•  
   11) for each qŒ{(w,b)ŒW(p)(B)| ($(c,(p,i),s,d,A)ŒE...
•  
   12) let (N,X)=CreatePlace(q, N, X, TRUE)
•  
   13) od
•  
   14) od
•  
   16) loop
•  
   17) loop
•  
   18) let Dchanged={d|dŒDŸ(dœD⁄mx(b-1(d))¹mx(b-1(d))...
•  
   19) if Dchanged¹Æ
•  
   20) then
•  
   21) let N=N // store old FPN state
•  
   22) let N:(S,T,F;D,b,v,c,t,mx)=ExpandFPN(G,N,Dchan...
•  
   23)
•  
   24) for each zŒ{sŒS|b(s)=p(u)Ÿp(u)ŒD-DŸpŒPg} do
•  
   25) let N=CreatePlace((w(p)(B,p(u)) ,N, TRUE) // g...
•  
   26) od
•  
   28) let N=ResetMarkings(N) // create axiom-based m...
•  
   29) let N=EvaluateFPN(N) // evaluation
•  
   31) for each sŒ{zŒS| grounded(z)} do // grounding
•  
   32) let (a,b)=mx(s)
•  
   33) if mx(s,‘‘)=1 then mx(s,Ø)=0
•  
   34) else mx(s,‘‘)=0
•  
   35) fi
•  
   36) let X=X»{s}
•  
   37) od
•  
   39) let N=RemoveIncomingArcs(N, X) // satisfy stru...
•  
   40) fi
•  
   41) until Dchanged=Æ // FPN unchanged
•  
   43) for each (w,b)ŒUserDialog(D,G) do // user dial...
•  
   44) CreateOrReviseAxiom((w,b) , N, G)
•  
   45) od
•  
   46)
•  
   47) until ("p(u)ŒD)(pŒPtÆp(u)ŒX⁄mx(b-1(p(u)),’’)=0...
•  
   48) // positive results is definite and consistent...
•  
   49) return {p(u)ŒX| pŒPtŸmx(b-1(p(u)),’’)=1}
•  
  50) end
•  
   Figure 4.35. Algorithm GFRNInference
•  
   data-driven analysis
•  
   outer (interactive) inference loop
•  
  inner (automatic) inference loop
•  
   Definition 4.17 Grounded place
•  
   Expansion process
•  
   algorithm CreatePlace
•  
  algorithm ExpandFPN
•  
   1) input dŒL{NPL0}, N:(S,T,F;D,X,b,v,c,t,mx)ŒL{FPN...
•  
   2) input G:(P, Fr, Fb, I, E, cf, th, W, w) ŒL{GFRN...
•  
   3) output (N,X)
•  
   4) local variables sŒ // place identifier
•  
   5) begin
•  
   6) let s=createID()
•  
   7) let S=S»{s}
•  
   9) if ax=TRUE then let X=X»{s} fi
•  
   11) if d=(Øp(u), b)
•  
   12) then let mx(s)=(0,b)
•  
   13) else let mx(s)=(b,0) /* d=(p(u), b) */
•  
   14) fi
•  
   15) let D=D»{p(u)}
•  
   16) let b(s)=p(u)
•  
   17) return (N,X)
•  
  18) end
•  
   Figure 4.36. Algorithm CreatePlace
•  
   expansion of transitions
•  
   1) input G:(P, Fr, Fb, I, E, cf, th, W, w) ŒL{GFRN...
•  
   2) input N:(S,T,F;D,b,v,c,t,mx)ŒL{FPN}; DchangedÕD...
•  
   3) output N:(S,T,F;D,X,b,v,c,t,mx)ŒL{FPN}; XÕS
•  
   4) local variables bindingsetŒREL; gŒU(B); Da+,Da-...
•  
   5) begin
•  
   6) for each iŒ{i:(i,V,K)ŒI|uŒU(B)Ÿp(u)ŒDchangedŸ(c...
•  
   7) remove all transitions from N that have been cr...
•  
   8) od
•  
   10) for each iŒ{i:(i,V,K)ŒI|uŒU(B)Ÿp(u)ŒDchangedŸ(...
•  
   11) let bindingset=ComputeBindingsForImpl(G,i,N)
•  
   12) for each gŒbindingset do
•  
   13) let Da+={p(u1,..,ux)|(c,(p,i),’’,premise*,<a1,...
•  
   14) let Da-={p(u1,..,ux)|(c,(p,i),Ø,premise*,<a1,....
•  
   15) let Dc+={p(u1,..,ux)|(c,(p,i),’’,conclusion,<a...
•  
   16) let Dc-={p(u1,..,ux)|(c,(p,i),Ø,conclusion,<a1...
•  
   18) if Da+»Da-ÕD /* forward expansion: if premise ...
•  
   19) ⁄ Dc+»D¹Æ /* or backward expansion: if hypothe...
•  
   20) then
•  
   21) for each dŒ(Da+»Da-»Dc+»Dc-)-D do
•  
   22) let (N,X)=CreatePlace((d,0),N,X,G,FALSE)
•  
   23) od
•  
   24) if ExistsMT(N, i, Da+, Da-, Dc+, Dc-)=FALSE
•  
   25) then
•  
   26) let N=CreateTransition(N, i, Da+, Da-, Dc+, Dc...
•  
   27) for each dŒda+ do
•  
   28) let N=CreateTransition(N, i, (Da+\d)»Dc-, Da-»...
•  
   29) for each dŒda- do
•  
   30) let N=CreateTransition(N, i, Da+»Dc-, (Da-\d)»...
•  
   31) // create CTs
•  
   32) fi
•  
   33) fi
•  
   34) od
•  
   35) od
•  
   36) return (N,X)
•  
  37) end
•  
   Figure 4.37. Algorithm ExpandFPN
•  
  Definition 4.18 Derivability
•  
   $(v1,f,W)ŒK WÕ{v2,..,vn}
•  
   ⁄ $(vx,f,v1)ŒK vxŒ{v2,..,vn}Ÿ$f-1ŒFUN Ÿ "x defn...
•  
   ⁄ $(e,Œ,v1,vx)ŒK ⁄ $(e,Œ,vx,v1)ŒK.
•  
   We define the notion of derivability based on the ...
•  
   Definition 4.19 Derivation sink
•  
   algorithm ComputeBindings- ForImpl
•  
   dealing with IQs
•  
   1) input G:(P,Fr,Fb,I,E,cf,th,W,w) ŒL{GFRN}; iŒI; ...
•  
   2) output bindingsetŒREL
•  
   3) local variables bindingset, bindingset’ŒREL, gŒ...
•  
   4) begin
•  
   5) let bindingset=Æ
•  
   6) for each {(c,(p,i),s,d,<a>)ŒE| Øsink(a)ŸØs=prem...
•  
   7) // for each variable that does not represent a ...
•  
   8) let bindingset’=Æ
•  
   9) for each {p(u)ŒD| mx(p(u),s)³th(i)} do
•  
   10) if bindingset=Æ
•  
   11) then
•  
   12) let g[a]={u}
•  
   13) if ConstraintsHold(g,K) then let bindingset=bi...
•  
   14) else
•  
   15) for each gŒbindingset do
•  
   16) let g[a]={u}
•  
   17) if ConstraintsHold(g,K) then let bindingset’=b...
•  
   18) od
•  
   19) fi
•  
   20) od
•  
   21) let bindingset=bindingset»bindingset’
•  
   22) od
•  
   23) if $(c,(p,i),s,premise_quantified,a)ŒE
•  
   24) then
•  
   25) for each {p(u)ŒD| mx(p(u),s)³th(i)} do
•  
   26) let bindingset’=Æ
•  
   27) for each gŒbindingset do
•  
   28) let g[a]=g[a]»{u}
•  
   29) if ConstraintsHold(g,K) then let bindingset’=b...
•  
   30) od
•  
   31) let bindingset=bindingset»bindingset’
•  
   32) od
•  
   33) fi
•  
   35) let bindingset=ComplementBindings(bindingset,i...
•  
   36) if $(c,(p,i),s,premise_quantified,a)ŒE // sele...
•  
   37) then let bindingset=bindingset-{gŒbindingset| ...
•  
   38) (g’¹gŸg[a]Ãg’[a]Ÿg[V\a]=g[V\a])}
•  
   39) fi
•  
   40) return bindingset
•  
  41) end
•  
   Figure 4.38. Algorithm ComputeBindingsForImpl
•  
  algorithm Complement- Bindings
•  
   1) input G:=(P, Fr, Fb, I, E, cf, th, W, w) ŒL{GFR...
•  
   2) output bindingsetŒREL
•  
   3) local variables bindingset‘ŒREL; gŒU(B)
•  
   4) begin
•  
   5) let bindingset‘=bindingset
•  
   6) for each (e, Œ,<w1,w2>)ŒK do
•  
   7) for each gŒbindingset do
•  
   8) for each uŒg[w2] do
•  
   9) let g[w1]=u
•  
   10) if ConstraintsHold(g,K) then let bindingset‘=b...
•  
   11) od
•  
   12) let g[w2]={g[w1]}
•  
   13) if ConstraintsHold(g,K) then let bindingset‘=b...
•  
   14) od
•  
   15) od
•  
   17) let bindingset=bindingset‘
•  
   18) for each gŒbindingset do
•  
   19) let Vbound={vŒV|g(v)¹Æ}
•  
   20) if "vŒV-Vbound $v2,..,vnŒVbound v –K* v2,..,vn...
•  
   21) then
•  
   22) derive bindings of all vŒV-Vbound from g
•  
   23) else
•  
   24) let bindingset=bindingset-{g}
•  
   25) fi
•  
   26) od
•  
   27) return bindingset
•  
  28) end
•  
   Figure 4.39. Algorithm ComplementBindings
•  
   4.3.2.3 Complexity and scalability
•  
   Worst-case complexity of the proposed algorithms
•  
   Complement- Bindings
•  
   ComputeBindings ForImpl
•  
  ExpandFPN and GFRNInference
•  
   Figure 4.40. Example GFRN for termination problem
•  
   Discussion of analysis results
•  
  4.4 Implementing the Varlet Analyst
•  
   4.4.1 Architecture
•  
   Figure 4.41. Architecture of the Varlet Analyst
•  
   4.4.2 User interface
•  
   4.4.2.1 The Customization Front-End
•  
   description of sample GFRN
•  
   multiple views to handle complexity
•  
   Figure 4.42. Customization Front-End
•  
   consistency check implementation of analysis opera...
•  
   Figure 4.43. Customization Front-End (2)
•  
   4.4.2.2 The Analysis Front-End
•  
  detailed representation
•  
   Figure 4.44. Analysis Front-End (overview)
•  
   Figure 4.45. Analysis Front-End (detail view)
•  
   visualizing imperfect information
•  
   indicating imperfect information
•  
   automatic inference
•  
   Figure 4.46. Graphical and textual documentation o...
•  
   4.5 Evaluation
•  
   first prototype
•  
   second prototype
•  
   case study
•  
   domain analysis
•  
   user guidance
•  
   concurrent inference
•  
  experiences with the current tool
•  
   4.6 Related work
•  
   Blaha and Premerlani
•  
   Petit et al. Andersson
•  
   Signore et al.
•  
   Hainaut et al.
•  
   Hodges and Ramanathan Vossen and Fahrner
•  
   Soutou Blockeel and De Raedt
•  
   DBInformer, ERwin, SeeData
•  
  Sousa
•  
   4.7 Summary
•  
  CHAPTER 5 Conceptual Schema Migration and Data Int...
•  
   schema migration
•  
   problem of iterations
•  
   problem of data integration
•  
   approach: tight integration
•  
   Figure 5.1. Incremental schema migration and gener...
•  
   5.1 The migration graph model
•  
  graph
•  
  Definition 5.1 Graph
•  
   G := (N, E, yN, A) is a graph over two given type ...
•  
   Moreover, we define the following auxiliary functi...
•  
   graph model in Progres
•  
  migration graph model
•  
   5.1.1 Graph-based representation of logical and co...
•  
   logical schema
•  
   rational for selecting the conceptual schema
•  
   Figure 5.2 Migration graph model
•  
   conceptual schema
•  
   graph constraints graph tests
•  
   Figure 5.3. Graph test DuplicateClassName
•  
   5.1.2 The schema mapping graph model
•  
   mapping types and classes
•  
   mapping inheritance relationships
•  
   Figure 5.4. Sample situation: correspondence among...
•  
   mapping keys
•  
   mapping attributes and relationships
•  
   5.2 A graphical formalism to implement schema tran...
•  
   graph grammars
•  
  graph production
•  
  Definition 5.2 Graph production
•  
   A graph production is a tuple r:(P, Q, C, T), wher...
•  
  Definition 5.3 Application of a production
•  
   A production r:(P,Q,C,T) is applied to graph G in ...
•  
   Figure 5.5. Graph production AddRSToLSchema
•  
   5.2.1 Triple graph grammars
•  
   Figure 5.6. Mapping rule MapRSToClass
•  
   generation of reverse and forward translators
•  
   attribute transfer clauses
•  
   Figure 5.7. Reverse production MapRSToClassrv
•  
   application conditions
•  
   Figure 5.8. Forward production MapRSToClassfw
•  
   start graph
•  
   Figure 5.9. Startgraph for schema migration
•  
  translation algorithm
•  
   algorithm MapSchema(R, S)
•  
   1) input R, a set of forward and reverse productio...
•  
   2) input S, a start graph (according to Figure5.9...
•  
   3) output G, a migration graph (according to Figur...
•  
   4) begin
•  
   5) let G=S
•  
   6) repeat
•  
   7) let r:(P,Q,C,T)ŒR be a production that fulfills...
•  
   8) - P has a match in G represented by a morphism ...
•  
   9) - this match cannot be extended in G by a match...
•  
   10) let G = GØ(r,m)
•  
   11) until no production pŒP fulfills the condition...
•  
   12) return G
•  
  13) end
•  
   Figure 5.10. Algorithm MapSchema
•  
   5.2.2 Mapping variants to class hierarchies
•  
  MapVariantTo- ConcreteClass
•  
   Figure 5.11. Mapping rule MapVariantToConcreteClas...
•  
  Example 5.1 Application of rules MapRSToClass and ...
•  
   Figure 5.12. Example RS Tenant with two variants a...
•  
   Figure 5.13. Example application of rules MapRSToC...
•  
  MapVariantsTo- AbstractClassrv
•  
   Figure 5.14. Production MapVariantsToAbstractClass...
•  
  Example 5.2 Application of production MapVariantsT...
•  
   Figure 5.15. Example application of production Map...
•  
   MapVariantsTo- Inheritancerv
•  
   Figure 5.16. Production MapVariantsToInheritancerv...
•  
   Example 5.3 Application of production MapVariantsT...
•  
   Figure 5.17. Example application of production Map...
•  
   5.2.3 Mapping columns to class attributes
•  
  key columns
•  
   Figure 5.18. Mapping rule MapColToAttr
•  
   5.2.4 Mapping inclusion dependencies to relationsh...
•  
   MapRINDToAssoc [1:1]
•  
   Figure 5.19. Mapping rule MapRINDToAssoc[1:1]
•  
   MapRINDToAssoc [N:0,1]
•  
   MapRINDToAssoc [0,N:0,1]
•  
   MapIINDTo Inheritance
•  
   Figure 5.20. Mapping rule MapRINDToAssoc[N:0,1]
•  
   Figure 5.21. Mapping rule MapRINDToAssoc[0,N:0,1]
•  
  5.2.5 Discussion
•  
   Figure 5.22. Mapping rule MapIINDToInheritance
•  
  5.3 Conceptual schema redesign
•  
   5.3.1 Schema redesign transformations
•  
  insufficiency of predefined transformations
•  
   5.3.2 An extensible catalog of schema redesign tra...
•  
   SplitClass
•  
   Figure 5.23. Catalog of conceptual redesign transf...
•  
   Figure 5.24. Schema transformation SplitClass
•  
   MoveAttribute
•  
   Figure 5.25. Schema transformation MoveAttribute
•  
  Generalize
•  
   Figure 5.26. Schema transformation Generalize
•  
  PushUpAttr
•  
   Figure 5.27. Schema transformation PushUpAttribute...
•  
   5.3.3 Complex schema redesign transformations
•  
   Figure 5.28. Complex transformation MoveOverAggreg...
•  
   5.4 Incremental change propagation
•  
   5.4.1 The history graph
•  
  history graph
•  
   Figure 5.29. Basic structure of a history graph
•  
   transformation templates
•  
  dependencies among edges
•  
   Figure 5.30. Template of transformation Generalize...
•  
   restriction: path expressions
•  
  transitive closure in path expressions
•  
  Definition 5.4 1-context of a set of nodes
•  
   The 1-context of a set of nodes S in a graph G is ...
•  
  Definition 5.5 Context of a transformation applica...
•  
   The context of an application of a transformation ...
•  
   negative conditions
•  
   history graph model
•  
   Figure 5.31. History graph model
•  
  Definition 5.6 History graph
•  
   The history graph is a graph that includes the mig...
•  
   5.4.2 The propagation mechanism
•  
  application of transformations to the history grap...
•  
  Definition 5.7 Application of transformations to a...
•  
   A transformation that is represented by a producti...
•  
   change propagation
•  
   Phase I: forward propagation
•  
   Figure 5.32. Phase I: forward propagation
•  
   Phase II: backward propagation
•  
   Phase III: reevaluation
•  
   Figure 5.33. Phase II: backward propagation
•  
   Figure 5.34. Phase III: reevaluation
•  
   Phase IV: translation
•  
   Figure 5.35. Phase IV: translation
•  
   realization in Progres
•  
   Figure 5.36. Transaction PropagateChange
•  
  adaption of productions
•  
   Figure 5.37. Graph test Generalize_getParams
•  
   Figure 5.38. Production Generalize_withParams
•  
   scalability
•  
  5.5 Implementing the Varlet Migrator
•  
  5.5.1 Architecture
•  
   Figure 5.39. Architecture of the Varlet Migrator
•  
   Figure 5.40. Using the Progres environment to exte...
•  
   command extraction
•  
  textual unparsers
•  
   5.5.2 User interface
•  
   initial translation
•  
   Figure 5.41. Logical schema after first analysis s...
•  
  conceptual redesign
•  
   Figure 5.42. Redesigned conceptual schema (Migrati...
•  
   iteration
•  
   Figure 5.43. Completed logical schema (top) and up...
•  
   change propagation
•  
   implementation of extensions
•  
   Figure 5.44. Implementation of conceptual extensio...
•  
   5.6 Data integration
•  
  ObjectDRIVER
•  
   Figure 5.45. ObjectDRIVER overview
•  
  Integration of ObjectDRIVER and Varlet
•  
   Figure 5.46. Integration of the ObjectDRIVER middl...
•  
   5.6.1 Generating descriptions for relational and o...
•  
   Figure 5.47. Relational schema description for Obj...
•  
   5.6.2 Generating object-relational mapping descrip...
•  
   Figure 5.48. Object schema description for ObjectD...
•  
   classes and subclasses
•  
   Figure 5.49. Mapping description for classes and s...
•  
   Figure 5.50. Test getClassInstantiationConstraint
•  
  base table attributes
•  
   Figure 5.51. Mapping description for base table at...
•  
   Figure 5.52. Test getAttrMappedToColInBaseTable
•  
   remote attributes
•  
   Figure 5.53. Mapping description for remote attrib...
•  
   Figure 5.54. Test getAttrMappedToColInRemoteTable
•  
  base table relationships
•  
   Figure 5.55. Mapping description for base table re...
•  
   Figure 5.56. Test getRelMappedToBaseTable
•  
   remote relationships
•  
   Figure 5.57. Mapping description for remote relati...
•  
   Figure 5.58. Test getRelMappedToRemoteTable
•  
   IND-based inheritance
•  
   Figure 5.59. Mapping description for IND-based inh...
•  
   Figure 5.60. Test getInheritMappedToI_IND
•  
   object-oriented application code
•  
   Figure 5.61. Mapping Description for ObjectDRIVER
•  
   Figure 5.62. MIS application code (example)
•  
   5.7 Evaluation
•  
   experiences with triple graph grammars
•  
   case study
•  
   middleware generation
•  
  5.8 Related work
•  
   5.8.1 Conceptual schema migration and consistency ...
•  
   Vossen and Fahrner Behm et al.
•  
   Jeusfeld and Johnen
•  
   Hainaut et al.
•  
   problem of consistency
•  
   problem of idiosyncrasies
•  
  problem of variant structures
•  
   5.8.2 Data integration
•  
   Behm et al. Fong
•  
   Hainaut et al.
•  
  COTS middleware Web-gateways
•  
   5.9 Summary
•  
  CHAPTER 6 Conclusions and Future Perspectives
•  
   6.1 Major contributions
•  
   selection of a theory to manage uncertainty
•  
   GFRN as a basis for LDB analysis
•  
   implementation and evaluation
•  
   flexible schema translation
•  
   incremental consistency preservation
•  
  heterogeneous data integration
•  
   6.2 Transferability of results
•  
   schema analysis
•  
   conceptual migration
•  
   6.3 Open problems
•  
   selection of CVs
•  
   top-down migration
•  
   loss of layout information during change propagati...
•  
   6.4 Future perspectives
•  
   generalizing GFRNs
•  
   self-adaptation
•  
   Figure 6.1. Self-adapting analysis process
•  
   LDB federation and evolution
•  
   abstract losslessness criterion
•  
   user experiments
•  
  APPENDIX A Additional Definitions and Specificatio...
•  
  A.1 Interpretation of a logical schema
•  
  Definition A.1 Interpretation of a logical schema
•  
   The interpretation of a logical schema (T, R, D, A...
•  
   A.2 Specification of the migration graph model
•  
   logical schema ASG
•  
   conceptual schema ASG
•  
   SMG model
•  
   history graph model
•  
   graph tests to check for constraint violations
•  
   APPENDIX B A Catalog of Redesign Transformations
•  
  Aggregate
•  
   Figure B.1. Transformation Aggregate
•  
  AssociationToClass
•  
   Figure B.2. Transformation AssociationToClass
•  
  ChangeAssoc- Cardinality
•  
   Figure B.3. Transformation ChangeAssocCardinality
•  
  ChangeAttribute- Type
•  
   Figure B.4. Transformation ChangeAttributeType
•  
  ClassToAssociation
•  
   Figure B.5. Transformation ClassToAssociation
•  
  CreateAssociation
•  
   Figure B.6. Transformation CreateAssociation
•  
  CreateAttribute
•  
   Figure B.7. Transformation CreateAttribute
•  
  CreateClass
•  
   Figure B.8. Transformation CreateClass
•  
  CreateInheritance
•  
   Figure B.9. Transformation CreateInheritance
•  
  CreateKey
•  
   Figure B.10. Transformation CreateKey
•  
  ConvertAbstract
•  
   Figure B.11. Transformation ConvertAbstract
•  
  ConvertConcrete
•  
   Figure B.12. Transformation ConvertConcrete
•  
  DisAggregate
•  
   Figure B.13. Transformation DisAggregate
•  
  Generalize
•  
   Figure B.14. Transformation Generalize
•  
  MergeClass
•  
   Figure B.15. Transformation MergeClass
•  
  MoveAttribute
•  
   Figure B.16. Transformation MoveAttribute
•  
  PushDown- Attribute
•  
   Figure B.17. Transformation PushDownAttribute
•  
  PushDown- Association
•  
   Figure B.18. Transformation PushDownAssociation
•  
  PushUpAttribute
•  
   Figure B.19. Transformation PushUpAttribute
•  
  PushUp-Association
•  
   Figure B.20. Transformation PushUpAssociation
•  
  Remove
•  
   Figure B.21. Transformation Remove
•  
  RenameClass
•  
   Figure B.22. Transformation RenameClass
•  
  RenameAttribute
•  
   Figure B.23. Transformation RenameAttribute
•  
  Rename- Relationship
•  
   Figure B.24. Transformation RenameRelationship
•  
  SplitClass
•  
   Figure B.25. Transformation SplitClass
•  
  Specialize
•  
   Figure B.26. Transformation Specialize
•  
  SwapAssoc- Direction
•  
   Figure B.27. Transformation SwapAssocDirection
•  
   References
•  
  Index
•  
   Numerics
•  
   A
•  
   B
•  
   C
•  
   D
•  
   E
•  
   F
•  
   G
•  
   H
•  
   I
•  
   J
•  
   K
•  
   L
•  
   M
•  
   N
•  
   O
•  
   P
•  
   Q
•  
   R
•  
   S
•  
   T
•  
   U
•  
   V
•  
   Y
•  
   Abbreveations
•  
   A
•  
   B
•  
   C
•  
   D
•  
   E
•  
   F
•  
   G
•  
   I
•  
   J
•  
   K
•  
   L
•  
   M
•  
   N
•  
   O
•  
   P
•  
   R
•  
   S
•  
   T
•  
   U
•  
   W