United States Patent
`(12)
`(10) Patent No.:
`US 8,117,233 B2
`Liu et al.
`(45) Date of Patent:
`*Feb. 14, 2012
`
`
`US008117233B2
`
`(54) METHOD AND SYSTEM FOR
`MESSAGE-ORIENTED SEMANTIC WEB
`r
`SERVICE COMPOSITION BASED ON
`ARTIFICIAL INTELLIGENCE PLANNING
`
`(75)
`
`.
`(73) Assignee:
`
`(*) Notice:
`
`Inventors: Zhen Liu, Tarrytown, NY (US); Anand
`Ranganathan, White Plains, NY (US):
`aL
`“eining
`|
`°
`Anton Y. Riabov, Ossining, NY (US)
`.
`.
`.
`International Business Machines
`Corporation, Armonk, NY (US)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C, 154(b) by 504 days.
`This patent is subject to a terminal dis-
`claimer.
`
`(21) Appl. No.: 11/748,216
`(22) Filed:
`May14, 2007
`.
`Prior Publication Data
`US 2008/0288595 Al
`Nov. 20, 2008
`
`(65)
`
`(51)
`
`Int. Cl.
`(2006.01)
`GO6F 7/00
`(52) U.S.C). ccc ceecresrenneeens 707/802; 707/608
`(58) Field of Classification Search........... 707/999 .007,
`707/802, 608
`See application file for complete search history.
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`5,675,786 A
`6,086,619 A *
`oeoat BI *
`4
`’
`6.742.054 BL*
`7,016,910 B2
`7,505,989 B2
`7,577,554 B2*
`
`10/1997 McKee etal.
`7/2000 Hausman etal... 703/6
`loouos Gould et a oe 717/162
`ersen ¢
`.
`5/2004 Upton, IV sscsseseussaean 10/6
`3/2006 Hgilsson et al.
`3/2009 Gardneret al.
`8/2009 Lystad etal. wee 703/2
`
`7,665,064 B2*
`7,716,272 B2*
`7,739,351 B2*
`7877421 B2
`7904545 B2
`2003/0055668 Al*
`2003/0120642 Al
`2003/0135628 Al*
`2003/0142818 Al
`2004/0024841 A1*
`2004/0073545 Al*
`
`2/2010 Ableetal. ow. TATALT
`..
`. 709/201
`5/2010 Skwarek et al.
`
`6/2010 Shkvarchuk et al.
`......... 709/217
`‘1/2011 Bergeret al.
`3/2011. Golovchinskyet al.
`3/2003 Saranetal. vce 705/1
`6/2003 Egilssonetal.
`7/2003 Fletcher et al. sesso 709/229
`7/2003 Raghunathanetal.
`2/2004 Becker et al. sacs 709/219
`4/2004 Greenblatt etal. uo. 707/3
`inued
`(Continued)
`OTHER PUBLICATIONS
`Jos de Bruijn, “Semantic Web Technologies: Advanced SPARQL”,
`published 2006, pp. 1-4. accessed online at <http:/‘www.inf.unibz.
`it/~debruijn/teaching/swt/2006/lecture4-handouts-2x3.pdf> on Sep.
`22, 2009.*
`
`(Continued)
`Primary Examiner — Hung T Vy
`Assistant Examiner
`Phuong Thao Cao
`(74) Attorney, Agent, or Firm — William J. Stock: F. Chau &
`Associates, LLC
`
`ABSTRACT
`(57)
`A method for modeling a web service operation, includes:
`defining an input message pattern that describes input
`requirements of a web service operation, wherein the input
`message pattern includesa set of variables representing data
`elements that must be contained in a message input to the web
`service operation, and a graph pattern that semantically
`describes the data elements that must be contained in the
`message input to the web service operation; and defining an
`output message pattern that describes an output message of
`the web service operation, wherein the output message pat-
`tern includesa set of variables and exemplars that represent
`data elements contained in the output message, and a graph
`.
`.
`:
`.
`pattem that semantically describes the data elements con
`tamed
`in the output message.
`
`17 Claims, 5 Drawing Sheets
`
`
`
`
`StockService
`
`
`
`
`
`
`getStockPrice
`
`MessageIn
`Operation:
`ti
`~
`CTicker
`seme
`ow,
`
`
`
`
`froamExchange
`
`Price
`
`ompan
`;
`-=
`A wy type
`ompany)
`
`
`couhtickerOf pany hasPrice
`
`lype
`_
`hasM
`Stock
`far
`
`
`
`
`y _hastlonvelwyMonetaryValuedf type inCurrency
`
`
`
`?Company
`registeredAt
`.
`2Company
`atExchange
`
`
`USDollar
`
`~~_legisteredAt
`mN,
`oA NYSE—
`fromExcaange
`
`Message Out
`
` contains,
`
`
`
`\ l _TimeStamp I
`
`
`AtickerrSymbal
`
`|CC
`
`
`
`
`CTFickerSymbol
`rdf type
`tickerOf
`
`
`AtickerSymbol }-——
`
`Booking, Exh. 1047, Page 1
`
`Booking, Exh. 1047, Page 1
`
`

