The aim of the thesis was to develop an algorithm to generate synthetic XML documents to cover the resolution of an XPath query with test cases, with a special emphasis on the ease of configuration. We have also implemented a prototype, optimized its performance and demonstrated its properties by running it on sample data. Powered by TCPDF (www.tcpdf.org)

The PHP: Hypertext Preprocessor language (PHP) has evolved to a sophisticated mainstream programming language for rapid development of significant Web applications at major sites including Facebook.com, Wikipedia.org and Yahoo.com. Leading software vendors such as Oracle and IBM are rushing in providing tools that bridge their products to PHP. However, we have observed a gap in facilitating PHP to utilize Web services efficiently. This thesis reports our efforts in design and implementation of PHP applications that consume Web services. In doing so, I have proposed a framework facilitating PHP programs to utilize Web services with high performance capability. In addition, a number of Web service standards including WS-Addressing and those in WS-Security are integrated into my PHP implementation. Examples of using various Amazon Web Services are provided with details.

Web Services have been the dominant technology in business integration and implementation of service oriented architectures. PHP is a server-side language popular for development of applications. A significant advantage of PHP is its light weight development for feature-rich web applications. Typically, PHP is used for making good-looking front end user interfaces; Java or other programming languages are used to develop the back end application. A secure and robust way for PHP programs to call back-end services is by Web Services. However, when the Web Service operations have complex interfaces, writing PHP client code can be difficult and error-prone. This thesis research seeks to develop a Web service-PHP program middleware that automatically handles the client-side Web Service calls. Two Web Services are developed, as well as two Web applications that consume the two Web Services, and experiments that demonstrate the usage of the WS-PHP middleware component are conducted.

