More Web Proxy on the site http://driver.im/

article

Taming the infinite chase: query answering under expressive relational constraints

Authors:

Michael KiferAuthors Info & Claims

Journal of Artificial Intelligence Research, Volume 48, Issue 1

Pages 115 - 174

Published: 01 October 2013 Publication History

Abstract

The chase algorithm is a fundamental tool for query evaluation and for testing query containment under tuple-generating dependencies (TGDs) and equality-generating dependencies (EGDs). So far, most of the research on this topic has focused on cases where the chase procedure terminates. This paper introduces expressive classes of TGDs defined via syntactic restrictions: guarded TGDs (GTGDs) and weakly guarded sets of TGDs (WGT-GDs). For these classes, the chase procedure is not guaranteed to terminate and thus may have an infinite outcome. Nevertheless, we prove that the problems of conjunctive-query answering and query containment under such TGDs are decidable. We provide decision procedures and tight complexity bounds for these problems. Then we show how EGDs can be incorporated into our results by providing conditions under which EGDs do not harmfully interact with TGDs and do not affect the decidability and complexity of query answering. We show applications of the aforesaid classes of constraints to the problem of answering conjunctive queries in F-Logic Lite, an object-oriented ontology language, and in some tractable Description Logics.

References

[1]

Abiteboul, S., Hull, R., ' Vianu, V. (1995). Foundations of Databases. Addison-Wesley.

[2]

Adler, I., Gottlob, G., ' Grohe, M. (2007). Hypertree width and related hypergraph invariants. Eur. Journal of Combinatorics, 28 (8), 2167-2181.

Digital Library

[3]

Aho, A., Sagiv, Y., ' Ullman, J. D. (1979). Equivalence of relational expressions. SIAM Journal of Computing, 8 (2), 218-246.

Digital Library

[4]

Arenas, M., Bertossi, L. E., ' Chomicki, J. (1999). Consistent query answers in inconsistent databases. In Proc of PODS 1999, pp. 68-79.

Digital Library

[5]

Artale, A., Calvanese, D., Kontchakov, R., ' Zakharyaschev, M. (2009). The DL-lite family and relations. J. Artif. Intell. Res., 36, 1-69.

[6]

Baader, F., Brandt, S., ' Lutz, C. (2005). Pushing the EL envelope. In Proc. of IJCAI 2005, pp. 364-369.

Digital Library

[7]

Baget, J.-F., Leclère, M., Mugnier, M.-L., ' Salvat, E. (2011a). On rules with existential variables: Walking the decidability line. Artif. Intell., 175 (9-10), 1620-1654.

Digital Library

[8]

Baget, J.-F., Mugnier, M.-L., Rudolph, S., ' Thomazo, M. (2011b). Walking the complexity lines for generalized guarded existential rules. In Proc. of IJCAI 2011, pp. 712-717.

Digital Library

[9]

Bárány, V., Gottlob, G., ' Otto, M. (2010). Querying the guarded fragment. In Proc. of LICS 2010, pp. 1-10.

[10]

Beeri, C., Fagin, R., Maier, D., Mendelzon, A. O., Ullman, J. D., ' Yannakakis, M. (1981). Properties of acyclic database schemes. In Proc. of STOC 1981, pp. 355-362.

[11]

Beeri, C., ' Vardi, M. Y. (1981). The implication problem for data dependencies. In Proc. of ICALP 1981, pp. 73-85.

Digital Library

[12]

Bourhis, P., Morak, M., ' Pieris, A. (2013). The impact of disjunction on query answering under guarded-based existential rules. In Proc. of IJCAI 2013.

[13]

Cabibbo, L. (1998). The expressive power of stratified logic programs with value invention. Inf. Comput., 147 (1), 22-56.

Digital Library

[14]

Calì, A., Calvanese, D., De Giacomo, G., ' Lenzerini, M. (2001). Accessing data integration systems through conceptual schemas. In Proc. of ER 2001, pp. 270-284.

[15]

Calì, A., Console, M., ' Frosini, R. (2013). On separability of ontological constraints. Forthcoming.

[16]

