Search

The popular isolation level multiversion Read Committed (RC) exchanges some of the strong guarantees of serializability for increased transaction throughput. Nevertheless, transaction workloads can sometimes be executed under RC while still guaranteeing serializability at a reduced cost. Such workloads are said to be robust against RC. This paper provides a high level overview of deciding robustness against RC. In particular, we discuss how a sound and complete test can be obtained through the formalization of transaction templates. We then increase the modeling power of transaction templates by extending them with functional constraints which are useful for capturing data dependencies like foreign keys. We show that the incorporation of functional constraints can identify more workloads as robust than would otherwise be the case. Even though the robustness problem becomes undecidable in its most general form, we establish that various restrictions on functional constraints lead to decidable and even tractable results that can be used to model and test for robustness against RC for practical scenarios.

The isolation level Multiversion Read Committed (RC), offered by many database systems, is known to trade consistency for increased transaction throughput. Sometimes, transaction workloads can be safely executed under RC obtaining the perfect isolation of serializability at the lower cost of RC. To identify such cases, we introduce an expressive model of transaction programs to better reason about the serializability of transactional workloads. We develop tractable algorithms to decide whether any possible schedule of a workload executed under RC is serializable (referred to as the robustness problem). Our approach yields robust subsets that are larger than those identified by previous methods. We provide experimental evidence that workloads that are robust against RC can be evaluated faster under RC compared to stronger isolation levels. We discuss techniques for making workloads robust against RC by promoting selective read operations to updates. Depending on the scenario, the performance improvements can be considerable. Robustness testing and safely executing transactions under the lower isolation level RC can therefore provide a direct way to increase transaction throughput without changing DBMS internals.

Dit onderzoek vormde een haalbaarheidstudie omtrent de toepasbaarheid van NER-modellen op bedrijfsdocumenten. De thesis werd geschreven binnen de context van een stage voor het accountantskantoor Van Havermaet. Tijdens de stage werd NER als subdomein van NLP onderzocht. Vervolgens werden verschillende NER-softwarepakketten voorgesteld. De Python module 'spaCy' werd uiteindelijk toegepast. De achterliggende algoritmes van dit softwarepakket werden toegelicht. Uiteindelijk werden een reeks experimenten uitgevoerd om de toepasbaarheid te meten. De thesis werd afgesloten door een bundeling van 'lessons learned' en praktisch advies.

Many companies nowadays make use of data to optimize their processes. However, the collected data can contain various inconsistencies due to typing errors, for example. This forces the company to clean the data before deducing insights. One possible solution to discover erroneous information is finding columns that determine other columns, also called Functional Dependencies (FDs). For example, two people that live in the same city have to live in the same country. However, as FDs do not allow errors, we have to find a method to find dependencies that approximately hold in the relation, referred to as Approximate Functional Dependencies (AFDs). This thesis aims to design a relevance-focused tool for domain experts to discover AFDs. We review the existing measures to determine the degree of approximation of an AFD by testing them on various theoretical examples. Based on the findings of these tests, we decide on a combination of measures that focuses on discovering relevant AFDs. Then, we integrate those measures and other AFD metadata into c-metric, a score representing the confidence in a particular AFD. Our extensive experimental evaluation of the c-metric shows that the metric is significantly more suitable for relevant AFD discovery than the existing approximation measures. Finally, to assist domain experts in discovering relevant AFDs, we implement a tool that visualizes our c-metric and other AFD metadata, such as probability distributions.

In this thesis we use machine learning techniques to predict email campaign open rates based on the subject line. We tackle the following two specific problems: “Given the subject line, what will be the open rate of the email for a target audience?” and “Given a subject line, will a specific user open the email?”. Both problems are solved in the context of one company that has a small email campaign dataset combined with a large audience. For the first problem, we use regression models such as Ridge regression to predict the open rate of a single subject line for the target audience of the company. We analyze the effect of multiple pre-processors such as scales and Principal Component Analysis. However, due to the lack of email subject line data this model is outperformed by a simple statistical model that utilizes the individual user data. Next, for user-specific open predictions, there is no baseline or simple statistical model. Instead, we propose a method that uses classification models, such as logistic regression and a random forest classifier, to predict for each individual user if they will open an email with a specific subject line by combining the features from the user and an email. We will demonstrate that word embeddings have a significant influence on the machine learning model and that the model performance can improve by only using emails form a single language. We have devised a method of calculating the open rate of an email from the user-specific predictions.