`

`US 8,117,233 B2
`Page 2
`
`
`
`
`
`.
`
`U.S. PATENT DOCUMENTS
`2004/0073661 Al*
`4/2004 Libachetal. oo. 709/224
`2004/0111533 Al*
`6/2004 Beisiegel etal. wu... 709/246
`2004/0138936 Al
`7/2004 Johnsonet al.
`2004/0148214 Al*
`7/2004 Azizetal. we 7105/8
`2004/0162741 Al
`8/2004 Flaxer etal.
`2005/0021548 Al
`1/2005 Bohannonet al.
`2005/0021745 Al
`1/2005 Bookman etal.
`2005/0044525 Al*
`2/2005 Lazarov wee T17/104
`2005/0055330 Al*
`3/2005 Britton etal.
`ve TOF
`
`5/2005 Okitaetal. oe 345/589
`2005/0093881 Al*
`2005/0114757 Al
`5/2005 Sahota etal.
`2005/0289134 Al* 12/2005 Noguchi... TOVA
`2006/003 1288 AL*
`2/2006 Ter Horst et al.
`........... 709/204
`2006/0036983 A1*
`2/2006 Iwashita oe 716/5
`2006/0053172 Al
`3/2006 Gardnereial.
`2006/0167856 Al*
`7/2006 Angeleetal. we 7079/3
`2006/0167946 Al
`7/2006 Hellman ctal.
`2006/0173868 Al*
`8/2006 Angele etal.
`707/100
`
`2006/0195332 Al*
`8/2006 Bogneretal.
`w TO5/1
`2006/0195463 Al*
`8/2006 Bogneretal... 707/101
`2006/020025I Al
`9/2006 Gu etal.
`2006/0212855 A1™*
`9/2006 Bournasetal. ...
`717/140
`2006/0236306 A1l*
`10/2006 DeBruin etal.
`TTS
`
`1/2007 Toklu etal. 705/7
`2007/0021995 A1*
`2007/0023515 Al
`2/2007 Urken
`2007/0043803 Al
`2/2007 Whitehouseetal.
`2007/0050227 Al*
`3/2007 Teeganet al. uuu 705/8
`2007/0078815 Al
`4/2007 Wengetal
`2007/0156430 Al
`7/2007 Kaetkeret al.
`2007/0162893 Al
`7/2007 Moosmann etal.
`2007/0168303 Al
`7/2007 Moosmann et al.
`2007/0174811 Al
`7/2007 Kaetkeret al.
`2007/0179826 Al
`8/2007 Cutlip etal.
`2007/0186209 Al
`8/2007 Kaetkeretal.
`2007/0198971 Al
`8/2007 Dasuet al.
`2007/0220046 Al
`9/2007 Moosmann etal.
`.......... 709/223
`2007/0245013 A1* 10/2007 Saraswathy et al.
`2007/0265862 Al
`11/2007 Freundet al.
`2007/0288250 A1* 12/2007 Lemckeetal. oc. 705/1
`2008/0005155 Al*
`1/2008 Somaetal.
`707/102
`2008/0005278 Al*
`1/2008 Betzetal. owe 709/219
`2008/0120129 Al
`5/2008 Seubert etal.
`2008/0127064 Al
`5/2008 Orofino et al.
`2008/0161941 Al
`7/2008 Strassneret al.
`2008/0243449 Al
`10/2008 Feblowitz etal.
`2008/0250390 Al
`10/2008 Feblowitz etal.
`2008/0288595 Al
`11/2008 Liuetal.
`2010/0191521 Al
`7/2010 Huet etal.
`
`OTHER PUBLICATIONS
`
`Riabov et al., “Planning for Stream Processing Systems”, AAAI
`2005, pp. 1-6. (Provided by Applicant).*
`Nagarajan et al., “Semantic Interoperability of Web Services—Chal-
`lenges and Experiences”, 2006, pp. 1-8, accessed online at <http://
`Isdis.cs.uga.edu/library/download/techRep2-15-06.pdf> on Sep. 22,
`2009.*
`Fenselet al., “The Web Service Modeling Framework WSMF”, Elec-
`tronic Commerce Research and Applications 2002, pp. 1-33,
`accessed
`online
`at <http://www.wsmo.org/papers/publications/
`wsmf.paper.pdf> on Sep. 22, 2009.*
`Ankolekar et al., “DAML-S: Semantic Markup for Web Services”,
`2001, pp. 1-20, accessed online at <http://cimic.rutgers.cdu/~
`ahgomaa/mmis/semantic_markup.pdf> on Sep, 22, 2009.*
`Liu et al., “Modeling Web Services using semantic Graph Transfor-
`mation to aid Automatic Composition”, 2007, pp. 1-8, accessed
`online at <http://choices.cs.uiuc.edu/~ranganat/Pubs/ranganathan__
`A_Modeling.pdf> on Sep. 22, 2009.*
`Owenet al., “BPMNand Business Process Management: Introduc-
`tion to the New Business Modeling Standard”, Popkin Software
`2003, pp. 1-27.*
`Martin et al., “Bringing Semantics to Web Services: The OWL-S
`Approach”, SWSWPC 2004, vol. 3387 (2004), 17 pages.*
`Battle, “Boxes: black, white, grey and glass box views of web-
`services”, HPL-2003-30, 2003. 9 pages.*
`
`Lemmenset al., “Semantic Description of Location based Web Ser-
`vices Using an Extensible Location Ontology”, 2004, pp. 261-276.*
`L. Baresi and R. Heckel, Tutorial Introduction to Graph Transforma-
`tion: A Software Engineering Perspective. In Ist Int. Conference on
`Graph Transformation, 2002.
`D. Beradi. D. Calvanese, G. D, Giacomo, R. Hull, and M. Mecella.
`Automatic Composition of Transition-based Semantic Web Services
`with Messaging In VLDB,2005.
`B. Grosof, I. Horrocks, R. Volz and S. Decker. Description Logic
`Programs: Combining Logic Programs with Description Logic. In
`WWw’03.
`Heflin, J. and Munoz-Avila, H. 2002. LCW-Based Agent Planning
`for the Semantic Web in Ontologies and the Semantic Web, 2002
`AAAI Workshop.
`M. Leiarge,Z. Liu, and A. Riabov. Automatic Composition of Secure
`Workflows. In ATC-06, 2006.
`S. Narayanan and S. Mollrath Simulation, Verification and Auto-
`mated Composition of Web Services. In WWW,2002.
`X.T. Nguyen, R. Kowalezyk, and MT. Phan. Modclling and Soliving
`OoS Composition Problem Using Fuzzy DisCSP. In ICWS. 2006.
`J. Pathak, S. Basu and V, Honavar Modelling Web ServicesbyItera-
`tive Reformulation of I'unctional and Non-finctional Requirements.
`In ICSOC, 2006.
`M. Pistore, P. Traverso. P. Bertoll, and A. Marconi. Automated Syn-
`thesis of Composile BPEL4WS Web Services. In ICWS, 2005.
`A. Riabov and Z. Liu. Planning for Stream Processing Systems. In
`AAAI, 2005.
`Sheshagirl, M ; desJardins, M ; and Finin, T. 2003. A Planner for
`Composing Services Described in DAML-S. In Web Services and
`Agent-based Engineering AAMAS’03.
`Traverso, P., and Pistore, M. 2004. Automated Composition of
`Semantic Web Services into Executable Processes. In ISWC’04
`Zhou, J.; Ma, L.; Liu, Q.: Zhang, Li; Yu, Y.; and Pan, Y. 2004.
`Minerva A Scalable OWL Ontology Storage and Interence System.
`In lst Asian Semantic Web Symp.
`Sirin, E., and Persia, B 2004. Planning tor Semantic Web Services. In
`Semantic Web Services Workshop at 3rd ISWC.
`K. Sivashanmugam,J. Miller, A. Sheth, and K. Verma. Framework
`for Semantic Web Process Composition. Special Issue ofthe Interl
`Journal of Electronic Commerce, 2003.
`R. Berbneret al. Heuristics for Qo-S-aware Web Service composi-
`tion. In ICWS2006.
`A. Riabov and Z. Liu Scalable Planning for Distributed Stream
`Processing Systems. In ICAPS, 2006.
`R. Akkiraju et al. Semaplan: Combining planning with semantic
`matching to achieve web service composition. In ICWS, 2006.
`M. Sullivan. Tribeca: A stream database manager for networktraffic
`analysis. In Proc. of the 22nd Intl. Conf. on Very Large Data Bases,
`Sep. 1996.
`J. Ambile and C. Knoblock. Flexible and scalable query planning in
`distributed and heterogeneous environments. In AIPS’98, Jun. 1998.
`H.Wang and C. Zaniolo: ATLaS: A Native Extension of SQL for Data
`Mining and Stream Computations, UCLA CS Dept., Technical
`Report, Aug. 2002.
`M.A. Hammad, W. G. Aref, and A. K. Elmagarmid. Stream window
`join: Tracking moving objects in sensor-network databases. In Proc.
`of the 15th SSDBM Conference, Jul. 2003.
`C, Cranor et al. Gigascope: A stream database for network applica-
`tions. In SIGMOD,2003.
`S. Chandrasekaran et al. ‘lelegraphCQ: Continuous Dataflow Pro-
`cessing for an Uncertain World. CIDR, 2003.
`D. J. Abadi, et al: Aurora: a new model and architecture for data
`stream management. VLDB J. 12(2): 120-139 (2003).
`L’Ecu’E, F., L’Eger, A.: A formal model for semantic web service
`composition. In: ISWC. (2006).
`B. Parsia and E. Sirin. Pellet: An OWL DLreasoner.In the Semantic
`Web—ISWC 2004, 2004.
`N.Jain ct al. Design, implementation, and evaluation of the lincar
`road benchmarkonthe stream processing core. In SIGMOD’06, Jun.
`2006.
`and II.
`J. Blythe, C. Kesselman,
`Y. Gil,, E. Deelman,
`Tangmunarunkit. Artificial intelligence and grids: Workflow plan-
`ning and beyond. IEFE Intelligent Systems, Jan. 2004.
`
`Booking, Exh. 1047, Page 2
`
`Booking, Exh. 1047, Page 2
`
`

