Semantic Web Information Management (eBook)

Roberto De Virgilio is with Università di Roma Tre as PostDoc fellow under the supervision of Riccardo Torlone. The last years his research focuses on Semantic Web information management at different levels of abstraction. Fausto Giunchiglia is professor of computer science at the University of Trento, Department of Information and Communication Technology, ECCAI Fellow. His research has covered many different areas: knowledge representation, context and reasoning with context, knowledge management and peer-to-peer knowledge, semantic web, formal methods, theorem proving, and model checking. Letizia Tanca is a full professor with Politecnico di Milano. Her research interests range over all database theory, especially on deductive, active and object oriented databases, graph-based languages for databases, and the semantics of advanced database and information systems, representation and querying of semistructured information. Her most recent research interests concern context-aware database design, data integration, schema evolution, mobile databases and very small databases for mobile devices.

Preface 5
Contents 6
Contributors 16
Introduction 20
PART 1. Semantic Web Data Storage 21
PART 2. Reasoning in the Semantic Web 22
PART 3. Semantic Web Data Querying 23
PART 4. Semantic Web Applications 25
PART 5. Engineering Semantic Web Systems 26
Data and Metadata Management 27
Introduction 27
Databases, Schemas and Dictionaries 28
Data Models 30
Management of Multiple Models 32
Model-generic Schema Translation 36
Related Work 39
Conclusion 40
References 40
The Semantic Web Languages 43
Introduction 43
The Hierarchy of Languages 45
XML: Raw Data-No Semantics 45
RDF(S): Representing Objects and Relations Among Them 46
OWL: Ontologies-Representing Classes and Relations Among Them 46
C-OWL: Contextual Ontologies-Representing Context Mappings 47
RDF(S) 47
OWL 49
OWL Lite 49
OWL DL 50
OWL Full 50
C-OWL 51
Semantic Web and Databases 52
Conclusion 54
Appendix A: RDF(S) Constructs 54
Appendix B: OWL Constructs 54
References 55
Semantic Web Data Storage 57
Relational Technologies, Metadata and RDF 58
Introduction 58
The Relational Model 61
Modeling Metadata in Relational Systems 62
Separate Structures 62
Intermixed Context 62
Intensional Associations 64
RDF 65
Using Relational Systems for RDF Storage 67
Storing RDF as XML 68
Vertical Table 70
Graph-based Storage 71
Graph Schema-Vertical Data 73
Property Table 75
Vertical Partitioning 77
Smart Indexing 79
Conclusion 81
References 81
A Metamodel Approach to Semantic Web Data Management 84
Introduction 84
Motivating Example 86
Management of RDF Data 87
A Conceptual Representation 89
Logical Level 92
Physical Level 94
Query Processing 96
Related Work 96
Experimental Results 99
RDF Benchmark 99
Query 1 (Q1) 100
Query 2 (Q2) 100
Query 3 (Q3) 101
Query 4 (Q4) 101
Query 5 (Q5) 101
Query 6 (Q6) 102
Platform Environment 102
Evaluating Results 103
Performance Results 103
Q1 104
Q2 104
Q3 104
Q4 105
Q5 105
Q6 105
Scalability Results 105
Conclusion 106
References 107
Managing Terabytes of Web Semantics Data 109
Introduction 109
Definition and Model for the Web of Data 110
Providing Services on the Web of Data: A Model for a Large Scale Semantic Data Processing Infrastructure 111
Semantic Sitemap: A Dataset Publishing Model 113
The Sitemap Protocol and robots.txt 114
The Semantic Sitemaps Extension 114
Datasets 115
Adding Dataset Descriptions to the Sitemap Protocol 115
Pre-processing: Context-dependent Reasoning 116
Contexts on the Semantic Web 117
Aggregate Context 118
Lifting Rules 118
Import Closure of RDF Models 118
Deductive Closure of RDF Models 119
Technical Overview 120
Performance Overview 121
Discussion 121
Indexing: The SIREn Model 122
SIREn Data Model 122
SIREn Query Model 124
SIREn Operators 124
Content Operators 124
SPARQL Interpretation 125
Experimental Benchmark 126
Ranking: The DING Model 128
A Two-layer Model for Web Data 129
DING Algorithm 130
Combining DING and Entity Rank 131
Leveraging Sindice in SIGMA 131
Sig.ma: Processing Dataflow and Interaction with Sindice 132
Creation of a Sig.ma Query Plan 133
Data Sources Selection 134
Extraction and Alignment of Related Subgraphs 134
Consolidation 135
Value Labelling, Consolidation and Source List Refinement 136
Conclusion 136
References 138
Reasoning in the Semantic Web 140
Reasoning in Semantic Web-based Systems 141
Introduction 141
Background 142
Logic Programming 142
Description Logics 144
Standards on the Semantic Web 145
OWL 2 145
WSML 146
Reasoning Techniques 147
Description Logic Paradigm 147
Tableaux Methods 147
Pellet 148
Translation to Rule Based Systems 149
KAON2 149
Rule Paradigm 149
Bottom-up Techniques 150
Magic-sets Evaluation 151
IRIS 151
Top-down (SLD) Resolution with Memoing: SLG 152
XSB 153
Reasoning on the Web 153
Expressivity 154
Approximate Reasoning 156
Approximation of the Reasoning Method 156
Approximation of the Request 157
Approximation of the Knowledge Base 157
Conclusion 158
References 158
Modular Knowledge Representation and Reasoning in the Semantic Web 161
Introduction 161
Ontologies and Description Logics 163
Description Logic SHOIQb 164
Sublanguages of SHOIQb 166
Reference Distributed Ontology Framework 167
Distributed Description Logics 168
Formalization 168
Reasoning in DDL 170
Modeling with DDL 171
E-connections 174
Formalization 174
Reasoning in E-connections 178
Modeling with E-connections 179
Package-based Description Logics 182
Formalization 182
Reasoning in P-DL 184
Modeling with P-DL 184
Integrated Distributed Description Logics 187
Formalization 187
Reasoning in IDDL 189
Modeling with IDDL 189
Conclusion 191
References 193
Semantic Matching with S-Match 196
Introduction 196
State of the Art 197
Rondo 198
Cupid 198
COMA 198
Semantic Matching 199
The Tree Matching Algorithm 200
Step 1. 201
Step 2. 201
Step 3. 202
Step 4. 203
Node Matching Algorithm 205
Efficient Semantic Matching 206
Conjunctive Concepts at Nodes 207
Tests for Less and More General Relations 207
Disjunctive Concepts at Nodes 208
The S-Match Architecture 209
Evaluation 209
Evaluation Set Up 209
Evaluation Results 211
Conclusion 213
References 213
Preserving Semantics in Automatically Created Ontology Alignments 216
Introduction 216
Related Research Fields 217
Preliminaries 218
Ontologies 218
Correspondences and Mappings 219
Distributed Ontologies 220
Faults and Diagnoses 221
Mapping Revision 222
Model-based Mapping Revision 223
Consistency-Preserving Revision 223
Coherence-Preserving Revision 224
Heuristic Mapping Revision 226
Static Heuristic Revision 226
Heuristics for Coherence Preservation 227
Bowtie Rule (B-Rule) 227
Partition Rule (P-Rule) 228
Cycle Rule (CYC-Rule) 229
Blind Multiple Correspondences 229
Uncertainty-Aware Mapping Revision 231
Probabilistic Mapping Revision 232
Fuzzy Mapping Revision 232
Conclusion 233
References 234
tOWL: Integrating Time in OWL 237
Introduction 237
Preliminaries 239
Concrete Domains 239
4D Fluents 240
tOWL 242
tOWL Overview 242
OWL Schema of tOWL 242
A tOWL Ontology for the Leveraged Buyouts 246
Leveraged Buyouts 247
TBox 247
ABox 251
Use Cases 253
Related Work 254
Temporal RDF 254
OWL-Time 255
4D Fluents 256
Conclusion 257
References 258
Semantic Web Data Querying 259
Datalog Extensions for Tractable Query Answering over Ontologies 260
Introduction 260
Preliminaries 263
Databases and Queries 264
Dependencies 264
The Chase 265
Treewidth 267
Guarded Datalog± 268
Combined Complexity 268
Data Complexity 270
Linear Datalog± 273
Combined Complexity 273
Data Complexity 274
Weakly Guarded Datalog± 275
Combined Complexity 276
Data Complexity 278
Extensions 279
Negative Constraints 279
Non-conflicting Keys 280
Ontology Querying 282
DL-LiteA 282
F-Logic Lite 286
Conclusion 288
References 289
On the Semantics of SPARQL 291
Introduction 291
The W3C Syntax of SPARQL 293
Basic Definitions 294
Basic Structures 294
More Complex Queries 296
Final Remarks 298
An Algebraic Syntax for SPARQL 299
Translating SPARQL into the Algebraic Formalism 301
Semantics of SPARQL 303
Blank Nodes in Graph Patterns 309
Bag Semantics of SPARQL 310
On the Complexity of the Evaluation Problem 311
Related Work 315
Conclusion 316
References 317
Labeling RDF Graphs for Linear Time and Space Querying 318
Introduction 319
Contributions 320
Motivating Example 321
Preliminaries-RDF as Graphs 323
Queries on RDF Graphs 324
Triple Patterns and Adjacency 327
Labeling Schemes for RDF Graphs 328
Foundation: Tree Labeling 328
Reachability in Graphs 331
cig-labeling Scheme 332
Label Size 334
Adjacency & Reachability Test
Optimal cig-labeling 336
cig-labeling on Trees and cigs 337
cigs: Sharing-Limited Graphs 337
Labeling cigs and Trees 339
Properties of cig-labelings on cigs and Trees 339
Limitations and Extensions 340
Processing SPARQL with cig-labelings 341
Processing 1-SPARQL 341
Processing A-SPARQL 342
Towards Full SPARQL 344
Towards Path Expressions 345
Conclusion 345
References 346
SPARQLog: SPARQL with Rules and Quantification 349
Introduction 350
Contributions 352
Preliminaries 352
SPARQL Rule Languages 355
SPARQL and Rule Extensions of SPARQL 355
Other Rule-based RDF Query Languages 356
Quantifier Alternation in Data Exchange 357
SPARQLog: SPARQL with Rules and Quantification 358
SPARQLog Syntax 360
Denotational Semantics for SPARQLog 361
Relational Operational Semantics for SPARLog 363
Soundness and Completeness 365
Proof of Lemma 15.2 and Theorem 15.1 366
Properties of SPARQLog 368
Designing Tractable Fragments of SPARQLog 368
SwARQLog 370
Expressiveness of Quantifier Alternation in SPARQLog 372
Experimental Comparison with SPARQL Engines 375
Conclusion 377
References 377
SP2Bench: A SPARQL Performance Benchmark 379
Introduction 379
Structure 381
Benchmark Design Decisions 382
Requirements for Domain-specific Benchmarks 382
The SP2Bench Data Generator 383
Characteristics of DBLP Data 383
Structure of Document Classes 383
Development of Document Classes over Time 385
Other Characteristics 386
Data Generator Implementation and RDF Scheme 387
The SP2Bench RDF Scheme for DBLP 388
The SP2Bench Benchmark Queries 390
RDF Characteristics 390
SPARQL Characteristics 392
Discussion of Benchmark Queries 392
Benchmark Query Q1: 393
Benchmark Query Q2: 393
Benchmark Queries Q3abc: 394
Benchmark Query Q4: 394
Benchmark Queries Q5ab: 395
Benchmark Query Q6: 395
Benchmark Query Q7: 396
Benchmark Query Q8: 396
Benchmark Query Q9: 397
Benchmark Query Q10: 397
Benchmark Query Q11: 397
Benchmark Query Q12: 398
Benchmark Metrics 398
Conclusion 399
References 400
Semantic Web Applications 402
Using OWL in Data Integration 403
Introduction 404
The Data Integration Framework 406
Computational Characterization of Query Answering 412
Data Integration Using OWL 2 QL 415
Schema-Rewriting 416
LAV-Rewriting 417
GAV-Rewriting 417
Source-Evaluation 418
Related Work 420
Conclusion 425
References 425
Service Knowledge Spaces for Semantic Collaboration in Web-based Systems 431
Introduction 431
Semantic Collaboration in Networked Web-based Systems 432
Service Knowledge Space 435
Preliminary Notions 435
Model-based Service Description 436
Ontological Infrastructure 437
Local Service Knowledge 437
Network Service Knowledge 440
Distributed Semantic Service Management 443
Distributed Service Registry Structure 444
Distributed Service Registry Maintenance 445
Semantic Collaboration with Distributed Service Registry 446
Selection of semantic neighbors 446
Request forwarding and collection of search results 447
Extending the search results through related services 447
Experimental Evaluation 448
Related Work 449
Ontology-based Service Description 449
Service Discovery and Matchmaking 450
P2P Service-based Semantic Collaboration 451
Conclusion 452
References 453
Informative Top-k Retrieval for Advanced Skill Management 455
Introduction 456
Preliminaries 457
Reference Formalism 457
Query Language 458
Top-k Retrieval 459
Human Resources Retrieval 459
Ontology Component 461
Database Component 463
Query Process (by Example) 466
Match Explanation 468
Experiments 472
Related Work 474
Research Approaches 475
Commercial Tools 476
Appendix A: Ontology Axioms Excerpts 476
Appendix B: Example Candidate Profiles Set 479
References 481
Engineering Semantic Web Systems 483
MIDST: Interoperability for Semantic Annotations 484
Introduction 484
State of the Art 486
From Database to Ontology 487
From Ontology to Database 488
Translation Between Ontologies and Databases 488
Model Independent Schema and Data Translation 490
Basic Translations 491
More Complex Translations 492
OWL and Relational Database Interoperability 493
Relational Data Model 493
OWL Data Model 495
An Extended Supermodel 497
Management of Intersections 498
Management of Restrictions 499
Classes Equivalence 499
Properties Equivalence 499
Object and Datatype Properties Generalization 500
Functional Datatype Properties 500
Symmetric, Transitive and Inverse Object Properties 500
Translation Rules 500
Conclusion 503
References 504
Virtuoso: RDF Support in a Native RDBMS 506
Introduction 506
State of the Art 507
Vertical Layouts 507
Triples Indexed with Sorted Lists 507
Clustered Quad Stores 508
SPARQL Processor Without Local Data Storage 509
Triple Storage 509
Compression 510
Alternative Index Layouts 511
SPARQL and SQL 511
SQL Cost Model and RDF Queries 512
Basic RDF Inferencing 512
Data Manipulation 513
Full Text 513
Aggregation 513
RDF Sponge 513
Clustering and Scalability 514
Query Execution Model 515
Performance 516
Mapping Relational Data into RDF for SPARQL Access 517
Applications and Benchmarks 520
Web 2.0 Applications 520
OpenLink Data Spaces (ODS) 520
Berlin SPARQL Benchmark 520
Future Directions 521
Clustering 521
Updating Relational Data by SPARUL Statements 521
Conclusion 522
References 523
Hera: Engineering Web Applications Using Semantic Web-based Models 525
Introduction 525
Method 527
Data Modeling 528
Application Modeling 529
Basic Constructs in Application Model 529
Other Constructs in the Application Model 533
Presentation Modeling 535
User Modeling 536
Aspect Orientation 537
Tool Support 539
Hera Studio 539
Other Tools 541
Related Work 542
WebML 543
OOHDM 543
UWE 544
OOWS 545
Conclusion 546
References 547
Index 549