Calì, A., Gottlob, G., ' Kifer, M. (2008). Taming the infinite chase: Query answering under expressive relational constraints. In Proc. of KR 2008, pp. 70-80.

[17]

Calì, A., Gottlob, G., ' Lukasiewicz, T. (2009). A general datalog-based framework for tractable query answering over ontologies. In Proc. of PODS 2009, pp. 77-86.

Digital Library

[18]

Calì, A., Gottlob, G., ' Lukasiewicz, T. (2012a). A general datalog-based framework for tractable query answering over ontologies. J. Web Semantics, 14, 57-83. Extended version of (Calì, Gottlob, ' Lukasiewicz, 2009).

Digital Library

[19]

Calì, A., Gottlob, G., Orsi, G., ' Pieris, A. (2012b). On the interaction of existential rules and equality constraints in ontology querying. In Proc. of Correct Reasoning 2012, pp. 117-133.

[20]

Calì, A., Gottlob, G., ' Pieris, A. (2011). New expressive languages for ontological query answering. In Proc. of AAAI 2011.

[21]

Calì, A., Gottlob, G., ' Pieris, A. (2012a). Ontological query answering under expressive entity-relationship schemata. Inf. Syst., 37 (4), 320-335.

Digital Library

[22]

Calì, A., Gottlob, G., ' Pieris, A. (2012b). Towards more expressive ontology languages: The query answering problem. Artif. Intell., 193, 87-128.

Digital Library

[23]

Calì, A., ' Kifer, M. (2006). Containment of conjunctive object meta-queries. In Proc. of VLDB 2006, pp. 942-952.

[24]

Calì, A., Lembo, D., ' Rosati, R. (2003a). On the decidability and complexity of query answering over inconsistent and incomplete databases. In PODS 2003, pp. 260-271.

Digital Library

[25]

Calì, A., Lembo, D., ' Rosati, R. (2003b). Query rewriting and answering under constraints in data integration systems. In Proc. of IJCAI 2003, pp. 16-21.

Digital Library

[26]

Calì, A., ' Martinenghi, D. (2010). Querying incomplete data over extended er schemata. TPLP, 10 (3), 291-329.

[27]

Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., ' Rosati, R. (2007). Tractable reasoning and efficient query answering in description logics: The DL-lite family. J. Autom. Reasoning, 39 (3), 385-429.

Digital Library

[28]

Calvanese, D., De Giacomo, G., ' Lenzerini, M. (2002). Description logics for information integration. In Computational Logic: Logic Programming and Beyond, Vol. 2408 of LNCS, pp. 41-60. Springer.

[29]

Calvanese, D., De Giacomo, G., ' Lenzerini, M. (1998). On the decidability of query containment under constraints. In Proc. of PODS 1998, pp. 149-158.

Digital Library

[30]

Chandra, A. K., Kozen, D., ' Stockmeyer, L. J. (1981a). Alternation. J. of the ACM, 28 (1), 114-133.

Digital Library

[31]

Chandra, A. K., Lewis, H. R., ' Makowsky, J. A. (1981b). Embedded implicational dependencies and their inference problem. In Proc. of STOC 1981, pp. 342-354.

[32]

Chandra, A. K., ' Merlin, P. M. (1977). Optimal implementation of conjunctive queries in relational data bases. In Proc. of STOC 1977, pp. 77-90.

[33]

Chandra, A. K., ' Vardi, M. Y. (1985). The implication problem for functional and inclusion dependencies is undecidable. SIAM J. Comput., 14, 671-677.

Digital Library

[34]

Chen, P. P. (1976). The entity-relationship model - toward a unified view of data. Trans. Database Syst., 1 (1), 9-36.

Digital Library

[35]

Civili, C., ' Rosati, R. (2012). A broad class of first-order rewritable tuple-generating dependencies. In Proc. of Datalog 2.0 2012, pp. 68-80.

Digital Library

[36]

Courcelle, B. (1990). The monadic second-order logic of graphs. I. recognizable sets of finite graphs. Information and Computation, 85 (1), 12-75.

Digital Library

[37]

