Document Server@UHasselt
(3.246 recursos)
Repository of the University of Hasselt containing publications in the fields of statistics, computer science, information strategies and material from the Institute for behavioural sciences.
Mostrando recursos 1 - 20 de 381
1.
On the desirability and limitations of linear spatial database models - Vandeurzen, Luc; Gyssens, Marc; Van Gucht, Dirk
A general linear spatial database model is presented in which both the representation and the manipulation of non-spatial data is based on first-order logic over the real numbers with addition. We first argue the naturalness of our model and propose it as a general framework to study and compare linear spatial database models. However, we also establish that no reasonable safe extension of our data manipulation language can be complete for the linear spatial queries in that even very simple queries such as deciding colinearity or computing convex hull of a finite set of points cannot be expressed. We show...
2.
On the expressiveness of linear-constraint query languages for spatial databases - Gyssens, Marc; Vandeurzen, Luc; Van Gucht, Dirk
We exhibit a coordinate-based language, called PFOL, which is sound for the linear queries computable in first-order logic over the reals and extends the latter's restriction to linear arithmetic. To evaluate its expressive power, we first consider PFOL-finite, the PFOL programs that compute finite outputs upon finite inputs. In order to study this fragment of PFOL, we also define an equivalent syntactical language, called SPFOL. We show that SPFOL has the same expressive power as SafeEuql (S. Cluet, R. Hull (Eds.), Proceedings of the Sixth International Workshop on Database Programming Languages, Lecture Notes in Computer Science, Vol. 1369, Springer, Berlin,...
3.
Complexity of Decision Problems for Simple Regular Expressions. - Martens, Wim; Neven, Frank; Schwentick, Thomas
We study the complexity of the inclusion, equivalence, and intersection problem for simple regular expressions arising in practical XML schemas. These basically consist of the concatenation of factors where each factor is a disjunction of strings possibly extended with * or
?. We obtain lower and upper bounds for various fragments of simple regular expressions. Although we show that inclusion and intersection are already intractable for very weak expressions, we also identify some tractable cases. For equivalence, we only prove an initial tractability result leaving the complexity of more general cases open. The main motivation for this research comes from database...
4.
Finite state machines for strings over infinite alphabets - Neven, Frank; Schwentick, Thomas; Vianu, Victor
Motivated by formal models recently proposed in the context of XML, we study automata and logics on strings over infinite alphabets. These are conservative extensions of classical automata and logics defining the regular languages on finite alphabets. Specifically, we consider register and pebble automata, and extensions of first-order logic and monadic second-order logic. For each type of automaton we consider one-way and two-way variants, as well as deterministic, nondeterministic, and alternating control. We investigate the expressiveness and complexity of the automata and their connection to the logics, as well as standard decision problems. Some of our results answer open questions...
5.
On the power of tree-walking automata. - Neven, Frank; Schwentick, Thomas
Tree-walking automata (TWAs) recently received new attention in the fields of formal languages and databases. To achieve a better understanding of their expressiveness, we characterize them in terms of transitive closure logic formulas in normal form. It is conjectured by Engelfriet and Hoogeboom that TWAs cannot define all regular tree languages, or equivalently, all of monadic second-order logic. We prove this conjecture for a restricted, but powerful, class of TWAs. In particular, we show that 1-bounded TWAs, that is TWAs that are only allowed to traverse every edge of the input tree at most once in every direction, cannot define...
6.
XML with data values: typechecking revisited - Alon, Noga; Milo, Tova; Neven, Frank
We investigate the typechecking problem for XML queries: statically verifying that every answer to a query conforms to a given output DTD, for inputs satisfying a given input DTD. This problem had been studied by a subset of the authors in a simplified framework that captured the structure of XML documents but ignored data values. We revisit here the typechecking problem in the more realistic case when data values are present in documents and tested by queries. In this extended framework, typechecking quickly becomes undecidable. However, it remains decidable for large classes of queries and DTDs of practical interest. The...
7.
A formal model for an expressive fragment of XSLT - Bex, Geert Jan; Maneth, Sebastian; Neven, Frank
The extension of the eXtensible Style sheet Language (XSL) by variables and passing of data values between template rules has generated a powerful XML query language: eXtensible Style sheet Language Transformations (XSLT). An informal introduction to XSTL is given, on the bases of which a formal model of a fragment of XSLT is defined. This formal model is in the spirit of tree transducers, and its semantics is defined by rewrite relations. It is shown that the expressive power of the fragment is already beyond that of most other XML query languages. Finally, important properties such as termination and closure...
8.
Query automata over finite trees - Neven, Frank; Schwentick, Thomas
A main task in document transformation and information retrieval is locating subtrees satisfying some pattern. Therefore, unary queries, i.e., queries that map a tree to a set of its nodes, play an important role in the context of structured document databases. The motivation of this work is to understand how the natural and well-studied computation model of tree automata can be used to compute such queries. We define a query automaton (QA) as a deterministic two-way finite automaton over trees that has the ability to select nodes depending on the state and the label at those nodes. We study QAs...
9.
On Query Languages for Linear Queries Definable with Polynomial Constraints - Gyssens, Marc; Van Gucht, Dirk; Vandeurzen, Luc
It has been argued that the linear database model, in which semi-linear sets are the only geometric objects, is very suitable for most spatial database applications. For querying linear databases, the language FO+ linear has been proposed. We present both negative and positive results regarding the expressiveness of FO+ linear. First, we show that the dimension query is definable in FO+ linear, which allows us to solve several interesting queries. Next, we show the non-definability of a whole class of queries that are related to sets not definable in FO+ linear. This result both sharpens and generalizes earlier results independently...
10.
Two- versus three-dimensional connectivity testing of first-order queries to semi-algebraic sets - Geerts, Floris; Van den Bussche, Jan; Smits, Lieven
This paper addresses the question whether one can determine the connectivity of a semi-algebraic set in three dimensions by testing the connectivity of a finite number of two-dimensional samples of the set, where these samples are defined by first-order queries. The question is answered negatively for two classes of first-order queries: cartesian-product-free, and positive one-pass.
11.
Constraint databases: A tutorial introduction - Van den Bussche, Jan
A tutorial introduction to the basic definitions surrounding the idea of constraint databases. This paper is written like a transcript of an invited talk I gave at a meeting bringing together researchers from finite model theory, database theory, and computer-aided verification, which was held at Schloss Dagstuhl in October 1999.
12.
Efficient on-line topological simplification of network-like data - Van den Bussche, Jan; Geerts, Floris; Revesz, Peter
We describe an efficient on-line algorithm to simplify network-like data with the goal of speeding up path queries on these data. Our algorithm is on-line in that it reacts to updates on the data, keeping the simplification up-to-date. The supported updates are insertions of vertices and edges; hence, our algorithm is semi-dynamic. We provide both analytical and empirical evaluations of the efficiency of our approach. Specifically, we prove an 0(log m) upper bound on the amortized time complexity of our maintenance algorithm, with m the number of edges. We also show that the overhead due to maintenance is negligible using...
13.
Constraint databases, queries, and query languages - Van den Bussche, Jan
We formally define the constraint database model, the concept of query in this model, and the basic constraint query languages provided by the relational calculus, the relational algebra, and DATALOG. We show how a computationally complete constraint query language can be obtained by augmenting the constraint relational calculus with basic programming language features. We look into some basic model-theoretic issues concerning the constraint relational calculus, in particular the equivalence problem. The notion of o-minimal structure turns out to be a useful abstraction to discuss these issues in some generality. We will see that equivalence of relational calculus queries on constraint...
14.
On capturing first-order topological properties of planar spatial databases - Van den Bussche, Jan; Kuijpers, Bart
Spatial databases are modeled as closed semi-algebraic subsets of the real plane. First-order logic over the reals, expanded with a symbol to address the database, provides a natural language for expressing properties of such databases. Motivated by applications in geographical information systems, this paper investigates the question of which topological properties can be thus expressed. We introduce a novel, two-tiered logic for expressing topological properties, called CL, which is subsumed by first-order logic over the reals. We put forward the question whether the two logics are actually equivalent (when restricting attention to topological properties). We answer this question affirmatively on...
15.
DTDs versus XML Schema: A Practical Study. - Neven, Frank; Bex, Geert Jan; Van den Bussche, Jan
Among the various proposals answering the shortcomings of Document Type Definitions (DTDs), XML Schema is the most widely used. Although DTDs and XML Schema Defintions (XSDs) differ syntactically, they are still quite related on an abstract level. Indeed, freed from all syntactic sugar, XML Schemas can be seen as an extension of DTDs with a restricted form of specialization. In the present paper, we inspect a number of DTDs and XSDs harvested from the web and try to answer the following questions: (1) which of the extra features/expressiveness of XML Schema not allowed by DTDs are effectively used in practice;...
16.
XPath containment in the presence of disjunction, DTDs, and variables. - Neven, Frank; Schwentick, Thomas
XPath is a simple language for navigating an XML tree and returning a set of answer nodes. The focus in this paper is on the complexity of the containment problem for various fragments of XPath. In addition to the basic operations (child, descendant, filter, and wildcard), we consider disjunction, DTDs and variables. W.r.t. variables we study two semantics: (1) the value of variables is given by an outer context; (2) the value of variables is defined existentially.We establish an almost complete classification of the complexity of the containment problem w.r.t. these fragments.
17.
Typechecking Top-Down Uniform Unranked Tree Transducers. - Martens, Wim; Neven, Frank
We investigate the typechecking problem for XML queries: statically verifying that every answer to a query conforms to a given output schema, for inputs satisfying a given input schema. As typechecking quickly turns undecidable for query languages capable of testing equality of data values, we return to the limited framework where we abstract XML documents as labeled ordered trees. We focus on simple top-down recursive transformations motivated by XSLT and structural recursion on trees. We parameterize the problem by several restrictions on the transformations (deleting, non-deleting, bounded width) and consider both tree automata and DTDs as output schemas. The complexity...
18.
On the power of walking for querying tree-structured data - Neven, Frank
XSLT is the prime example of an XML query language based on tree-walking. Indeed, stripped down, XSLT is just a tree-walking tree-transducer equipped with registers and look-ahead. Motivated by this connection, we want to pinpoint the computational power of devices based on tree-walking. We show that in the absence of unique identifiers even very powerful extensions of the tree-walking paradigm are not relationally complete. That is, these extensions do not capture all of first-order logic. In contrast, when unique identifiers are available, we show that various restrictions allow to capture LOGSPACE, PTIME, PSPACE, and EXPTIME. These complexity classes are defined...
19.
A formal model for an expressive fragment of XSLT - Bex, Geert Jan; Maneth, Sebastian; Neven, Frank
The extension of the eXtensible Style sheet Language (XSL) by variables and passing of data values between template rules has generated a powerful XML query language: eXtensible Style sheet Language Transformations (XSLT). An informal introduction to XSTL is given, on the bases of which a formal model of a fragment of XSLT is defined. This formal model is in the spirit of tree transducers, and its semantics is defined by rewrite relations. It is shown that the expressive power of the fragment is already beyond that of most other XML query languages. Finally, important properties such as termination and closure...
20.
Expressiveness of structured document query languages based on attribute grammars - Neven, Frank; Van den Bussche, Jan
Structured document databases can be naturally viewed as derivation trees of a context-free grammar. Under this view, the classical formalism of attribute grammars becomes a formalism for structured document query languages. From this perspective, we study the expressive power of BAGs: Boolean-valued attribute grammars with propositional logic formulas as semantic rules, and RAGs: relation-valued attribute grammars with first-order logic formulas as semantic rules. BAGs can express only unary queries; RAGs can express queries of any arity. We first show that the (unary) queries expressible by BAGs are precisely those definable in monadic second-order logic. We then show that the queries...
1.