`

`US 8,117,233 B2
`Page 3
`
`D. B. Terry et al. Continuous queries over append-only databases. In
`SIGMOD,pp. 321-330, 1992.
`C-N HsuandC .A. Knoblock. Semantic query optimization for query
`plans of helerogeneous mulli-dalabase systems, IEEE Transactions
`on Knowledge and Data Engineering, 12(6):959-978, Nov./Dec.
`2000.
`R. Ginis, R. Strom: An Autonomic Messaging Middleware with
`Stateful Stream Transformation, Proceedings of the International
`Conference on Autonomic Computing (ICAC’04).
`A. Arasu, S. Babu, J. Widom. The CQT. continuous query language:
`Semantic foundations and query execution. Technical Report 2003-
`67, Stanford Lniversity, 2003.
`
`D.J. Abadi et al. The Design of the Borealis Stream Processing
`Engine (CIDR), Jan. 2005, Asilomar, CA.
`H. Knublauch, M. A. Musen, and A. L. Rector. Editing description
`logic ontologies with the protege owl plugin. Whistler, BC, Canada,
`2004.
`M. Stonebraker, U.¢etintemel, S.B. Zdonik: The 8 requirements of
`real-time stream processing. SIGMODRecord 34(4): 42-47 (2005).
`Sv Hashemian, A graph-based. approach to web services composi-
`tion, Proceedings of the 2005 Symposium on Applications and the
`Internet (SAINT ’05), pp. 1-7.
`
`* cited by examiner
`
`Booking, Exh. 1047, Page 3
`
`Booking, Exh. 1047, Page 3
`
`

`