To optimally benefit from the elasticity and scalability of the cloud, applications need to be able to adapt to workload changes by provisioning and de-provisioning resources in an autonomic manner. This process is usually referred to as auto-scaling. A lot of research has already been conducted in the field of auto-scaling. However, auto-scaling in a cloud-native environment is still an open issue about which only very little literature exists. The first part of this thesis provides an extensive overview of the available scientific literature in the field of auto-scaling. It compares the state-of-the-art techniques and discusses their major shortcomings. The second part of this thesis reports on a series of conducted experiments in which the benefits of using machine learning-based prediction models in auto-scaling are being validated in a cloud-native environment. The conclusion of this thesis is that the cloud-native paradigm increases the burden of auto-scaling due to the large number of critical components and the high dimensional interdependencies of microservices. As a result, there are still numerous challenges that need to be solved to lower the complexity and improve the efficiency of auto-scaling in this context. Machine learning-based prediction techniques show a lot of potential to solve several of these challenges. Especially online machine learning models have a few interesting properties that set them apart from many other techniques.

While the migration from DTD to XML Schema was driven by a need for increased expressivity and flexibility, the latter was also significantly more complex to use and understand. Whereas DTDs are characterized by their simplicity, XML Schema Documents are notoriously difficult. In this article, we introduce the XML specification language BonXai, which incorporates many features of XML Schema but is arguably almost as easy to use as DTDs. In brief, the latter is achieved by sacrificing the explicit use of types in favor of simple patterns expressing contexts for elements. The goal of BonXai is not to replace XML Schema but rather to provide a simpler alternative for users who want to go beyond the expressiveness and features of DTD but do not need the explicit use of types. Furthermore, XML Schema processing tools can be used as a back-end for BonXai, since BonXai can be automatically converted into XML Schema. A particularly strong point of BonXai is its solid foundation rooted in a decade of theoretical work around pattern-based schemas. We present a formal model for a core fragment of BonXai and the translation algorithms to and from a core fragment of XML Schema. We prove that BonXai and XML Schema can be converted back-and-forth on the level of tree languages and we formally study the size trade-offs between the two languages. We acknowledge the financial support of grant number MA 4938/2-1 from the Deutsche Forschungsgemeinschaft (Emmy Noether Nachwuchsgruppe). We further acknowledge the financial support of the Future and Emerging Technologies (FET) programme within the Seventh Framework Programme for Research of the European Commission, under the FET-Open grant agreement FOX, number FP7-ICT-233599.

Evaluating queries over massive amounts of data is a major challenge in the big data era. Modern massively parallel systems, such as, Spark, organize query answering as a sequence of rounds each consisting of a distinct communication phase followed by a computation phase. The communication phase redistributes data over the available servers, while in the subsequent computation phase each server performs the actual computation on its local data. There is a growing interest in single-round algorithms for evaluating multiway joins where data is first reshuffled over the servers and then evaluated in a parallel but communication-free way. As the amount of communication induced by a reshuffling of the data is a dominating cost in such systems, we introduce a framework for reasoning about data partitioning to detect when we can avoid the data reshuffling step. Specifically, we formalize the decision problems parallel-correctness and transfer of parallel-correctness, provide semantical characterizations, and obtain tight complexity bounds.