A general XML index can itself be sizable leading to low efficiency. To alleviate this predicament, frequently asked queries can be indexed by a database system. They are referred to as views. Answering queries using materialized views is always cheaper than evaluating over the base data. Traditional techniques solve this problem by considering only a single view. We approach this problem by exploiting the potential relationships of multiple views, which can be used together to answer a given query. Experiments show that significant performance gain can be achieved from multiple views. / A XML query can be decomposed to a sequence of structural joins (e.g., parent/child and ancestor/descendant) and content joins. Thus, structural join optimization is a key to improving join-based evaluation. We optimize structural join with two orthogonal methods: partition-based method exploits the spatial specialities of XML encodings by projecting them on a plane; and location-based method improves structural join by accurately pruning all irrelevant nodes, which cannot produce results. / As XML (eXtensible Markup Language) becomes a universal medium for data exchange over the Internet, efficient XML query processing is now the focus of considerable research and development activities. This thesis describes works toward efficient XML query evaluation and optimization in native XML databases. / XML indexes are widely studied to evaluate XML queries and in particular to accelerate join-based approaches. Index-based approaches outperform join-based approaches (e.g., holistic twig join) if the queries match the index. Existing XML indexes can only support a small set of XML queries because of the varieties in XML query representations. A XML query may involve child-axis only, both child-axis and branches, or additional descendant-or-self-axis but only in the query root. We propose novel indexes to efficiently support a much wider range of XML queries (with /, //, [], *). / Tang, Nan. / "December 2007." / Advisers: Kam-Fei Wong; Jeffrey Xu Yu. / Source: Dissertation Abstracts International, Volume: 69-08, Section: B, page: 4861. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2007. / Includes bibliographical references (p. 152-163). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstracts in English and Chinese. / School code: 1307.

In computer science many data are shaped as trees. In the context of the Web, it is the case for XML formatted data in particular. XML is a markup language that has rapidly become a standard for information storage and data exchange. As query languages for relational databases are not well-suited to XML data, the need to have query languages specific to XML documents has increased. We distinguish unary queries which select a set of subparts of a document from n-ary queries which select a set of n-tuples of subparts of a document. Many logical formalisms for unary queries have been proposed, but less work has been done on logical formalisms for n-ary queries. This thesis is a fundamental study of n-ary queries that proposes two logical formalisms for n-ary queries: an extension of the navigational paradigm of the W3C standard XPath to n-ary queries, called the composition language, and an adapation of the spatial logic TQL introduced by Cardelli and Ghelli. The question of expressive power, the complexity of the query evaluation problem as well as the satisfiability problem are considered. In particular, the satisfiability problem for a TQL fragment is proved to be decidable by reduction to the emptiness test of a new class of tree automata with global constraints that is studied independently.

Ces dernières années, XML est devenu le format standard pour l'échange de données. Les documents XML sont généralement produits à partir de bases de données, durant le traitement de documents, ou au sein d'applications Web. L'échange de données en flux est fréquemment utilisé lors de l'envoi de données volumineuses par le réseau. Ainsi le transfert par flux est adéquat pour de nombreux traitements XML.<br /><br />Dans cette thèse, nous étudions des algorithmes d'évaluation de requêtes sur des flux XML. Notre objectif est de gérer efficacement la mémoire, afin de pouvoir évaluer des requêtes sur des données volumineuses, tout en utilisant peu de mémoire. Cette tâche s'avère complexe, et nécessite des restrictions importantes sur les langages de requêtes. Nous étudions donc les requêtes définies par des automates déterministes ou par des fragments du standard W3C XPath, plutôt que par des langages plus puissants comme les standards W3C XQuery et XSLT.<br /><br />Nous définissons tout d'abord les Streaming Tree Automata (STAs), qui opèrent sur les arbres d'arité non bornée dans l'ordre du document. Nous prouvons qu'ils sont équivalents aux Nested Word Automata et aux Pushdown Forest Automata. Nous élaborons ensuite un algorithme d'évaluation au plus tôt, pour les requêtes définies par des STAs déterministes. Bien qu'il ne stocke que les candidats nécessaires, cet algorithme est en temps polynomial à chaque événement du flux, et pour chaque candidat. Par conséquent, nous obtenons des résultats positifs pour l'évaluation en flux des requêtes définies par des STAs déterministes. Nous mesurons une telle adéquation d'un langage de requêtes à une évaluation en flux via un nouveau modèle de machines, appelées Streaming Random Access Machines (SRAMs), et via une mesure du nombre de candidats simultanément vivants, appelé concurrence. Nous montrons également qu'il peut être décidé en temps polynomial si la concurrence d'une requête définie par un STA déterministe est bornée. Notre preuve est basée sur une réduction au problème de la valuation bornée des relations reconnaissables d'arbres.<br /><br />Concernant le standard W3C XPath, nous montrons que même de petits fragments syntaxiques ne sont pas adaptés à une évaluation en flux, sauf si P=NP. Les difficultés proviennent du non-déterminisme de ce langage, ainsi que du nombre de conjonctions et de disjonctions. Nous définissons des fragments de Forward XPath qui évitent ces problèmes, et prouvons, par compilation vers les STAs déterministes en temps polynomial, qu'ils sont adaptés à une évaluation en flux.

Les contraintes arithmétiques sont largement utilisées dans les langages formels comme les expressions, les grammaires d'arbres et les chemins réguliers. Ces contraintes sont utilisées dans les modéles de contenu des types (XML Schemas) pour imposer des bornes sur le nombre d'occurrences de nœuds. Dans les langages de requêtes (XPath, XQuery), ces contraintes permettent de sélectionner les nœuds ayant un nombre limité de nœuds accessibles par une expression de chemin donnée. Les types et chemins étendus avec les contraintes de comptage constituent le prolongement naturel de leurs homologues sans comptage déjà considérés comme des constructions fondamentales dans les langages de programmation et les systèmes de type pour XML. Un des défis majeurs en programmation XML consiste à développer des techniques automatisées permettant d'assurer statiquement un typage correct et des optimisations de programmes manipulant les données XML. À cette fin, il est nécessaire de résoudre certaines tâches de raisonnement qui impliquent des constructions telles que les types et les expressions XPath avec des contraintes de comptage. Dans un futur proche, les compilateurs de programmes XML devront résoudre des problèmes de base tels que le sous-typage afin de s'assurer au moment de la compilation qu'un programme ne pourra jamais générer de documents non valides à l'exécution. Cette thèse étudie les logiques capables d'exprimer des contraintes de comptage sur les structures d'arbres. Il a été montré récemment que le mu-calcul sur les graphes, lorsqu'il est étendu à des contraintes de comptage portant exclusivement sur les nœuds successeurs immédiats est indécidable. Dans cette thèse, nous montrons que, sur les arbres finis, la logique avec contraintes de comptage est décidable en temps exponentiel. En outre, cette logique fournit des opérateurs de comptage selon des chemins plus généraux. En effet, la logique peut exprimer des contraintes numériques sur le nombre de nœuds descendants ou même ascendants. Nous présentons également des traductions linéaires d'expressions XPath et de types XML comportant des contraintes de comptage dans la logique.

In this thesis we present an automated system that allows users to execute XPATH queries against an XML data source. The system exploits the shared-inlining mapping from XML to Relational data. At the core of the system is an XPATH to SQL transformation algorithm that produces corresponding SQL queries for a subset of XPATH. This approach allows one to utilize standard relational databases to store XML data. Given a DTD, the system creates appropriate relational tables based on the shared-inlining method. The system is capable of transforming an XML data source that conforms to the DTD into relational data. The main component of the system is the XPATH interpreter that parses an XPATH expression for the XML data source and transforms it into an equivalent SQL query. The SQL query is then executed against the relational database and results are packaged into XML and returned as the answer to the XPATH query. The use of the relational database to store and query the XML data is transparent to the user as they interact only with the XPATH interpreter. This methodology provides a novel technique to provide an XML database system implementation. Index Words: XML SQL transformation, XPATH to SQL queries, XSU, Data mapping.

<p>Planning is indeed a highly regulated procedure at the operational level such as military related activities where the staff may benefit from documents such as guidelines that regulate the work process, responsibilities and results of such planning activities.</p><p>This thesis proposes a method for analyzing office documents that make up an operational order according to document ontology. With the semantic desktops aiming at combining semantic annotations and intelligent reasoning in desktop computers, the product of this project intends to add a plug-in to such environments such as IRIS semantic desktop, which accordingly enables such application to interpret documents whether the they  or change within the application.</p><p>The result of our work helps the end user to extract data using his/her favorite patterns such as goals, targets or even milestones that make up decisive points. This information eventually form semantic objects, which ultimately reside in the knowledgebase of the semantic desktop for further reasoning in the future referring of the application, whether automatically or upon the user's request.</p>

A data word (resp. a data tree) is a &#64257-nite word (resp. tree) whose every position carries a letter from a &#64257-nite alphabet and a datum form an in&#64257-nite domain. In this thesis we investigate automata and logics for data words and data trees with decidable reasoning problems: we focus on the emptiness problem in the case of automata, and the satis&#64257-ability problem in the case of logics. On data words, we present a decidable extension of the model of alternating register automata studied by Demri and Lazi'c. Further, we show the decidability of the satis&#64257-ability problem for the linear-time temporal logic on data words LTL_\downarrow (X, F, U) (studied by Demri and Lazi'c) with quanti&#64257-cation over data values. We also prove that the lower bounds of non-primitive recursiveness shown by Demri and Lazi'c for LTL&#8595- (X, F) carry over to LTL&#8595- (F). On data trees, we consider three decidable automata models with di&#64256-erent characteristics. We &#64257-rst introduce the Downward Data automaton (DD automata). Its execution consists in a transduction of the &#64257-nite labeling of the tree, and a veri&#64257-cation of data properties for every subtree of the transduced tree. This model is closed under boolean operations, but the tests it can make on the order of the siblings is very limited. Its emptiness problem is 2ExpTime. On the contrary, the other two automata models we introduce have an emptiness problem with a non-primitive recursive complexity, and are closed under intersection and union, but not complementation. They are both alternating automata with one register to store and compare data values. The automata class ATRA(guess, spread) extends the top-down automata ATRA of Jurdzinski and Lazic. We exhibit similar decidable extensions as the one showed in the case of data words. This class can test for any tree regular language--in contrast to DD automata. Finally, we consider a bottom-up alternating tree automaton with one register (called BUDA). Although the BUDA class is one-way, it has features that allow to test data properties by navigating the tree in both directions: upward and downward. In opposition to ATRA(guess, spread), this automaton cannot test for properties on the the sequence of siblings (like, for example, the order in which labels appear). All these three models have connections with the logic XPath--a logic conceived for xml documents, which can be seen as data trees. Through the aforementioned automata we show that the satis&#64257-ability of three natural fragments of XPath are decidable. These fragments are: downward XPath, where navigation can only be done by child and descendant axes- forward XPath, where navigation also contains the next sibling axis and its transitive closure- and vertical XPath, whose navigation consists in the child, descendant, parent and ancestor axes. Whereas downward XPath is ExpTime-complete, forward and vertical XPath have non-primitive recursive lower bounds.