Author name cluster

Marc Gyssens

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.

11 papers

2 author rows

AIJ Journal 2013 Journal Article

On the conditional independence implication problem: A lattice-theoretic approach

Mathias Niepert
Marc Gyssens
Bassem Sayrafi
Dirk Van Gucht

Conditional independence is a crucial notion in the development of probabilistic systems which are successfully employed in areas such as computer vision, computational biology, and natural language processing. We introduce a lattice-theoretic framework that permits the study of the conditional independence (CI) implication problem relative to the class of discrete probability measures. Semi-lattices are associated with CI statements and a finite, sound and complete inference system relative to semi-lattice inclusions is presented. This system is shown to be (1) sound and complete for inferring general from saturated CI statements and (2) complete for inferring general from general CI statements. We also show that the general probabilistic CI implication problem can be reduced to that for elementary CI statements. The completeness of the inference system together with its lattice-theoretic characterization yields a criterion we can use to falsify instances of the probabilistic CI implication problem as well as several heuristics that approximate this falsification criterion in polynomial time. We also propose a validation criterion based on representing constraints and sets of constraints as sparse 0–1 vectors which encode their semi-lattices. The validation algorithm works by finding solutions to a linear programming problem involving these vectors and matrices. We provide experimental results for this algorithm and show that it is more efficient than related approaches.

Details DOI

MFCS Conference 2009 Conference Paper

Regular Expressions with Counting: Weak versus Strong Determinism

Wouter Gelade
Marc Gyssens
Wim Martens

Abstract We study deterministic regular expressions extended with the counting operator. There exist two notions of determinism, strong and weak determinism, which almost coincide for standard regular expressions. This, however, changes dramatically in the presence of counting. In particular, we show that weakly deterministic expressions with counting are exponentially more succinct and strictly more expressive than strongly deterministic ones, even though they still do not capture all regular languages. In addition, we present a finite automaton model with counters, study its properties and investigate the natural extension of the Glushkov construction translating expressions with counting into such counting automata. This translation yields a deterministic automaton if and only if the expression is strongly deterministic. These results then also allow to derive upper bounds for decision problems for strongly deterministic expressions with counting.

Details

UAI Conference 2008 Conference Paper

On the Conditional Independence Implication Problem: A Lattice-Theoretic Approach

Mathias Niepert
Dirk Van Gucht
Marc Gyssens

A lattice-theoretic framework is introduced that permits the study of the conditional independence (CI) implication problem relative to the class of discrete probability measures. Semi-lattices are associated with CI statements and a finite, sound and complete inference system relative to semi-lattice inclusions is presented. This system is shown to be (1) sound and complete for saturated CI statements, (2) complete for general CI statements, and (3) sound and complete for stable CI statements. These results yield a criterion that can be used to falsify instances of the implication problem and several heuristics are derived that approximate this “latticeexclusion” criterion in polynomial time. Finally, we provide experimental results that relate our work to results obtained from other existing inference algorithms.

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

I&C Journal 2001 Journal Article

Equivalence and Normal Forms for the Restricted and Bounded Fixpoint in the Nested Algebra

Marc Gyssens
Dan Suciu
Dirk Van Gucht

The nested model is an extension of the traditional, “flat” relational model in which relations can also have relation-valued entries. Its “default” query language, the nested algebra, is rather weak, unfortunately, since it is only a conservative extension of the traditional, flat relational algebra, and thus can express only a small fraction of the polynomial-time queries. Therefore, it was proposed to extend the nested algebra with a fixpoint construct, but the resulting language turned out to be too powerful: many inherently exponential queries could also be expressed. Two polynomial-time restrictions of the fixpoint closure of the nested algebra were proposed: the restricted fixpoint closure (by Gyssens and Van Gucht) and the bounded fixpoint closure (by Suciu). Here, we prove two results. First we show that both restrictions are equivalent in expressive power. The proof technique relies on known encodings of nested relations into flat ones, and on a novel technique, called type substitution, by which we reduce the equivalence of the two restrictions to its obvious counterpart in the flat relational model. Second we prove that both the bounded fixpoint queries and the restricted fixpoint queries admit normal forms, in which the fixpoint occurs exactly once. The proof technique relies on a novel encoding method of nested relations into flat ones.

Details DOI

TCS Journal 2001 Journal Article

On the expressiveness of linear-constraint query languages for spatial databases

Luc Vandeurzen
Marc Gyssens
Dirk Van Gucht

