The web can be though of as a huge graph. However, semantic web principles promote knowledge representation as an even huger distributed graph. Exploiting information within this graph requires to evaluate queries and to transform extracted information.
In XML trees, queries are based on the evaluation of regular tree expressions à la XPath. Queries and documents can be considered as mu-calculus formulas interpreted on finite trees. We have already shown how to optimize such queries.
On the semantic web, the SPARQL query language allows boolean combination of edges in RDF graphs. We have shown how SPARQL can be extended with regular expressions to express path expressions instead of triples. This allows constructs such as transitive closures.
In both cases, the questions are the same: what is the complexity of query evaluation? How to statically determine that a query has no answer by construction? How to build an efficient query evaluator?
We want to study the combination of both approaches through a common query language expressing path expressions in SPARQL and considering the problem within the full mu-calculus (including foward/backward navigation and nominals).
This raises at least three difficulties: (1) regarding path expressions, it is necessary to evaluate queries in graphs instead of trees, (2) these graphs can be interpreted modulo a specific logic, i.e., the deductive closure of the logic would enrich the actual graph with new nodes and edges, and (3) regarding SPARQL, path expressions will increase the expressiveness with respect to the constrained regular expressions used so far.
The best trade-offs between query expressiveness and data logics on one side and techniques for optimising query evaluation on the other side will be investigated.
The results of this work may be applied to languages and services for manipulating web data: search engines, document transformation and aggregation or distributed reasoners.
Références:
Faisal Alkhateeb, Jean-François Baget, Jérôme Euzenat, Extending SPARQL with Regular Expression Patterns (for Querying RDF), Journal of web semantics 7(2):57-73, 2009
Piero Bonatti, Carsten Lutz, Aniello Murano, Moshe Vardi, The Complexity of Enriched mu-Calculi. Proc. ICALP, pp540-551, 2006
Pierre Genevès, Nabil Layaïda, Alan Schmitt, Efficient static analysis of XML paths and types, Proc. Conference on Programming Language Design and Implementation (PLDI), San Diego (CA US), pp342-351, 2007
Qualification: Master or equivalent in computer science.
Researched skills:
Environnement: The doctoral work is to be carried out in the Exmo and Wam team, two reputed teams within the semantic web research area and XML programming, respectively. We are in contact with the most important teams in France and Europe on these topics.
Doctoral school: Doctoral school MSTII, Grenoble.
Advisors: Jérôme Euzenat (Jerome:Euzenat#inrialpes:fr) and Nabil Layaïda (Nabil:Layaida#inrialpes:fr)
Groups: Exmo and WAM, INRIA Grenoble Rhône-Alpes
Hiring date: September 2009.
Place of work: The position is located at INRIA Rhône-Alpes, Montbonnot (near Grenoble, France) a main computer science research lab, in a stimulating research environment. Research will be carried out in the Exmo team under the supervision of Jérôme Euzenat. It will require the involvement of the candidate in related projects.
Duration: 36 months
Salary: 1537 EUR/month net (including full health insurance and social benefits) upgraded to 1620 EUR/month the 3rd year.
Contact: For further information, contact Jerome:Euzenat#inrialpes:fr or Nabil:Layaida#inrialpes:fr.
Procedure:
Visit
INRIA's
presentation (including FAQ and forms) .
File: Provide Vitæ, motivation letter and references.
Please be sure to apply on INRIA online application system