Dantsin, E., Eiter, T., Gottlob, G., ' Voronkov, A. (2001). Complexity and expressive power of logic programming. ACM Computing Surveys, 33 (3), 374-425.

Digital Library

[38]

De Virgilio, R., Orsi, G., Tanca, L., ' Torlone, R. (2012). NYAYA: A system supporting the uniform management of large sets of semantic data. In Proc. of ICDE 2012, pp. 1309-1312.

Digital Library

[39]

Deutsch, A., Nash, A., ' Remmel, J. B. (2008). The chase revisited. In Proc. of PODS 2008, pp. 149-158.

Digital Library

[40]

Fagin, R. (1983). Degrees of acyclicity for hypergraphs and relational database schemes. J. ACM, 30 (3), 514-550.

Digital Library

[41]

Fagin, R., Kolaitis, P. G., Miller, R. J., ' Popa, L. (2005). Data exchange: semantics and query answering. Theor. Comput. Sci., 336 (1), 89-124.

[42]

Goncalves, M. E., ' Grädel, E. (2000). Decidability issues for action guarded logics. In Proc. of DL 2000, pp. 123-132.

[43]

Gottlob, G., Hernich, A., Kupke, C., ' Lukasiewicz, T. (2012). Equality-friendly wellfounded semantics and applications to description logics. In Proc. of AAAI 2012.

[44]

Gottlob, G., Leone, N., ' Scarcello, F. (2001). Hypertree decompositions: A survey. In Proc. of MFCS 2001, pp. 37-57.

[45]

Gottlob, G., Leone, N., ' Scarcello, F. (2002). Hypertree decompositions and tractable queries. J. Comp. Syst. Sci., 64 (3).

Digital Library

[46]

Gottlob, G., Leone, N., ' Scarcello, F. (2003). Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree width. J. Comput. Syst. Sci., 66 (4), 775-808.

Digital Library

[47]

Gottlob, G., Manna, M., ' Pieris, A. (2013a). Combining decidability paradigms for existential rules. To appear in TPLP.

[48]

Gottlob, G., Manna, M., ' Pieris, A. (2013b). Querying hybrid fragments of existential rules. Forthcoming.

[49]

Gottlob, G., ' Nash, A. (2006). Data exchange: computing cores in polynomial time. In Proc. of PODS 2006, pp. 40-49.

Digital Library

[50]

Gottlob, G., Orsi, G., ' Pieris, A. (2011). Ontological queries: Rewriting and optimization. In Proc. of ICDE 2011, pp. 2-13.

[51]

Gottlob, G., ' Schwentick, T. (2012). Rewriting ontological queries into small nonrecursive datalog programs. In Proc. of KR 2012.

[52]

Grädel, E. (1999). On the restraining power of guards. J. Symb. Log., 64 (4), 1719-1742.

[53]

Grau, B. C., Horrocks, I., Krötzsch, M., Kupke, C., Magka, D., Motik, B., ' Wang, Z. (2012). Acyclicity conditions and their application to query answering in description logics. In Proc. of KR 2012.

[54]

Greco, S., Spezzano, F., ' Trubitsyna, I. (2011). Stratification criteria and rewriting techniques for checking chase termination. PVLDB, 4 (11), 1158-1168.

Digital Library

[55]

Hernich, A., Kupke, C., Lukasiewicz, T., ' Gottlob, G. (2013). Well-founded semantics for extended datalog and ontological reasoning. In Proc. of PODS 2013, pp. 225-236.

Digital Library

[56]

Hernich, A., Libkin, L., ' Schweikardt, N. (2011). Closed world data exchange. ACM Trans. Database Syst., 36 (2), 14-53.

Digital Library

[57]

Heymans, S., Nieuwenborgh, D. V., ' Vermeir, D. (2005). Guarded open answer set programming. In Proc. of LPNMR 2005.

Digital Library

[58]

Johnson, D. S., ' Klug, A. (1984). Testing containment of conjunctive queries under functional and inclusion dependencies. J. Comp. Syst. Sci., 28, 167-189.

[59]

Kifer, M., Lausen, G., ' Wu, J. (1995). Logical foundations of object-oriented and framebased languages. J. ACM, 42, 741-843.

