A New Algorithm for the Containment Problem of Conjunctive Queries with Safe Negation

Author

Felea, Victor

Author_Institution

Fac. of Inf., Alexandra loan Cuza Univ. of Iasi, Iasi, Romania

fYear

2010

fDate

11-16 April 2010

Firstpage

82

Lastpage

90

Abstract

Many queries about real databases have a particular form, e.g., the negated part consists of one single literal or they contain just a single binary relation, etc. For a particular class of queries, it is useful to construct algorithms for the containment problem, that are better than those for the whole class of queries. The paper is about the problem of query containment for conjunctive queries with safe negation property. A new algorithm to test the containment problem of two queries is given. Several aspects of the time complexity for the proposed algorithm are specified. From this point of view, the new algorithm proves to be better than the previous for some classes of queries.

Keywords

computational complexity; query processing; conjunctive queries; query containment problem; safe negation property; time complexity; Acoustic testing; Cities and towns; Data analysis; Databases; Informatics; Knowledge management; Query processing; Sufficient conditions; negation; query containment; safeness;

fLanguage

English

Publisher

ieee

Conference_Titel

Advances in Databases Knowledge and Data Applications (DBKDA), 2010 Second International Conference on

Conference_Location

Menuires

Print_ISBN

978-1-4244-6081-6

Type

conf

DOI

10.1109/DBKDA.2010.42

Filename

5477142