Stuttgart, Univ., Diplomarbeit, 2007.

Systems for selective dissemination of information (SDI) are used to efficiently filter, transform, and route incoming XML documents according to pre-registered XPath profiles to subscribers. Recent work focuses on the efficient implementation of the SDI core/filtering engine. Surprisingly, all systems are based on the best effort principle: The resulting XML document is delivered to the consumer as soon as the filtering engine has successfully finished. In this paper, we argue that a more specific Quality-of-Service consideration has to be applied to this scenario. We give a comprehensive motivation of quality of service in SDI-systems, discuss the two most critical factors of XML document size and shape and XPath structure and length, and finally outline our current prototype of a Quality-of-Service-based SDI-system implementation based on a real-time operating system and an extention of the XML toolkit.

Un mot de données (resp. un arbre de données) est un mot (resp. arbre) fini, dont chaque position est étiquetée avec une lettre d'un alphabet fini et une donnée d'un domaine infini. Dans cette thèse, nous étudions des automates et des logiques sur des mots et des arbres de données ayant des propriétés décidables: nous nous concentrons sur le problème du test du vide dans le cas des automates, et sur le problème de la satisfaisabilité dans le cas des logiques. Sur les mots de données, nous présentons une extension décidable du modèle d'automate alternant avec registre étudié par Demri et Lazic. En outre, nous montrons la décidabilité du problème de satisfaisabilité pour la logique du temps linéaire sur les mots de données LTL(X,F,U) (étudié par Demri et Lazic) étendue avec une quantification sur des données. Nous montrons aussi que la borne inférieure de non-récursivité primitive montré par Demri et Lazic pour LTL(X,F) est déjà valable pour LTL(F). Sur les arbres de données, nous considérons trois modèles décidables d'automates avec des caractéristiques différentes. Nous commençons par introduire l'automate avec donnée ``downward'' (automates DD). Son exécution consiste en une transduction ré-étiquetant la partie finie de l'étiquetage de l'arbre, et une vérification des propriétés des données de chaque sous-arbre de l'arbre résultant de la transduction. Ce modèle est clos par les opérations booléennes, mais les tests autorisés sur l'ordre des noeuds ayant le même père sont très limités. Son problème du vide est dans 2ExpTime. Au contraire, les deux autres modèles d'automates que nous introduisons ont un problème du vide avec une complexité non récursive primitive, et sont clos par intersection et union, mais par par complémentation. Ils ont tous les deux un contrôle alternant ainsi qu'un registre pour stocker et comparer les données. La classe des automates ATRA(guess,spread) généralise le modèle d'automate top-down ATRA de Jurdzinski et Lazic. Nous introduisons des extensions décidables similaires à celles que nous avons étudiées dans le cas de mots de données. Cette classe d'automates généralise la notion de langage rationnel d'arbre, ---contrairement aux automates DD. Enfin, nous considérons un modèle d'automate bottom-up avec un contrôle alternant et un registre (appelé BUDA). Bien que les BUDA soient bottom-up, ils peuvent tester des propriétés sur les données en navigant dans l'arbre dans les deux directions: vers le haut et vers le bas. Au contraire de ATRA(guess,spread), ce modèle d'automate ne peut pas tester de propriétés sur la séquence des noeuds ayant le même père (comme, par exemple, l'ordre dans lequel apparaissent leurs étiquettes). Ces trois modèles d'automates ont des liens avec la logique XPath---une logique conçue pour les documents XML, qui peuvent être vus comme des arbres de données. En utilisant les automates que nous avons mentionnés ci-dessus, nous montrons que la satisfaisabilité de trois fragments naturels de XPath sont décidables. Ces fragments sont: downward XPath, où la navigation ne peut se faire que via les axes child et descendant- forward XPath, où la navigation permet également les axes next sibling ainsi que sa clôture transitive, et vertical XPath, dont la navigation est limitée aux axes child, descendant, parent et ancestor. Alors que downward XPath est ExpTime-complet, les fragments forward et vertical de XPath ont une borne inférieure de non-récursivité primitive. / 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.

Sistemos veikimo logika – mazgo pasirinkimo semantika, pasinaudojant sukurtais dokumentų standartais aprašytais XML kalba (DTD, XSD). Problema iškyla, kai kuriant dinaminių dokumentų analizės įrankius laikomasi griežtų taisyklių, tai reiškia negalima sulaužyti statinio tipo dokumento struktūros ir jo logikos. Problemos sprendimui yra panaudojama XPath technologija. Tokiu būdų yra sukuriamos statinio tipo užklausos ir išrenkamas dokumentų turinys, kuris vėliau atvaizduojamas vartotojo ekrane. Pagrindinis darbas yra sukurti įrankį, kurio pagalba galima atlikti statinę dokumento analizę. Dokumento duomenimis galima migruoti į pasirinktą reliacinę duomenų bazę ar kitą pasirinktą (PDF, XSL) dokumento formatą. Tokie įrankiai - analizatoriai leidžia sutaupyti daug laiko apdorojant, išrenkant, išsaugant ir analizuojant turimus duomenis. / Nowadays, there is a lot of information in the internet, personal computer, mobile phone and everywhere around us. How we exchange this information? There are many decisions, but the most popular exchange form is using XML document standards. What is more, it will be everything good, but people are, who wants to use them, often faced with certain problems. They are trying get this information from these documents, but they cannot read it or very hard without any special software. Some people do not trust XML documents, because they didn’t use any time of them. Where is the problem? Some people could not understand XML document methodology; others did not use special software for special XML documents. It is software for storing and migrating signed XML documents. Special tools can save us time. People can quickly access the documents and information they need. It can help people work together in ways that are most effective for them.

