the proceedings contain 16 papers. the topics discussed include: efficient algorithms for the tree homeomorphism problem;a methodology for coupling fragments of XPath with structural indexes for XML documents;conjunct...
详细信息
ISBN:
(纸本)9783540759867
the proceedings contain 16 papers. the topics discussed include: efficient algorithms for the tree homeomorphism problem;a methodology for coupling fragments of XPath with structural indexes for XML documents;conjunctive query containment over trees;a better semantics for XQuery with side-effects;repairing inconsistent XML write-access control policies;on the consistent rewriting of conjunctive queries under primary key constraints;relational completeness of query languages for annotated databases;a theory of stream queries;querying structural and behavioral properties of business processes;succinctness of pattern-based schema languages for XML;analysis of imperative XML programs;efficient inclusion for a class of XML types with interleaving and counting;and towards practical typechecking for macro tree transducers.
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 re...
详细信息
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.
the widespread adoption of XML has led to programminglanguagesthat support XML as a first class construct. In this paper, we present a method for analyzing and optimizing imperative XML processing programs. In parti...
详细信息
the widespread adoption of XML has led to programminglanguagesthat support XML as a first class construct. In this paper, we present a method for analyzing and optimizing imperative XML processing programs. In particular, we present a program analysis, based on a flow-sensitive type system, for detecting both redundant computations and redundant traversals in such programs. the analysis handles imperative loops that traverse XML values explicitly and declarative queries over XML data in a uniform framework. We describe two optimizations that take advantage of our analysis: one merges queries that traverse the same set of XML nodes, and the other replaces an XPath expression by a previously computed result. We demonstrate performance improvements for selected XMark benchmark queries and XLinq sample queries. (C) 2009 Elsevier B.V. All rights reserved.
Data streams are modeled as infinite or finite sequences of data elements coming from an arbitrary but fixed universe. the universe can have various built-in functions and predicates. Stream queries are modeled as fun...
详细信息
ISBN:
(纸本)9783540759867
Data streams are modeled as infinite or finite sequences of data elements coming from an arbitrary but fixed universe. the universe can have various built-in functions and predicates. Stream queries are modeled as functions from streams to streams. Both timed and untimed settings are considered. Issues investigated include abstract definitions of computability of stream queries;the connection between abstract computability, continuity, monotonicity, and non-blocking operators;and bounded memory computability of stream queries using abstract state machines (ASMs).
the proceedings contains 49 papers from the 11thinternational IEEE symposium on Visual languages VL '95. Topics discussed include visual programming and visual programminglanguages, computer software visualizati...
详细信息
the proceedings contains 49 papers from the 11thinternational IEEE symposium on Visual languages VL '95. Topics discussed include visual programming and visual programminglanguages, computer software visualization, visual interfaces, constraint based programming, algorithm animation, graphical user interfaces, object oriented dataflow, incremental parsing, and programming by demonstration.
this article deals withthe computation of consistent answers to queries on relational databases that violate primary key constraints. A repair of such inconsistent database is obtained by selecting a maximal number o...
详细信息
this article deals withthe computation of consistent answers to queries on relational databases that violate primary key constraints. A repair of such inconsistent database is obtained by selecting a maximal number of tuples from each relation without ever selecting two distinct tuples that agree on the primary key. We are interested in the following problem: Given a Boolean conjunctive query q, compute a Boolean first-order (FO) query psi such that for every database db, psi evaluates to true on db if and only if q evaluates to true on every repair of db. Such psi is called a consistent FO rewriting of q. We use novel techniques to characterize classes of queries that have a consistent FO rewriting. In this way, we are able to extend previously known classes and discover new ones. Finally, we use an Ehrenfeucht-Fraisse game to show the non-existence of a consistent FO rewriting for there exists x there exists y(R((x) under bar, y) boolean AND R((y) under bar, c)), where c is a constant and the first coordinate of R is the primary key. (C) 2009 Elsevier B.V. All rights reserved.
Annotated relational databases can be queried either by simply making the annotations explicitly available along the ordinary data, or by adapting the standard query operators so that they have an implicit effect also...
详细信息
Annotated relational databases can be queried either by simply making the annotations explicitly available along the ordinary data, or by adapting the standard query operators so that they have an implicit effect also on the annotations. We compare the expressive power of these two approaches. As a formal model for the implicit approach we propose the color algebra, an adaptation of the relational algebra to deal withthe annotations. We show that the color algebra is relationally complete: it is equivalent to the relational algebra on the explicit annotations. Our result extends a similar completeness result established for the query algebra of the MONDRIAN annotation system, from unions of conjunctive queries to the full relational algebra. We also show that the color algebra is nonredundant: no operator can be expressed in terms of the other operators. We also present a generalization of the color algebra that is relationally complete in the presence of built-in predicates on the annotations. (C) 2010 Elsevier Inc. All rights reserved.
Most real-world applications have come to rely on the mature technology of relational databases for persistent storage, interacting through SQL embedded in the host programming language. Using logic programming we pre...
详细信息
ISBN:
(纸本)9783540929949
Most real-world applications have come to rely on the mature technology of relational databases for persistent storage, interacting through SQL embedded in the host programming language. Using logic programming we present a higher-level alternative to SQL, close in spirit to natural language, yielding much more concise expressions that are easier to understand and promote better code maintenance. this is achieved using the flexible operator syntax and the deductive capabilities, first to compile a clausal representation of the database scheme from a high-level description, and then to interpret queries and commands, through the compiled scheme, into SQL statements.
Traversal strategies are at the heart of transformational programming with rewriting-based frameworks such as Stratego/XT or Tom and specific approaches for generic functional programming such as Strafunski or "S...
详细信息
ISBN:
(纸本)9781605585680
Traversal strategies are at the heart of transformational programming with rewriting-based frameworks such as Stratego/XT or Tom and specific approaches for generic functional programming such as Strafunski or "Scrap your boilerplate". Such traversal strategies are distinctively based on one-layer traversal primitives from which traversal schemes are derived by recursive closure. We describe a mechanized, formal model of such strategies. the model covers two different semantics of strategies, strategic programming laws, termination conditions for strategy combinators as well as properties related to the success/failure behavior of strategies. the model has been mechanized in Isabelle/HOL.
Several recent language designs have offered a unified language for programming a distributed system, with explicit notation of locations;we call these "location-aware" languages. these languages provide con...
详细信息
ISBN:
(纸本)9781605585680
Several recent language designs have offered a unified language for programming a distributed system, with explicit notation of locations;we call these "location-aware" languages. these languages provide constructs allowing the programmer to control the location (the choice of host, for example) where a piece of code should run, which can be useful for security or performance reasons. On the other hand, a central mantra of WWW system engineering prescribes that web servers should be "stateless": that no "session state" should be maintained on behalf of individual clients-that is. no state that pertains to the particular point of the interaction at which a client program resides. Many implementations of location-aware languages are not at home on the web: they hold some kind of client-specific state on the server. We show how to implement a symmetrical location-aware language on top of a stateless server.
暂无评论