Abstract
In this paper, we investigate the problem of query rewriting using views in a hybrid language allowing nominals (i.e., individual names) to occur in intentional descriptions. Of particular interest, restricted form of nominals where individual names refer to simple values enable the specification of value constraints, i.e, sets of allowed values for attributes. Such constraints are very useful in practice enabling, for example, fine-grained description of queries and views in integration systems and thus can be exploited to reduce the query processing cost. We use description logics to formalize the problem of query rewriting using views in presence of value constraints and show that the technique of query rewriting can be used to process queries under the certain answer semantics. We propose a sound and complete query rewriting Bucket-like algorithm. Data mining techniques have been used to favor scalability w.r.t. the number of views. Experiments on synthetic datasets have been conducted.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Abiteboul, S., Duschka, O.M.: Complexity of answering queries using materialized views. In: PODS 1998, Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 254–263. ACM Press, New York (1998)
Afrati, F.N., Li, C., Mitra, P.: Answering queries using views with arithmetic comparisons. In: Popa, L. (ed.) PODS 2002, Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 209–220. ACM, New York (2002)
Agrawal, R., Srikant, R.: Fast algorithms for mining association rules in large databases. In: Bocca, J.B., Jarke, M., Zaniolo, C. (eds.) VLDB 1994, Proceedings of the International Conference on Very Large Data Bases, pp. 487–499. Morgan Kaufmann, San Francisco (1994)
Baader, F., Calvanese, D., McGuinness, D.L., Nardi, D., Patel-Schneider, P.F.: The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge University Press, Cambridge (2003)
Bayardo Jr., R.J., Goethals, B., Zaki, M.J. (eds.): FIMI 2004, Proceedings of the IEEE ICDM Workshop on Frequent Itemset Mining Implementations, UK, November 2004. CEUR Workshop Proceedings, vol. 126 (2004) CEUR-WS.org
Bayardo Jr., R.J., Zaki, M.J. (eds.): FIMI 2003, Proceedings of the IEEE ICDM Workshop on Frequent Itemset Mining Implementations, USA, November. CEUR Workshop Proceedings, vol. 90 (2003) CEUR-WS.org
Beeri, C., Halevy, A., Rousset, M.C.: Rewriting Queries Using Views in Description Logics. In: Fensel, D., Sycara, K., Mylopoulos, J. (eds.) PODS 1997, Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Tucson, Arizona, May 12–14, pp. 99–108. ACM Press, New York (1997)
Borgida, A., Patel-Schneider, P.F.: A semantics and complete algorithm for subsumption in the classic description logic. Journal of Artificial Intelligence Research (JAIR) 1, 277–308 (1994)
De Marchi, F., Petit, J.-M.: Zigzag: a new algorithm for mining large inclusion dependencies in database. In: ICDM 2003, Proceedings of the IEEE International Conference on Data Mining, pp. 27–34. IEEE Computer Society, Los Alamitos (2003)
Eiter, T., Gottlob, G.: Identifying the minimal transversals of a hypergraph and related problems. SIAM Journal on Computing 24(6), 1278–1304 (1995)
Flouvat, F., De Marchi, F., Petit, J.-M.: iZi: A new toolkit for pattern mining problems. In: An, A., Matwin, S., Raś, Z.W., Ślęzak, D. (eds.) ISMIS 2008. LNCS, vol. 4994, pp. 131–136. Springer, Heidelberg (2008)
Goasdoué, F., Rousset, M.-C.: Answering queries using views: A krdb perspective for the semantic web. ACM Transactions on Internet Technology 4(3), 255–288 (2004)
Gunopulos, D., Khardon, R., Mannila, H., Saluja, S., Toivonen, H., Sharm, R.S.: Discovering all most specific sentences. ACM transactions on database systems 28(2), 140–174 (2003)
Halevy, A.Y.: Answering queries using views: A survey. VLDB Journal 10(4), 270–294 (2001)
Horrocks, I., Sattler, U.: Ontology reasoning in the shoq(d) description logic. In: Nebel, B. (ed.) IJCAI 2001, International Joint Conferences on Artificial Intelligence, pp. 199–204. Morgan Kaufmann, San Francisco (2001)
Huhtala, Y., Kärkkäinen, J., Porkka, P., Toivonen, H.: Tane: An efficient algorithm for discovering functional and approximate dependencies. Computer Journal 42(2), 100–111 (1999)
Khachiyan, L., Boros, E., Elbassioni, K.M., Gurvich, V.: An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation. Discrete Applied Mathematics 154(16), 2350–2372 (2006)
Küsters, R.: Non-Standard Inferences in Description Logics. LNCS, vol. 2100. Springer, Heidelberg (2001)
Lenzerini, M.: Data integration: A theoretical perspective. In: PODS 2002, Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Madison, Wisconsin (2002)
Levy, A.Y., Rajaraman, A., Ordille, J.J.: Querying heterogeneous information sources using source descriptions. In: Vijayaraman, T.M., Buchmann, A.P., Mohan, C., Sarda, N.L. (eds.) VLDB 1996, Proceedings of the International Conference on Very Large Data Bases, pp. 251–262. Morgan Kaufmann, San Francisco (1996)
Mannila, H., Toivonen, H.: Levelwise search and borders of theories in knowledge discovery. Data mining and knowledge discovery 1(3), 241–258 (1997)
Pottinger, R., Halevy, A.Y.: Minicon: A scalable algorithm for answering queries using views. VLDB Journal 10(2-3), 182–198 (2001)
Schaerf, A.: Reasoning with individuals in concept languages. Data & Knowledge Engineering 13(2), 141–176 (1994)
Ullman, J.D.: Information integration using logical views. Theoretical Computer Science 239(2), 189–210 (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Jaudoin, H., Flouvat, F., Petit, J.M., Toumani, F. (2009). Towards a Scalable Query Rewriting Algorithm in Presence of Value Constraints. In: Spaccapietra, S. (eds) Journal on Data Semantics XII. Lecture Notes in Computer Science, vol 5480. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-00685-2_2
Download citation
DOI: https://doi.org/10.1007/978-3-642-00685-2_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-00684-5
Online ISBN: 978-3-642-00685-2
eBook Packages: Computer ScienceComputer Science (R0)