Programs for extracting structured information from text, namely information extractors, often operate separately on document segments obtained from a generic splitting operation such as sentences, paragraphs, k-grams, HTTP requests, and so on. An automated detection of this behavior of extractors, which we refer to as split-correctness, would allow text analysis systems to devise query plans with parallel evaluation on segments for accelerating the processing of large documents. Other applications include the incremental evaluation on dynamic content, where re-evaluation of information extractors can be restricted to revised segments, and debugging, where developers of information extractors are informed about potential boundary crossing of different semantic components. We propose a new formal framework for split-correctness within the formalism of document spanners. Our preliminary analysis studies the complexity of split-correctness over regular spanners. We also discuss different variants of split-correctness, for instance, in the presence of black-box extractors with “split constraints”. We thank the anonymous reviewers for PODS 2019 for many helpful remarks. The work of Johannes Doleschal was supported by the Special Research Fund (BOF) of Hasselt University and the Deutsche Forschungsgemeinschaft (DFG), Grant MA 4938/4-1. The work of Benny Kimelfeld and Yoav Nahshon was supported in part by the Israel Science Foundation (ISF), Grant 1295/15.

Selligent Marketing Cloud offers end-to-end marketing solutions for businesses. The platform captures tons of user-interaction data on a daily basis and aims to expose the data to provide insightful reporting and analysis. While Selligent has been able to successfully provide such reporting functionalities, the company is longing for a future proof solution that provides increased scalability. Moreover, the reporting functionalities are limited in the sense that they focus on a single reporting dimension. In reality, however, the interaction data can be used to deliver insights in multiple dimensions. This work describes how recent advancements in the field of large-scale, distributed processing are leveraged to create a scalable end-to-end reporting application. This application delivers near real-time results and allows for multiple dimensions of the interaction data to be addressed. The activities carried out within the framework of this thesis already contribute directly to production innovations at Selligent.

Chisel is a tool for flexible manipulation of CSV-like data, motivated by the recent effort of the World Wide Web Consortium (W3C) towards a recommendation for tabular data and metadata on the Web. In brief, Chisel supports an expressive built-in schema language for CSV-like data, that can handle both tabular and non-tabular data. Furthermore, it supports a simple programming language for transforming tabular and non-tabular CSV-like data. In the demo, we showcase the system for specifying and validating schemas, building transformations, and setting up a pipeline for automatic conversion of "wild" CSV-like data into structured tabular data. We present use cases for Chisel specifically targeted at exemplifying the ease of specifying, modifying, and understanding Sculpt schemas as well as extracting and transforming data.

In this thesis, we discuss the subject of handwriting synthesis'the pro- cess of using computer algorithms to generate visualizations resembling human handwriting. Specifically, we focus on personal handwriting syn- thesis: writing arbitrary text in a style that resembles a specific person's handwriting. We performed a literature survey of existing methods which qualify for our criteria to be considered personal handwriting synthesis methods: the ability to write full sentences in a handwriting style based on an existing style. We selected seven methods meeting these criteria for in- depth discussion, comparison and analysis. We will propose a framework based on user testing which can be used to benchmark the quality of handwriting synthesis methods: the better a method is at generating output which is indistinguishable from human handwriting, the higher we define its quality. Our framework is designed to cover two scenarios: first, evaluating real and synthetic handwriting samples from unknown writers, and second, evaluating real and synthetic samples of one's own handwriting. Using our framework, we have performed an experiment in which we compare two handwriting synthesis methods found in the literature. With our framework, it becomes possible to create a ranking of handwrit- ing synthesis methods based on their quality.

Due to the increasing popularity of cloud computing and big data, there is a growing need for data processing in distributed and parallel settings. Of particular interest are the evaluations of queries in a single-round of communication where data is distributed over different servers according to some distribution policy, after which each server evaluates the query over the locally available data. Based on this setting, a correctness condition called parallel-correctness has been studied as well as transferability of parallel-correctness while considering unions of conjunctive queries under set semantics. In this thesis, we extend this study toward bag semantics, as bag semantics are often used in practice and their usage is inevitable for certain aggregation functions. We provide characterizations for both parallel-correctness and transferability for conjunctive queries with inequalities under bag semantics and use these characterizations to study the complexity of these problems. The existing distributed evaluation model is however quite restrictive on possible distribution policies for certain conjunctive queries under bag semantics. We therefore propose a slightly modified model based on ordered networks.

