×

Semantic query optimization in the presence of types. (English) Zbl 1408.68049

Summary: Both semantic and type-based query optimization rely on the idea that queries may exhibit non-trivial rewritings if the state space of the database is restricted. While these two problems have always been studied as separate problems in previous work, in this paper we present a unifying, logic-based query optimization framework that builds upon the classical chase algorithm and brings both problems together. As a major challenge, our novel setting requires chasing conjunctive queries with union and negation in the presence of dependencies containing negation and disjunction. Tackling this problem, we study the applicability of the chase in this setting, develop novel conditions that guarantee its termination, identify fragments for which minimal query computation (w.r.t. a generic cost function) is always possible, and investigate the complexity of related decision problems.

MSC:

68P15 Database theory

Software:

Datalog
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Beeri, C.; Vardi, M. Y., A proof procedure for data dependencies, J. ACM, 31, 4, 718-741 (1984) · Zbl 0632.68097
[3] Buneman, P.; Fan, W.; Weinstein, S., Interaction between path and type constraints, ACM Trans. Comput. Log., 4, 4, 530-577 (2003) · Zbl 1365.68197
[6] Calvanese, D.; Giacomo, G.; Lembo, D.; Lenzerini, M.; Rosati, R., Tractable reasoning and efficient query answering in description logics: The DL-Lite family, J. Automat. Reason., 39, 3, 385-429 (2007) · Zbl 1132.68725
[7] Calvanese, D.; Giacomo, G. D.; Lenzerini, M., Conjunctive query containment and answering under description logic constraints, ACM Trans. Comput. Log., 9, 3, 1-31 (2008) · Zbl 1367.68084
[8] Chakravarthy, U. S.; Grant, J.; Minker, J., Logic-based approach to semantic query optimization, ACM Trans. Database Syst., 15, 2, 162-207 (1990)
[12] Deutsch, A.; Ludäscher, B.; Nash, A., Rewriting queries using views with access patterns under integrity constraints, Theoret. Comput. Sci., 371, 3, 200-226 (2007) · Zbl 1108.68040
[14] Deutsch, A.; Popa, L.; Tannen, V., Query reformulation with constraints, SIGMOD Rec., 35, 1, 65-73 (2006)
[15] Dong, G.; Su, J., Conjunctive query containment with respect to views and constraints, Inform. Process. Lett., 57, 2, 95-102 (1996) · Zbl 1022.68508
[16] Fagin, R., Horn clauses and database dependencies, J. ACM, 29, 4, 952-985 (1982) · Zbl 0493.68092
[17] Fagin, R.; Kolaitis, P. G.; Miller, R. J.; Popa, L., Data exchange: Semantics and query answering, Theoret. Comput. Sci., 336, 1, 89-124 (2005) · Zbl 1080.68019
[18] Fan, W.; Libkin, L., On XML integrity constraints in the presence of DTDs, J. ACM, 49, 3, 368-406 (2002) · Zbl 1326.68120
[22] Greco, S.; Spezzano, F., Chase termination: a constraints rewriting approach, VLDB, 3, 93-104 (2010)
[23] Halevy, A. Y., Answering queries using views: A survey, VLDB, 10, 4, 270-294 (2001) · Zbl 1012.68910
[25] Johnson, D. S.; Klug, A. C., Testing containment of conjunctive queries under functional and inclusion dependencies, J. Comput. System Sci., 28, 1, 167-189 (1984) · Zbl 0563.68081
[26] Kifer, M.; Lausen, G.; Wu, J., Logical foundations of object-oriented and frame-based languages, J. ACM, 42, 4, 741-843 (1995) · Zbl 0885.68054
[31] Litwin, W.; Risch, T., Main memory orientated optimization of oo queries using typed Datalog with foreign predicates, IEEE Trans. Knowled. Data Eng., 4, 6, 517-528 (1992)
[32] Maier, D.; Mendelzon, A. O.; Sagiv, Y., Testing implications of data dependencies, ACM Trans. Database Syst., 4, 4, 455-469 (1979)
[34] Meier, M., On the termination of the chase algorithm (2010), Dissertation, University of Freiburg
[35] Meier, M.; Schmidt, M.; Lausen, G., On chase termination beyond stratification, PVLDB, 2, 1, 970-981 (2009)
[45] Stockmeyer, L. J., The polynomial-time hierarchy, Theoret. Comput. Sci., 3, 1-22 (1976) · Zbl 0353.02024
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.