Info Beasiswa 2015 di PhD position on Streaming Path Queries for Linked Data

Please find below an offer for a PhD position on the subject Streaming Path Queries for Linked Data.


* LOCALIZATION
The Links Research Team, common to the CRIStAL research lab and Inria Nord Europe research center, Lille area, France.
The PhD candidate will defend a Doctorate degree at University of Lille.


* APPLICATION
We are looking for an excellent candidate expecting to get a Master Degree in Computer Science before September 2015.
Applications should be sent by email to
links-apply+streaming@lists.gforge.inria.fr
The application should include the candidate's CV, a cover letter explaining the candidate's motivation for the subject, and the names and contact information for one or two references who will be contacted directly. Please contact us on the same email address if you need additional information.


* IMPORTANT DATES
Suggested starting date for the thesis : between October and December 2015.
Deadline for application : May 15th 2015.


* ABOUT THE POSITION
The candidate will be employed by Inria. Monthly salary after taxes : around 1580 euro (social security included).
The thesis director is Joachim Niehren.


* LINKS
The Links research team https://team.inria.fr/links/
The CRIStAL research lab http://www.cristal.univ-lille.fr/
Inria Nord Europe http://www.inria.fr/centre/lille
University of Lille Science and Technologies http://www.univ-lille1.fr/


* DETAILED SUBJECT DESCRIPTION AND REFERENCES


Complex event processing for linked data [1,2] is fundamental to dynamic data management, where linked data is produced dynamically, exchanged over streams, stored in large scale distributed environments, queried, updated, and transformed [12]. Even though streams of complex events appear most naturally in distributed applications with sensors producing continuous data, or social networks in which all kind of structured data is exchanged, stream processing has not been introduced into NoSQL databases, whose purpose is to serve for managing  distributed linked data. In particular, we are interested in IBM's NoSQL database JAQL [3], which like all others is based on map/reduce style distributed programming with path queries for linked data [4].


In this thesis, we propose to develop stream processing algorithms that can be applied for complex event processing for linked data and integrated into NoSQL databases. The first task is to develop algorithms for answering path queries on data graphs. We hope that we can rely on existing streaming algorithms for path queries that were developed for data trees in the context of XML [8,9,10,11] also within the Links project [5,6]. The new questions are the following:
- Under which conditions can queries on data graphs be reduced to queries of spanning tree of the graph.
- How does the choice of the spanning tree influence the queries that can be expressed for the data
graph, and how does the complexity of the algorithms for query answering depend on it.
- How can one answer SPARQL queries on RDF graphs including conjunctive path queries with data
joins and aggregation?
- How can all this be done in practice by extending Links' QuiX-Toolsuite for answering path queries on XML data trees.


The second task is to lift streaming algorithms for answering path queries into map-reduce style distributed programming language based on path queries for linked data. The idea that a function can be mapped to linked data on many processors, return a linked data stream on any processor, and reduce the streams to a single result stream in real time. Rather than dealing with NoSQL databases directly, our objective is to develop a canonical purely functional programming with path queries and map-reduce distribution as a kind of core language. Motivated by our previous work on X-Fun [6,7], a uniform core language for XML processing with or without streams, we believe that a uniform distributed programming language should exist, that can serve as core language for various NoSQL databases, with or without streaming semantics.
The new questions are as follows:
- find a uniform language for distributed map-reduce style programming, that can serve as core language for NoSQL databases,
- provide a streaming evaluator for this language under the assumption that a algorithms for answering path queries on streams is provided.
- implement the streaming streaming evaluator and apply it prototypically to a fragment of a NoSQL database such as JAQL.


Bibliography
[1] Darko Anicic, Sebastian Rudolph, Paul Fodor, and Nenad Stojanovic. Stream reasoning and complex
event processing in ETALIS. Semantic Web, 3(4), 2012.
[2] Danh Le Phuoc, Minh Dao-Tran, Josiane Xavier Parreira, and Manfred Hauswirth. A native and adaptive
approach for unified processing of linked streams and linked data. In ISWC, 2011.
11[3] K. S. Beyer, V. Ercegovac, R. Gemulla, A. Balmin, M. Y. Eltabakh, C.-C. Kanne, F. Ã-zcan, and E. J.
Shekita. JAQL: A scripting language for large scale semistructured data analysis. Proceedings of the VLDB
Endowment (PVLDB), 4(12):1272â?"1283, 2011.
[4] V. Benzaken, G. Castagna, K. Nguyen, and J. Siméon. Static and dynamic semantics of NoSQL
languages. In R. Giacobazzi, R. Cousot, R. Giacobazzi, and R. Cousot, editors, ACM Symposium on
Principles of Programming Languages (POPL), pages 101â?"114. ACM, 2013.
[5] Tom Sebastian, Denis Debarbieux, Olivier Gauwin, Joachim Niehren, Mohamed Zergaoui
Early Nested Word Automata for XPath Query Answering on XML Streams. Theoretical Computer Science,
Elsevier, 2015, pp.42.
[6] Pavel Labath, Joachim Niehren. A Uniform Programming Language for Implementing XML Standards
41st International Conference on Current Trends in Theory and Practice of Computer Science, Lecture Notes
in Computer Science, Jan 2015.
[7] Pavel Labath. Hyperstreaming for XML standards. PhD thesis. University of Bratislava, Jan 2015.
[8] A. K. Gupta and D. Suciu. Stream processing of XPath queries with pred- icates. In ACM SIGMOD
Conference, pages 419â?"430. 2003.
[9] M. Kay. A streaming XSLT processor. In Balisage: The Markup Conference 2010. Balisage Series on
Markup Technologies, volume 5, 2010.
[10] B. Mozafari, K. Zeng, and C. Zaniolo. High-performance complex event processing over XML streams. In
SIGMOD Conference, pages 253â?"264. ACM, 2012.
[11] D. Olteanu. SPEX: Streamed and progressive evaluation of XPath. IEEE Trans. on Know. Data Eng.,
19(7):934â?"949, 2007.
[12] Mohammed Elseidy, Abdallah Elguindy, Aleksandar Vitorovic, Christoph Koch: Scalable and Adaptive
Online Joins. PVLDB 7(6): 441-452 (2014)