111111
`
`1111111111111111111111111111111111111111111111111111111111111
`US007739080Bl
`
`c12) United States Patent
`Becket al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,739,080 Bl
`Jun.15,2010
`
`(54) CONSOLIDATION OF PRODUCT DATA
`MODELS
`
`(75)
`
`Inventors: Brandon M. Beck, Austin, TX (US);
`Shawn A. P. Smith, Austin, TX (US)
`
`(73) Assignee: Versata Development Group, Inc.,
`Austin, TX (US)
`
`( *) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 28 days.
`
`(21) Appl. No.: 10/827,078
`
`(22)
`
`Filed:
`
`Apr. 19, 2004
`
`(51)
`
`(52)
`
`(58)
`
`(56)
`
`Int. Cl.
`(2006.01)
`G06F 7160
`(2006.01)
`G06F 19100
`(2006.01)
`G06F 9144
`(2006.01)
`G06N 5102
`U.S. Cl. ............................... 703/2; 700/95; 700/97;
`705/7; 706/47
`Field of Classification Search ................. 703/1-2;
`700/95, 97; 705/7; 706/47
`See application file for complete search history.
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`5,515,524 A *
`5,576,965 A *
`5,615,341 A *
`5,802,508 A *
`5,825,651 A *
`5,873,081 A *
`5,996,114 A *
`
`5/1996 Lynch eta!. .................. 703/13
`1111996 Akasaka eta!. ............... 700/97
`3/1997 Agrawal eta!. ............... 705/10
`9/1998 Morgenstern ................ 706/55
`10/1998 Gupta eta!.
`................ 700/103
`211999 Hare! ... ... .. ... ... ... ... ... .. ... 707/3
`1111999 Moeller ...................... 714/699
`
`6,002,854 A *
`6,009,406 A *
`6,178,502 B1 *
`6,216,109 B1 *
`6,241,775 B1 *
`6,300,948 B1 *
`6,405,308 B1 *
`
`12/1999 Lynch eta!. ................... 703/1
`12/1999 Nick ........................... 705/10
`112001 Caswell eta!. ................. 713/1
`4/2001 Zweben et al .................. 705/8
`6/2001 Blatchford .. ... ... .. ... ... ... 623/27
`10/2001 Geller et al ................. 715/866
`6/2002 Gupta eta!.
`................... 713/1
`(Continued)
`
`OTHER PUBLICATIONS
`Symbolic Model Checking an approach to the state explosion prob(cid:173)
`lem; Kenneth L McMillan; May 1992; Carnegie Mellon University.*
`(Continued)
`
`Primary Examiner-Kamini S Shah
`Assistant Examiner-Akash Saxena
`(74) Attorney, Agent, or Firm-Hamilton & Terrile, LLP;
`Kent B. Chambers
`
`(57)
`
`ABSTRACT
`
`A model consolidation process combines multiple configu(cid:173)
`ration models into a single unified configuration model that
`contains the union of the allowable combinations (i.e. com(cid:173)
`binations that are buildable) from each of the original models.
`An aspect of at least one embodiment ofthe model consoli(cid:173)
`dation process is that it allows models to be combined in such
`a way that any incompatibilities or contradictions between
`models are detected and automatically resolved where pos(cid:173)
`sible. If an incompatibility is detected that caunot be auto(cid:173)
`matically resolved, then the configuration models should not
`be combined. Instead if this incompatibility case occurs, at
`least one embodiment of the model consolidation process
`produces a description of the problem encountered and report
`the problem along with the necessary information required
`for a human to resolve it.
`
`22 Claims, 13 Drawing Sheets
`
`Directed Acyclic Graph (DAG)
`
`200 )
`
`Family C
`
`• • •
`
`Page 1 of 26
`
`FORD 1001
`
`

`
`US 7, 739,080 Bl
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`2008/0147584 A1 *
`
`6/2008 Buss ........................... 706/47
`
`6,584,369 B2 *
`6/2003
`6,807,576 B1 * 10/2004
`6,882,892 B2 *
`4/2005
`6,983,187 B2 *
`112006
`7,171,400 B2 *
`112007
`7,188,333 B1*
`3/2007
`7,480,597 B2 *
`112009
`7,574,379 B2 *
`8/2009
`7,584,079 B2 *
`9/2009
`2002/0013631 A1 *
`112002
`2002/0165701 A1 * 1112002
`2003/0069737 A1 *
`4/2003
`2004/0002838 A1 *
`112004
`2004/0030786 A1 *
`2/2004
`2004/0133457 A1 *
`7/2004
`2006/0106626 A1 *
`5/2006
`2006/0136904 A1 *
`6/2006
`2007/0074180 A1 *
`3/2007
`
`Patel eta!. .................. 700/100
`Jeffries et a!. ............... 709/225
`Farrah eta!. .................. 700/97
`Kern, Thomas .............. 700/97
`Koubenski et al. ............. 707/3
`LaMotta et a!. ............. 717/106
`Clark et al. .................... 703/2
`Flaxer eta!. .................. 705/26
`Lichtenberg et a!. ........... 703/2
`Parunak eta!. ................ 700/28
`Lichtenberg et a!. ........... 703/7
`Koubenski et al. ............. 705/1
`Oliver eta!. ................... 703/2
`Zehavi ....................... 709/229
`Sadiq et al. .................... 705/7
`Jeng et al ....................... 705/1
`Weidmanetal. ............ 717/172
`............. 717/136
`Hinchey et a!.
`
`OTHER PUBLICATIONS
`
`UVT: a unification-based tool for knowledge base verification; Polat,
`F. Guvenir, H.A.; Expert, IEEE; Publication Date: Jun. 1993; vol. 8,
`Issue: 3; on pp. 69-75 ;ISSN: 0885-9000.*
`The combining DAG: a technique for parallel data flow analysis;
`Kramer, R.; Gupta, R.; Sofia, M.L.; Parallel and Distributed Systems,
`IEEE Transactions on; vol. 5, Issue 8, Aug. 1994 pp. 805-813.*
`J. Estublier, J. Favre, P. Morat, "Toward SCM/PDM Integration?"
`Spring-Verag Berlin Heidelberg 1998.*
`An Object Model for Evolutionary Configuration Management
`(1993) Hannu Peltonen, Tomi Miinnistii, Reijo Sulonen, Kari Alho.*
`The combining DAG: a technique for parallel data flow analysis;
`Kramer, R.; Gupta, R.; Sofia, M.L.; Parallel and Distributed Systems,
`IEEE Transactions on; vol. 5, Issue 8, Aug. 1994 pp. 805-813 (this
`reference is cited and provided with office action dated Jul. 5, 2006). *
`* cited by examiner
`
`Page 2 of 26
`
`FORD 1001
`
`

`
`102
`
`104
`
`106
`
`Stitched Rules
`
`~
`00
`•
`~
`~
`~
`
`~ = ~
`
`+
`
`I
`
`I I lllililii!lilillil!ll!i!i!l!l!i!lilililiililililil!il
`
`II
`
`II
`
`Space defined by the , u,.,.,---'
`of models 102 and 1 04
`
`Space defined by the
`MDC of Model 102
`108
`
`Unspecified Buildable
`Configurations
`112
`
`Figure 1 (prior art)
`
`Space defined by the
`MDC of Model102
`11Q
`
`MKT2 space
`116
`
`MKT1 space
`114
`
`~ = := ....
`0 ....
`
`~Ul
`N
`
`0
`
`('D
`('D
`
`rFJ =(cid:173)
`.....
`....
`0 .....
`....
`
`(.H
`
`d
`rJl
`-....l
`~ w
`
`\C = 00 = = """"'
`
`Page 3 of 26
`
`FORD 1001
`
`

`
`U.S. Patent
`
`Jun.15,2010
`
`Sheet 2 of 13
`
`US 7,739,080 Bl
`
`-
`-
`
`(!)
`<(
`0
`.c.
`a.
`ro
`.....
`(!)
`(.)
`(3
`>.
`(.)
`<(
`"'0
`......
`Q)
`(.)
`.....
`Q)
`i5
`
`<(
`
`2!:-. E
`ro
`LL
`
`co
`2!:-
`.E
`ro
`LL
`
`u
`2!:-
`.E
`ro
`LL
`
`•
`•
`•
`
`C'-
`
`e
`:::s
`.t:n
`Li:
`
`Page 4 of 26
`
`FORD 1001
`
`

`
`U.S. Patent
`
`Jun.15,2010
`
`Sheet 3 of 13
`
`US 7,739,080 Bl
`
`I
`I
`I
`-
`
`Q)
`..l<:
`.....
`IU
`:::!!:
`
`-
`
`Q)
`..l<:
`.....
`IU
`:::!!:
`
`...-- -
`
`""' ..........
`
`"
`" 0:::
`
`UJ
`en
`
`C)
`z
`UJ
`
`C)
`z
`UJ
`
`0:::
`UJ
`en
`
`t'
`"'
`....
`0
`"t::
`S:
`e
`:::,
`.tn
`u:
`
`~
`
`t'
`"'
`....
`0
`"t::
`S:
`e
`:::,
`-~
`LL:
`
`C"')
`
`N
`N
`(0
`
`Q)
`"C
`0
`...
`E
`
`0 -
`
`(!)
`<(
`c
`
`N
`<r-
`CD
`"C
`c:
`co
`N
`Q
`CD
`rn
`Cii
`"C
`0
`...
`E
`
`0 -
`
`(!)
`<(
`c
`
`Page 5 of 26
`
`FORD 1001
`
`

`
`r 504
`
`USA Model
`
`Canada Model
`
`""
`r 5os ~
`r 5oa v v
`
`,..
`
`Conventional Model
`Stitching Process
`
`"= 510
`
`Mexico Model
`
`may be created and
`maintained
`independenUy.
`502
`
`500 )
`
`-..
`
`Combined
`USA+Canada+Mexlco
`Model
`
`I
`
`'
`
`I
`I
`
`\_ Contains all of the
`information present
`in the USA, Canada,
`
`unspecified
`buildable
`configurations.
`512
`
`Figure 5 (Prior Art)
`
`~
`00
`•
`~
`~
`~
`
`~ = ~
`
`2'
`:=
`......
`~Ul
`N
`0 ......
`0
`
`rFJ =(cid:173)
`......
`,j;o,.
`
`('D
`('D
`
`0 .....
`......
`(.H
`
`d
`rJl
`-....l
`~ w
`
`\C = 00 = = ""'"'
`
`Page 6 of 26
`
`FORD 1001
`
`

`
`MKT Family
`
`•
`
`ENG Family
`
`•
`
`Configuration Model602: defining constraints= {SER1}
`,-----------------------
`.------------------------------;
`!
`!
`! MKT1
`
`MKT1.ENG1
`
`MKT2
`
`I
`I !.----------
`
`intersect
`
`MKT1.ENG2
`
`MKT2.ENG1
`
`MKT2.ENG2
`
`intersect
`
`604
`
`606
`
`Configuration Model612: defining constraints= {SER2}
`
`.......................................................................... ,
`SER Family
`
`Complete Model Is the
`Intersection of MKT, ENG,
`SER Families
`
`MKT1.ENG1.SER1
`MKT1.ENG1.SER2
`MKT1.ENG2.SER1
`MKT1.ENG2.SER2
`MKT2.ENG1.SER1
`MKT2.ENG1.SER2
`MKT2.ENG2.SER1
`MKT2.ENG2.SER2
`
`MKT1.ENG1.SERt
`MKT1.ENG1.SER2
`MKT1. ENG2.SE R1
`MKT1. ENG2.SE R2
`MKT2.ENG1.SER1
`MKT2.ENG1.SER2
`MKT2. ENG2.SE R1
`MKT2. ENG2.SE R2
`
`.------------------------------;:
`ENG Family
`
`------------------------------------,
`SER Family
`.
`
`i
`'
`I
`!
`I
`!intersect
`~
`I
`i
`--------------l==---\-
`;
`-\:.::
`
`MKT1.ENG1
`
`MKTI.ENG2
`
`MKT2.ENG1
`
`MKT2.ENG2
`
`MKT1.ENG1.SER1
`MKT1.ENG1.SER2
`MKT1.ENG2.SER1
`MKT1.ENG2.SER2
`MKT2.ENG1.SER1
`MKT2.ENG1.SER2
`MKT2.ENG2.SER1
`MKT2.ENG2.SER2
`
`·----------------i------------------
`616
`;.
`
`602
`
`612
`
`622
`
`r-----------------------r
`~
`MKT Family
`'
`I
`MKT1~'''~ !
`1.
`i Intersect
`~
`I
`i
`==~~----------\-
`
`MKT2
`
`-\:.:: 614
`
`MKT1 ~'-'-'-"!
`
`MKT2~'-'-'-~ !
`!
`................................................ •
`
`608
`( .......................................................................... ,
`
`'
`
`Complete Model Is the
`Intersection of MKT, ENG,
`SERFamllies
`
`'
`
`610
`
`MKT1.ENG1.SER1
`MKT1.ENG1.SER2
`MKT1.ENG2.SER1
`MKT1. ENG2.SE R2
`MKT2. ENG1.SE R1
`MKT2.ENG1.SER2
`MKT2.ENG2.SER1
`MKT2. ENG2.SE R2
`61 ~-------------------------------------~
`
`620
`
`636
`
`Combination of Model 602
`and Model612
`
`MKT1.ENG1.SER1
`MKT1.ENGI.SER2
`MKTI.ENG2.SER1
`MKTI.ENG2.SER2
`MKT2.ENGI.SER1
`MKT2.ENGI.SER2
`MKT2.ENG2.SER1
`MKT2. ENG2.SE R2
`
`\::=
`
`Actual Result of Combining Configuration Models 602 and 612
`..................................................
`~
`MKTFamlly
`!
`!
`I
`!intersect
`I
`I
`
`-------·--------------------.. ,.
`~
`ENG Family
`MKTI.ENGI ~ ~
`i
`!
`!
`~---~-:~~~~-~~--~---!
`
`MKT1.ENG2
`
`MKT2.ENG1
`
`!intersect
`
`SER Family
`
`MKT1.ENG1.SER1
`MKT1.ENGI.SER2
`MKTI.ENG2.SER1
`MKT1.ENG2.SER2
`MKT2.ENGI.SER1
`MKT2.ENG1.SER2
`MKT2.ENG2.SER1
`MKT2.ENG2.SER2
`
`624
`
`626
`Figure 6 (Prior Art)
`
`628
`
`630
`
`~
`00
`•
`~
`~
`~
`
`~ = ~
`
`2'
`:= ....
`0 ....
`
`~Ul
`N
`
`0
`
`('D
`('D
`
`rFJ =(cid:173)
`.....
`Ul
`0 .....
`....
`
`(.H
`
`d
`rJl
`-....l
`~ w
`
`\C = 00 = = ""'"'
`
`Page 7 of 26
`
`FORD 1001
`
`

`
`704
`
`Model A
`
`706
`
`Model B
`
`•
`•
`•
`
`Model N
`
`700
`
`)
`
`~
`7J)_
`•
`~
`~
`~
`
`~ = ~
`
`2'
`:= ....
`0 ....
`
`~Ul
`N
`
`0
`
`Model
`Consoldation
`Process
`
`Consolidated
`A+B+ ... + N
`Model
`
`710
`
`('D
`('D
`
`rFJ =(cid:173)
`.....
`0\
`0 .....
`....
`
`(.H
`
`Contains all of the
`information present in
`Models A through N.
`712
`
`Set of models that
`may be created and
`maintained
`independently.
`ZQ2
`
`Figure 7
`
`d
`rJl
`-....l
`~ w
`
`\C = 00 = = """"'
`
`Page 8 of 26
`
`FORD 1001
`
`

`
`Adjusting Model612 So It May Be Combined With Model602
`, ....................................................... .,
`~
`MKTFamily
`
`ENG Family
`
`SER Family
`
`'
`,
`:
`I
`!
`:
`i
`:
`L
`!
`·--------------,-------------j
`
`MKT1.ENG1
`
`MKT1.ENG2
`
`MKT2.ENG1
`
`MKT2.ENG2
`
`I
`
`MKT1.ENG1.SER1
`MKT1.ENG1.SER2
`MKT1.ENG2.SER1
`MKT1.ENG2.SER2
`MKT2.ENG1.SER1
`
`MKT2.ENG1.SER2 Ej l
`:L 608
`i
`--------------------------------------!
`
`MKT2.ENG2.SER1
`MKT2.ENG2.SER2
`
`606
`
`v- 602
`
`~
`00
`•
`~
`~
`~
`
`~ = ~
`
`N
`0
`
`-
`CD
`.!
`0
`""'
`
`-
`
`1
`
`1
`
`1
`
`I
`
`'
`:
`:
`!
`! MKT1
`:
`:
`::!:
`:
`i
`S
`!
`:
`"l;j
`~ i
`'
`:
`l;
`L 604
`8 i ______________________ j
`
`N ... CD
`
`a;
`"CC
`0
`==
`r:::
`0
`~ = Cl>
`
`I;:
`r:::
`0
`0
`
`N ... CD
`
`a;
`"tt_
`o"tt ==s
`0 =
`r:::
`.,
`~~ =-1:1>
`'E
`0
`0
`
`compare
`----------.& .............................. ,
`MKTFamlly
`
`compare
`
`r---------------------------••t
`
`ENG Family
`
`.
`
`MKT1
`
`MKT1.ENG1
`
`MKT1.ENG2
`
`intersect
`
`intersect
`
`614
`
`MKT2ENG1 ~ [
`!'-- 616
`!
`MKT2 ENG2
`.......................................................................
`
`r""'"'"'"'"'"'"'"'"'"""'"'"'"'"'"'"'"'"'"'"'"'"'"''"''"'"'"''"''"'"''"'"""'"'-"'1
`SERFamily
`
`:
`:
`i
`i
`i
`i
`i
`:
`L
`-----~-~:~~~~:~-=~------------j
`
`MKT1.ENG1.SER1
`MKT1.ENG1.SER2
`MKT1.ENG2.SER1
`MKT1.ENG2.SER2
`MKT2.ENG1.SER1
`MKT2.ENG1.SER2
`MKT2.ENG2.SER1
`
`.------------------------·--------·-... -,
`
`Complete Model
`
`612
`
`MKT1.ENG1.SER1
`MKT1.ENG1.SER2
`MKT1.ENG2.SER1
`MKT1.ENG2.SER2
`MKT2.ENG1.SER1
`MKT2.ENG1.SER2
`MKT2.ENG2.SER1
`MKT2.ENG2.SER2
`
`616
`
`No adjuslmenl required
`for MKT family.
`
`___________ !___________
`
`MKTFamily
`
`MKT1
`
`intersect
`
`r- 824
`
`, _______________________ ...
`
`Adjust model612 by adding space to ENG family
`and removing space from SER.
`
`·--------------~--------------~-------------------------------------·
`!
`!
`
`ENG Family
`
`SER Family
`
`MKT1.ENG1
`
`MKT1.ENG2
`
`832
`
`intersect
`
`MKT2.ENG1
`
`MKT2.ENG2 ~ ~ 826
`
`.. ______________________________ 1
`
`MKT1.ENG1.SER1
`MKT1.ENG1.SER2
`MKT1.ENG2.SER1
`MKT1.ENG2.SER2
`MKT2.ENG1.SER1
`MKT2.ENG1.SER2
`MKT2.ENG2.SER1
`MKT2.ENG2.SER2
`
`;. ____________________________________ j'-
`
`'
`
`Figure 8
`
`Adjustments to families may not affect
`the complete model.
`
`-----------------~-----------------
`
`I
`
`822
`
`834
`
`828
`
`MKT1.ENG1.SER1
`MKT1.ENG1.SER2
`MKT1.ENG2.SER1
`MKT1.ENG2.SER2
`MKT2.ENG1.SER1
`MKT2.ENG1.SER2
`MKT2.ENG2.SER1
`MKT2.ENG2.SER2
`~----------------·-------------------
`
`2'
`:= ....
`0 ....
`
`~Ul
`N
`
`0
`
`('D
`('D
`
`rFJ =(cid:173)
`.....
`-....l
`0 ....
`....
`
`(.H
`
`d
`rJl
`-....l
`~ w
`
`\C = 00 = = """"
`
`Page 9 of 26
`
`FORD 1001
`
`

`
`Result of Combining Configuration Models 602 and 612 Using Model Consolidation System 1200
`
`Configuration Model 602: defining constraints= {SER1}
`·------------------------------,
`
`ENG Family
`
`.
`
`MKTFamily
`
`602
`
`MKT1
`
`MKT2
`
`. .
`i
`!.----------
`
`intersect
`
`MKT1.ENG1
`
`MKT1.ENG2
`
`MKT2.ENG1
`
`MKT2.ENG2
`
`intersect
`
`·------------------------------------,
`i
`I
`
`SER Family
`
`MKT1.ENG1.SER1
`MKT1.ENG1.SER2
`MKT1.ENG2.SER1
`MKT1.ENG2.SER2
`MKT2.ENG1.SER1
`MKT2.ENG1 .SER2
`MKT2.ENG2.SER1
`MKT2.ENG2.SER2
`
`Complete Model Is the
`Intersection of MKT, ENG,
`SER Families
`
`.............................. _ .. _____________________ i
`i
`!
`i
`!
`!
`i
`!
`!
`!
`I
`~
`
`MKT1.ENG1.SER1
`MKT1.ENG1.SER2
`MKT1.ENG2.SER1
`MKT1.ENG2.SER2
`MKT2.ENG1.SER1
`MKT2.ENG1.SER2
`MKT2. ENG2.SER1
`MKT2.ENG2.SER2
`.
`!-------------------------------------
`
`604
`
`606
`
`608
`
`610
`
`------------··--------~
`MKT Family
`
`~
`
`ENG Family
`
`Configuration Model612 (ADJUSTED): defining constraints= {SER2}
`,------------------------------,
`................................................................................................ T
`~
`~
`SER Family
`MKT1 ENG1 SER1 ~ !
`!
`~
`I
`i
`i
`i
`i
`
`intersect
`
`MKT1 ENG1 SER2
`MKT1 ENG2 SER1
`MKT1 ENG2 SER2
`MKT2 ENG1 SER1
`MKT2 ENG1 SER2
`MKT2 ENG2 SER1
`MKT2 ENG2 SER2
`
`-------------------------------·------.
`
`Complete Model is the
`Intersection of MKT, ENG,
`SER Families
`
`•
`
`MKT1.ENG1.SER1
`MKT1.ENG1.SER2
`MKT1.ENG2.SER1
`MKT1.ENG2.SER2
`MKT2. ENG1.SER1
`MKT2.ENG1.SER2
`MKT2.ENG2.SER1
`MKT2. ENG2.SER2
`l-----------------------------------
`
`822
`
`MKT1
`
`MKT2
`
`~
`~
`MKT1.ENG1
`I
`I
`! MKT1.ENG2
`! ,
`! 1ntersect !
`!
`! MKT2.ENG1
`! MKT2.ENG2
`~-----------------------------
`
`J
`
`I
`
`824
`
`826
`
`828
`
`830
`
`Actual Result of Combining Configuration Models 602 and 612 (ADJUSTED)
`
`MKTFamlly
`
`ENG Family
`
`SERFamlly
`
`~-----------------·---------------.
`
`Consolidation of Modol602
`and Model 612
`
`922
`
`MKT1
`
`intersect
`
`MKT2
`
`MKT1.ENG1
`
`MKT1.ENG2
`
`MKT2.ENG1
`
`MKT2.ENG2
`
`intersect
`
`MKT1.ENG1.SER1
`MKT1.ENG1.SER2
`MKT1.ENG2.SER1
`MKT1.ENG2.SER2
`MKT2.ENG1.SER1
`MKT2.ENG1.SER2
`MKT2.ENG2.SER1
`MKT2.ENG2.SER2
`
`MKT1.ENG1.SER1
`MKT1.ENG1.SER2
`MKT1.ENG2.SER1
`MKT1.ENG2.SER2
`MKT2. ENG1.SER1
`MKT2.ENG1.SER2
`MKT2.ENG2.SER1
`MKT2. ENG2.SER2
`
`·------------------------------~
`
`924
`
`926
`
`-
`
`-
`
`-
`
`·-------------------------------------\
`
`-'C 928
`
`·------------------------------------ \::
`1
`
`930
`
`Figure 9A
`
`~
`00
`•
`~
`~
`~
`
`~ = ~
`
`~ = = ....
`0 ....
`
`~
`
`Ul
`N
`
`0
`
`rFJ =(cid:173)
`.....
`
`('D
`('D
`
`QO
`
`0 .....
`....
`
`(.H
`
`d
`rJl
`-....l
`~ w
`
`\C = 00 = = """'
`
`Page 10 of 26
`
`FORD 1001
`
`

`
`602
`
`612
`
`930
`
`Stitched Rules
`
`~
`00
`•
`~
`~
`~
`
`~ = ~
`
`+
`
`I
`
`I -
`
`I 1 liillilililimmmimililiiiliiiliilliilliiilil 1
`
`I
`
`I I
`
`Space defined by the , .... .,.~___J
`of models 602 and 612
`
`Space defined by the
`MDC of Model602
`
`Space defined by the
`MDC of Model612
`
`~ = := ....
`0 ....
`
`~Ul
`N
`
`0
`
`('D
`('D
`
`rFJ =(cid:173)
`.....
`\0
`0 .....
`....
`
`(.H
`
`Figure 98
`
`d
`rJl
`-....l
`~ w
`
`\C = 00 = = """"'
`
`Page 11 of 26
`
`FORD 1001
`
`

`
`1000
`
`~
`
`1001
`I
`
`1002
`I
`
`I
`
`Build a unified DAG from the I
`
`rules of all input models
`
`~t"!~-="by~
`
`1004
`
`1005
`
`Determine which families
`can't be trivially combined
`together
`
`Create marker rules for the
`non-trivial families and add
`them to the indexed rules
`
`For each family, qualify its
`rules with the defining
`constraints from the model it
`comes from
`
`1006 :
`
`~
`constraints from the RHS of I
`
`Remove added defining
`
`rules where they cause
`cycles in the DAG
`
`~
`00
`•
`~
`~
`~
`
`~ = ~
`
`~
`
`= := ....
`....
`
`~Ul
`N
`0
`
`0
`
`rFJ
`
`('D
`('D
`
`=-
`.....
`....
`0
`.....
`0
`....
`
`(.H
`
`d
`rJl
`-....l
`~ w
`
`\C = 00
`= = """"
`
`LHS is from
`a trivial family
`
`LHS is from a
`non-trivial family
`
`Perform the non-trivial
`combination algorithm
`
`1010
`'
`
`( Stop )
`
`Figure 10
`
`Page 12 of 26
`
`FORD 1001
`
`

`
`U.S. Patent
`
`Jun.15,2010
`
`Sheet 11 of 13
`
`US 7,739,080 Bl
`
`1107
`
`Output optionality overlap
`error message
`
`No
`
`1100
`
`~
`
`1101
`
`1102
`
`1103
`
`1104
`
`1105
`
`1106
`
`Start
`
`Group all of the rules
`together by LHS feature
`
`Determine all possible sets
`of rules with overlapping
`RHS features
`
`Resolve false buildables
`
`Optionally apply restriction
`rules
`
`Figure 11
`
`Page 13 of 26
`
`FORD 1001
`
`

`
`1204(1)
`
`1204(2)
`
`Network
`1202
`
`~
`00
`•
`~
`~
`~
`
`~ = ~
`
`2'
`:= ....
`0 ....
`
`~Ul
`N
`
`0
`
`('D
`('D
`
`rFJ =(cid:173)
`.....
`....
`N
`0 .....
`....
`
`(.H
`
`1206(N) 1206(N-1}
`
`1206(9
`
`Figure 12
`
`d
`rJl
`-....l
`~ w
`
`\C = 00 = = """"'
`
`Page 14 of 26
`
`FORD 1001
`
`

`
`/1300
`
`1317
`
`.
`
`I
`
`•11 DISPLAY I
`
`·1314
`
`1318
`
`1315
`
`MAIN
`
`/
`MEMORY •
`
`.
`
`1319 G.
`
`DRIVER
`
`1/0 •
`
`Processor •
`
`VIDEO
`I MEMORY
`
`~
`00
`•
`~
`~
`~
`
`~ = ~
`
`~ = := ....
`0 ....
`
`~Ul
`N
`
`0
`
`('D
`
`(.H
`
`rFJ =-('D
`.....
`....
`0 .....
`....
`
`(.H
`
`·1310
`
`1309
`
`USER INPUT
`DEVICE(S)
`
`MASS STORAGE
`
`Figure 13
`
`d
`rJl
`-....l
`~ w
`
`\C = 00 = = """"'
`
`Page 15 of 26
`
`FORD 1001
`
`

`
`US 7,739,080 Bl
`
`1
`CONSOLIDATION OF PRODUCT DATA
`MODELS
`
`BACKGROUND OF THE INVENTION
`
`2
`
`Main feature
`
`Optionality Constraints
`
`Time frame
`
`4.8literV8
`
`s
`
`XL&US
`
`May-December Rule 1
`2003
`
`15
`
`Rule 1 means "the 4.8liter V8 is standard with the XL trim
`and US market from May to December 2003." The main
`feature represents the feature that is being affected by the rule.
`Optionalities can be positive or negative: positive optionali(cid:173)
`ties state that the main feature can work with the constraints;
`negative optionalities state the main feature cannot work with
`the constraints. Constraints qualifY the rule and can be an
`arbitrary Boolean expression of features such as AND, NOT,
`and OR operators. In the rules below, a"." indicates an AND
`operation, a"-" indicates a NOT operation, and a"+" indi(cid:173)
`cates an OR operation. The timeframe specifies when the
`other rule elements are effective.
`A buildable configuration describes what features can and
`can't exist with other features of a product. The example rule
`above defines a buildable configuration in the following way:
`"the 4.8 liter V8 is buildable (because it is standard) with the
`25 combination of XL and US." If the combination of features,
`such as of XL and US, is not buildable, the example rule is
`inactive. Consequently, even though the engine is buildable
`with that combination, if the combination is not buildable, the
`three features together are not a buildable configuration. A
`30 rule that would make the example rule inactive is the follow-
`ing:
`
`20
`
`35
`
`Main feature Optionality
`
`XL
`
`N
`
`Constraints
`us
`
`Time frame
`
`September 2002
`
`Rule2
`
`1. Field of the Invention
`The present invention relates in general to the field of
`information processing, and more specifically to a system and
`method for consolidating data from various product data 10
`models.
`2. Description of the Related Art
`A configurable product can be described by a configuration
`model having a set of configuration rules. A configurable
`product can be conceptually broken down into sets of select(cid:173)
`able families and features of families that make up each
`product. A family represents a classification of a particular
`type of feature. Families are typically classified as groups of
`features with the same functional purpose. Example families
`for an automobile are "engines," "tires," "seats," and "exterior
`paint color." Families can also represent other groups such as
`market areas. For example, a family can include a marketing
`region such as USA, Canada, Mexico, Europe, or any other
`region. Families can be represented in terms of the minimum
`and maximum number of features that must be present in a
`configuration from a family for the configuration to be valid.
`A common family minimum and maximum or "(min, max)"
`is ( 1, 1 ). This notation means that exactly one feature from the
`family must be part of a configuration for the configuration to
`be valid. Other common (min, max) settings are (0, 1 ), mean(cid:173)
`ing that either no features or a single feature from the family
`must be present in a configuration for it to be valid, and (0,
`-1 ), meaning that zero or any positive number of features
`from the family must be present in a configuration for it to be
`valid.
`A feature represents an option that can be ordered on a
`product. All features are members of a family. Features are
`both assigned optionalities and used to qualifY other features 40
`and the optionalities assigned to them. An example feature
`from the engine family is a "4.8 liter V8." Features relate to
`each other via ordering codes or optionalities. Example
`optionalities include "S", "0", "M", and "N," which translate
`to standard, optional, mandatory, and not available. A specific
`example would be "the 4.8 liter V8 engine is standard on the
`GS trim."
`Features relate to each other via configuration rules. A rule
`can be characterized as generally including a 'left hand side',
`(LHS), a 'right hand side' (RHS), and a specified relationship
`between the LHS and RHS. Each LHS feature may be asso(cid:173)
`ciated with one or more RHS features, which indicates that a
`single feature in the LHS may be constrained or otherwise
`qualified by one or more RHS features. The RHS describes
`when a rule is in effect and what features are particularly
`affected. For example, a rule with a RHS of"XA, XB" means
`that the rule is in effect in cases where you have at least XA
`and XB in a buildable configuration, and XA and XB are
`features particularly affected by the rule along with the LHS
`feature. Configuration rules include optionalities that define a 60
`relationship between the LHS and RHS. Further exemplary
`discussion of LHS and RHS rule concepts is described in
`Gupta eta!., U.S. Pat. No. 5,825,651 entitled "Method and
`Apparatus for Maintaining and Configuring Systems."
`A configuration rule includes a main feature, an optional(cid:173)
`ity, one or more constraints, and an applicable timeframe. As
`an example:
`
`45
`
`50
`
`55
`
`Rule 2 means "the XL trim main feature is not available
`with US from September of2002 onward." Until the XL main
`feature is made available with the US by changing the option(cid:173)
`ality from "N" to one that expresses a positive relationship,
`there will not be a buildable configuration for XL, US, and the
`4.8 L engine.
`Thus, a rule defines a buildable configuration between its
`main feature and its constraints only. A rule does NOT define
`a buildable configuration relationship between the members
`of its constraints. A separate rule must define that buildable
`configuration. Consequently, all rules together for a product
`define the complete product buildable configurations. In
`order to determine if the three features in the example rule
`(the main feature and the constraints) are a buildable configu(cid:173)
`ration, the rules written on each of those features (i.e. where
`each feature is the main feature) should to be considered
`jointly. Inactive rules do not define buildable configurations
`until they become active.
`A "model" refers to a collection of rules that define the
`buildable configurations of one or more products.
`Referring to FIG. 2, the families in each model are inter(cid:173)
`nally organized in accordance with a directed acyclic graph
`("DAG") 200. The DAG contains an edge between a child
`family and a parent family if there exists a rule with a LHS
`feature that belongs to the child family and a RHS feature that
`belongs to the parent family. The DAG organization allows a
`65 child family to reference an ancestor but not the other way
`around. Cyclic references within a model as in FIG. 4 can
`produce ambiguities within the model.
`
`Page 16 of 26
`
`FORD 1001
`
`

`
`US 7,739,080 Bl
`
`3
`Each model contains variations of the buildable configu(cid:173)
`rations of the product. For example, a company may market a
`product with a particular set of standard features in one region
`and market the same product with a different set of standard
`features in another region. For example, in an automotive 5
`context, a V6 engine may be standard for a particular auto(cid:173)
`mobile model in one country, and a VS engine may be stan(cid:173)
`dard for the particular automobile model in another country.
`In a computer context, a power supply with a 11 OV input may
`be standard in one country and a power supply with a 220V 10
`input may be standard in another country.
`Defining and maintaining the configuration space for a
`large product can often be difficult to do in a single configu(cid:173)
`ration model. In order to limit the complexity and facilitate
`maintenance the configuration space is often defined in mul- 15
`tiple configuration models. Each of these models are then
`assigned a set of defining constraints that specifY which por(cid:173)
`tion of the overall configuration space for the product it is
`defining. An example breakdown of the configuration space
`definition for an automotive vehicle could be into 3 separate 20
`models. Each model would define the configuration space of
`the automobile in one of 3 countries: USA, Canada, or
`Mexico. In this example each configuration model would
`have as a defining constraint one of the features representing
`each country. In the USA model the only allowable configu- 25
`rations would all contain the "USA" feature. Although not
`specifically included in this example, time can also be a
`defining constraint.
`A model may contain labels that describe the time period
`and space over which the model applies (also referred to as 30
`"model defining constraints"). For example, a model which
`describes the availability of cars in the United States during
`the years 2004 to 2006 may have defining constraints of
`"CARS.USA.2004-2006" while a model that describes the
`availability of all vehicles in North America during 2005 may 35
`have defining constraints of "{CARS+TRUCKS}.{USA+
`CANADA+MEXIC0}.2005".
`While it is convenient to have this logical separation of the
`configuration space for maintenance purposes it is often
`desired to provide a single unified model that represents the 40
`configuration space for the entire product. The resulting uni(cid:173)
`fied configuration model can then be used to answer any
`questions that one of the original models could answer and it
`will give the same result. The set of allowable feature com(cid:173)
`binations for the unified model should be equivalent to the 45
`union of allowable feature combinations for each of the origi(cid:173)
`nal configuration models.
`Thus, despite the differences in various models, it is often
`desirable to combine the multiple models into a consolidated
`model having a unified set of rules (also referred to as 50
`"stitched rules"). Referring to FIG. 5, the conventional con(cid:173)
`solidation system 500 includes a model 502 that represents a
`set of three models that may be created and maintained sepa(cid:173)
`rately. Model 504 is, for example, a configuration model that
`describes how a particular product may be built and sold for 55
`the USA market. Model 506 is a configuration model that
`describes how the same product may be built and sold for the
`Canadian market. Model 508 is a configuration model that
`describes how the same product may be built and sold for the
`Mexican market. Models 504, 506, and 508 may be combined 60
`into a single model 512 by conventional consolidation (also
`referred to as "stitching") processes 510. The consolidated
`model 512 will contain stitched rules that represent all the
`information present in the original three models. However, in
`many circumstances the conventional consolidation pro- 65
`cesses 510 produce unspecified configuration buildables in
`consolidated model 512. "Unspecified configuration build-
`
`4
`abies" are configuration buildables included in consolidated
`model512 that are not defined in any of the source models, i.e.
`models 504, 506, and 508. An unspecified configuration
`buildable is, thus, an error that can have significant adverse
`consequences. Conventional consolidation processes do not
`automatically detect unspecified configuration buildables and
`correct them. Since models can contain thousands, hundreds
`of thousands, or more rules, a high degree of automation is
`often a key to success for modeling and model data driven
`technologies.
`Referring to FIG. 1, for example, assume models 102 and
`104 are two configuration models with the following rules:
`Model102: model defining constraints={MKTl}
`MKTlOALL
`ENGl SALL
`Model104: model defining constraints={MKT2}
`MKT20ALL
`ENGl SALL
`ENG20ALL
`The rules in models 102 and 104 are interpreted as allowing
`the following buildable configurations:
`Model102:
`MKTl.ENGl
`Model104:
`MKT2.ENG1
`MKT2.ENG2
`An example conventional consolidation process 510 that
`simply combined the rules from models 102 and 104 using a
`simple aggregation process would yield a consolidated model
`106 with the following rules:
`Model 106: model defining constraints
`{MKT1+MKT2}
`MKTlOALL
`MKT20ALL
`ENGl SALL
`ENG20ALL
`The rules of model 106 are interpreted as allowing the
`following buildable configurations:
`Model106:
`MKT1.ENG1 (corresponds to element 108)
`MKT1.ENG2 (corresponds to element 112)
`MKT2.ENG1 (corresponds to element 110)
`MKT2.ENG2 (corresponds to element 110)
`Model106 includes the model space defined by the model
`defining constraints 108 of model 102 and the model space
`defined by the model defining constraints of 110 of model
`104. Unfortunately, in addition to representing the stitched
`rules of models 102 and 104, model 106 also includes an
`unspecified buildable configuration "MKT1.ENG2" 112. In
`the embodiment ofFIG.1, buildable configurations of model
`104 have been extended into the model defining constraints
`MKT1 space 114. Model defining constraints space MKT2
`space 116 accurately contains only the buildable configura(cid:173)
`tions ofmodel104.
`The consolidated model should faithfully represent the
`buildable configurations of the products represented by mod(cid:173)
`els 102 and 104 without including any errors such as the
`unspecified buildable configurations 112. Conventional con(cid:173)
`solidation processes attempt to solve this problem by modi(cid:173)
`fYing, adding, and removing stitched rules so that rules from
`each source model do not extend outside of the space defined
`by their source model's defining constraints.
`An example enhanced conventional consolidation process
`510 that combined the rules from models 102 and 104, con(cid:173)
`straining each to their source model's defining constraints,
`would yield a consolidated model 406 with the following
`rules:
`
`("MDC")=
`
`Page 17 of 26
`
`FORD 1001
`
`

`
`US 7,739,080 Bl
`
`5
`Model406: model defining constraints={MKT1+MKT2}
`MKTl 0 ALL
`(source model 102's defining
`constraints={MKTl})
`ENG1 S MKTl
`(source model 102's defining
`constraints={MKTl})
`MKT2 0 ALL
`(source model 104's defining
`constraints={MKT2})
`ENG1 S MKT2
`(source model 104's defining
`constraints={MKT2})
`ENG2 0 MKT2
`(source model 104's defining 10
`constraints={MKT2})
`The rules of model 406 are interpreted as allowing the
`following buildable configurations:
`Model406:
`MKTl.ENGl
`MKT2.ENG1
`MKT2.ENG2
`The new model 406 accurately combines the intent of
`source models 102 and 104 without introducing new unspeci(cid:173)
`fied buildable combinations.
`Although consolidation appears to be the straight forward
`process of adding all the rules from each model being con(cid:173)
`solidated and