Because XML has become a new standard for data representation, there is a need for a simple conceptual model that works well with XML-based development. In this research we present a conceptual model for XML, called C-XML, which meets this new need of systems analysts who store their data using XML. We describe our implementation of an automatic conversion from XML Schema to C-XML that preserves information and constraints. With this conversion, we can view an XML Schema instance graphically at a higher level of abstraction. We also describe our implementation of an automatic conversion from C-XML to XML Schema. Our con- version preserves information and constraints as long as we count the special C-XML comments that we insert in an XML-Schema instance to capture the constraints in C-XML that are not representable in XML Schema. In connection with defining C- XML and implementing conversions between C-XML and XML Schema, we are also able to make several insightful observations. We point out ways in which C-XML is more expressive than XML Schema, and we make recommendations for extending XML Schema. We also point out ways in which XML Schema is more expressive than conceptual models, and we make recommendations for augmenting traditional con- ceptual models to better accommodate XML. The work accomplished in connection with this research establishes the basis for several fundamental activities in system analysis, design, development, and evolution.

ITC/USA 2007 Conference Proceedings / The Forty-Third Annual International Telemetering Conference and Technical Exhibition / October 22-25, 2007 / Riviera Hotel & Convention Center, Las Vegas, Nevada / Many engineers express frustration with the multitude of vendor specific tools required to describe measurements and configure data acquisition systems. In general, tools are incompatible between vendors, forcing the engineer to enter the same or similar data multiple times. With the emergence of XML technologies, user centric data modeling for the flight test community is now possible. With this new class of technology, a vendor neutral, standard language to define measurements and configure systems may finally be realized. However, the allure of such a universal language can easily become too abstract, making it untenable for hardware configuration and resulting in a low vendor adoption rate. Conversely, a language that caters too much to vendor specific configuration will defeat its purpose. Achieving this careful balance is not trivial, but is possible. Doing so will produce a useful standard without putting it out of the reach of equipment vendors. This paper discusses the concept, merits, and possible solutions for a standard measurement metadata model. Practical solutions using XML and related technologies are discussed.

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 noeuds. Dans les langages de requêtes (XPath, XQuery), ces contraintes permettent de sélectionner les noeuds ayant un nombre limité de noeuds 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 μ-calcul sur les graphes, lorsqu'il est étendu à des contraintes de comptage portant exclusivement sur les noeuds 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 noeuds 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.

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.

Pendant la dernière décennie, le format de données XML est devenu l'un des principaux moyens de représentation et d'échange de données sur le Web. La détection de l'indépendance entre une requête et une mise à jour, qui a lieu en absence d'impact d'une mise à jour sur une requête, est un problème crucial pour la gestion efficace de tâches comme la maintenance des vues, le contrôle de concurrence et de sécurité. Cette thèse présente une nouvelle technique d'analyse statique pour détecter l'indépendance entre requête et mise à jour XML, dans le cas où les données sont typées par un schéma. La contribution de la thèse repose sur une notion de type plus riche que celle employée jusqu'ici dans la littérature. Au lieu de caractériser les éléments d'un document XML utiles ou touchés par une requête ou mise à jour en utilisant un ensemble d’étiquettes, ceux-ci sont caractérisés par un ensemble de chaînes d'étiquettes, correspondants aux chemins parcourus pendant l'évaluation de l’expression dans un document valide pour le schéma. L'analyse d'indépendance résulte du développement d'un système d'inférence de type pour les chaînes. Cette analyse précise soulève une question importante et difficile liés aux schémas récursifs: un ensemble infini de chaînes pouvant être inférées dans ce cas, est-il possible et comment se ramener à une analyse effective donc finie. Cette thèse présente donc une technique d'approximation correcte et complète assurant une analyse finie. L'analyse de cette technique a conduit à développer des algorithmes pour une implantation efficace de l'analyse, et de mener une large série de tests validant à la fois la qualité de l'approche et son efficacité. / In the last decade XML became one of the main standards for data storage and exchange on the Web. Detecting XML query-update independence is crucial to efficiently perform data management tasks, like those concerning view-maintenance, concurrency control, and security. This thesis presents a novel static analysis technique to detect XML query-update independence, in the presence of a schema. Rather than types, the presented system infers chains of types. Each chain represents a path that can be traversed on a valid document during query/update evaluation. The resulting independence analysis is precise, although it raises a challenging issue: recursive schemas may lead to infer infinitely many chains. This thesis presents a sound and complete approximation technique ensuring a finite analysis in any case, together with an efficient implementation performing the chain-based analysis in polynomial space and time.

