View-based query answering in description logics: semantics and complexity. (English) Zbl 1280.68250
Summary: View-based query answering is the problem of answering a query based only on the precomputed answers to a set of views. While this problem has been widely investigated in databases, it is largely unexplored in the context of Description Logic ontologies. Differently from traditional databases, Description Logics may express several forms of incomplete information, and this poses challenging problems in characterizing the semantics of views. In this paper, we first present a general framework for view-based query answering, where we address the above semantical problems by providing two notions of view-based query answering over ontologies, all based on the idea that the precomputed answers to views are the certain answers to the corresponding queries. We also relate such notions to privacy-aware access to ontologies. Then, we provide decidability results, algorithms, and data complexity characterizations for view-based query answering in several Description Logics, ranging from those with limited modeling capability to highly expressive ones.
MSC:
| 68T30 | Knowledge representation |
| 68T27 | Logic in artificial intelligence |
| 68P20 | Information storage and retrieval of data |
Keywords:
view-based query processing; description logics; ontologies; conjunctive queries; incomplete information; certain answers; privacy-aware data management; data complexity; DL-lite family; EL-familySoftware:
XPathReferences:
| [1] | Ullman, J. D., Information integration using logical views, (Proc. of the 6th Int. Conf. on Database Theory. Proc. of the 6th Int. Conf. on Database Theory, ICDTʼ97. Proc. of the 6th Int. Conf. on Database Theory. Proc. of the 6th Int. Conf. on Database Theory, ICDTʼ97, Lecture Notes in Comput. Sci., vol. 1186 (1997), Springer), 19-40 · Zbl 0944.68047 |
| [2] | S. Abiteboul, O. Duschka, Complexity of answering queries using materialized views, in: Proc. of the 17th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems, PODSʼ98, 1998, pp. 254-265.; S. Abiteboul, O. Duschka, Complexity of answering queries using materialized views, in: Proc. of the 17th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems, PODSʼ98, 1998, pp. 254-265. |
| [3] | Halevy, A. Y., Answering queries using views: A survey, Very Large Database J., 10, 4, 270-294 (2001) · Zbl 1012.68910 |
| [4] | Zhang, Z.; Mendelzon, A., Authorization views and conditional query containment, (Proc. of the 10th Int. Conf. on Database Theory. Proc. of the 10th Int. Conf. on Database Theory, ICDT 2005. Proc. of the 10th Int. Conf. on Database Theory. Proc. of the 10th Int. Conf. on Database Theory, ICDT 2005, Lecture Notes in Comput. Sci., vol. 3363 (2005), Springer), 259-273 · Zbl 1112.68378 |
| [5] | S. Rizvi, A.O. Mendelzon, S. Sudarshan, P. Roy, Extending query rewriting techniques for fine-grained access control, in: Proc. of the ACM SIGMOD Int. Conf. on Management of Data, 2004, pp. 551-562.; S. Rizvi, A.O. Mendelzon, S. Sudarshan, P. Roy, Extending query rewriting techniques for fine-grained access control, in: Proc. of the ACM SIGMOD Int. Conf. on Management of Data, 2004, pp. 551-562. |
| [6] | Stouppa, P.; Studer, T., A formal model of data privacy, (Virbitskaite, I.; Voronkov, A., Ershov Memorial Conference. Ershov Memorial Conference, Lecture Notes in Comput. Sci., vol. 4378 (2007), Springer), 400-408 · Zbl 1185.68824 |
| [7] | A.Y. Levy, A.O. Mendelzon, Y. Sagiv, D. Srivastava, Answering queries using views, in: Proc. of the 14th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems, PODSʼ95, 1995, pp. 95-104.; A.Y. Levy, A.O. Mendelzon, Y. Sagiv, D. Srivastava, Answering queries using views, in: Proc. of the 14th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems, PODSʼ95, 1995, pp. 95-104. |
| [8] | D. Calvanese, G. De Giacomo, M. Lenzerini, M.Y. Vardi, View-based query processing and constraint satisfaction, in: Proc. of the 15th IEEE Symp. on Logic in Computer Science, LICS 2000, 2000, pp. 361-371.; D. Calvanese, G. De Giacomo, M. Lenzerini, M.Y. Vardi, View-based query processing and constraint satisfaction, in: Proc. of the 15th IEEE Symp. on Logic in Computer Science, LICS 2000, 2000, pp. 361-371. |
| [9] | Calvanese, D.; De Giacomo, G.; Lenzerini, M.; Vardi, M. Y., View-based query processing: On the relationship between rewriting, answering and losslessness, Theoret. Comput. Sci., 371, 3, 169-182 (2007) · Zbl 1108.68038 |
| [10] | (Baader, F.; Calvanese, D.; McGuinness, D.; Nardi, D.; Patel-Schneider, P. F., The Description Logic Handbook: Theory, Implementation and Applications (2003), Cambridge University Press) · Zbl 1058.68107 |
| [11] | Horrocks, I., Ontologies and the Semantic Web, Commun. ACM, 51, 12, 58-67 (2008) |
| [12] | Calvanese, D.; De 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 |
| [13] | Poggi, A.; Lembo, D.; Calvanese, D.; De Giacomo, G.; Lenzerini, M.; Rosati, R., Linking data to ontologies, J. Data Semantics, X, 133-173 (2008) · Zbl 1132.68061 |
| [14] | F. Baader, S. Brandt, C. Lutz, Pushing the \(\mathcal{EL} \); F. Baader, S. Brandt, C. Lutz, Pushing the \(\mathcal{EL} \) |
| [15] | A. Krisnadhi, C. Lutz, Data complexity in the \(\mathcal{EL} \); A. Krisnadhi, C. Lutz, Data complexity in the \(\mathcal{EL} \) · Zbl 1137.68593 |
| [16] | R. Rosati, On conjunctive query answering in \(\mathcal{EL}\) http://ceur-ws.org/; R. Rosati, On conjunctive query answering in \(\mathcal{EL}\) http://ceur-ws.org/ |
| [17] | Horrocks, I.; Sattler, U.; Tobies, S., Reasoning with individuals for the description logic \(SHIQ\), (McAllester, D., Proc. of the 17th Int. Conf. on Automated Deduction. Proc. of the 17th Int. Conf. on Automated Deduction, CADE 2000. Proc. of the 17th Int. Conf. on Automated Deduction. Proc. of the 17th Int. Conf. on Automated Deduction, CADE 2000, Lecture Notes in Comput. Sci., vol. 1831 (2000), Springer), 482-496 · Zbl 0963.68197 |
| [18] | Horrocks, I.; Patel-Schneider, P. F.; van Harmelen, F., From \(SHIQ\) and RDF to OWL: The making of a web ontology language, J. Web Semantics, 1, 1, 7-26 (2003) |
| [19] | Glimm, B.; Horrocks, I.; Lutz, C.; Sattler, U., Conjunctive query answering for the description logic \(SHIQ\), J. Artificial Intelligence Res., 31, 151-198 (2008) · Zbl 1183.68244 |
| [20] | D. Calvanese, G. De Giacomo, M. Lenzerini, R. Rosati, View-based query answering over description logic ontologies, in: Proc. of the 11th Int. Conf. on the Principles of Knowledge Representation and Reasoning, KR 2008, 2008, pp. 242-251.; D. Calvanese, G. De Giacomo, M. Lenzerini, R. Rosati, View-based query answering over description logic ontologies, in: Proc. of the 11th Int. Conf. on the Principles of Knowledge Representation and Reasoning, KR 2008, 2008, pp. 242-251. |
| [21] | Abiteboul, S.; Hull, R.; Vianu, V., Foundations of Databases (1995), Addison Wesley Publ. Co. · Zbl 0848.68031 |
| [22] | Baader, F.; Nutt, W., Basic description logics, (Baader, F.; Calvanese, D.; McGuinness, D.; Nardi, D.; Patel-Schneider, P. F., The Description Logic Handbook: Theory, Implementation and Applications (2003), Cambridge University Press), 43-95, Ch. 2 · Zbl 1058.68107 |
| [23] | D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, R. Rosati, Data complexity of query answering in description logics, in: Proc. of the 10th Int. Conf. on the Principles of Knowledge Representation and Reasoning, KR 2006, 2006, pp. 260-270.; D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, R. Rosati, Data complexity of query answering in description logics, in: Proc. of the 10th Int. Conf. on the Principles of Knowledge Representation and Reasoning, KR 2006, 2006, pp. 260-270. · Zbl 1270.68294 |
| [24] | Ortiz, M.; Calvanese, D.; Eiter, T., Data complexity of query answering in expressive description logics via tableaux, J. Automat. Reason., 41, 1, 61-98 (2008) · Zbl 1154.68102 |
| [25] | Artale, A.; Calvanese, D.; Kontchakov, R.; Zakharyaschev, M., The DL-Lite family and relations, J. Artificial Intelligence Res., 36, 1-69 (2009) · Zbl 1192.68657 |
| [26] | Maier, D.; Mendelzon, A. O.; Sagiv, Y., Testing implications of data dependencies, ACM Trans. Database Systems, 4, 4, 455-469 (1979) |
| [27] | A. Rajaraman, Y. Sagiv, J.D. Ullman, Answering queries using templates with binding patterns, in: Proc. of the 14th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems, PODSʼ95, 1995, pp. 105-112.; A. Rajaraman, Y. Sagiv, J.D. Ullman, Answering queries using templates with binding patterns, in: Proc. of the 14th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems, PODSʼ95, 1995, pp. 105-112. |
| [28] | R. Pottinger, A.Y. Levy, A scalable algorithm for answering queries using views, in: Proc. of the 26th Int. Conf. on Very Large Data Bases, VLDB 2000, 2000, pp. 484-495.; R. Pottinger, A.Y. Levy, A scalable algorithm for answering queries using views, in: Proc. of the 26th Int. Conf. on Very Large Data Bases, VLDB 2000, 2000, pp. 484-495. |
| [29] | Afrati, F. N.; Gergatsoulis, M.; Kavalieros, T., Answering queries using materialized views with disjunction, (Proc. of the 7th Int. Conf. on Database Theory. Proc. of the 7th Int. Conf. on Database Theory, ICDTʼ99. Proc. of the 7th Int. Conf. on Database Theory. Proc. of the 7th Int. Conf. on Database Theory, ICDTʼ99, Lecture Notes in Comput. Sci., vol. 1540 (1999), Springer), 435-452 |
| [30] | D. Srivastava, S. Dar, H.V. Jagadish, A. Levy, Answering queries with aggregation using views, in: Proc. of the 22nd Int. Conf. on Very Large Data Bases, VLDBʼ96, 1996, pp. 318-329.; D. Srivastava, S. Dar, H.V. Jagadish, A. Levy, Answering queries with aggregation using views, in: Proc. of the 22nd Int. Conf. on Very Large Data Bases, VLDBʼ96, 1996, pp. 318-329. |
| [31] | S. Cohen, W. Nutt, A. Serebrenik, Rewriting aggregate queries using views, in: Proc. of the 18th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems, PODSʼ99, 1999, pp. 155-166.; S. Cohen, W. Nutt, A. Serebrenik, Rewriting aggregate queries using views, in: Proc. of the 18th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems, PODSʼ99, 1999, pp. 155-166. |
| [32] | O.M. Duschka, M.R. Genesereth, Answering recursive queries using views, in: Proc. of the 16th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems, PODSʼ97, 1997, pp. 109-116.; O.M. Duschka, M.R. Genesereth, Answering recursive queries using views, in: Proc. of the 16th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems, PODSʼ97, 1997, pp. 109-116. |
| [33] | Flesca, S.; Greco, S., Rewriting queries using views, IEEE Trans. on Knowledge and Data Engineering, 13, 6, 980-995 (2001) |
| [34] | J. Gryz, Query folding with inclusion dependencies, in: Proc. of the 14th IEEE Int. Conf. on Data Engineering, ICDEʼ98, 1998, pp. 126-133.; J. Gryz, Query folding with inclusion dependencies, in: Proc. of the 14th IEEE Int. Conf. on Data Engineering, ICDEʼ98, 1998, pp. 126-133. |
| [35] | O.M. Duschka, A.Y. Levy, Recursive plans for information gathering, in: Proc. of the 15th Int. Joint Conf. on Artificial Intelligence, IJCAIʼ97, 1997, pp. 778-784.; O.M. Duschka, A.Y. Levy, Recursive plans for information gathering, in: Proc. of the 15th Int. Joint Conf. on Artificial Intelligence, IJCAIʼ97, 1997, pp. 778-784. |
| [36] | A. Calì, D. Lembo, R. Rosati, Query rewriting and answering under constraints in data integration systems, in: Proc. of the 18th Int. Joint Conf. on Artificial Intelligence, IJCAI 2003, 2003, pp. 16-21.; A. Calì, D. Lembo, R. Rosati, Query rewriting and answering under constraints in data integration systems, in: Proc. of the 18th Int. Joint Conf. on Artificial Intelligence, IJCAI 2003, 2003, pp. 16-21. |
| [37] | C. Li, E. Chang, On answering queries in the presence of limited access patterns, in: Proc. of the 8th Int. Conf. on Database Theory, ICDT 2001, 2001, pp. 219-233.; C. Li, E. Chang, On answering queries in the presence of limited access patterns, in: Proc. of the 8th Int. Conf. on Database Theory, ICDT 2001, 2001, pp. 219-233. · Zbl 1047.68580 |
| [38] | Calì, A.; Calvanese, D.; Martinenghi, D., Dynamic query optimization under access limitations and dependencies, J. Univers. Comput. Sci., 15, 1, 33-62 (2009) · Zbl 1216.68085 |
| [39] | S. Chaudhuri, S. Krishnamurthy, S. Potarnianos, K. Shim, Optimizing queries with materialized views, in: Proc. of the 11th IEEE Int. Conf. on Data Engineering, ICDEʼ95, 1995, pp. 190-200.; S. Chaudhuri, S. Krishnamurthy, S. Potarnianos, K. Shim, Optimizing queries with materialized views, in: Proc. of the 11th IEEE Int. Conf. on Data Engineering, ICDEʼ95, 1995, pp. 190-200. |
| [40] | S. Adali, K.S. Candan, Y. Papakonstantinou, V.S. Subrahmanian, Query caching and optimization in distributed mediator systems, in: Proc. of the ACM SIGMOD Int. Conf. on Management of Data, 1996, pp. 137-148.; S. Adali, K.S. Candan, Y. Papakonstantinou, V.S. Subrahmanian, Query caching and optimization in distributed mediator systems, in: Proc. of the ACM SIGMOD Int. Conf. on Management of Data, 1996, pp. 137-148. |
| [41] | Tsatalos, O. G.; Solomon, M. H.; Ioannidis, Y. E., The GMAP: A versatile tool for physical data independence, Very Large Database J., 5, 2, 101-118 (1996) |
| [42] | Grahne, G.; Mendelzon, A. O., Tableau techniques for querying information sources through global schemas, (Proc. of the 7th Int. Conf. on Database Theory. Proc. of the 7th Int. Conf. on Database Theory, ICDTʼ99. Proc. of the 7th Int. Conf. on Database Theory. Proc. of the 7th Int. Conf. on Database Theory, ICDTʼ99, Lecture Notes in Comput. Sci., vol. 1540 (1999), Springer), 332-347 |
| [43] | P.G. Kolaitis, Schema mappings, data exchange, and metadata management, in: Proc. of the 24rd ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems, PODS 2005, 2005, pp. 61-75.; P.G. Kolaitis, Schema mappings, data exchange, and metadata management, in: Proc. of the 24rd ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems, PODS 2005, 2005, pp. 61-75. |
| [44] | L. Libkin, Data exchange and incomplete information, in: Proc. of the 25th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems, PODS 2006, 2006, pp. 60-69.; L. Libkin, Data exchange and incomplete information, in: Proc. of the 25th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems, PODS 2006, 2006, pp. 60-69. |
| [45] | D. Calvanese, G. De Giacomo, M. Lenzerini, M.Y. Vardi, Rewriting of regular expressions and regular path queries, in: Proc. of the 18th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems, PODSʼ99, 1999, pp. 194-204.; D. Calvanese, G. De Giacomo, M. Lenzerini, M.Y. Vardi, Rewriting of regular expressions and regular path queries, in: Proc. of the 18th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems, PODSʼ99, 1999, pp. 194-204. · Zbl 1015.68083 |
| [46] | Calvanese, D.; De Giacomo, G.; Lenzerini, M.; Vardi, M. Y., Rewriting of regular expressions and regular path queries, J. Comput. System Sci., 64, 3, 443-465 (2002) · Zbl 1015.68083 |
| [47] | G. Grahne, A. Thomo, Query containment and rewriting using views for regular path queries under constraints, in: Proc. of the 22nd ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems, PODS 2003, 2003, pp. 111-122.; G. Grahne, A. Thomo, Query containment and rewriting using views for regular path queries under constraints, in: Proc. of the 22nd ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems, PODS 2003, 2003, pp. 111-122. |
| [48] | Grahne, G.; Thomo, A., Algebraic rewritings for optimizing regular path queries, Theoret. Comput. Sci., 296, 3, 453-471 (2003) · Zbl 1045.68072 |
| [49] | D. Calvanese, G. De Giacomo, M. Lenzerini, M.Y. Vardi, Answering regular path queries using views, in: Proc. of the 16th IEEE Int. Conf. on Data Engineering, ICDE 2000, 2000, pp. 389-398.; D. Calvanese, G. De Giacomo, M. Lenzerini, M.Y. Vardi, Answering regular path queries using views, in: Proc. of the 16th IEEE Int. Conf. on Data Engineering, ICDE 2000, 2000, pp. 389-398. |
| [50] | D. Calvanese, G. De Giacomo, M. Lenzerini, M.Y. Vardi, Query processing using views for regular path queries with inverse, in: Proc. of the 19th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems, PODS 2000, 2000, pp. 58-66.; D. Calvanese, G. De Giacomo, M. Lenzerini, M.Y. Vardi, Query processing using views for regular path queries with inverse, in: Proc. of the 19th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems, PODS 2000, 2000, pp. 58-66. |
| [51] | M.F. Fernandez, D. Suciu, Optimizing regular path expressions using graph schemas, in: Proc. of the 14th IEEE Int. Conf. on Data Engineering, ICDEʼ98, 1998, pp. 14-23.; M.F. Fernandez, D. Suciu, Optimizing regular path expressions using graph schemas, in: Proc. of the 14th IEEE Int. Conf. on Data Engineering, ICDEʼ98, 1998, pp. 14-23. |
| [52] | Milo, T.; Suciu, D., Index structures for path expressions, (Proc. of the 7th Int. Conf. on Database Theory. Proc. of the 7th Int. Conf. on Database Theory, ICDTʼ99. Proc. of the 7th Int. Conf. on Database Theory. Proc. of the 7th Int. Conf. on Database Theory, ICDTʼ99, Lecture Notes in Comput. Sci., vol. 1540 (1999), Springer), 277-295 |
| [53] | Y. Papakonstantinou, V. Vassalos, Query rewriting for semistructured data, in: Proc. of the ACM SIGMOD Int. Conf. on Management of Data, 1999, pp. 455-466.; Y. Papakonstantinou, V. Vassalos, Query rewriting for semistructured data, in: Proc. of the ACM SIGMOD Int. Conf. on Management of Data, 1999, pp. 455-466. |
| [54] | F.N. Afrati, R. Chirkova, M. Gergatsoulis, B. Kimelfeld, V. Pavlaki, Y. Sagiv, On rewriting XPath queries using views, in: Proc. of the 12th Int. Conf. on Extending Database Technology, EDBT 2009, 2009, pp. 168-179.; F.N. Afrati, R. Chirkova, M. Gergatsoulis, B. Kimelfeld, V. Pavlaki, Y. Sagiv, On rewriting XPath queries using views, in: Proc. of the 12th Int. Conf. on Extending Database Technology, EDBT 2009, 2009, pp. 168-179. |
| [55] | Calvanese, D.; De Giacomo, G.; Lenzerini, M.; Vardi, M. Y., An automata-theoretic approach to Regular XPath, (Proc. of the 12th Int. Symp. on Database Programming Languages. Proc. of the 12th Int. Symp. on Database Programming Languages, DBPL 2009. Proc. of the 12th Int. Symp. on Database Programming Languages. Proc. of the 12th Int. Symp. on Database Programming Languages, DBPL 2009, Lecture Notes in Comput. Sci., vol. 5708 (2009), Springer), 18-35 |
| [56] | C. Beeri, A.Y. Levy, M.-C. Rousset, Rewriting queries using views in description logics, in: Proc. of the 16th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems, PODSʼ97, 1997, pp. 99-108.; C. Beeri, A.Y. Levy, M.-C. Rousset, Rewriting queries using views in description logics, in: Proc. of the 16th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems, PODSʼ97, 1997, pp. 99-108. |
| [57] | D. Calvanese, G. De Giacomo, M. Lenzerini, Answering queries using views over description logics knowledge bases, in: Proc. of the 17th Nat. Conf. on Artificial Intelligence, AAAI 2000, 2000, pp. 386-391.; D. Calvanese, G. De Giacomo, M. Lenzerini, Answering queries using views over description logics knowledge bases, in: Proc. of the 17th Nat. Conf. on Artificial Intelligence, AAAI 2000, 2000, pp. 386-391. |
| [58] | Hustadt, U.; Motik, B.; Sattler, U., Reasoning in description logics by a reduction to Disjunctive Datalog, J. Automat. Reason., 39, 3, 351-384 (2007) · Zbl 1132.68735 |
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.