While services such as Amazon AWS make computing power abundantly available, adding more computing nodes can incur high costs in, for instance, pay-as-you-go plans while not always significantly improving the net running time (aka wall-clock time) of queries. In this work, we provide algorithms for parallel evaluation of SGF queries in MapReduce that optimize total time, while retaining low net time. Not only can SGF queries specify all semi-join reducers, but also more expressive queries involving disjunction and negation. Since SGF queries can be seen as Boolean combinations of (potentially nested) semi-joins, we introduce a novel multi-semi-join (MSJ) MapReduce operator that enables the evaluation of a set of semi-joins in one job. We use this operator to obtain parallel query plans for SGF queries that outvalue sequential plans w.r.t. net time and provide additional optimizations aimed at minimizing total time without severely affecting net time. Even though the latter optimizations are NP-hard, we present effective greedy algorithms. Our experiments, conducted using our own implementation Gumbo on top of Hadoop, confirm the usefulness of parallel query plans, and the effectiveness and scalability of our optimizations, all with a significant improvement over Pig and Hive., Comment: added Gumbo code reference, added Subset Sum reference, adjusted alignment in Figure 1, adjusted Figure 5 (remove redundant units, larger font), removed capitals in Table 2, boxes for environment ends, clarified proof in appendix, reference cleanup (pages, capitalization), uncapitalized "REQUEST" and "ASSERT" when used in text, small rewordings (no results affected)

A dominant cost for query evaluation in modern massively distributed systems is the number of communication rounds. For this reason, there is a growing interest in single-round multiway join algorithms where data is first reshuffled over many servers and then evaluated in a parallel but communication- free way. The reshuffling itself is specified as a distribution policy. We introduce a correctness condition, called parallel-correctness, for the evaluation of queries w.r.t. a distribution policy. We provide a semantical characterization for when conjunctive queries (and extensions thereof) are parallel-correct and give matching complexity bounds for the associated decision problem. Motivated by scenarios for workload optimization, we further consider the problem of parallel-correctness transfer from a query Q to a query Q0, that is, whether Q0 is parallelcorrect for all distribution policies for which Q is parallelcorrect. In this case, Q0 can always be evaluated after Q without repartitioning the data. We provide a semantical characterization for parallel-correctness transfer and provide matching complexity bounds for the associated decision problem for conjunctive queries (and extensions). Finally, we investigate restrictions of queries and families of distribution policies with better complexities, including, for instance, the Hypercube distributions.

Typechecking consists of statically verifying whether the output of an XML transformation always conforms to an output type for documents satisfying a given input type. In this general setting, both the input and output schema as well as the transformation are part of the input for the problem. However, scenarios where the input or output schema can be considered to be fixed, are quite common in practice. In the present work, we investigate the computational complexity of the typechecking problem in the latter setting. (c) 2008 Elsevier Inc. All rights reserved.

A dominant cost for query evaluation in modern massively distributed systems is the number of communication rounds. For this reason, there is a growing interest in single-round multiway join algorithms where data is first reshuffled over many servers and then evaluated in a parallel but communication-free way. The reshuffling itself is specified as a distribution policy. We introduce a correctness condition, called parallel-correctness, for the evaluation of queries w.r.t. a distribution policy. We study the complexity of parallel-correctness for conjunctive queries as well as transferability of parallel-correctness between queries. We also investigate the complexity of transferability for certain families of distribution policies, including, for instance, the Hypercube distribution., 30 pages

