Paper Info
Title
Conjunctive queries with constraints: homomorphism, containment and rewriting
Abstract
While the complexity of containment of standard conjunctive queries is NP-complete, adding constraints changes the complexity to $\Pi^P_2$-complete. This is because in such cases, we need to consider a team of containment mappings to establish containment as opposed to considering a single containment mapping in the standard case. The situation is different when homomorphism property holds, where considering a single mapping is sufficient to establish containment. We identify new classes of conjunctive queries with constraints that satisfy homomorphism property. For each class, we introduce a set of polynomial membership tests. Based on this, we propose an algorithm for rewriting of conjunctive queries with linear arithmetic constraints for which homomorphism property holds.
Year
DOI
Venue
2010
10.1007/978-3-642-11829-6_6
FoIKS
Keywords
Field
DocType
standard conjunctive query,homomorphism property,standard case,single containment mapping,containment mapping,single mapping,constraints change,new class,conjunctive query,linear arithmetic constraint,conjunctive queries,satisfiability
Conjunctive query,Polynomial,Computer science,Theoretical computer science,Rewriting,Homomorphism,Linear arithmetic,Containment
Conference
Volume
ISSN
ISBN
5956
0302-9743
3-642-11828-3
Citations 
PageRank 
References 
0
0.34
15
Authors
2
Name
Order
Citations
PageRank
Ali Kiani181.87
Nematollaah Shiri228028.31