XML promotes separation of presentation and data, reusability, extensibility, and division of labor. In addition, it has a simplified data model, allows one transaction in one place, and helps to simplify testing. XML is also becoming increasingly popular for allowing integration with legacy systems, a trend which promises to continue in the future. In this work a method for development of web site for processing data stored in relational database system is proposed. Method is based on Microsoft SQL Server 2000 new features that support XML functionality. The combination of these features makes SQL Server 2000 an XML-enabled database server. The design of data processing system on the Web was based on mapping between UML, relational and XML schemas. For implementation of the system SQL Server Annotated Schemas, XPath queries, Transact-SQL FOR XML, Updategrams and XSL technologies were used. The experimental Information System for Forest Re-Creation was developed.

Stuttgart, Univ., Diplomarb., 2002.

The eXtensible Access Control Markup Language (XACML) is allowing enterprises to implement a standard way of access control to their resources. Security administrators no longer need to duplicate their efforts in writing multiple policies for different resources since a XACML policy can be applied to multiple resources. Companies such as IBM, Sun Microsystems, Oracle, and Cisco are already providing integration of XACML in their products. Although the introduction of XACML has provided enterprises with a better approach of commonly realizing access control, there are still inconsistencies that policy administrators need to be aware of. This thesis identifies some of the inconsistencies in XACML today and introduces a new tool that can be used to visualize some of those inconsistencies. This new tool could be used by a policy administrator to visualize possible conflicting data among a set of policies.

The nature of semistructured data in web collections is evolving. Even when XML web documents are valid with regard to a schema, the actual structure of such documents exhibits significant variations across collections for several reasons: an XML schema may be very lax (e.g., to accommodate the flexibility needed to represent collections of documents in RSS feeds), a schema may be large and different subsets used for different documents (e.g., this is common in industry standards like UBL), or open content models may allow arbitrary schemas to be mixed (e.g., RSS extensions like those used for podcasting). A schema alone may not provide sufficient information for many data management tasks that require knowledge of the actual structure of the collection. Web applications (such as processing RSS feeds or web service messages) rely on XPath-based data manipulation tools. Web developers need to use XPath queries effectively on increasingly larger web collections containing hundreds of thousands of XML documents. Even when tasks only need to deal with a single document at a time, developers benefit from understanding the behaviour of XPath expressions across multiple documents (e.g., what will a query return when run over the thousands of hourly feeds collected during the last few months?). Dealing with the (highly variable) structure of such web collections poses additional challenges. This thesis introduces DescribeX, a powerful framework that is capable of describing arbitrarily complex XML summaries of web collections, providing support for more efficient evaluation of XPath workloads. DescribeX permits the declarative description of document structure using all axes and language constructs in XPath, and generalizes many of the XML indexing and summarization approaches in the literature. DescribeX supports the construction of heterogenous summaries where different document elements sharing a common structure can be declaratively defined and refined by means of path regular expressions on axes, or axis path regular expression (AxPREs). DescribeX can significantly help in the understanding of both the structure of complex, heterogeneous XML collections and the behaviour of XPath queries evaluated on them. Experimental results demonstrate the scalability of DescribeX summary refinements and stabilizations (the key enablers for tailoring summaries) with multi-gigabyte web collections. A comparative study suggests that using a DescribeX summary created from a given workload can produce query evaluation times orders of magnitude better than using existing summaries. DescribeX’s light-weight approach of combining summaries with a file-at-a-time XPath processor can be a very competitive alternative, in terms of performance, to conventional fully-fledged XML query engines that provide DB-like functionality such as security, transaction processing, and native storage.

The nature of semistructured data in web collections is evolving. Even when XML web documents are valid with regard to a schema, the actual structure of such documents exhibits significant variations across collections for several reasons: an XML schema may be very lax (e.g., to accommodate the flexibility needed to represent collections of documents in RSS feeds), a schema may be large and different subsets used for different documents (e.g., this is common in industry standards like UBL), or open content models may allow arbitrary schemas to be mixed (e.g., RSS extensions like those used for podcasting). A schema alone may not provide sufficient information for many data management tasks that require knowledge of the actual structure of the collection. Web applications (such as processing RSS feeds or web service messages) rely on XPath-based data manipulation tools. Web developers need to use XPath queries effectively on increasingly larger web collections containing hundreds of thousands of XML documents. Even when tasks only need to deal with a single document at a time, developers benefit from understanding the behaviour of XPath expressions across multiple documents (e.g., what will a query return when run over the thousands of hourly feeds collected during the last few months?). Dealing with the (highly variable) structure of such web collections poses additional challenges. This thesis introduces DescribeX, a powerful framework that is capable of describing arbitrarily complex XML summaries of web collections, providing support for more efficient evaluation of XPath workloads. DescribeX permits the declarative description of document structure using all axes and language constructs in XPath, and generalizes many of the XML indexing and summarization approaches in the literature. DescribeX supports the construction of heterogenous summaries where different document elements sharing a common structure can be declaratively defined and refined by means of path regular expressions on axes, or axis path regular expression (AxPREs). DescribeX can significantly help in the understanding of both the structure of complex, heterogeneous XML collections and the behaviour of XPath queries evaluated on them. Experimental results demonstrate the scalability of DescribeX summary refinements and stabilizations (the key enablers for tailoring summaries) with multi-gigabyte web collections. A comparative study suggests that using a DescribeX summary created from a given workload can produce query evaluation times orders of magnitude better than using existing summaries. DescribeX’s light-weight approach of combining summaries with a file-at-a-time XPath processor can be a very competitive alternative, in terms of performance, to conventional fully-fledged XML query engines that provide DB-like functionality such as security, transaction processing, and native storage.

Workshop "Netz- und Service-Infrastrukturen" Überblicksvortrag XSLT. Arbeitsweise, Kontrollfluss, Elemente und Funktionen