de
en
Schliessen
Detailsuche
Bibliotheken
Projekt
Impressum
Datenschutz
Schliessen
Publizieren
Besondere Sammlungen
Digitalisierungsservice
Hilfe
Impressum
Datenschutz
zum Inhalt
Detailsuche
Schnellsuche:
OK
Ergebnisliste
Titel
Titel
Inhalt
Inhalt
Seite
Seite
Im Werk suchen
Management of uncertainty and inconsistency in database reengineering processes / Jens H. Jahnke. 1999
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
Die detaillierte Suchanfrage erfordert aktiviertes Javascript.