63 research outputs found
Simulation Subsumption or Déjà vu on the Web
No full textSimulation unification is a special kind of unification adapted to retrieving semi-structured data on the Web. This article introduces simulation subsumption, or containment, that is, query subsumption under simulation unification. Simulation subsumption is crucial in general for query optimization, in particular for optimizing pattern-based search engines, and for the termination of recursive rule-based web languages such as the XML and RDF query language Xcerpt. This paper first motivates and formalizes simulation subsumption. Then, it establishes decidability of simulation subsumption for advanced query patterns featuring descendant constructs, regular expressions, negative subterms (or subterm exclusions), and multiple variable occurrences. Finally, we show that subsumption between two query terms can be decided in O(n!n) where n is the sum of the sizes of both query terms
Data Model and Query Constructs for Versatile Web Query Languages
No full textAs the Semantic Web is gaining momentum, the need for
truly versatile query languages becomes increasingly apparent. A Web
query language is called versatile if it can access in the same query program
data in different formats (e.g. XML and RDF). Most query languages
are not versatile: they have not been specifically designed to cope
with both worlds, providing a uniform language and common constructs
to query and transform data in various formats. Moreover, most of them
do not provide a flexible data model that is powerful enough to naturally
convey both Semantic Web data formats (especially RDF and
Topic Maps) and XML. This article highlights challenges related to the
data model and language constructs for querying both standard Web
and Semantic Web data with an emphasis on facilitating sophisticated
reasoning. It is shown that Xcerpt’s data model and querying constructs
are particularly well-suited for the Semantic Web, but that some adjustments
of the Xcerpt syntax allow for even more effective and natural
querying of RDF and Topic Maps
Model Theory and Entailment Rules for RDF Containers, Collections and Reification
No full textAn RDF graph is, at its core, just a set of statements consisting of subjects, predicates and objects. Nevertheless, since its inception
practitioners have asked for richer data structures such as containers (for
open lists, sets and bags), collections (for closed lists) and reification (for
quoting and provenance). Though this desire has been addressed in the
RDF primer and RDF Schema specification, they are explicitely ignored
in its model theory. In this paper we formalize the intuitive semantics
(as suggested by the RDF primer, the RDF Schema and RDF semantics specifications) of these compound data structures by two orthogonal
extensions of the RDFS model theory (RDFCC for RDF containers and
collections, and RDFR for RDF reification). Second, we give a set of
entailment rules that is sound and complete for the RDFCC and RDFR
model theories. We show that complexity of RDFCC and RDFR entailment remains the same as that of simple RDF entailment
AMaχoS—Abstract Machine for Xcerpt
No full textWeb query languages promise convenient and efficient access
to Web data such as XML, RDF, or Topic Maps. Xcerpt is one such Web
query language with strong emphasis on novel high-level constructs for
effective and convenient query authoring, particularly tailored to versatile
access to data in different Web formats such as XML or RDF.
However, so far it lacks an efficient implementation to supplement the
convenient language features. AMaχoS is an abstract machine implementation
for Xcerpt that aims at efficiency and ease of deployment. It
strictly separates compilation and execution of queries: Queries are compiled
once to abstract machine code that consists in (1) a code segment
with instructions for evaluating each rule and (2) a hint segment that
provides the abstract machine with optimization hints derived by the
query compilation. This article summarizes the motivation and principles
behind AMaχoS and discusses how its current architecture realizes
these principles
Calbindin D28k
No full textThis is an invited short review summarizing the most significant studies related to calbindin D28k. Professor Sara Linse and I have collaborated on this protein for close to 20 years (we can therefore both be considered primary authors if you wish). Included are also the authors Mikael Bauer, who worked on this protein as a graduate student with Sara and Tommy Cedervall who worked with me as a postdoctoral fellow.--author-supplied descriptio
Effective and Efficient Data Access in the Versatile Web Query Language Xcerpt
No full textAccess to Web data has become an integral part of many applications
and services. In the past, such data has usually been accessed
through human-tailoredHTMLinterfaces.Nowadays, rich client interfaces
in desktop applications or, increasingly, in browser-based clients ease data
access and allow more complex client processing based on XML or RDF
data retrieved throughWeb service interfaces. Convenient specifications of
the data processing on the client and flexible, expressive service interfaces
for data access become essential in this context.Web query languages such
as XQuery, XSLT, SPARQL, or Xcerpt have been tailored specifically for
such a setting: declarative and efficient access and processing ofWeb data.
Xcerpt stands apart among these languages by its versatility, i.e., its ability
to access not just oneWeb format but many. In this demonstration, two aspects
of Xcerpt are illustrated in detail: The first part of the demonstration
focuses on Xcerpt’s pattern matching constructs and rules to enable effective
and versatile data access. It uses a concrete practical use case from
bibliography management to illustrate these language features. Xcerpt’s
visual companion language visXcerpt is used to provide an intuitive interface
to both data and queries. The second part of the demonstration shows
recent advancements in Xcerpt’s implementation focusing on experimental
evaluation of recent complexity results and optimization techniques, as
well as scalability over a number of usage scenarios and input sizes
Implementation of Web Query Languages Reconsidered
No full textVisions of the next generation Web such as the "Semantic Web" or the "Web 2.0" have triggered the emergence of a multitude of data formats. These formats have different characteristics as far as the shape of data is concerned (for example tree- vs. graph-shaped). They are accompanied by a puzzlingly large number of query languages each limited to one data format. Thus, a key feature of the Web, namely to make it possible to access anything published by anyone, is compromised.
This thesis is devoted to versatile query languages capable of accessing data in a variety of Web formats. The issue is addressed from three angles: language design, common, yet uniform semantics, and common, yet uniform evaluation. % Thus it is divided in three parts:
First, we consider the query language Xcerpt as an example of the advocated class of versatile Web query languages. Using this concrete exemplar allows us to clarify and discuss the vision of versatility in detail.
Second, a number of query languages, XPath, XQuery, SPARQL, and Xcerpt, are translated into a common intermediary language, CIQLog. This language has a purely logical semantics, which makes it easily amenable to optimizations. As a side effect, this provides the, to the best of our knowledge, first logical semantics for XQuery and SPARQL. It is a very useful tool for understanding the commonalities and differences of the considered languages.
Third, the intermediate logical language is translated into a query algebra, CIQCAG. The core feature of CIQCAG is that it scales from tree- to graph-shaped data and queries without efficiency losses when tree-data and -queries are considered: it is shown that, in these cases, optimal complexities are achieved. CIQCAG is also shown to evaluate each of the aforementioned query languages with a complexity at least as good as the best known evaluation methods so far. For example, navigational XPath is evaluated with space complexity O(q d) and time complexity O(q n) where q is the query size, n the data size, and d the depth of the (tree-shaped) data.
CIQCAG is further shown to provide linear time and space evaluation of tree-shaped queries for a larger class of graph-shaped data than any method previously proposed. This larger class of graph-shaped data, called continuous-image graphs, short CIGs, is introduced for the first time in this thesis. A (directed) graph is a CIG if its nodes can be totally ordered in such a manner that, for this order, the children of any node form a continuous interval.
CIQCAG achieves these properties by employing a novel data structure, called sequence map, that allows an efficient evaluation of tree-shaped queries, or of tree-shaped cores of graph-shaped queries on any graph-shaped data. While being ideally suited to trees and CIGs, the data structure gracefully degrades to unrestricted graphs. It yields a remarkably efficient evaluation on graph-shaped data that only a few edges prevent from being trees or CIGs
An epidemiological assessment of lens opacifications that impaired vision in patients injected with radium-224
No full textThe incidence of lens opacifications that impaired vision (cataract) was analyzed among 831 patients who were injected with known dosages of 224Ra in Germany shortly after World War II. The dependence of the incidence on dosage, i.e., injected activity per unit body weight, and on time after treatment was determined. The observations are equally consistent with proportionality of the incidence of cataract to the square of dosage or with a linear dependence beyond a threshold of 0.5 MBq/kg. The possibility of a linear dependence without threshold was strongly rejected (P less than 0.001). The analysis of temporal dependences yielded a component that was correlated with the injected amount of 224Ra and a component that was uncorrelated. The former was inferred by a maximum likelihood analysis to increase approximately as the square of the time after treatment. The component unrelated to the treatment was found to increase steeply with age and to become dominant within the collective of patients between age 50 and 60. The relative magnitudes of the two components were such that a fraction of 55 to 60% of the total of 58 cataracts had to be ascribed to the dose-related incidence. Impaired vision due to cataract was diagnosed before age 54 in 25 cases. In terms of injected activity per unit body weight no dependence of the sensitivity on age was found; specifically there was no indication of a faster occurrence of the treatment-related cataracts in patients treated at older ages
Data Integration on the (Semantic) Web with Rules and Rich Unification
No full textFor the last decade a multitude of new data formats for the World Wide Web
have been developed, and a huge amount of heterogeneous semi-structured data
is flourishing online. With the ever increasing number of documents on the
Web, rules have been identified as the means of choice for reasoning about
this
data, transforming and integrating it. Query languages such as SPARQL and rule
languages such as Xcerpt use compound queries that are matched or unified with
semi-structured data. This notion of unification is different from the one
that is known from logic programming engines in that it (i) provides
constructs that allow queries to be incomplete in several ways (ii) in that
variables may have different types, (iii) in that it results in sets of
substitutions for the variables in the query instead of a single substitution
and (iv) in that subsumption between queries is much harder to decide than in
logic programming.
This thesis abstracts from Xcerpt query term simulation, SPARQL graph pattern
matching and XPath XML document matching, and shows that all of them can be
considered as a form of rich unification. Given a set of mappings between
substitution sets of different languages, this abstraction opens up the
possibility for format-versatile querying, i.e. combination of queries in
different formats, or transformation of one format into another format within
a single rule.
To show the superiority of this approach, this thesis introduces an extension
of Xcerpt called Xcrdf, and describes use-cases for the combined querying
and integration of RDF and XML data. With XML being the predominant Web
format, and RDF the predominant Semantic Web format, Xcrdf extends Xcerpt
by a set of RDF query terms and construct terms, including query primitives
for RDF containers collections and reifications. Moreover, Xcrdf includes
an RDF path query language called RPL that is more expressive than previously
proposed polynomial-time RDF path query languages, but can still be evaluated
in polynomial time combined complexity.
Besides the introduction of this framework for data integration based on rich
unification, this thesis extends the theoretical knowledge about Xcerpt in
several ways: We show that Xcerpt simulation unification is decidable, and
give complexity bounds for subsumption in several fragments of Xcerpt query
terms. The proof is based on a set of subsumption monotone query term
transformations, and is only feasible because of the injectivity requirement
on subterms of Xcerpt queries. The proof gives rise to an algorithm for
deciding Xcerpt query term simulation. Moreover, we give a semantics to
locally and weakly stratified Xcerpt programs, but this semantics is
applicable not only to Xcerpt, but to any rule language with rich unification,
including multi-rule SPARQL programs. Finally, we show how Xcerpt grouping
stratification can be reduced to Xcerpt negation stratification, thereby also
introducing the notion of local grouping stratification and weak grouping
stratification
- …
