Foundations for Efficient Web Service Selection (eBook)

Foreword 5
Preface 7
Acknowledgements 9
Contents 10
Introduction 13
1.1 Web Service Foundation 14
1.1.1 Historical Perspective 14
1.1.2 Web Services vs. Data 16
1.1.3 Service Query Optimization 16
1.2 Major Issues in Building a Web Service Foundation 17
1.2.1 Summary of Contributions 20
1.3 Preview of Chapters 22
Towards a WSMS: The State of the Art 23
2.1 Scenario 24
2.2 Web Service Reference Model 25
2.3 Web Service Stack 26
2.4 Key Dimensions for Building a WSMS 27
2.5 The WSMS Architecture 31
A Foundational Service Framework 36
3.1 Case Study: Car Brokerage 37
3.2 Service Query Model 38
3.3 Service Calculus 45
3.4 Service Query Algebra 47
3.4.1 Algebraic Operators 48
3.4.1.1 F-map 48
3.4.1.2 Q-Select 49
3.4.1.3 Compose 49
3.4.2 Algebraic Equivalent Rules 51
3.5 Implementing the Algebraic Operators 52
3.5.1 Storing the Service Relations 52
3.5.2 Implementing the Service Algebra 53
3.5.2.1 F-map 53
3.5.2.2 Q-select 54
3.5.2.3 Compose 54
3.5.3 Complexity of Service Algebraic Operators 55
3.5.4 Generating SEPs 57
3.6 Service Query Optimization 60
3.6.1 QoWS for SEPs 60
3.6.2 Score Function 60
3.6.3 Optimization Algorithms 61
3.7 Analytical Model 65
3.7.1 DP-based Query Optimization 66
3.7.2 DAC-DP Query Optimization 66
3.8 Experimental Study 67
Multi-objective Service Query Optimization 71
4.1 The Service Skyline 72
4.2 Computing Database Skylines: An overview 73
4.2.1 Block Nested Loops Algorithms 73
4.2.2 Divide-and-Conquer Algorithm 74
4.2.3 Bitmap Algorithm 75
4.2.4 Index-based Algorithm 75
4.2.5 Nearest Neighbor Algorithm 77
4.3 Challenges of Computing the SEP Skyline 78
4.4 SEP Skyline Computation 80
4.4.1 Using B-trees 81
4.4.2 Nearest Neighbor Algorithm 82
4.4.3 Extending BBS 84
4.4.3.1 Characteristics of the data space 88
4.4.3.2 Structure of the R-tree 89
4.4.3.3 Summary 89
4.4.4 Operation Graph based Indexing (OGI) 90
4.5 Experimental Study 91
4.5.1 Number of QoWS Attributes 92
4.5.2 Number of Operations per SEP 92
4.5.3 Cardinality of Service Relations 93
4.5.4 Sizes of the SEP Skylines 94
Skyline Computation for Multi-Service Query Optimization 96
5.1 Preliminaries 97
5.2 One Pass Algorithm 98
5.3 Dual Progressive Algorithm 100
5.3.1 Basic Progressive Enumeration 100
5.3.2 Node Duplication 101
5.3.3 Parent Table 103
5.3.4 Analysis 104
5.3.4.1 Correctness 105
5.3.4.2 Complexity 106
5.4 A Bottom-Up Approach 109
5.4.1 The Early Pruning Heuristic 109
5.4.2 Linear Composition Plans 110
5.4.3 Complexity Analysis 113
5.5 Experimental Study 114
5.5.1 Efficiency and Scalability 114
5.5.2 Heap Size 116
5.5.3 MEP Skyline Size 117
5.5.4 Discussion 117
Skyline Computation over Uncertain QoWS 119
6.1 p-dominant Service Skyline 120
6.2 Preliminaries 123
6.2.1 Problem Definition 124
6.2.2 p-dominant Skyline Vs. p-skyline 125
6.3 Computing the p-dominant Skyline using p-R-tree 128
6.3.1 p-R-tree 129
6.3.1.1 p-Complete Dominate 129
6.3.1.2 Building the p-R-tree 130
6.3.2 A Dual Pruning Process 131
6.3.2.1 Pruning using ˆ Sp 131
6.3.3 Computing the Dominate Probability 132
6.3.4 The Main Memory p-R-tree 133
6.3.5 The Two Phase Algorithm 134
6.3.6 Analysis 135
6.3.6.1 Time Complexity of Phase I 136
6.3.6.2 Time Complexity of Phase II 137
6.4 Experimental Study 138
6.4.1 Size of the p-dominant skylines 139
6.4.2 Performance and Scalability 140
6.4.3 Pruning Efficiency 141
6.4.4 Computing p-dominant Skyline with (p + )-R-tree 142
Related Work 144
7.1 Web Service Querying and Optimization 144
7.2 Evaluation of Web Service Deployment Systems 145
7.2.1 Research Prototypes 146
7.2.2 Discussion of Web Service Deployment Platforms 150
Conclusions 153
8.1 Summary 153
8.2 Directions for Future Research 155
8.2.1 Ontology Management for Web Services 155
8.2.2 QoWS Management 155
8.2.3 Service Model Extension 156
8.2.4 Reversed Two-phase Service Query Optimization 156
8.2.5 Subspace Service Skyline 156
8.2.6 Uncertain QoWS Stream Processing 157
8.2.7 Failure Recovery in Service Query Optimization 157
References 159
Index 164