On the aggregation problem for synthesized web services

Ting Deng, Wenfei Fan, Leonid Libkin, Yinghui Wu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

The paper formulates and investigates the aggregation problem for synthesized mediators of Web services (SWMs). An SWM is a finite-state transducer defined in terms of templates for component services. Upon receiving an artifact, an SWM selects a set of available services from a library to realize its templates, and invokes those services to operate on the artifact, in parallel; it produces a numeric value as output (e.g., the total price of a package) by applying synthesis rules. Given an SWM, a library and an input artifact, the aggregation problem is to find a mapping from the component templates of the SWM to available services in the library that maximizes (or minimizes) the output. As opposed to the composition syntheses of Web services, the aggregation problem aims to optimize the realization of a given mediator, to best serve the users' need. We analyze this problem, and show that its complexity depends on the underlying graph structure of the mediator: while it is undecidable when such graphs contain even very simple cycles, it is solvable in single-exponential time (in the size of the specification) for SWMs whose underlying graphs are acyclic. We prove several results of this kind, with matching lower bounds (NP and PSPACE), and analyze restrictions that lead to polynomial-time solutions.
Original languageEnglish
Title of host publicationDatabase Theory - ICDT 2010, 13th International Conference, Lausanne, Switzerland, March 23-25, 2010, Proceedings
Number of pages10
ISBN (Print)978-1-60558-947-3
Publication statusPublished - 2010


Dive into the research topics of 'On the aggregation problem for synthesized web services'. Together they form a unique fingerprint.

Cite this