USOO8117233B2
`
`(12) United States Patent
`US 8,117,233 B2
`(10) Patent N0.:
`Liu et a].
`(45) Date of Patent:
`*Feb. 14, 2012
`
`(54)
`
`lVIETHOD AND SYSTEM FOR
`MESSAGE-ORIENTED SEMANTIC WEB
`SERVICE COMPOSITION BASED ON
`ARTIFICIAL INTELLIGENCE PLANNING
`
`(75)
`
`Inventors: Zhen Liu, Tarrytown, NY (US); Anand
`Ranganathan, White Plains, NY HIS);
`Anton V. Riabov, Ossining, NY (US)
`
`(73)
`
`Assignee:
`
`International Business Machines
`Corporation, Armonk, NY (US)
`
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`use. 154(b) by 504 days.
`
`This patent is subject to a terminal dis-
`claimer.
`
`(21)
`
`Appl. N0.: 11/748,216
`
`(22)
`
`Filed:
`
`May 14, 2007
`
`(65)
`
`Prior Publication Data
`
`US 2008/0288595 A1
`
`Nov. 20, 2008
`
`Int. Cl.
`(2006.01)
`G06F 7/00
`US. Cl.
`........................................ 707/802; 707/608
`Field of Classification Search ........... 707/999.007,
`707/802, 608
`See application file for complete search history.
`
`References Cited
`
`U. S. PATENT DOCUMENTS
`
`5,675,786 A
`6,086,619 A *
`6,523,174 B1*
`6,640,231 B1
`6,742,054 B1*
`7,016,910 B2
`7,505,989 B2
`7,577,554 B2 *
`
`10/1997 McKee el al.
`................. 703/6
`7/2000 Hausman et al.
`2/2003 Gould et al.
`.................. 717/162
`10/2003 Andersen et al.
`5/2004 Upton, IV ......................... 710/6
`3/2006 Egilsson et a1.
`3/2009 Gardner et al.
`8/2009 Lystad et a1.
`...................... 703/2
`
`7,665,064 B2 *
`7,716,272 B2 *
`7,739,351 B2 '“"
`7,877,421 B2
`7,904,545 B2
`2003/0055668 A1 *
`2003/0120642 A1
`2003/0135628 A1 *
`2003/0142818 A1
`2004/0024841 A1 ""
`2004/0073545 A1 *
`
`.................... 717/117
`2/2010 Able et al.
`5/2010 Skwarek et al.
`..
`.. 709/201
`
`6/2010 Shkvarchuk et al.
`......... 709/217
`1/2011 Berger et a1.
`3/2011 Golovchinsky et al,
`3/2003 Saran et a1,
`....................... 705/1
`6/2003 Egilsson et a1.
`............... 709/229
`7/2003 Pletcher et a1.
`7/2003 Raghunathan et al.
`2/2004 Becker et a1,
`................. 709/219
`4/2004 GreenblaLt et al.
`............... 707/3
`
`(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 7 Hung T Vy
`Assistant Examiner
`Phuong Thao Cao
`(74) Attorney, Agent, orFirm 7 William J. Stock; F. Chan &
`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 includes a 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 includes a set of variables and exemplars that represent
`data elements contained in the output message, and a graph
`pattern that semantically describes the data elements con-
`tained in the output message.
`
`17 Claims, 5 Drawing Sheets
`
`
`
`
`
`dft
`
`
`
`
`ype
`
`
`7Cotm an
`
`
`'
`p
`y
`
`
`registered,“
`
`(Ticker
`
`/
`\
`Co
`dfl
`
`1
`
`
`
`
`
`StockServiee
`
`
`Message Out
`Message 1n
`Operation:
`
`
`getSlockPrlce
`
`contains
`
`
`_TimeStamp I
`
`[TH-Tl
`
`A---
`
`N. _m:
`- — —
`at
`r
`ype \
`Com an
`\
`hasPrice
`Pm
`:
`—5109k
`hasMonVal
`
`”1‘ type
`/' Monetar Value
`,
`
`
`/ / y
`nCurrency
`?Company
`atExchange
`,
`USDollar
`
`
`
`
`\reglsteredAt\
`flkerSymbol
`‘7— ,d1 We tickerOf \ NYSE
`
`
`/
`
`7tickersymbo/
`tromExmenge
`
`
`
`Page 1 of 17
`
`GOOGLE EXHIBIT 1021
`
`Page 1 of 17
`
`GOOGLE EXHIBIT 1021
`
`

`

`US 8,117,233 B2
`
`Page 2
`
`..................... 707/3
`
`U.S. PATENT DOCUMENTS
`2004/0073661 A1 *
`4/2
`4 Eibach et a1.
`................. 709/224
`2004/0111533 A1*
`6/2
`4 Beisiegel et al.
`............. 709/246
`2004/0138936 A1
`7/2
`4 Johnson et a1.
`2004/0148214 A1*
`7/2
`4 Aziz et al.
`......................... 705/8
`2004/0162741 A1
`8/2
`4 Flaxer et al.
`2005/0021548 A1
`1/2
`5 Bohannon et a1.
`2005/0021745 A1
`1/2
`5 Bookrnan etal.
`2005/0044525 A1*
`2/2
`5 Lazarov .................... 717/104
`2005/0055330 A1*
`3/2
`5 Britton et a1.
`707/1
`
`............ 345/589
`2005/0093881 A1*
`5/2
`5 Okita etal.
`
`2005/0114757 A1
`5/2
`5 Sahota et al.
`2005/0289134 A1 *
`12/2
`5 Noguchi
`........................... 707/4
`2006/003 [288 A l *
`2/2
`6 Ter Horst et al.
`1111111111111 709/204
`2006/0036983 A1*
`2/2
`6 Iwashita ........................... 716/5
`2006/0053172 A1
`3/2
`6 Gardner et al.
`2006/0167856 A1*
`7/2
`6 Angele et a1.
`2006/0167946 A1
`7/2
`6 Hellman et a1.
`
`2006/0173868 A1*
`8/2
`6 Angele et a1.
`707/100
`
`2006/0195332 A1*
`8/2
`6 Bogner et al.
`705/1
`2006/0195463 A1 *
`8/2
`6 Bogner et al.
`................ 707/101
`2006/020025l A 1
`9/2
`6 Gu et al.
`2006/0212855 A1 ’1
`9/2
`6 Bournas etal.
`.. 717/140
`2006/0236306 A1* 10/2
`6 DeBruin et al.
`717/113
`
`2007/0021995 A1*
`1/2
`7 Toklu et al.
`....................... 705/7
`2007/0023515 A1
`2/2
`7 Urkcn
`2007/0043803 A1
`2/2
`7 Whitehouse et al.
`2007/0050227 A1*
`3/2
`7 Teegan et al.
`..................... 705/8
`2007/0078815 A1
`4/2
`7 Weng et al
`2007/0156430 A1
`7/2
`7 Kaetker et al.
`2007/0162893 A1
`7/2
`7 Moosmann et a1.
`2007/0168303 A1
`7/2
`7 Moosrnann et a1.
`2007/0174811 A1
`7/2
`7 Kaetker et al.
`2007/0179826 A1
`8/2
`7 Cutlip et al.
`2007/0186209 A1
`8/2
`7 Kaetker et al.
`2007/0198971 A1
`8/2
`7 Dasu et a1.
`2007/0220046 A1
`9/2
`7 Moosmann et a1.
`.......... 709/223
`2007/0245013 A1 *
`10/2
`7 Saraswathy et al.
`2007/0265862 A1
`11/2
`7 Freund et a1.
`2007/0288250 A1* 12/2
`7 Lerncke et al.
`................... 705/1
`2008/0005155 A1*
`1/2
`8 Soma et al.
`707/102
`2008/0005278 A1*
`1/2
`8 Betz et al.
`............ 709/219
`2008/0120129 A1
`5/2
`8 Seubert et al.
`2008/0127064 A1
`5/2
`8 Orofino et al.
`2008/0161941 A1
`7/2
`8 Strassner et a].
`2008/0243449 A1
`10/2
`8 Feblowitz et a1.
`2008/0250390 A1
`10/2
`8 Feblowitz et a1.
`2008/0288595 A1
`11/2
`8 Liu et al.
`2010/0191521 A1
`7/2 10 Huet et al.
`
`.
`
`
`
`
`
`OTHER PUBLICATIONS
`
`Riabov et al., “Planning for Stream Processing Systems”, AAAI
`2005, pp. 1-6. (Provided by Applicant).*
`N agarajan et al., “Semantic Interoperability of Web Services%hal-
`lenges and Experiences”, 2006, pp. 1-8, accessed online at <http://
`lsdis.cs.uga.edu/library/download/techRep2—15-06.pdi> on Sep. 22,
`2009*
`Fensel et 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.pdt> on Sep. 22, 2009*
`Ankolekar et al., “DAML—S: Semantic Markup for Web Services”,
`2001, pp. 1-20, accessed online at <http://cimic.rutgers.edu/~
`ahgornaa/mrnis/sernanticirnarkuppdt‘z 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,
`AiModelingpdb on Sep. 22, 2009*
`Owen et al., “BPMN and 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.*
`
`Page 2 of 17
`
`Lernnrens et 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 1st 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 V012 and S. Decker. Description Logic
`Programs: Combining Logic Programs with Description Logic. In
`WVVW’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. andA. Riabov. Automatic Composition of Secure
`VVorkflows. 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. Modelling and Soliving
`OoS Composition Problem Using Fuzzy DisCSP. In ICWS. 2006.
`J. Pathak, S. Basu and V. Honavar Modelling Web Services by Itera-
`tive Reformulation of Functional and Non-finctional Requirements.
`In ICSOC, 2006.
`M. Pistore, P. Traverso. P. Bertoll, and A. Marconi. Automated Syn-
`thesis of Composite 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 1st Asian Semantic Web Symp.
`Sirin, E., and Persia, B 2004. Planning for 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 of the Interl
`Journal of Electronic Commerce, 2003.
`R. Berbner et a1. Heuristics for Qo—S-aware Web Service composi—
`tion. In ICWS 2006.
`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 network traffic
`analysis. In Proc. of the 22nd Intl. Conf. on Very Large Data Bases,
`Sep. 1996.
`J. Ambite 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, andA. K. Elrnagarrnid. Stream window
`join: Tracking moving objects in sensor-network databases In Proc.
`ofthe 15th SSDBM Conference, Jul. 2003.
`C, Cranor et a1. Gigascope: A stream database for network applica-
`tions. In SIGIVIOD, 2003.
`'I'elegraphCQ: Continuous Dataflow Pro-
`S. Chandrasekaran et a1.
`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’Eeu’E, F., L’Eger, A.: A formal model for semantic web service
`composition. In: ISW'C. (2006).
`B. Parsia and E. Sirin. Pellet: An OWL DL reasoner. In the Semantic
`WebiISVVC 2004, 2004.
`N. Jain et al. Design, implementation, and evaluation of the linear
`road benchmark on the stream processing core. In SIGMOD’06, Jun.
`2006.
`and II.
`J. Blythe, C. Kesselman,
`Y. Gil,, E. Deelman,
`Tangrnunarunkit. Artificial intelligence and grids: Workflow plan-
`ning and beyond. IEEE Intelligent Systerrrs, Jan. 2004.
`
`Page 2 of 17
`
`

`

`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 Hsu andC .A. Knoblock. Semantic query optimization for query
`plans of heterogeneous mulLi-database 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 CQI, continuous query language:
`Semantic foundations and query execution. Technical Report 2003-
`67, Stanford University, 2003.
`
`D]. 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. \Vhistler, BC, Canada,
`2004.
`M. Stonebraker, Ucetintemel, S.B. Zdonik: The 8 requirements of
`real—time stream processing. SIGMOD Record 34(4): 4247 (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
`
`Page 3 of 17
`
`Page 3 of 17
`
`

`

`US. Patent
`
`Feb. 14, 2012
`
`Sheet 1 0f 5
`
`us 8,117,233 32
`
`.2...I.I.I83?
`
`Sgootaxoeml>
`
`6%:@5on
`
`_metal
`
`moramm;gImw>z
`|lI..I83::g
`
`@820meth
`
`mmcmgoxmfi
`
`
`
`3:930;m2m>>§oco§83E
`
`EvEBmBE
`
`33”PE
`
`
`
`maggomeo:_8E>m$v_o:m
`
`85:2
`
`233668
`
`Encamaxo:
`
`_‘.OE
`
`50@3322
`528.80E@9382
`
`25:8
`
`25:8%
`
`mBwaxoon
`
`mocmfiemfio
`
`
`
`Page 4 of 17
`
`Page 4 of 17
`
`
`
`
`
`
`

`

`s”U
`
`1
`
`0
`
`e
`
`us 8,117,233 32
`
`1lIIn]\quEoEO_mmeugAEmEoEmm;HIIIIIIV
`“amEoEeool
`
`
`M_.||Hl\v‘82::
`
`%e
`
`.mwe:9;:amwEszEmammmm;
`
`$235225:8
`
`
`
`mw>z23.8208
`
`
`
`mcmfimeoc$3652a$520
`
`N.w_..._
`
`
`
`m59:82:2;985025:8e”:2$8m:629382-gammesfimooE23392PImwz
`
`
`
`Page 5 of 17
`
`Page 5 of 17
`
`
`

`

`7118,
`
`9
`
`233 B2
`
`<m.OE
`
`
`
`wmw>z235368
`
`\\m2..25be
`
`
`
`mmcmcoxmegSign;a£52m
`
`U
`
`29:00am”cozfimqomQS”mg
`tamLEmEooEcoiasofimmEmEoO
`
`
`M$52832318;%e
`
`
`
`0.l.III.I.2‘3:363320M,
`
`
`.cmEoEmS1IIIII...>cquoEoan_$052
`
`3358001:|m‘352Em.....Em
`
`Page 6 of 17
`
`Page 6 of 17
`
`
`

`

`US. Patent
`
`Feb. 14, 2012
`
`Sheet 4 0f 5
`
`us 8,117,233 32
`
`_gemfiwmafil
`
`_85:35
`
`33:2
`
`EmEmmwm;
`
`@9583
`
`8585288.!
`
`So@3322
`
`
`
`mEmEoo
`
`835.28%
`
`“:0szon
`
`mozngoeflma
`
`
`25:50EEmammmmE
`
`._m=oom:
`
`85mm;
`
`
`
`5:2505magaflmcos.
`
`x0055:
`
`
`
`23$meme
`
`.193:1
`
`A62
`35”PE__
`2&9me
`
`3:36
`
`Page 7 of 17
`
`mo;
`
`
`
`j:1.|.I..l.I.I.J
`
`mmd.“—
`
`Page 7 of 17
`
`
`
`
`
`
`
`
`
`

`

`US. Patent
`
`Feb.14,2012
`
`Sheet50f5
`
`us 8,117,233 32
`
`1|
`
`52601a
`
`moEmm
`
`...................cozqcommo
`
`Page 8 of 17
`
`\
`
`.Eam
`
`EmEoo
`
`
`
`meommmmnin—
`
`Page 8 of 17
`
`
`
`

`

`US 8,117,233 B2
`
`1
`METHOD AND SYSTEM FOR
`MESSAGE-ORIENTED SEMANTIC WEB
`SERVICE COMPOSITION BASED ON
`ARTIFICIAL INTELLIGENCE PLANNING
`
`RELATED APPLICATIONS
`
`This application is related to: commonly assigned US.
`application Ser, No. 11/695,410, filed Apr. 2, 2007, entitled
`“MET {OD AND SYSTEM FOR COMPOSING STREAM
`
`PROCESSING APPLICATIONS ACCORDING TO A
`SEIVIANTIC DESCRIPTION OF A PROCESSING GOAL”,
`and incorporated by reference herein in its entirety; and com-
`monly assigned US. application Ser. No. 11/695,349, filed
`Apr. 2, 2007, entitled “METHOD AND SYSTEM FOR
`AUTOMATICALLY
`ASSEMBLING
`PROCESSING
`GRAPHS IN INFORIVIATION PROCESSING SYSTEMS”,
`and incorporated by reference herein in its entirety.
`
`BACKGROU \]
`
`) OF THE INVENTION
`
`1. Technical Field
`
`The present invention relates to web service composition,
`and more particularly, to a method and system for message-
`oriented semantic web service composition based 011 artificial
`intelligence planning.
`2. Discussion of the Related Art
`A web service is a software system designed to support
`interoperable Machine-to-Machine interaction over a net-
`work. Web services are frequently Web application program-
`ming interfaces (APIs) that can be accessed over a network,
`such as the 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 infonnation
`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 compose services that are seman-
`tically compatible and to create workflows that produce the
`desired information.
`However, many existing service models like OWL-S (as
`described in Martin et a1, 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 OWL-S, SA-WSDI, (as
`described inAkkiraju et a1, R. 2005. Web service semanticsi
`WSDL-S. W3C Submission), which allows linking semantic
`annotations to WSDL files, associates inputs and outputs with
`concepts in an ontology,
`During automatic composition of workflows, a planner is
`used to decide which kinds of messages can be given as input
`to a web service and how it can construct these messages from
`other messages that have been produced by other web ser-
`vices in a partial plan. A challenge with planning concerns the
`use of description logic reasoning for checking if two com-
`ponents carbe connected. For example, since a planner needs
`to perform a large number of such checks while building a
`plan, this results in a large number ofcalls to a reasoner during
`plan-building.
`
`10
`
`15
`
`20
`
`30
`
`35
`
`40
`
`45
`
`60
`
`65
`
`2
`SUMMARY OF THE INVENTION
`
`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
`message pattern includes a 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 includes a set of variables and exemplars that represent
`data elements contained in the output message, and a graph
`pattern that semantically describes the data elements con-
`tained in the output message.
`Each ofthe variables is a member of a first set, wherein the
`first set is infinite and disjoint from a set of resource descrip-
`tion framework (RDF) terms. A triple pattern is a member of
`a second set, wherein the second set includes tuples with three
`fields, wherein first and third fields of the three fields are
`members of a third set, wherein the third set includes a union
`of the set of RDF terms and the first set, and a second field of
`the three fields is a universal resource indicator (URI).
`Each of the graph patterns is 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 individuals or literals
`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 pattem, 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
`message pattern includes a set ofvariables and exemplars that
`represent data elements contained in the output message, and
`a graph pattern that semantically describes the data elements
`contained in the output message; inputting a request of a
`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 message pattern.
`The exemplar request message includes a set of data ele-
`ments, and an RDF graph that semantically describes the data
`elements in the exemplar request message. The RDF graph of
`the exemplar request message includes triples 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 RDF 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.
`
`Page 9 of 17
`
`Page 9 of 17
`
`

`

`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 messages associated 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 ines-
`sage pattern such that: the exemplar messages include at least
`all the data elements that must be contained in the message
`input to the web service operation; and an RDF graph
`obtained after substituting variables in the input graph pattern
`can be logically inferred from a union of RDF graphs in the
`exemplar messages. The logic inference is based on a descrip-
`tion logic process.
`A match between exemplar messages associated with
`incoming edges to 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 messages include at least all the data elements that
`must be contained in a response message defined in the
`response message pattern 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 web service descriptions, translating the
`web service descriptions into a stream processing planning
`language (SPPL), and during the translation, performing
`description logic program (DLP) reasoning on output ines-
`sage graph patterns of the web service descriptions, and stor-
`ing the translated and reasoned web service descriptions in an
`SPPL domain; and a plan-builder for receiving a composition
`request, translating the composition request into a planning
`goal, and producing a workflow by recursively connecting
`web service operations to one another based on their web
`service descriptions stored in the SPPL domain until a goal
`message is produced.
`The DLP reasoning is performed only once for each web
`service operation in an offline manner. The plan-builder
`checks graph-embedding relationships between the input
`message graph pattern 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 phase the 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 ines-
`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 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 program code for defining an output message
`pattem that describes an output message of the web service
`
`10
`
`15
`
`20
`
`30
`
`35
`
`40
`
`45
`
`60
`
`65
`
`Page 10 of 17
`
`4
`operation, wherein the output message pattern includes a set
`of variables and exemplars that represent data elements con—
`tained in the output mes sage, and a graph pattern 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 understood that they are not intended to be consid—
`ered limitations on the invention as 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;
`FIG. 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 shown in 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 embodiment of the present invention.
`
`DETAILED DESCRIPTION OF EXEMPLARY
`
`
`EMBODIMENTS
`
`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
`web service 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.
`By developing this model, automatic composition ofwork-
`flows that process, transform or analyze data to produce some
`desired information is enabled. The model provides rich
`descriptions of the inputs and outputs of web service opera—
`tions. This allows us to compare the semantics of the data
`produced as output by one 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 oftwo services.
`The model provides both a workflow-independent and a
`workflow-dependcnt description of a web service operation.
`The workflow-independent description provides the minimal
`conditions that must be 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.
`
`Page 10 of 17
`
`

`

`US 8,117,233 B2
`
`5
`A key aspect of the model is the notion of semantic propa-
`gation, i.e., the semantic description ofthe output message of
`an operation depends on the semantics of the input message,
`which in turn depends on the semantics of the previous ines-
`sage in the workflow, and so forth. In order to model semantic
`propagations, we model operations using graph transforrna—
`tions (as described in L. Baresi and R. IIeckel. Tutorial intro-
`duction to graph transformation: A software engineering per-
`spective. In 15’ Int. Conference on Graph Transformation,
`2002, a copy of which is incorporated by reference herein in
`its entirety). The graph transformations allow replacing 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.
`One difference between our model and other semantic web
`service models like OWL-S and SA-WSDL that 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 diflicult 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
`approach also 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 about services,
`which aids the automatic composition of workfiows that
`involve data processing and data transformation.
`Another difference between our model and existing mod-
`els like OWL-S and SA-WSDL is in 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 model to 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 RDF 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 how it can construct these mes sages from other
`messages that have been produced so far by other operations
`in a partial plan.
`Based on our model, we define the conditions under which
`web services can be connected to one another in a workflow.
`In accordance with another exemplary embodiment of the
`present invention, we have also developed a planner that can
`automatically build workflows given a user requirement in
`terms of a 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
`Logic Programs (DLP) (as described in B. Grosof, I. Hor—
`rocks, R. Volz, and S. Decker. Description logic programs:
`
`10
`
`15
`
`20
`
`30
`
`35
`
`40
`
`45
`
`60
`
`65
`
`6
`combining logic programs with description logic. In WWW
`’03, a copy of which is incorporated by reference herein in its
`entirety) in building plans. One of the features of the planner
`is the use of a two-phase approach, where pre—reasoning is
`performed on component descriptions and the results of the
`reasoning are then reused when generating plans for different
`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 into Workllows; The Semantic Planner, and Evaluation.
`Model of Web Services
`
`In our model, web service operations are described by the
`kinds of messages the