On first-order query rewriting for incomplete database histories

[en] Multiwords are defined as words in which single symbols can be replaced by nonempty sets of symbols. Such a set of symbols captures uncertainty about the exact symbol. Words are obtained from multiwords by selecting a single symbol from every set. A pattern is certain in a multiword W if it occurs in every word that can be obtained from W. For a given pattern, we are interested in finding a logic formula that recognizes the multiwords in which that pattern is certain. This problem can be seen as a special case of consistent query answering (CQA).We show how our results can be applied in CQA on database histories under primary key constraints.

Research center :

CREMMI - Modélisation mathématique et informatique

Disciplines :

Electrical & electronics engineering

Author, co-author :

Bruyère, Véronique ; Université de Mons > Faculté des Sciences > Service d'Informatique théorique

Decan, Alexandre ; Université de Mons > Faculté des Sciences > Systèmes d'information

Wijsen, Jef ; Université de Mons > Faculté des Sciences > Service des Systèmes d'information

Language :

English

Title :

On first-order query rewriting for incomplete database histories

Publication date :

25 July 2009

Event name :

International Symposium/Workshop on Temporal Representation and Reasoning

Event place :

Bressanone-Brixen, Italy

Event date :

2009

Research unit :

S829 - Informatique théorique
S832 - Systèmes d'information

Research institute :

R300 - Institut de Recherche en Technologies de l'Information et Sciences de l'Informatique
R150 - Institut de Recherche sur les Systèmes Complexes

Commentary :

Début 23 juillet -Fin 25 juillet IEEE Computer Society Press

Available on ORBi UMONS :

since 10 July 2010

Statistics

Number of views

1 (0 by UMONS)

Number of downloads

0 (0 by UMONS)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

Bibliography

M. Arenas, L. E. Bertossi, and J. Chomicki, "Consistent query answers in inconsistent databases," in PODS. ACM Press, 1999, pp. 68-79.
A. Fuxman and R. J. Miller, "First-order query rewriting for inconsistent databases," J. Comput. Syst. Sci., vol. 73, no. 4, pp. 610-635, 2007.
L. Grieco, D. Lembo, R. Rosati, and M. Ruzzi, "Consistent query answering under key and exclusion dependencies: algorithms and experiments," in CIKM, O. Herzog, H.-J. Schek, N. Fuhr, A. Chowdhury, and W. Teiken, Eds. ACM, 2005, pp. 792-799.
J. Wijsen, "Consistent query answering under primary keys: a characterization of tractable queries," in ICDT, ser. ACM International Conference Proceeding Series, R. Fagin, Ed., vol. 361. ACM, 2009, pp. 42-52.
-, "On the consistent rewriting of conjunctive queries under primary key constraints," Inf. Syst., 2009.
D. M. Gabbay, A. Pnueli, S. Shelah, and J. Stavi, "On the temporal basis of fairness," in POPL, 1980, pp. 163-173.
J. A. W. Kamp, "Tense logic and the theory of linear order," Ph.D. dissertation, University of California, Los Angeles, 1968.
R.McNaughton and S.Papert, Counter-free Automata. Cambridge, MA: MIT Press, 1971.
M. P. Schützenberger, "On finite monoids having only trivial subgroups," Information and Control, vol. 8, no. 2, pp. 190-194, 1965.
F. Blanchet-Sadri, R. Mercas, and G. Scott, "A generalization of Thue freeness for partial words," Theor. Comput. Sci., vol. 410, no. 8-10, pp. 793-800, 2009.
L. Libkin, Elements of Finite Model Theory. Springer, 2004.
D. E. Knuth, J. H. M. Jr., and V. R. Pratt, "Fast pattern matching in strings," SIAM J. Comput., vol. 6, no. 2, pp. 323-350, 1977.
A. V. Aho and M. J. Corasick, "Efficient string matching: An aid to bibliographic search," Commun. ACM, vol. 18, no. 6, pp. 333-340, 1975.