Digital Library

[60]

Koch, C. (2002). Query rewriting with symmetric constraints. In Proc. of FoIKS 2002, pp. 130-147.

[61]

Kontchakov, R., Lutz, C., Toman, D., Wolter, F., ' Zakharyaschev, M. (2010). The combined approach to query answering in dl-lite. In Proc. of KR 2010.

[62]

Krötzsch, M., ' Rudolph, S. (2007). Conjunctive queries for EL with composition of roles. In Proc. of DL 2007.

[63]

Krötzsch, M., ' Rudolph, S. (2011). Extending decidable existential rules by joining acyclicity and guardedness. In Proc. of IJCAI 2011, pp. 963-968.

Digital Library

[64]

Leone, N., Manna, M., Terracina, G., ' Veltri, P. (2012). Efficiently computable datalog; programs. In Proc. of KR 2012.

[65]

Li, L., ' Horrocks, I. (2003). A software framework for matchmaking based on semantic web technology. In Proc. of WWW 2003.

Digital Library

[66]

Lutz, C., Toman, D., ' Wolter, F. (2009). Conjunctive query answering in the description logic EL using a relational database system. In Proc. of IJCAI 2009, pp. 2070-2075.

Digital Library

[67]

Maier, D., Mendelzon, A. O., ' Sagiv, Y. (1979). Testing implications of data dependencies. Trans. Database Syst., 4 (4), 455-469.

Digital Library

[68]

Mailharrow, D. (1998). A classification and constraint-based framework for configuration. Artif. Intell. for Eng. Design, Anal. and Manuf., 12 (4), 383-397.

[69]

Marnette, B. (2009). Generalized schema-mappings: from termination to tractability. In Proc. of PODS 2009, pp. 13-22.

Digital Library

[70]

Millstein, T., Levy, A., ' Friedman, M. (2000). Query containment for data integration systems. In PODS 2000.

Digital Library

[71]

Mitchell, J. C. (1983). The implication problem for functional and inclusion dependencies. Inf. and Control, 56, 154-173.

Digital Library

[72]

Nash, A., Deutsch, A., ' Remmel, J. (2006). Data exchange, data integration, and chase. Tech. rep. CS2006-0859, UCSD.

[73]

Orsi, G., ' Pieris, A. (2011). Optimizing query answering under ontological constraints. PVLDB, 4 (11), 1004-1015.

[74]

Patel-Schneider, P. F., ' Horrocks, I. (2007). A comparison of two modelling paradigms in the semantic web. J. Web Semantics, 5 (4), 240-250.

Digital Library

[75]

Pérez-Urbina, H., Motik, B., ' Horrocks, I. (2010). Tractable query answering and rewriting under description logic constraints. J. Appl. Logic, 8 (2), 186-209.

[76]

Qian, X. (1996). Query folding. In Proc. of ICDE 1996, pp. 48-55.

[77]

Rabin, M. O. (1969). Decidability of second-order theories and automata on infinite trees. Trans. Am. Math. Soc., 141 (1-35), 4.

[78]

Rosati, R. (2007). On conjunctive query answering in EL. In Proc. of DL 2007.

[79]

Rosati, R. (2011). On the finite controllability of conjunctive query answering in databases under open-world assumption. J. Comput. Syst. Sci., 77 (3), 572-594.

Digital Library

[80]

Savo, D. F., Lembo, D., Lenzerini, M., Poggi, A., Rodriguez-Muro, M., Romagnoli, V., Ruzzi, M., ' Stella, G. (2010). Mastro at work: Experiences on ontology-based data access. In Proc. of Description Logics.

Cited By

Han SIves Z(2024)Implementation Strategies for Views over Property GraphsProceedings of the ACM on Management of Data10.1145/36549492:3(1-26)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654949
Fagin RKolaitis PLembo DPopa LScafoglieri FMarquis PSon TKern-Isberner G(2023)A framework for combining entity resolution and query answering in knowledge basesProceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning10.24963/kr.2023/23(229-239)Online publication date: 2-Sep-2023
https://dl.acm.org/doi/10.24963/kr.2023/23
Lanzinger MSferrazza SGottlob GElkind E(2023)MV-Datalog+/-Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/718(6447-6451)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/718
Show More Cited By

