Research themes: Web, programming languages, logic, multimedia
Supervisor: Cécile Roisin
Co-supervisor: Pierre Genevès
Location: INRIA Grenoble Rhône-Alpes, Montbonnot
Contact: Pierre dot Geneves at inria dot fr, Cecile dot Roisin at inria dot fr
The technological development around XML is unprecedented in many respects. In recent years, the amount of information which is stored, exchanged, and presented using XML has drastically increased in many different application areas. A large family of standards have been or are being developed by international standard bodies (World Wide Web Consortium, ISO, etc.) for various tasks such as querying, formatting, modeling scientific content, and for modeling interactions between distributed entities and the coordination of such interactions, validation of data by schemas, their update, etc. Another unique dimension of the XML technology boom is the availability of many free tools, broadening the set of potential developers to an extent that has never been reached before, and encouraging experimentation and innovation. Finally, a third dimension is the rich interaction between academic research and industrial players, which takes place within the standard bodies, in international technical meetings, and more generally on the world stage for people interested in XML technologies.
In this context, the ability to query XML data in a safe, effective and consistent manner on different platforms such as mobile devices becomes crucial. XQuery is the increasingly popular W3C standard language for querying XML data. One of the major challenges in web software development today is to help achieving a good quality of code in terms of reliability and performance for executing XQuery programs (in particular on mobile devices), by providing development environments that are adapted to the production of high-level XQuery code containing XPath queries. One of the main scientific difficulties consists in addressing the very high computational complexity of reasoning with XPath queries and XML schemas (for restrictions making this problem decidable). Such automatic reasoning is necessary for performing static type verification for XML [b, c, 1]. In this context, recent breakthroughs by the WAM team [1, 5] paved the way for the development of a new class of effective static analyzers capable of supporting real world XPath queries and XML schemas [2].
The subject of this PhD thesis concerns the extension of these results to XQuery, for which no current development environment provides any form of static analysis to ensure type-safety and optimization at compile-time. The impact of results in this direction would be even more important if we consider the recent advances in standard formats of data such as the advent of OpenStreetMap, HTML5, SVG and other formats oriented interface [9, 10], and interactions between browsers and remote services [a] [6]. For all these reasons, we believe t hat a consistent and reliable alternative to JavaScript can be played with languages such as XQuery.
In recent years, we have observed a change in the basic equipment used to access digital services in general and the web in particular. Indeed, it is no longer the personal computer, whether a workstation or a laptop, but the telephone and other tablets that became the privileged computer devices. This kind of terminal has the advantage of being in direct contact with the real world of the user, through its communication capabilities, its mobility and its recording abilities of the environment: geographic location, video camera, motion capture, etc. Thus, IT is evolving in terms of uses and it is necessary to accompany this mutation on the theoretical and technological side by improving the development of applications for these devices. However, so far, no mobile development environment, whether Xcode for iPhone / iPad or those for Android, provides static analysis functions for validating and optimizing code for mobile applications. This is the central theme of this thesis that, starting from the analysis of characteristics of the data processed on mobile devices (multimedia data, XML stream) and the specificities of these equipments (low energy independence, reduced memory capacity), aims at helping the production of efficient code in order to optimize and verify the application programs for mobile devices. Such programs often consists in JavaScript code that runs in the mobile browser and that performs requests using XQuery [a].
Concretely, the proposed work will consist in extending a logical environment for XML reasoning (see the XML Reasoning project) so that it allows for the efficient resolution of the previously exposed aspects, while modeling the largest possible number of features found in XQuery.
The theoretical foundations are based on formal verification techniques recently developed in the team [1, 5], and which are now mature enough to be introduced in the broader context of software development [3, 4]. The development environment will provide:
Current partnerships of the team will provide a framework for direct experimentation and validation of these tools. Indeed, the researchers of the team and their partners are now confronted with the problem of code production for indoor navigation mobile applications, in which data consist of XML structured streams for geolocation and audio [6, 11]. At a broader level, expected results aims at improving the development environments for mobile devices, and therefore the art of software development. Therefore, applicants should have interests in programming languages for the web, with a concern in the intersection of theory and practice.
[a] XQuery in the browser. Ghislain Fourny, Donald Kossmann, Tim Kraska, Markus Pilman, and Daniela Florescu. SIGMOD '08.
[b] XML Typechecking. Véronique Benzaken, Giuseppe Castagna, Haruo Hosoya, Benjamin C. Pierce, Stijn Vansummeren. Encyclopedia of Database Systems, 2009, p. 3646-3650.
[c] Stéphane Demri, Denis Lugiez, Complexity of modal logics with Presburger constraints, Journal of Applied Logic, Volume 8, Issue 3, September 2010, p. 233-252.
[1] Efficient Static Analysis of XML Paths and Types. Pierre Geneves, Nabil Layaida and Alan Schmitt. In PLDI'07 : Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, pages 342-351.
[2] Impact of XML Schema Evolution. Pierre Geneves, Nabil Layaida and Vincent Quint. In TOIT'11 : ACM Transactions on Internet Technology, vol. 11, issue 1, pages 1-27, July 2011.
[3] Inconsistent Path Detection for XML IDEs. Pierre Geneves, Nabil Layaida. In ICSE’11 : Proceedings of the 33rd ACM/IEEE International Conference on Software Engineering, ICSE 2011, pp. 983-985, May 2011.
[4] Eliminating Dead-Code from XQuery Programs. Pierre Geneves, Nabil Layaida. In ICSE’10 : Proceedings of the 32nd ACM/IEEE International Conference on Software Engineering, ICSE 2010, pp. 305-306, May 2010.
[5] XML Reasoning Made Practical (ICDE'10). Pierre Geneves and Nabil Layaida. In ICDE’10 : Proceedings of the 26th IEEE International Conference on Data Engineering, pages 1169-1172.
[6] Mixed Reality Browsers. Jacques Lemordant. In International workshop on AR Standards, February 2011.
[7] From Templates to Schemas: Bridging the Gap Between Free Editing and Safe Data Processing. Vincent Quint, Cecile Roisin, Stéphane Sire, Christine Vanoirbeek. In ACM DocEng 2010, pp. 61-64, ACM, September 2010.
[8] Authoring XML all the Time, Everywhere and by Everyone. Stephane Sire, Christine Vanoirbeek, Vincent Quint, Cecile Roisin. In Proceedings of XML Prague 2010, pp. 125-149, Institute for Theoretical Computer Science, March 2010.
[9] Timesheets.js: When SMIL Meets HTML5 and CSS3. Fabien Cazenave, Vincent Quint, Cecile Roisin. In DocEng 2011: Proceedings of the 2011 ACM Symposium on Document Engineering, pp. 43-52, ACM, September 2011.
[10] Timesheets.js: Tools for Web Multimedia. Fabien Cazenave, Vincent Quint, Cecile Roisin. In Multimedia’11: Proceedings of the 19th ACM International Conference on Multimedia, ACM, November 2011.
[11] One Idea and Three Concepts for Indoor-Outdoor Navigation. A. Colbrant, J. Lemordant, D.Liodenot, M. Razafinahazo. Rapport de recherche Inria decembre 2011.
XQuery, static analysis, type system, security, mobile computing
12 March 2012