Abstract
A widely acknowledged obstacle for realizing the vision of the Semantic Web is the inability of many current Semantic Web approaches to cope with data available in such diverging representation formalisms as XML, RDF, or Topic Maps. A common query language is the first step to allow transparent access to data in any of these formats. To further the understanding of the requirements and approaches proposed for query languages in the conventional as well as the Semantic Web, this report surveys a large number of query languages for accessing XML, RDF, or Topic Maps. This is the first systematic survey to consider query languages from all these areas. From the detailed survey of these query languages, a common classification scheme is derived that is useful for understanding and differentiating languages within and among all three areas.
Introduction: The Tower of Babel in Web Querying
In the early 2000s, the "Semantic Web" represented the frontier of computer science—a vision where the web would transition from a collection of text for human consumption into a structured database accessible by machines. However, this vision faced a significant technical hurdle: data fragmentation across wildly different representation formalisms.
As shown in the project metadata above, this work was part of the REWERSE (Reasoning on the Web with Rules and Semantics) project, specifically deliverable I4-D1. The core issue addressed is that data was being stored in three primary, incompatible formats: XML (hierarchical trees), RDF (subject-predicate-object triples), and Topic Maps (complex associations). Each format possessed its own ecosystem of query languages. For developers, this fragmentation was a nightmare; querying a library database in RDF alongside a bookstore in XML required mastering entirely different syntactical and semantic paradigms. This survey evaluates whether a common query language is possible and how existing tools measure up against the requirements of a unified web.
Methodology: A Rigorous Evaluation Framework
The researchers conducted a systematic survey of 73 query languages. Rather than a simple listing, they developed a rigorous evaluation framework consisting of 111 distinct criteria grouped into six functional areas:
- Ease of Use: Evaluates human-readability and "meta-circularity" (the ability of a language to query its own structures).
- Functionality: Assesses whether the language supports complex data restructuring, selection, and negation.
- Semantics: Determines if the language has a formal mathematical definition or exists only as a "black box" implementation.
- Formal Properties: Checks for Turing-completeness and the existence of a "polynomial core" to ensure efficient execution.
- Reasoning: Measures the ability to perform recursion to find transitive relationships (e.g., identifying a "grandparent" relationship through "parent" links).
- Ontology Awareness: Examines whether the language understands Semantic Web "dictionaries" like RDFS or OWL.
The Benchmark: A Unified Book Collection
To ensure a fair comparison, the authors introduced a Collection of Sample Data. This benchmark consists of a carefully crafted set of information regarding books, authors, and genres. The data was represented in three equivalent forms:
- XML: Utilizing nested tags and ID/IDREF links.
- RDF: Using the Turtle serialization format.
- Topic Maps: Using Linear Topic Map (LTM) syntax.
This standardized dataset allowed the researchers to demonstrate exactly how specific queries—such as "Find all authors of historical essays"—would be expressed and executed across dozens of different languages.
Taxonomy of Query Languages: The Reasoning Divide
The most significant insight from the survey is that syntax (e.g., SQL-style vs. XPath-style) is secondary to reasoning capability. The authors argue that a language's fitness for the Semantic Web is primarily defined by its ability to handle recursion and ontologies. Based on this, they proposed a four-class taxonomy:
- Class 1 (Selection-Only): Languages like XPath that are excellent for data retrieval but cannot construct new data structures.
- Class 2 (Non-recursive): Languages like SQL or RDQL that can build new data but lack the ability to follow recursive paths.
- Class 3 (Limited Reasoning): This class is split between languages that understand ontologies but lack recursion (e.g., RQL) and those that support recursion but lack ontology awareness (e.g., XSLT/XQuery).
- Class 4 (Ontology-Aware Recursive): Considered the "Gold Standard" for the Semantic Web, these languages (such as TRIPLE, tolog, and the authors' own Xcerpt) combine both recursive power and ontological understanding.
Findings and the Maturity Gap
The survey of 73 languages revealed a stark "maturity gap." XML-based languages were found to be highly mature and standardized. In contrast, RDF and Topic Map languages were in a "Wild West" phase, often characterized by prototypes or "sketchy proposals" lacking formal semantics.
Furthermore, the authors noted a lack of support for "total queries." While most languages excel at partial pattern matching, few can effectively verify that a dataset only contains specific information, a critical requirement for high-integrity data verification.
Conclusion and Future Directions
The authors acknowledge certain limitations, including the inherent subjectivity in selecting evaluation criteria and the difficulty in providing deep formal analysis for poorly documented prototype languages. They also raise the question of whether a single language can efficiently handle the differing computational complexities of trees (XML) vs. graphs (RDF).
The paper concludes by positioning Xcerpt as a strong candidate for a unified web query language, suggesting that future research should focus on "theory extensibility"—the ability for a query language to integrate different reasoning engines based on the specific requirements of the task at hand.
Summary updated