Taming the infinite chase: query answering under expressive relational constraints
1. Information systems
  1. Data management systems
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory

Recommendations

The chase revisited
PODS '08: Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems

We revisit the standard chase procedure, studying its properties and applicability to classical database problems. We settle (in the negative) the open problem of decidability of termination of the standard chase, and we provide sufficient termination ...
Taming the infinite chase: query answering under expressive relational constraints
KR'08: Proceedings of the Eleventh International Conference on Principles of Knowledge Representation and Reasoning

A crucial task in Knowledge Representation is answering queries posed over a knowledge base, represented as a set of facts plus a set of rules. In this paper we address the problem of answering conjunctive queries posed over knowledge bases where rules ...
Optimizing the chase: scalable data integration under constraints

We are interested in scalable data integration and data exchange under constraints/dependencies. In data exchange the problem is how to materialize a target database instance, satisfying the source-to-target and target dependencies, that provides the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Artificial Intelligence Research

Journal of Artificial Intelligence Research Volume 48, Issue 1

October 2013

990 pages

ISSN:1076-9757

Issue’s Table of Contents

Publisher

AI Access Foundation

El Segundo, CA, United States

Publication History

Published: 01 October 2013

Published in JAIR Volume 48, Issue 1

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

72
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Han SIves Z(2024)Implementation Strategies for Views over Property GraphsProceedings of the ACM on Management of Data10.1145/36549492:3(1-26)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654949
Fagin RKolaitis PLembo DPopa LScafoglieri FMarquis PSon TKern-Isberner G(2023)A framework for combining entity resolution and query answering in knowledge basesProceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning10.24963/kr.2023/23(229-239)Online publication date: 2-Sep-2023
https://dl.acm.org/doi/10.24963/kr.2023/23
Lanzinger MSferrazza SGottlob GElkind E(2023)MV-Datalog+/-Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/718(6447-6451)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/718
Cima GCroce FLenzerini MDemartini GZuccon GCulpepper JHuang ZTong H(2021)Query Definability and Its Approximations in Ontology-based Data ManagementProceedings of the 30th ACM International Conference on Information & Knowledge Management10.1145/3459637.3482466(271-280)Online publication date: 26-Oct-2021
https://dl.acm.org/doi/10.1145/3459637.3482466
Benedikt MBourhis PCate BPuppis GBoom M(2021)Inference from Visible Information and Background KnowledgeACM Transactions on Computational Logic10.1145/345291922:2(1-69)Online publication date: 21-Jun-2021
https://dl.acm.org/doi/10.1145/3452919
Console MKolaitis PPieris ALibkin LPichler RGuagliardo P(2021)Model-theoretic Characterizations of Rule-based OntologiesProceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3452021.3458310(416-428)Online publication date: 20-Jun-2021
https://dl.acm.org/doi/10.1145/3452021.3458310
Gottlob GHernich AKupke CLukasiewicz T(2021)Stable Model Semantics for Guarded Existential Rules and Description Logics: Decidability and ComplexityJournal of the ACM10.1145/344750868:5(1-87)Online publication date: 22-Oct-2021
https://dl.acm.org/doi/10.1145/3447508
Barceló PFigueira DGottlob GPieris A(2020)Semantic Optimization of Conjunctive QueriesJournal of the ACM10.1145/342490867:6(1-60)Online publication date: 29-Oct-2020
https://dl.acm.org/doi/10.1145/3424908
Hernich ALutz CPapacchini FWolter F(2020)Dichotomies in Ontology-Mediated Querying with the Guarded FragmentACM Transactions on Computational Logic10.1145/337562821:3(1-47)Online publication date: 20-Feb-2020
https://dl.acm.org/doi/10.1145/3375628
Barcelo PDalmau VFeier CLutz CPieris ASuciu DTao YWei Z(2020)The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDsProceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3375395.3387653(259-270)Online publication date: 14-Jun-2020
https://dl.acm.org/doi/10.1145/3375395.3387653
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents