Author name cluster

Frank Neven

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

9 papers

2 author rows

Highlights Conference 2016 Conference Abstract

Containment for Conjunctive Queries with Negation

With Bas Ketsman
Frank Neven
Thomas Schwentick

A query Q is contained in a query Q’ if, for every database D, the result Q(D) is contained in Q'(D). Deciding containment is an interesting and often used sub-problem for minimisation of queries, verification of dependencies and other tasks. It was shown that the containment of conjunctive queries is intimately related to the existence of a homomorphism between the queries and that deciding containment in this case is NP-complete [1]. We have shown that deciding containment for conjunctive queries _with negation_ is coNEXPTIME-complete in general [2]. Previously the problem seems only to have been studied for queries over schemas of bounded arity, where it was known to be Pi^p_2-complete [3]. PUBLICATION: This result has been published in [2] for the 19th International Conference on Database Theory, ICDT 2016, Bordeaux, France, March 15-18, 2016. REFERENCES [1] Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90 [2] Gaetano Geck, Bas Ketsman, Frank Neven, Thomas Schwentick: Parallel-Correctness and Containment for Conjunctive Queries with Union and Negation. ICDT 2016: 9: 1-9: 17 [3] Marie-Laure Mugnier, Geneviève Simonet, Michaël Thomazo: On the complexity of entailment in existential conjunctive first-order logic with atomic negation. Inf. Comput. 215: 8-31 (2012)

Details

I&C Journal 2008 Journal Article

Typechecking top-down XML transformations: Fixed input or output schemas

Wim Martens
Frank Neven
Marc Gyssens

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.

Details DOI

TCS Journal 2005 Journal Article

On the complexity of typechecking top-down XML transformations

Wim Martens
Frank Neven

We investigate the typechecking problem for XML transformations: statically verifying that every answer to a transformation 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 input and output schemas. The complexity of the typechecking problems in this scenario ranges from PTIME to EXPTIME.

Details DOI

MFCS Conference 2004 Conference Paper

Complexity of Decision Problems for Simple Regular Expressions

Wim Martens
Frank Neven
Thomas Schwentick

Abstract 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 theory, or more specifically XML and semi-structured data. We namely show that all lower and upper bounds for inclusion and equivalence, carry over to the corresponding decision problems for extended context-free grammars and single-type tree grammars, which are abstractions of DTDs and XML Schemas, respectively. For intersection, we show that the complexity only carries over for DTDs.

Details

I&C Journal 2003 Journal Article

On the power of tree-walking automata

Frank Neven
Thomas Schwentick

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 all regular languages. We then extend this result to a class of TWAs that can simulate first-order logic (FO) and is capable of expressing properties not definable in FO extended with regular path expressions; the latter logic being a valid abstraction of current query languages for XML and semistructured data.

Details DOI

CSL Conference 2002 Invited Paper

Automata, Logic, and XML

Frank Neven

Abstract We survey some recent developments in the broad area of automata and logic which are motivated by the advent of XML. In particular, we consider unranked tree automata, tree-walking automata, and automata over infinite alphabets. We focus on their connection with logic and on questions imposed by XML.

Details

TCS Journal 2002 Journal Article

Query automata over finite trees

Frank Neven
Thomas Schwentick

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 over ranked as well as over unranked trees. Unranked trees differ from ranked ones in that there is no bound on the number of children of nodes. We characterize the expressiveness of the different formalisms as the unary queries definable in monadic second-order logic (MSO). In contrast to the ranked case, special stay transitions had to be added to QAs over unranked trees to capture MSO. We establish the complexity of the non-emptiness, containment, and equivalence of QAs to be complete for EXPTIME.

Details DOI

I&C Journal 2001 Journal Article

Adding For-Loops to First-Order Logic

Frank Neven
Martin Otto
Jurek Tyszkiewicz
Jan Van den Bussche

We study the query language BQL: the extension of the relational algebra with for-loops. We also study FO(FOR): the extension of first-order logic with a for-loop variant of the partial fixpoint operator. In contrast to the known situation with query languages, which include while-loops instead of for-loops, BQL and FO(FOR) are not equivalent. Among the topics we investigate are: the precise relationship between BQL and FO(FOR); inflationary versus noninflationary iteration; the relationship with logics that have the ability to count; and nested versus unnested loops.

Details DOI

MFCS Conference 2001 Conference Paper

Towards Regular Languages over Infinite Alphabets

Frank Neven
Thomas Schwentick
Victor Vianu

Abstract 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 oneway and two-way variants, as well as deterministic, non-deterministic, and alternating control. We investigate the expressiveness and complexity of the automata, their connection to the logics, as well as standard decision problems.

Details