Please use this identifier to cite or link to this item:
Title: On the complexity of deciding typability in the relational algebra
Authors: VANSUMMEREN, Stijn 
Issue Date: 2005
Publisher: Springer
Source: Acta Informatica, 41(6). p. 367-381
Abstract: We investigate the complexity of the typability problem for the relational algebra. This problem consists of deciding, for a given relational algebra expression, whether there exists an assignment of types to variables occurring in the expression such that the expression is well-typed under the assignment. We obtain that the problem is NP-complete in general. In particular, we show that the problem becomes NP-hard due to (1) the cartesian product operator, (2) the selection operator on arbitrary sets of typed predicates, (3) the selection operator on ldquowell-behavedrdquo sets of typed predicates together with join and projection or renaming. However, the problem is in P when (1) we only allow union, difference, join and selection on ldquowell-behavedrdquo sets of typed predicates, or (2) we allow all operators except cartesian product, where the set of selection predicates can mention at most one base type. Most of these results follow from a close connection of the typability problem to non-uniform constraint satisfaction.
Document URI:
ISSN: 0001-5903
e-ISSN: 1432-0525
DOI: 10.1007/s00236-005-0162-6
ISI #: 000228546000003
Category: A1
Type: Journal Contribution
Validations: ecoom 2006
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
onthecompl.pdfPublished version146.16 kBAdobe PDFView/Open
Show full item record


checked on Sep 2, 2020


checked on May 13, 2022

Page view(s)

checked on May 17, 2022


checked on May 17, 2022

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.