Yu / Bouguettaya Foundations for Efficient Web Service Selection

1. Auflage 2009
ISBN: 978-1-4419-0314-3
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 160 Seiten

Foundations for Efficient Web Service Selection describes the foundational framework for efficient Web service selection. It lays out a theoretical underpinning for the design of models and algorithms for searching and optimizing access to Web services. Excerpts from Prof. Fabio Casati's foreword: ' This excellent book looks at the search problem from a broader perspective. Instead of narrowing down on a specific aspect or subproblem of service search, it dissects and analyzes the fundamental problems in search and presents concrete, applicable solutions as well as the theoretical foundations behind them...One aspect I found particularly significant in the book is the mind shift it generates from thinking about service modeling for the sake of supporting deployment or invocation to modeling for supporting search. This design for search approach is exactly what we do when we design databases because search is what we worry about in that case, and there is no reason why this shouldn't be the case for services if we want services to be searchable with a similar effectiveness.'

Autoren/Hrsg.

Yu, Qi

Bouguettaya, Athman

Inhaltsverzeichnis

1;Foreword;5
2;Preface;7
3;Acknowledgements;9
4;Contents;10
5;Introduction;13
5.1;1.1 Web Service Foundation;14
5.1.1;1.1.1 Historical Perspective;14
5.1.2;1.1.2 Web Services vs. Data;16
5.1.3;1.1.3 Service Query Optimization;16
5.2;1.2 Major Issues in Building a Web Service Foundation;17
5.2.1;1.2.1 Summary of Contributions;20
5.3;1.3 Preview of Chapters;22
6;Towards a WSMS: The State of the Art;23
6.1;2.1 Scenario;24
6.2;2.2 Web Service Reference Model;25
6.3;2.3 Web Service Stack;26
6.4;2.4 Key Dimensions for Building a WSMS;27
6.5;2.5 The WSMS Architecture;31
7;A Foundational Service Framework;36
7.1;3.1 Case Study: Car Brokerage;37
7.2;3.2 Service Query Model;38
7.3;3.3 Service Calculus;45
7.4;3.4 Service Query Algebra;47
7.4.1;3.4.1 Algebraic Operators;48
7.4.1.1;3.4.1.1 F-map;48
7.4.1.2;3.4.1.2 Q-Select;49
7.4.1.3;3.4.1.3 Compose;49
7.4.2;3.4.2 Algebraic Equivalent Rules;51
7.5;3.5 Implementing the Algebraic Operators;52
7.5.1;3.5.1 Storing the Service Relations;52
7.5.2;3.5.2 Implementing the Service Algebra;53
7.5.2.1;3.5.2.1 F-map;53
7.5.2.2;3.5.2.2 Q-select;54
7.5.2.3;3.5.2.3 Compose;54
7.5.3;3.5.3 Complexity of Service Algebraic Operators;55
7.5.4;3.5.4 Generating SEPs;57
7.6;3.6 Service Query Optimization;60
7.6.1;3.6.1 QoWS for SEPs;60
7.6.2;3.6.2 Score Function;60
7.6.3;3.6.3 Optimization Algorithms;61
7.7;3.7 Analytical Model;65
7.7.1;3.7.1 DP-based Query Optimization;66
7.7.2;3.7.2 DAC-DP Query Optimization;66
7.8;3.8 Experimental Study;67
8;Multi-objective Service Query Optimization;71
8.1;4.1 The Service Skyline;72
8.2;4.2 Computing Database Skylines: An overview;73
8.2.1;4.2.1 Block Nested Loops Algorithms;73
8.2.2;4.2.2 Divide-and-Conquer Algorithm;74
8.2.3;4.2.3 Bitmap Algorithm;75
8.2.4;4.2.4 Index-based Algorithm;75
8.2.5;4.2.5 Nearest Neighbor Algorithm;77
8.3;4.3 Challenges of Computing the SEP Skyline;78
8.4;4.4 SEP Skyline Computation;80
8.4.1;4.4.1 Using B-trees;81
8.4.2;4.4.2 Nearest Neighbor Algorithm;82
8.4.3;4.4.3 Extending BBS;84
8.4.3.1;4.4.3.1 Characteristics of the data space;88
8.4.3.2;4.4.3.2 Structure of the R-tree;89
8.4.3.3;4.4.3.3 Summary;89
8.4.4;4.4.4 Operation Graph based Indexing (OGI);90
8.5;4.5 Experimental Study;91
8.5.1;4.5.1 Number of QoWS Attributes;92
8.5.2;4.5.2 Number of Operations per SEP;92
8.5.3;4.5.3 Cardinality of Service Relations;93
8.5.4;4.5.4 Sizes of the SEP Skylines;94
9;Skyline Computation for Multi-Service Query Optimization;96
9.1;5.1 Preliminaries;97
9.2;5.2 One Pass Algorithm;98
9.3;5.3 Dual Progressive Algorithm;100
9.3.1;5.3.1 Basic Progressive Enumeration;100
9.3.2;5.3.2 Node Duplication;101
9.3.3;5.3.3 Parent Table;103
9.3.4;5.3.4 Analysis;104
9.3.4.1;5.3.4.1 Correctness;105
9.3.4.2;5.3.4.2 Complexity;106
9.4;5.4 A Bottom-Up Approach;109
9.4.1;5.4.1 The Early Pruning Heuristic;109
9.4.2;5.4.2 Linear Composition Plans;110
9.4.3;5.4.3 Complexity Analysis;113
9.5;5.5 Experimental Study;114
9.5.1;5.5.1 Efficiency and Scalability;114
9.5.2;5.5.2 Heap Size;116
9.5.3;5.5.3 MEP Skyline Size;117
9.5.4;5.5.4 Discussion;117
10;Skyline Computation over Uncertain QoWS;119
10.1;6.1 p-dominant Service Skyline;120
10.2;6.2 Preliminaries;123
10.2.1;6.2.1 Problem Definition;124
10.2.2;6.2.2 p-dominant Skyline Vs. p-skyline;125
10.3;6.3 Computing the p-dominant Skyline using p-R-tree;128
10.3.1;6.3.1 p-R-tree;129
10.3.1.1;6.3.1.1 p-Complete Dominate;129
10.3.1.2;6.3.1.2 Building the p-R-tree;130
10.3.2;6.3.2 A Dual Pruning Process;131
10.3.2.1;6.3.2.1 Pruning using ˆ Sp;131
10.3.3;6.3.3 Computing the Dominate Probability;132
10.3.4;6.3.4 The Main Memory p-R-tree;133
10.3.5;6.3.5 The Two Phase Algorithm;134
10.3.6;6.3.6 Analysis;135
10.3.6.1;6.3.6.1 Time Complexity of Phase I;136
10.3.6.2;6.3.6.2 Time Complexity of Phase II;137
10.4;6.4 Experimental Study;138
10.4.1;6.4.1 Size of the p-dominant skylines;139
10.4.2;6.4.2 Performance and Scalability;140
10.4.3;6.4.3 Pruning Efficiency;141
10.4.4;6.4.4 Computing p-dominant Skyline with (p + )-R-tree;142
11;Related Work;144
11.1;7.1 Web Service Querying and Optimization;144
11.2;7.2 Evaluation of Web Service Deployment Systems;145
11.2.1;7.2.1 Research Prototypes;146
11.2.2;7.2.2 Discussion of Web Service Deployment Platforms;150
12;Conclusions;153
12.1;8.1 Summary;153
12.2;8.2 Directions for Future Research;155
12.2.1;8.2.1 Ontology Management for Web Services;155
12.2.2;8.2.2 QoWS Management;155
12.2.3;8.2.3 Service Model Extension;156
12.2.4;8.2.4 Reversed Two-phase Service Query Optimization;156
12.2.5;8.2.5 Subspace Service Skyline;156
12.2.6;8.2.6 Uncertain QoWS Stream Processing;157
12.2.7;8.2.7 Failure Recovery in Service Query Optimization;157
13;References;159
14;Index;164