The linear database model, in which semi-linear sets are the only geometric objects, has been identified as suitable for spatial database applications from both modeling expressiveness as query efficiency considerations. For querying linear databases, the language FO+linear has been proposed. In this paper, we examine the expressiveness of this language. First, we present a list of general queries expressible in FO+linear. In particular, we mention the dimension query, which in turn allows us to express several other interesting linear queries. Next, we show the non-expressibility in FO+linear of a whole class of linear queries that are related to sets not definable by linear formulae, a result which demonstrates the need for more expressive linear query languages. We present a method to extend FO+linear with operators in a sound way with respect to the linear queries expressible in FO+poly, and argue its validity by comparing it to another paradigm for enriching FO+linear. Whether any of the proposed extensions is complete for the linear queries definable in FO+poly remains open.

Details DOI

TCS Journal 1996 Journal Article

CGOOD, a categorical graph-oriented object data model

Chris Tuijn
Marc Gyssens

While the relational data model and many of its extensions have proven to be of considerable importance to many database applications, it has become clear that some advanced systems require more flexible structures and query languages. The expression of queries based on the occurrence of substructures on instance level (i. e. , pattern matchings) requires constructs which cannot be expressed easily in the traditional models. In this article, we introduce an object-oriented data model which solves these shortcomings. The instances of this data model will be represented by typed graphs. Both scheme and data will be defined entirely in terms of categorical constructs; pattern matching of graphs will be realized by morphisms in a suitable graph category. These morphisms will be used to define a powerful query and update language, which is capable of querying and restructuring the database in a natural and elegant way. Finally, we show that this query language is able to express the relational database operators, functional abstraction and transitive closure. It will become clear that the categorical approach provides a solid basis for data modeling because it offers a unifying, theoretical framework. The abstractive power of the categorical framework creates an environment which sheds new light upon existing concepts and is the source of many interesting generalizations. The capability to make abstraction of low-level details, moreover, will often simplify the proofs of many theorems which would be rather involved and confusing in the traditional frameworks.

Details DOI

AIJ Journal 1994 Journal Article

Decomposing constraint satisfaction problems using database techniques

Marc Gyssens
Peter G. Jeavons
David A. Cohen

There is a very close relationship between constraint satisfaction problems and the satisfaction of join-dependencies in a relational database which is due to a common underlying structure, namely a hypergraph. By making that relationship explicit we are able to adapt techniques previously developed for the study of relational databases to obtain new results for constraint satisfaction problems. In particular, we prove that a constraint satisfaction problem may be decomposed into a number of subproblems precisely when the corresponding hypergraph satisfies a simple condition. We show that combining this decomposition approach with existing algorithms can lead to a significant improvement in efficiency.

Details DOI

FOCS Conference 1992 Conference Paper

On the Completeness of Object-Creating Query Languages (Extended Abstract)

Jan Van den Bussche
Dirk Van Gucht
Marc Andries
Marc Gyssens

Recently, various database query languages have been considered that have the ability to create new domain elements. These languages, however, are not complete in the sense of Abiteboul and Kanellakis (1989). They provide a precise characterization for the class of queries that can be expressed in these languages. They call this class the constructive queries and motivate this term by establishing a close correspondence between object creation and the construction of hereditarily finite sets. >

Details

TCS Journal 1991 Journal Article

A comparison between algebraic query languages for flat and nested databases

Marc Gyssens
Dirk Van Gucht

Recently, much attention has been paid to query languages for nested relations. In the present paper, we consider the nested algebra and the powerset algebra, and compare them both mutually as well as to the traditional flat algebra. We show that either nest or difference can be removed as a primitive operator in the powerset algebra. While the redundancy of the nest operator might have been expected, the same cannot be said of the difference. Basically, this result shows that the presence of one nonmonotonic operator suffices in the powerset algebra. As an interesting consequence of this result, the nested algebra without the difference remains complete in the sense of Bancilhon and Paredaens. Finally, we show there are both similarities and fundamental differences between the expressiveness of query languages for nested relations and that of their counterparts for flat relations.

Details DOI

I&C Journal 1987 Journal Article

Object histories which avoid certain subsequences

Seymour Ginsburg
Marc Gyssens

In an earlier paper, one of the authors introduced a record-based model for describing historical data for objects (here called “object histories”). The major construct in the model is a computation-tuple sequence scheme (abbreviated CSS) which specifies the set of all “valid” object histories for the same type of object. In follow-up articles, the effects of interval queries and projections on object histories were examined. Now one of the components in a CSS is a finite set of constraints on object histories. In the present investigation the notion of bad-subsequence constraint is defined and CSS in which each constraint is of this kind are studied. (A bad-subsequence constraint σ is specified by a given set b of object histories. An object history u satisfies σ if u has no subsequence which is a sequence in b.) Among the results are the following: (i) Necessary and sufficient conditions for a set of object histories described by a given CSS to be described by another CSS having only bad-subsequence constraints, i. e. , when a given CSS is bad-subsequence representable; (ii) a characterization for when a bad-subsequence-representable CSS is also locally representable (in the sense of one of the earlier papers); and (iii) connections of bad-subsequence representability with functional-dependency representability.

Details DOI