`U.S. Patent
`
`Feb. 14, 2012
`
`Sheet 1 of 5
`
`US 8,117,233 B2
`
`NOsbessayy
`90}S}96|uayeiado89114
`BDIAIBSYOO}S
`
`ebueyoxqwod
`Sule]U0dCn>ulaBessay
`
`JOQWASeyo}g
`
`4901S”
`
`adgseyChuedwog>
`
`__-&adAl1pJI30
`
`
`
`jugwe]ysey
`
`OJUJSOL490}S
`
`arenas)
`
`sule}uoo
`
`
`
`r---H-adAyjp|dwelsauly<>
`
`ada}4p
`
`
`
`
`
`Aoualngu!anjeaAsejouol|odA}}pJ
`
`}ypeasajsibas
`
`Auedwong
`
`
`
`ada}|p
`
`1e}0QSN
`
`aBueuoxgye
`
`afueyoxqwoly
`
`joquiAgiayong
`
`ASAN
`
`edd}Jp
`
`lypelelsibel
`
`JOqUASJa4O11
`
`L‘Sid
`
`Booking, Exh. 1047, Page 4
`
`Booking, Exh. 1047, Page 4
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Feb. 14, 2012
`
`Sheet 2 of 5
`
`US 8,117,233 B2
`
`aBueyoxqwo4ure|Jayolpsey
`|ssaippy|juawa|qsey,alJorgdioy
`inosbessayy|
`Suieyu0dCwa>
`
`—_oei
`
`---
`owen
`
`(1e}U09
`
`Aue
`
`dwio5J0
`
`BDIAJBSOJUAIOD
`
`‘uoleladaQ
`
`
`
`[Jolqduog}eb
`
`“Sul
`
`adA}Jp.
`
`souanbas
`
`
`
`u|abessayy
`
`
`
`ASAN}ypelej}sibe.
`
`éOld
`
`adAyjp
`
`aWeNpslajsiBaysey
`
`ssauppyseu
`
`ada}ps
`
`ad}Jp
`
`Aquaab
`
`Sal
`
`Booking, Exh. 1047, Page 5
`
`Booking, Exh. 1047, Page 5
`
`
`
`
`
`