In the present work we analyze the algorithm that was introduced in [4]. The algorithm performs a translation of a conceptual schema to an XML schema expressed in the XML Schema language. We look for limitations of the algorithm and try to discover parameters that can be potentially used to influence its behavior. We propose solutions to the most serious limitations. Also, we introduce a concept of a translation profiling. The concept is based on a configuration that contains a set of parameters. We modify the algorithm to use the user requirements specified in the configuration. Thanks to the improvements, the new algorithm works with the concept of XML Namespaces, uses XML Schema designs and also, focuses on an elimination of redundancy. The elimination of redundancy in an output of the algorithm is an important part of this work and we create a formal model that helps us to solve this task.

In the present work we study conceptual modeling of business ar- tifacts and their implementation in Active XML. Business artifacts are key con- ceptual entities of business processes that develop in their lifecycle during these processes. There are several possible methods for definition of artifact lifecycles. In this work, we make use of emerging method called Guard-Stage-Milestone meta- model and we study the question on how to appropriately use and extend current framework for conceptual modeling of XML schemas in order to support modeling of business artifacts. We also deal with the issue of design of suitable represen- tation of business artifacts using Active XML. Last but not least, we study the question how to translate defined model into proposed Active XML representation, so that it was possible to immediately use and demonstrate functionality of defined model. Important part of this work is an implementation of proposed extension and a prototype implementation of system for execution of Active XML repre- sentations of translated models. The present work also introduces the reader in individual used concepts and describes similar existing approach for Active XML representation of business artifacts. 1

We study the problem of updating XML views defined over XML documents. A view update is performed by finding the base updates over the underlying data sources that achieve the desired view update. If such base updates do not exist, the view update is said to be untranslatable and rejected. In SQL, determining whether a view update is translatable is performed using schema level analysis, where the view definition and the base schema are used. XML schemas are more complex than SQL schemas, and can specify recursive types and cardinality constraints. There are two kinds of view updates: single view element update, where the user requires for an update over a particular view element, and a set of view elements update, where the user requires for an update over all view elements that satisfy a given XPath over the view. Accordingly, we propose one solution for each kind of view update problems based on schema level analysis for determining whether an update over XML views is translatable and for finding the translation if one exists, while considering the features of XML schemas.