We leven tegenwoordig in een samenleving waarin we graag alles opslaan wat we zien, horen of doen. De hoeveelheid data blijft maar stijgen, waardoor we met big data te maken krijgen. Voorbeelden van grote organisaties die te maken hebben met big data zijn Google en Facebook. Data wordt traditioneel opgeslagen in relationele databases. Deze databases hebben hiervoor reeds vele jaren perfect dienst gedaan. Ze zijn immers zeer betrouwbaar en zijn bestend tegen het verlies van data. Het probleem duikt nu op dat deze databases minder geschikt zijn voor het opslaan en verwerken van big data. Dit soort databases zijn perfect geschikt om verticaal te schalen. Het probleem is dat ze minder geschikt zijn om horizontaal te schalen. Databases die tegenwoordig heel populair zijn en die gebruik maken van een gedistribueerde techniek zijn de NoSQL databases. NoSQL kan op twee manieren worden geïnterpreteerd, maar de meest aangenomen definitie is "Not Only SQL". Dit komt neer op het feit dat dergelijke databases niet alleen maar SQL gebruiken om hun data op te vragen of toe te voegen. Er zijn tegenwoordig heel wat verschillende soorten NoSQL databases. Dit kan gaan van key-value stores tot graafdatabases. Ze kampen echter wel allemaal met hetzelfde probleem en dat is dat ze gedistribueerd zijn en dat ze daarom onderhevig zijn aan de CAP theorie.

In the current big data era, in which we are overloaded with huge amounts of data, there is a large demand for alternatives to traditional querying systems. In our context, big data refers to the petabyte scale data analysis to which industry and academia are ex- posed today; and, where hundreds or thousands of machines, running in parallel, are required to finish computations in a reasonable amount of time. However, the current data landscape also has a complex and non-traditional structure, which typically fits well into the graph model. In semi-structured data, the traditional relational query languages fall short. Hence, we consider the conjunctive regular path queries (CRPQs); a simple, but reasonably expressive language for querying graph data. This thesis is about the eval- uation of CRPQs in MapReduce, a framework that provides a programming abstraction that enables the design of algorithms that can be executed automatically on a cluster of machines in a fault-tolera

Deze thesis gaat over declarative networking, een onderzoeksgebied waarin men gedistribueerde programma’s implementeert met beschrijvende talen zoals Datalog [2], waarin men voornamelijk specificeert wat de uitvoer is, en niet zozeer hoe deze uitvoer moet berekend worden. Het voordeel van zulke talen is dat complexe algoritmen kunnen beschreven worden met redelijk korte programma’s [45, 37]. Ter vergelijking, om gegevensbanken te ondervragen gebruikt men standaard de beschrijvende taal SQL in plaats van een imperatieve programmeertaal zoals Java, omdat men voor deze toepassing vaak veel kortere en overzichtelijkere programma’s kan schrijven in SQL. In deze thesis gebruiken we twee bestaande modellen. Het eerste model bestaat uit relational transducers [7, 28, 29, 30, 54]; deze stellen een abstracte computer voor. Wij definiëren zelf netwerken van zulke relational transducers. Het tweede model wordt gevormd door de taal Dedalus [13, 14, 37]; dit is een programmeertaal geïnspireerd door Datalog. Wij veronderstellen in beide modellen dat een netwerk willekeurige vertragingen kan veroorzaken tussen het versturen en aankomen van boodschappen; dit is de zogenaamde asynchrone communicatie zoals typisch voorkomt op het Internet. Declarative networking is a field in which people implement distributed protocols and applications in high-level declarative languages like Datalog. Such a declarative formalism is believed to help the programmer express complex distributed computations with relatively few lines of code. In this thesis, we investigate many different aspects of declarative networking. The model of networked relational transducers is one main topic, for which we investigate the expressivity; the link between expressivity and distributed coordination; and, the decidability of eventual consistency. Another important topic consists of the language Dedalus, a Datalog-inspired language, for which we define a purely declarative semantics. We also show how this semantics can be used to reason about distributed message causality.