`

`U.S. Patent
`
`Feb. 14, 2012
`
`Sheet 3 of 5
`
`US 8,117
`
`>
`
`233 B2
`
`ZN
`
`alJOorgdsog
`
`‘uoneiad
`
`“Sul
`
` odd}Jp()edA}}pyCna>BNPelaisiBayseyau
`
`
`SUEHORSWON;Jayat|Seuuae|AquoaipLecoe
`
`aThvaee1sweNICeousnbes))9dA}|
`rosAuedwo9joSul|Ssouppy
`5uolelodiog—
`
`juawelysey—AquaaibAquaai6
`
`NIaseYSul
`
`
`/sseippysey
`
`
`
`ASAN}ypalalsibai
`
`Ve‘SIs
`
`Booking, Exh. 1047, Page 6
`
`INIPe-----LNIA
`
`Booking, Exh. 1047, Page 6
`
`
`

`

`U.S. Patent
`
`Feb. 14, 2012
`
`Sheet 4 of 5
`
`US 8,117,233 B2
`
`
`
`B91qyoo}s}eb
`
`|Bd
`
`adqsey
`
`juswalasey
`
`Auedwoojo
`
`OJUJBII490]
`
`PeIdwejsawil,
`
`gouenbes
`
`Jeyoqsn
`
`Aauaungul
`OnjeAAselouojy
`
`yo0]1S
`
`
`
`}ypele}sibe.
`
`Pv
`
`rex
`adA}pu||
`JOQUIASJEyOLL
`
`ge‘Sls
`
`
`
`
`INCebesseyy
`
`BDIAISSYIOIS
`
`uoleleda
`
`ulabessayy
`
`Suie}uoa<>
`
`Booking, Exh. 1047, Page 7
`
`Booking, Exh. 1047, Page 7
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Feb. 14, 2012
`
`Sheet 5 of 5
`
`US 8,117,233 B2
`
`JSonboy
`
`Uonisodwoy
`----4B9eHa}U|Jes|
`
`—-eeeeeeeee];:uolduosegq
`
`BIIAIES
`
`e- ulewog
`
`Idd$
`
`jauoseaydig
`
`
`
`Joyelaues)-UleWOG
`
`Booking, Exh. 1047, Page 8
`
`Booking, Exh. 1047, Page 8
`
`
`
`
`
`

