Source-linked AI summary
A General Framework for Representing, Reasoning and Querying with Annotated Semantic Web Data
Antoine Zimmermann, Nuno Lopes, Axel Polleres, Umberto Straccia
TL;DR
The paper addresses how to represent, reason over, and query increasingly inconsistent or unreliable annotated Semantic Web data. It develops a generic annotated-RDF framework with a deductive system and AnQL, covering multiple annotation domains and their combinations. The framework conservatively extends RDFS and encompasses temporal, fuzzy, and provenance annotations.
Problem
Existing Semantic Web work uses different RDF annotation domains, creating a need for a generic framework that supports their reasoning, querying, and combination.
Method
The paper formalises annotated RDF and RDFS semantics, provides a deductive system and AnQL, and defines methods for combining annotation domains.
Results
The framework conservatively extends RDFS, supports uniform reasoning and querying across annotation domains, and encompasses temporal, fuzzy, and provenance approaches.
Takeaways & Limitations
The framework provides a uniform way to represent and combine annotated and non-annotated Semantic Web data, including multiple annotation domains.
Takeaways & Limitations
The combination approach is limited to cases where one annotation domain is a lattice, while normalization for two commutative, idempotent, top-annihilating semirings remains open.
Abstract
from arXiv · showhide
We describe a generic framework for representing and reasoning with annotated Semantic Web data, a task becoming more important with the recent increased amount of inconsistent and non-reliable meta-data on the web. We formalise the annotated language, the corresponding deductive system and address the query answering problem. Previous contributions on specific RDF annotation domains are encompassed by our unified reasoning formalism as we show by instantiating it on (i) temporal, (ii) fuzzy, and (iii) provenance annotations. Moreover, we provide a generic method for combining multiple annotation domains allowing to represent, e.g. temporally-annotated fuzzy RDF. Furthermore, we address the development of a query language -- AnQL -- that is inspired by SPARQL, including several features of SPARQL 1.1 (subqueries, aggregates, assignment, solution modifiers) along with the formal definitions of their semantics.
1. Introduction
The paper presents a general framework that extends RDF with triple annotations, conservatively extends RDFS reasoning, and supports querying annotated data. It unifies temporal, fuzzy, and provenance domains and introduces systematic domain combination and an extended SPARQL query language.
- Motivation: RDF extensions attach meta-information to graphs or triples to represent domains such as time, imprecise information, trust, and provenance.RDFS supports deductions from RDF triples, while SPARQL is the standard query language for RDF.
- Framework: The framework extends RDF with annotations on triples and provides Annotated RDFS semantics together with a deductive system.Its semantics conservatively extends RDFS semantics.
- Query language: AnQL extends SPARQL with annotation querying and features including aggregates, nested queries, and variable assignments.The paper also addresses solution modifiers and other SPARQL 1.1-related functionality.
- Annotation domains: The paper details temporal, fuzzy, and provenance annotation domains and introduces a systematic method for combining multiple domains.It also discusses integration of annotated and non-annotated triples and data using different annotation domains.
- Related work: Earlier approaches addressed specific RDF annotation domains, while this framework provides unified reasoning and query support across them.The related work includes temporal, fuzzy, trust, provenance, logic-programming, and annotated-database approaches.
2. Preliminaries – Classical RDF and RDFS
The paper introduces RDF/RDFS syntax, semantics, and entailment, then defines a rule-based deductive system and query framework over RDF graphs.
- RDF syntax: RDF triples contain a subject, predicate, and object, while graphs are sets of triples over URI references, blank nodes, and literals.
- RDFS vocabulary: The ρdf fragment captures subproperty, subclass, typing, domain, and range relations as essential RDFS features.
- Semantics: RDFS interpretations assign finite domains and interpretation functions to resources, properties, classes, and literals, subject to graph-satisfaction conditions.
- Deductive system: The deductive system is sound and complete for entailment, and graph closure is unique and polynomial in graph size.
- Query answering: Queries use distinguished and existential variables in conjunctive graph bodies, with built-in predicates and functional assignments supported.
3. RDFS with Annotations
Annotated RDFS extends triples with values from an algebraic annotation domain, whose operations support combining information and propagating annotations through inference.
- Annotated language: Annotated triples have the form τ: λ, where λ is drawn from a domain whose meaning depends on the application, such as time or fuzzy truth.
- Annotation domains: An annotation domain is modeled as an idempotent, commutative semiring with bottom and top elements and operations ⊕ and ⊗.
- Domain order: The induced partial order expresses redundant or entailed information, including temporal containment between annotation intervals.
- Domain operations: The operation ⊕ combines annotations for the same statement, while ⊗ models conjunction during inference.
- Domain construction: Constructing a domain requires choosing annotation values and top and bottom elements, then defining operations supporting intended schema inferences.
3.3. Semantics
Annotated semantics map statements to annotation values and define satisfaction and entailment over finite interpretations, preserving a finite-model property.
- Interpretations: An annotated interpretation assigns each triple an element of the annotation domain through property and class interpretation functions.
- Interpretation structure: Interpretation domains for resources, properties, classes, and literals are finite nonempty sets with corresponding interpretation functions.
- Satisfaction: A model satisfies an annotated triple when the interpreted property extension covers its subject-object pair to at least the stated annotation value.
- Entailment: The Boolean domain D01 recovers the classical setting, while annotated entailment extends the usual grounding-based graph relation.
- Finite models: Any annotated RDFS graph has a finite model, so the framework establishes satisfiability without requiring separate consistency management.
3.4. Examples of primitive domains
The framework instantiates annotation domains for fuzzy truth, temporal validity, and provenance, showing how their operators support domain-specific inference and provenance aggregation.
- Fuzzy domain: Fuzzy RDFS uses [0, 1] with max for combining truth degrees and a continuous t-norm for conjunction.
- Fuzzy domain: Under the product t-norm, annotations 0.3 and 0.5 infer a membership annotation of 0.15.
- Temporal domain: Temporal annotations represent finite sets of disjoint intervals, ordered by temporal extent and combined through union-like join and intersection-like meet operations.
- Temporal domain: Temporal conjunction intersects intervals, exemplified by {[2005, 2010]} ⊗ {[2006, 2011]} = {[2006, 2010]}.
- Provenance domain: The provenance domain represents equivalent propositional formulas over atomic document provenances, combining alternative derivations with disjunction and joint premises with conjunction.
- Provenance domain: The provenance formalization adds the join operation needed when identical triples receive different annotations, addressing a gap in earlier approaches.
3.5. Deductive system
The deductive system extends classical RDFS reasoning to annotated triples while preserving soundness and completeness. Its rule schemata are domain-independent except for annotation operations, and closure remains polynomial under bounded operation costs.
- Domain-independent rules: The annotated deductive system uses rule schemata shared across annotation domains, requiring only domain-specific ⊗ and ⊕ operations.This supports implementation on top of existing systems.
- Correctness: The system is sound and complete: derivability implies entailment, and every entailment has a derivable annotation at least as informative as the entailed one.
- Complexity: The closure is computable in polynomial time when the annotation operations ⊗ and ⊕ have polynomially bounded complexity.The closure is defined from all derivable annotated triples without rule (1a).
- Example: In the temporal example, the premises yield (chadHurley, type, googleEmp): [2006, 2010].The inferred interval reflects the overlap of the two premise intervals.
3.6. Query Answering
Annotated query answering extends classical queries with annotation variables and built-in predicates, then selects maximally informative annotation vectors. Answers can be obtained by computing graph closure and querying the resulting database.
- Query language: Annotated queries replace ordinary triples with annotated triples and permit annotation variables in annotations or built-in predicates.Built-ins can constrain annotation values using predicates such as ⪯.
- Example: For the temporal employee query, the answers include Steve Chen [2006, 2011], Chad Hurley [2006, 2010], and three additional employees with their intervals.
- Answer semantics: An answer is entailed when every model of the graph satisfies the query, with annotation vectors retained only when they are ⪯-maximal.Maximality removes redundant or subsumed answers.
- Evaluation: The closure can be computed, stored in a database, and queried with SQL supporting built-in predicates and annotation-domain operations.
3.7. Queries with aggregates
The query language supports SQL-style and domain-specific aggregates, grouping, built-in temporal computations, ordering, and optional limits. These features allow annotated answers to be summarized and ranked using annotation values.
- Aggregate functions: Aggregates include SUM, AVG, MAX, MIN, COUNT, and the annotation-domain operations ⊕ and ⊗.
- Domain-specific aggregates: Built-in temporal aggregates can return the maximal employment interval for each employee across companies.The maxlength predicate returns the maximal interval in a set of temporal intervals.
- Grouping: Grouped queries can compute average employment length by grouping employees and averaging lengths derived from temporal annotations.The query groups by employee, applies length to each interval, and computes AVG for each group.
- Ordering: Ordered queries rank answers by an assigned order variable, including annotation order when the variable is an annotation, and can add LIMIT(k).
4. AnQL: Annotated SPARQL
AnQL extends SPARQL to query annotated RDF graphs, adding annotation variables and annotated graph patterns while preserving standard SPARQL behavior for fully ⊤-annotated data. Its semantics also formalize advanced querying features, including aggregates, assignments, subqueries, ordering, and limits.
- SPARQL foundations: AnQL retains SPARQL’s core solution concepts, including mappings, compatibility, basic graph patterns, filters, optional patterns, conjunction, and union.Its graph-pattern evaluation is defined recursively using relational-algebra operations over solution mappings.
- Query semantics: AnQL provides formal semantics for unsafe FILTERs and OPTIONAL patterns, including cases where filters fail or optional matches are absent.The definitions specify compatibility, filter truth, errors, and the resulting mappings for OPTIONAL evaluation.
- AnQL foundations: AnQL extends SPARQL by querying annotated RDF graphs with annotated graph patterns and annotation variables.Queries are defined over annotated graphs and distinguish annotation variables from ordinary variables.
- Query semantics: The solutions of annotated basic graph patterns correspond to answers of the associated annotated conjunctive queries.This correspondence is stated directly for BAPs and mirrors the standard SPARQL result for BGPs.
- Semantics and guarantees: AnQL is a conservative extension of SPARQL: annotating every RDF triple with ⊤ preserves a one-to-one correspondence between their solutions.Assuming built-in predicates are computable in finite time, AnQL answer sets are finite and computable in finite time.
- Further extensions: AnQL generalizes SPARQL with assignments, aggregates, GROUPBY, subqueries, ORDER BY, and LIMIT as composable operators within graph patterns.Unlike current SPARQL 1.1 syntax, these operators need not be tied to a sub-SELECT and may be nested within patterns.
5. On primitive domains and their combinations
The section addresses temporal-relation semantics and develops a systematic construction for combining annotation domains. It also identifies practical trade-offs and limits of these combinations.
- Temporal issues: AnQL can encode alternative interpretations of temporal predicates, such as beforeAny and beforeAll, producing different query answers.The beforeAll query returns no result in the cited example, while beforeAny can reproduce the alternative behavior.
- Temporal issues: Temporal relations over sets of intervals admit multiple quantifier-based interpretations, including existential and universal variants.The framework defines five ways to lift an Allen relation from individual intervals to sets of intervals.
- Temporal issues: The first three lifted relations are not disjoint, while the final four are incomplete as relation systems.For example, pairs of interval sets can satisfy both before∃∃ and after∃∃, whereas some pairs satisfy none of the final relations.
- Combining domains: The paper revises an earlier pointwise product approach for combining domains such as time, truth, and trust.The revised construction defines a compound domain systematically from two existing annotation domains.
- Combining domains: The proposed compound-domain operations preserve the required algebraic structure and support finite normalized representations.The paper states that the resulting structure is an idempotent, commutative semiring and proves properties of quasihomomorphisms and normalization.
- Discussion: The construction is novel for annotated settings and can reuse modules for primitive domains, but normalization and multi-domain reasoning remain constrained.The normalization algorithm is not optimized, the general semiring case remains open, and combining more than two domains may be complex or non-commutative.
- Discussion: Combining annotated and non-annotated triples can either enable inference across sources or preserve straightforward query answering, with different drawbacks.The integrated approach may require recomputing answers when a new domain is added, while segregated datasets do not support reciprocal reasoning across domains.
6. Implementation Notes
The implementation separates annotated RDFS inference from AnQL querying and parameterizes both by annotation domains and rules. A sensor-data use case illustrates temporal annotation and preprocessing.
- Architecture: The prototype has separate modules for Annotated RDFS inferencing and AnQL querying, implemented in Prolog over SWI-Prolog and ClioPatria.The AnQL module relies on the inferencing module to retrieve data.
- Inference: The Annotated RDFS module computes dataset closure bottom-up using a specified annotation domain and inference rules.The rules are expressed in a high-level language that abstracts from reification syntax, and domains and rulesets can be combined independently.
- Querying: Domain-specific AnQL support extends the grammar with annotation-value parsers and built-in functions.For fuzzy annotations, decimal parsing is added and the default value is 1 with min and max as the domain operations.
- Temporal domain: Temporal annotations are represented as ordered lists of disjoint intervals, with integers for concrete time points and constraint solving for operations.Non-annotated triples use [inf,sup] as their default temporal annotation.
- Sensor-data use case: The sensor use case represents readings as temporally annotated RDF, enabling precise representation and interlinking with other Web sources.The data-cleaning process selects the closest base station using signal strength, then merges consecutive records into intervals.
7. Conclusion
The paper presents a generic annotated RDF and RDFS framework with a corresponding query language. It unifies annotation-domain reasoning, domain combination, and expressive querying, and demonstrates the approach with an implementation and sensor-data experiment.
- Framework: The framework conservatively extends RDFS semantics to support multiple annotation domains and a uniform way to combine them.The conclusion names temporality, fuzziness, and trust as examples of supported features.
- Query language: AnQL extends SPARQL with annotation querying and features including aggregates, variable assignments, and subqueries.The paper also describes a constraint-logic-programming implementation and a practical sensor-data experiment.
Appendix A.1. Proof of Theorem 5.2
The appendix proves the normalization-related properties needed for the compound annotation construction. The proof proceeds through intermediate lemmas and algebraic rewrites.
- Proof strategy: The proof establishes two inequalities relating A to the operations ⊕1, ⊗1, ⊕2, and ⊗2.These inequalities form part of the argument for the compound-domain theorem.
- Proof strategy: The proof introduces notation and intermediary lemmas before rewriting the target property into progressively simpler forms.Several steps use associativity and distributivity of the domain operations.
- Algebraic simplification: Associativity of ⊕2 and distributivity of ⊗2 over ⊕2 simplify the final algebraic argument.The appendix states that the result follows after these rewrites and an established lemma.
- Proof boundary: The appendix notes that the opposite inequality does not hold in general.This marks an asymmetry in the algebraic relationship used by the proof.
Appendix A.2. Proof of Theorem 5.4
The proof establishes that normalization preserves the represented annotation function and that equal finite annotation sets have equal normal forms. It proceeds by proving preservation for saturation and reduction, then uses these lemmas to prove the theorem.
- Normalization: If D1 is a lattice, every finite annotation set A satisfies A = Normalise(A).This follows from the inductive preservation of the represented function through saturation and reduction.
- Qualification: If ⊗2 is idempotent, an inequality used in the proof becomes an equality.This is stated as a specific condition affecting the proof’s inequality.
- Reduction: The reduce algorithm preserves the quasi homomorphism, yielding A = Reduce(A).The argument removes pairs dominated in both annotation components while preserving the represented function.
- Theorem conclusion: For finite sets A and B with A = B, the proof concludes Normalise(A) = Normalise(B).It establishes mutual inclusion using normalized representatives and the auxiliary lemmas.
- Auxiliary properties: A quasihomomorphism is antitone when D1 is a lattice, providing the order-reversal property used in the normalization proof.For x ⪯1 x′, the proof derives f(x) ⪰2 f(x′).