The present work proposes visibly pushdown transducers (VPTs) for defining transformations of documents with a nesting structure. We show that this subclass of pushdown transducers enjoy good properties. Notably, we show that functionality is decidable in PTime and k-valuedness in co-NPTime. While this class is not closed under composition and its type checking problem against visibly pushdown automata is undecidable, we identify a subclass, the well-nested VPTs, closed under composition and with a decidable type checking problem. Furthermore, we show that the class of VPTs is closed under look-ahead, and that the deterministic VPTs with look-ahead characterize the functional VPTs transductions. Finally, we investigate the resources necessary to perform transformations defined by VPTs. We devise a memory efficient algorithm. Then we show that it is decidable whether a VPT transduction can be performed with a memory that depends on the level of nesting of the input document but not on its length., Doctorat en Sciences de l'ingénieur, info:eu-repo/semantics/nonPublished

We will not focus on the actual integration problem. Instead we focus on how to efficiently evaluate distributed queries. One of the key characteristics of the databases discussed in Section 1.2 is that sources are frequently updated. Updates lead to interesting challenges even if one is interested in simple queries. Indeed, answers to queries may vary over time as more data becomes available. However, it is cumbersome to repeat all queries over time especially if they combine information from several sources. We therefore propose a monitoring approach. Users regist er their queries once and these queries are then executed periodically in batch mode. Users are then notified as soon as new answers to t heir queries arrive. As t hese queries are evaluated repeatedly, it is natural to look at multi query optimization (MQO) in this setting. An important characteristic of monitoring systems is that they typically support multiple users and therefore we must consider a large number of queries. We have chosen to focus on t he optimization of the communication cost, one of t he main bottlenecks in our setting with large amounts of distributed data. In the development of our systems we ensured t hat users need no special expertise in some query language to formulate their queries. Being non-experts in computer science, the scientists are faced with two major challenges: (i) How to express such distributed queries. Expressing distributed queries is a non-trivial task, even if we assume that scientists are familiar with query languages like SQL. Such queries can get arbitrarily complex as more sources are considered; (ii) How to efficiently evaluate such distributed queries. An efficient evaluation must account for batches of hundreds (or even t housands) of submitted queries and must optimize all of t hem as a whole.

The regular languages constitute a highly robust class of languages. They can be represented by many different formalisms such as finite automata [92], regular expressions [67], finite semigroups [97], monadic second-order logic [18], right-linear grammars [21], quantifier-free first-order updates [39], ... Regular languages are closed under a wide range of operations and, even more importantly, almost any interesting problem concerning regular languages is decidable. All kinds of aspects of the regular languages have been studied over the past 50 years. From a practical perspective, the most widespread way to specify regular languages is by using regular expressions (REs). They are used in applications in many different areas of computer science, including bioinformatics [84], programming languages [108], model checking [105], and XML schema language [100]. XML is the lingua franca and the de facto standard for data exchange on the Web. When two parties exchange data in XML, the XML documents usually adhere to a certain format. Thereto, XML schema languages are used to describe the structure an XML document can have. The most common XML schema languages are DTD, XML Schema [100], both W3C standards, and Relax NG [22]. From a formal language theory point of view each of these is a grammar-based formalism with regular expressions at their right-hand sides. These expression, however, differ from the standard regular expressions in that they are extended by additional operators but are also restricted by the requirement to be deterministic. Although these requirements are recorded in W3C and ISO standards, it is not clear what their impact on the different schema languages is. The goal of this thesis therefore is a study of these consequences; in particular, we study the complexity of optimization in the presence of additional operators, illustrate the difficulties of migrating from one schema language to another, and study the implications of the determinism constraint (also in the presence of additional operators) and try to make it accessible in practice. Although the questions we ask are mainly inspired by questions about XML, we believe that the answers are also interesting for the general theoretical computer science community as they answer fundamental questions concerning regular expressions. Therefore, this thesis consists of two parts. In the first part, we study fundamental aspects of regular expression. In the second, we apply the former results to applications concerning XML schema languages. Although most of the work is of a foundational nature, we also developed software to bring these theoretical insights to practice.