`

`1
`METHOD AND SYSTEM FOR
`MESSAGE-ORIENTED SEMANTIC WEB
`SERVICE COMPOSITION BASED ON
`ARTIFICIAL INTELLIGENCE PLANNING
`
`RELATED APPLICATIONS
`
`BACKGROUND OF THE INVENTION
`
`1. Technical Field
`
`In an exemplary embodiment of the present invention, a
`method for modeling a web service operation, comprises:
`defining an input message pattern that describes input
`requirements of a web service operation, wherein the input
`messagepattern includesa set of variables representing data
`elements that must be contained in a message input to the web
`This application is related to: commonlyassigned US.
`service operation, and a graph pattern that semantically
`application Ser. No. 11/695,410, filed Apr. 2, 2007, entitled
`describes the data elements that must be contained in the
`“METHOD AND SYSTEM FOR COMPOSING STREAM
`
`message input to the web service operation, and defining an
`PROCESSING APPLICATIONS ACCORDING TO A
`output message pattern that describes an output message of
`SEMANTIC DESCRIPTION OF A PROCESSING GOAL”,
`the web service operation, wherein the output message pat-
`and incorporated by referenceherein in its entirety; and com-
`tern includesa set of variables and exemplars that represent
`monly assigned U.S. application Ser. No. 11/695,349,filed
`data elements contained in the output message, and a graph
`Apr. 2, 2007, entitled “METHOD AND SYSTEM FOR
`pattern that semantically describes the data elements con-
`AUTOMATICALLY
`ASSEMBLING
`PROCESSING
`tained in the output message.
`GRAPHSIN INFORMATION PROCESSING SYSTEMS”,
`Lachofthe variables is a memberofafirst set, wherein the
`and incorporated by reference hercin inits entirety.
`first set is infinite and disjoint from a set of resource descrip-
`tion framework (RDF) terms. A triple pattern is a member of
`a secondset, wherein the secondset includes tuples with three
`fields, wherein first and third fields of the three fields are
`membersofa third set, wherein the third set includes a union
`of the set of RDF termsandthe first set, and a secondfield of
`the three ficlds is a universal resource indicator (URI).
`Each of the graphpatternsis a set of triple patterns. The
`variables of the output message pattern represent data ele-
`ments carried forward from the message input to the web
`service operation. The exemplars represent new objects that
`did not appear in the message input to the web service opera-
`tion. The exemplars are represented as individualsorliterals
`in a web ontology language (OWL).
`In an exemplary embodiment of the present invention, a
`method for composing a workflow made up of web service
`operations, comprises: inputting a plurality of modeled web
`service operations, wherein each of the web service opera-
`tions includes: a pre-defined input message pattern, wherein
`the input message pattern includes a set of variables repre-
`senting data elements that must be contained in a message
`input to the web service operation, and a graph pattern that
`semantically describes the data elements that must be con-
`tained in the message input to the web service operation, and
`a pre-defined output message pattern, wherein the output
`messagepattern includesa set ofvariables and exemplars that
`represent data elements contained in the oulpul message, and
`a graph pattern that semantically describes the data elements
`contained in the output message; inputting a request ofa
`workflow to be composed, wherein the request includes an
`exemplar request message and a response message pattern;
`and composing a workflow in the form of a directed acyclic
`graph (DAG)that has a source vertex, wherein all outgoing
`edges from the source vertex are associated with semantics
`defined in the exemplar request message, and that has a sink
`vertex such that there is a match between exemplar messages
`associated with incoming edges to the sink vertex and the
`response messagepattern.
`The exemplar request message includesa set of data ele-
`ments, and an RDF graphthat semantically describes the data
`elements in the exemplar request message. The RDF graph of
`the exemplar request message includestriples that represent
`facts in OWL. The response message pattern includes a set of
`variables that correspond to data elements that must be
`present in an output of the workflow, and an RDI’ graph
`pattern that semantically describes constraints on values of
`the variables of the response message pattern and relation-
`ships between different variables of the response message
`pattern.
`
`The present invention relates to web service composition,
`and more particularly, to a method and system for message-
`oriented semantic web service compositionbased onartificial
`intelligence planning.
`2. Discussion of the Related Art
`A webservice is a software system designed to support
`interoperable Machine-to-Machine interaction over a net-
`work. Webservices are frequently Web application program-
`ming interfaces (APIs) that can be accessed over a network,
`such asthe Internet, and executed on a remote system hosting
`the requested services.
`An important class of web services consists of those that
`either do data processing or provide information, i.e., they
`take in messages containing input data or information
`requests, process them in some manner, and produce mes-
`sages containing output data or results.
`A challenge for software developers is to allow automatic
`composition of workflows (made up of web services) that
`process, transform or analyze data to produce some desired
`information. In such workflows,
`it
`is necessary to have
`expressive models of messages and of data processing capa-
`bilities of web services to composeservices thal are seman-
`tically compatible and to create workflows that produce the
`desired information.
`Ilowever, many existing service models like OWL-S (as
`described in Martinet al, D. 2004. OWL-S: Semantic markup
`for web services. In W3C Submission) do not allow expres-
`sions with variables in describing inputs and outputs. For
`example, OWL-S describes inputs and outputs using con-
`cepts in an ontology. Similarly to OWT.-S, SA-WSDI, (as
`described in Akkiraju et al, R. 2005. Web service semantics—
`WSDL-S. W3C Submission), which allows linking semantic
`annotations to WSDLfiles, associates inputs and outputs with
`concepts in an ontology.
`During automatic composition of workflows, a planneris
`used to decide which kinds of messages canbe given as input
`toa web service and howitcan construct these messages from
`other messages that have been produced by other web ser-
`vices ina partial plan. A challenge with planning concernsthe
`use of description logic reasoning for checking if two com-
`ponents car be connected. For example, since a planner needs
`to perform a large number of such checks while building a
`plan,this results in a large numberofcalls to areasoner during
`plan-building.
`
`US 8,117,233 B2
`
`2
`SUMMARYOF THE INVENTION
`
`10
`
`15
`
`20
`
`30
`
`35
`
`40
`
`45
`
`5
`
`60
`
`65
`
`Booking, Exh. 1047, Page 9
`
`Booking, Exh. 1047, Page 9
`
`