O objetivo geral desta tese é a detecção, o gerenciamento e a consulta às réplicas e às versões de documentos XML. Denota-se por réplica uma cópia idêntica de um objeto do mundo real, enquanto versão é uma representação diferente, mas muito similar, deste objeto. Trabalhos prévios focam em gerenciamento e consulta a versões conhecidas, e não no problema da detecção de que dois ou mais objetos, aparentemente distintos, são variações (versões) do mesmo objeto. No entanto, o problema da detecção é crítico e pode ser observado em diversos cenários, tais como detecção de plágio, ranking de páginas Web, identificação de clones de software e busca em sistemas peer-to-peer (P2P). Nesta tese assume-se que podem existir diversas réplicas de um documento XML. Documentos XML também podem ser modificados ao longo do tempo, ocasionando o surgimento de versões. A detecção de réplicas é relativamente simples e pode ser feita através do uso de funções hash. Já a detecção de versões engloba conceitos de similaridade, a qual pode ser medida por várias métricas, tais como similaridade de conteúdo, de estrutura, de assunto, etc. Além da análise da similaridade entre os arquivos também se faz necessária a definição de um mecanismo de detecção de versões. O mecanismo deve possibilitar o gerenciamento e a posterior consulta às réplicas e às versões detectadas. Para que o objetivo da tese fosse alcançado foram definidos um conjunto de funções de similaridade para arquivos XML e o mecanismo de detecção de réplicas e de versões. Também foi especificado um framework onde tal mecanismo pode ser inserido e os seus respectivos componentes, que possibilitam o gerenciamento e a consulta às réplicas e às versões detectadas. Foi realizado um conjunto de experimentos que validam o mecanismo proposto juntamente com a implementação de protótipos que demonstram a eficácia dos componentes do framework. Como diferencial desta tese, o problema de detecção de versões é tratado como um problema de classificação, para o qual o uso de limiares não é necessário. Esta abordagem é alcançada pelo uso da técnica baseada em classificadores Naïve Bayesianos. Resultados demonstram a boa qualidade obtida com o mecanismo proposto na tese. / The overall goals of this thesis are the detection, management and querying of replicas and versions of XML documents. We denote by replica an identical copy of a real-world object, and by version a different but very similar representation of this object. Previous works focus on version management and querying rather than version detection. However, the version detection problem is critical in many scenarios, such as plagiarism detection, Web page ranking, software clone identification, and peer-to-peer (P2P) searching. In this thesis, we assume the existence of several replicas of a XML document. XML documents can be modified over time, causing the creation of versions. Replica detection is relatively simple and can be achieved by using hash functions. The version detection uses similarity concepts, which can be assessed by some metrics such as content similariy, structure similarity, subject similarity, and so on. Besides the similarity analysis among files, it is also necessary to define the version detection mechanism. The mechanism should allow the management and the querying of the detected replicas and versions. In order to achieve the goals of the thesis, we defined a set of similarity functions for XML files, the replica and version detection mechanism, the framework where such mechanism can be included and its components that allow managing and querying the detected replicas and versions. We performed a set of experiments for evaluating the proposed mechanism and we implemented tool prototypes that demonstrate the accuracy of some framework components. As the main distinguishing point, this thesis considers the version detection problem as a classification problem, for which the use of thresholds is not necessary. This approach is achieved by using Naïve Bayesian classifiers.

<p>U stvarnom životu većina informacija dolazi kao neprecizne ili<br />nepotpune vrednosti.&nbsp; XML tehnologija je napravila veliki<br />napredak u oblasti skladi&scaron;tenja i prenosa podataka.&nbsp; Doktorska<br />disertacija defini&scaron;e fazi XML sintaksu koja kombinuje neodređenosti<br />u vrednostima XML-a i neodređenosti u strukturi XML dokumenata.<br />Takođe, rad pro&scaron;iruje standardnu XQuery upitnu sintaksu fazi<br />elementima i uvodi prioritete i pragove zadovoljenja pomoću<br />GPFCSP-a. Za razliku od drugih radova koji se fokusiraju na<br />postavljanje teorija i definisanje sintaksi, rad posebnu pažnju<br />posvećuje praktičnoj upotrebi definisanih sintaksi. Za potrebe<br />istraživanja razvijen je softverski paket koji omogućava rad kako sa<br />standardnim, tako i sa fazi XML, XSD i DTD dokumentima, kao i<br />postavljanje i izvr&scaron;avanje prioritizovanih fazi XQuery upita. Alat je<br />testiran nad primerima iz prakse.</p> / <p>In real life, as opposed to virtual, most information comes in the<br />form of imprecise or incomplete values. XML&nbsp; technology has<br />made great progress in the field of storage and data transfer.<br />This doctoral dissertation&nbsp; developed XML extension which<br />combines&nbsp; indefiniteness in the values of XML and<br />indefiniteness in the structure of XML into a single fuzzy XML<br />extension. Furthermore,&nbsp; dissertation&nbsp; expands XQuery syntax<br />with fuzzy values and&nbsp; includes priorities and thresholds in<br />fuzzy XQuery extension using&nbsp; GPFCSP for the first time.<br />Unlike other papers that focus on setting up theories and<br />defining syntax, in this&nbsp; dissertation, special attention&nbsp; is turned<br />to their practical use. A tool for working with XML, XSD and<br />DTD documents and prioritized fuzzy XQuery extension<br />queries has been developed. The tool has been tested on<br />practical examples.</p>