Excerpt of introduction: Unfortunately, in spite of the above mentioned advantages, the presence of a schema is not mandatory and many XML documents are not accompanied by one. For instance, in a recent study, Barbosa et al. have shown that approximately half of the XML documents available on the web do not refer to a schema. In another study, we have noted that about two-thirds of XSDs gathered from schema repositories and from the web are not valid with respect to the W3C XML Schema specification, rendering them essentially useless for immediate application (see Chapter 6). A similar observation was made by Sahuguet concerning DTDs. Based on the lack of schemas in practice, it is essential to devise algorithms that can infer a schema for a given collection of XML documents when none, or no syntactically correct one, is present. This is also acknowledged by Florescu who emphasizes that in the context of data integration: “We need to extract good-quality schemas automatically from existing data and perform incremental maintenance of the generated schemas.” It should be noted that even when a schema is already available, there are situations where inference can be useful. One such situation is schema cleaning: sometimes a schema is too general with respect to the XML data that it is supposed to describe. In that case, it can be advantageous to infer a new schema based solely on the data at hand.... In general, schema inference can be used to restrict schemas to a relevant subset of data needed by the application at hand, thereby facilitating difficult tasks like schema matching and data integration. Indeed, as argued by Hinkelman [Hin05], industry-level standards are too loosely defined in general, which can result in XML schemas where many business structures are formally specified as being optional.... Based on the above observations, it is hence essential to devise algorithms that can automatically infer a DTD or XSD from a given corpus of XML documents....

XML documents are often generated by some application in order to be processed by a another program. For a correct exchange of information it has to be guaranteed that for correct inputs only correct outputs are produced. The shape of correct documents, i.e., their type, is usually specified by means of schema languages. This thesis is concerned with methods for statically guaranteeing that transformations are correct with respect to pre-defined types. Therefore, we consider the XML transformation language TL abstracting the key features of common XML transformation languages. We show that each TL program can be decomposed into at most three stay macro tree transducers. By means of classical results for stay macro tree transducers, this decomposition allows to formulate a type checking algorithm for TL. This method, however, has even for small programs an exorbitant run-time. Therefore, we develop an alternative approach, which allows at least for a large class of transformations that they can be type checked in polynomial time. The developed algorithms have been implemented and tested for practical examples. XML-Dokumente werden oft von Anwendungen erzeugt, um von anderen Anwendungen konsumiert zu werden. Für einen korrekten Informationsaustausch muss garantiert werden, dass für korrekte Eingaben nur korrekte Ausgaben erzeugt werden. Die vorliegende Arbeit untersucht Methoden, um statisch zu garantieren, dass eine Transformation nur korrekte Ausgaben erzeugt. Dazu betrachten wir die Sprache TL, die die Eigenschaften gängiger XML-Transformationsprachen abstrahiert. Wir zeigen, dass jedes TL Programm in höchstens drei stay macro tree transducers zerlegt werden kann. Diese Zerlegung erlaubt, ein Typüberprüfungsverfahren zu konstruieren. Dieses weist allerdings selbst für kleine Programme exorbitante Laufzeiten auf. Darum entwickeln wir einen alternativen Ansatz, der zumindest für eine große Klasse praktischer Transfromationen Typüberprüfung in polynomieller Zeit erlaubt. Beide Ansätze wurden implementiert und an praktischen Beispielen getestet.

Martens et al. defined a pattern-based specification language equivalent in expressive power to the widely adopted XML Schema definitions (XSDs). This language consists of rules of the form (r, s) where r and s are regular expressions and can be seen as a type-free extension of DTDs with vertical regular expressions. Sets of such rules can be interpreted both in an existential or universal way. In the present paper, we study the succinctness of both semantics w.r.t. each other and w.r.t. the common abstraction of XSDs in terms of single-type extended DTDs. The investigation is carried out relative to three kinds of vertical pattern languages: regular, linear, and strongly linear patterns. We also consider the complexity of the simplification problem for each of the considered pattern-based schemas. (C) 2010 Elsevier Inc. All rights reserved.