`

`US 8,117,233 B2
`
`3
`Each vertex apart from the source and sink vertices is one
`of the modeled web service operations. For each vertex rep-
`resenting a web service operation in the workflow there is a
`match between exemplar messagesassociated with incoming
`edges to the vertex and the input message pattern of the web
`service operation. The match between exemplar messages
`associated with incoming edges to the vertex and the input
`message pattern of the web service operation exists when
`there is a substitution of variables defined in the input mes-
`sage pattern suchthat: the exemplar messages includeatleast
`all the data elements that must be contained in the message
`input to the web service operation; and an RDF graph
`obtainedafter substituting variables in the input graph pattern
`can be logically inferred from a union of RDF graphsin the
`exemplar messages. The logic inference is based ona descrip-
`tion logic process.
`A match between exemplar messages associated with
`incoming edgesto the sink vertex and the response message
`pattern of the workflow exists when there is a substitution of
`variables defined in the input message pattern such that: the
`exemplar messagesincludeatleast all the data elements that
`must be contained in a response message defined in the
`response messagepattern of the workflow, and an RDF graph
`obtained after substituting variables in the graph pattern that
`is part of the response message pattern can be logically
`inferred from a union of RDF graphs in the exemplar mes-
`sages.
`In an exemplary embodiment of the present invention, a
`planner for composing a workflow made up of web service
`operations, comprises: a domain-generator for receiving, a
`plurality ofmodeled webservice descriptions, translating the
`webservice descriptions into a stream processing planning
`language (SPPL), and during the translation, performing
`description logic program (DLP) reasoning on output mes-
`sage graph patterns of the web service descriptions, and stor-
`ing the translated and reasoned webservice descriptions in an
`SPPL domain; anda plan-builder for receiving a composition
`request, translating the composition request into a planning,
`goal, and producing a workflowby recursively connecting
`webservice operations to one another based on their web
`service descriptions stored in the SPPL domain until a goal
`messageis produced.
`‘The DLPreasoning is performed only once for each web
`service operation in an offline manner. The plan-builder
`checks graph-embedding relationships between the input
`message graphpattern and a union of RDF graphs in exem-
`plar messages when producing the workflow.
`The plan-builder operates in a pre-solve phase and a plan
`search phase, wherein in the pre-solve phasethe plan builder
`removes sources that cannot contribute to the goal and trans-
`lates predicate formulation into a propositional formulation,
`wherein in the plan search phase the plan-builder performs a
`branch-and-bound search of the web service descriptions
`stored in the SPPL domain.
`In an exemplary embodiment of the present invention, a
`computer program product comprises a computer useable
`medium having computer program logic recorded thereon for
`modeling a web service composition, the computer program
`logic comprising: program code for defining an input mes-
`sage pattern that describes input requirements of a web ser-
`vice operation, wherein the input message pattern includes a
`set of variables representing data elements that must be con-
`tained in a message inputto the web service operation, and a
`graph pattern that semantically describes the data elements
`that must be contained in the message inputto the web service
`operation; and programcode for defining an output message
`pattern that describes an output message of the web service
`
`4
`operation, wherein the output message pattern includesa set
`of variables and exemplars that represent data elements con-
`tained in the output message, and a graphpattern that seman-
`tically describes the data elements contained in the output
`message.
`The foregoing [features are of representative embodiments
`and are presented to assist in understanding the invention.It
`should be understoodthat they are not intended to be consid-
`ered limitations on the inventionas defined by the claims, or
`limitations on equivalents to the claims. Therefore, this sum-
`mary of features should not be considered dispositive in
`determining equivalents. Additional features ofthe invention
`will become apparent in the following description, from the
`drawings and from the claims.
`
`
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`
`
`FIG. 1 illustrates a semantic description of a web service
`operation according to an exemplary embodiment of the
`present invention;
`T'IG. 2 illustrates a semantic description of another web
`service operation according to an exemplary embodiment of
`the present invention:
`FIGS.3A and 3B illustrate how the semantic descriptions
`of the web service operations shownin FIGS. 1 and 2 change
`as a result of composing the web service operations into a
`workflow according to an exemplary embodiment of the
`present invention; and
`FIG.4 illustrates a semantic planner according to an exem-
`plary embodimentof the present invention.
`
`DETAILED DESCRIPTION OF EXEMPLARY
`
`
`LEMBODIMINTS
`
`40
`
`45
`
`5
`
`In accordance with an exemplary embodiment of the
`present invention, a model of associating rich semantic infor-
`mation with messages consumed and produced by web ser-
`vices is provided. The model describes input message
`requirements and an output message specification of each
`webservice operation using resource description framework
`(RDF) graph patterns. The terms used in these patterns are
`defined in web ontology language (OWL) ontologies that
`describe the application domain.
`Bydeveloping this model, automatic composition ofwork-
`flows that process, transform or analyzedata to produce some
`desired information is enabled. The model provides rich
`descriptions ofthe inputs and outputs of web service opera-
`tions. This allows us to compare the semantics of the data
`producedas output byone or more operations and the seman-
`tics of the data required as input by another operation and
`decide if the two are compatible. The semantics-based com-
`parability is better than a plain syntactic check and can help
`verify the semantic composability of two services.
`The model provides both a workflow-independent and a
`workflow-dependent description of a web service operation.
`The workflow-independent description provides the minimal
`conditions that mustbe satisfied by the data provided as input
`to the operation, and the minimal conditions that will be
`satisfied by the data produced as output. In a given workflow,
`however, the actual data provided as input may have addi-
`tional semantic constraints depending on the semantics ofthe
`data produced by previous services in the workflow. The
`actual data produced as output may similarly have additional
`constraints. Hence, the workflow-dependent description is a
`specialization of the workflow-independent description tak-
`ing into account the actual semantics ofthe data given as input
`to the operation.
`
`Booking, Exh. 1047, Page 10
`
`Booking, Exh. 1047, Page 10
`
`

`

`US 8,117,233 B2
`
`5
`Akeyaspect of the modelis the notion of semantic propa-
`gation, i.e., the semantic description ofthe output message of
`an operation dependson the semantics of the input message,
`which in turn depends on the semantics of the previous mes-
`sage in the workflow, and so forth. In order to model semantic
`propagations, we model operations using graph transforma-
`tions (as describedin L. Baresi and R. [eckel. Tutorial intro-
`duction to graph transformation: A software engineering per-
`spective. In 1°” Int. Conference on Graph Transformation,
`2002, a copy of whichis incorporated by reference herein in
`its entirety). The graph transformations allowreplacing vari-
`ables in the RDF graph pattern describing the output message
`with either single values or entire sub-graphs based on the
`actual semantics of the input message.
`Onedifference between our model and other semantic web
`service models like OWL-S and SA-WSDLthat describe or
`
`associate input and outputs using concepts in an ontology, is
`that our model describes input and output messages in terms
`of RDF graph patterns based on data instances that appear in
`these messages. Our approach allows associating constraints
`on these instances based on both the concepts(or classes) they
`belong to and their relationships to other instances. Such
`constraints are more difficult to express in pure concept-based
`representations and often require the creation of a large num-
`ber of additional concepts corresponding to different combi-
`nations of constraints.
`In addition,
`the instance-based
`approachalso allows describing messages of complex types
`such as sequences, and associating rich semantics with the
`elements within the complex type. As a result, our model
`allows associating rich semantic information aboutservices,
`which aids the automatic composition of workflows that
`involve data processing and data transformation.
`Another difference between our model and existing mod-
`els like OWL-S and SA-WSDLisin the use of variables. For
`example, existing models do not allow expressions with vari-
`ables for describing inputs and outputs. Our model describes
`inputs and outputs using graph patterns, which can be con-
`sidered as logical expressions with variables. The use of
`variables allows our modelto relate the semantics of outputs
`to the semantics of inputs. WSML(as described in de Bruijn.
`The Web Service Modeling Language WSML. http://www.
`wsmo.org/wsml/, 2005) also allows specifying axioms with
`variables in the pre- and port-conditions of a service capabil-
`ity. However, it does not have an explicit model of messages,
`which is necessary to determine if certain messages can be
`given as input to an operation. Our model explicitly defines
`the elements in a message and describes the semantics of
`these elements using an RDI graph consisting of OWL ABox
`assertions. This feature is useful during composition by arti-
`ficial intelligence (AI) planning, when the planner needs to
`decide what kind of messages can be given as input to an
`operation and howit can construct these messages fromother
`messagesthat have been produced so far by other operations
`in a partial! plan.
`Based on our model, we define the conditions under which
`webservices can be connected to one another in a workflow.
`In accordance with another exemplary embodiment of the
`present invention, we have also developed a plannerthat can
`automatically build workflows given a user requirement in
`terms ofa high-level web service whose inputs and outputs
`are also expressed as RDF graph patterns. The resulting work-
`
`flow is represented in Business Process Execution Language
`
`(BPEL) and describes a directed acyclic graph (DAG) of
`services that can be invoked to perform the tasks required.
`The planner incorporates reasoning based on Description
`Logie Programs (DLP) (as described in B. Grosof, I. Hor-
`rocks, R. Volz, and S. Decker. Description logic programs:
`
`6
`combining logic programs with description logic. In WWW
`*03, a copy of whichis incorporated by reference hereininits
`entirety) in building plans. Oneofthe features of the planner
`is the use of a two-phase approach, where pre-reasoning is
`performed on componentdescriptions and the results of the
`reasoning are then reused when generating plans fordifferent
`user goals.
`A description of exemplary embodiments of the present
`invention will now be provided in further detail under the
`following headings: Model ofWeb Services, Composing Ser-
`vices inlo Workflows; The Semantic Planner, and Evaluation.
`Model