The view selection problem for regular path queries. (English) Zbl 1136.68374
Laber, Eduardo Sany (ed.) et al., LATIN 2008: Theoretical informatics. 8th Latin American symposium, Búzios, Brazil, April 7–11, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-78772-3/pbk). Lecture Notes in Computer Science 4957, 121-132 (2008).
Summary: The view selection problem consists of finding a set of views to materialize that can answer the given set of workload queries and is optimal in some sense. In this paper we study the view selection problem for regular path queries over semistructured data and two specific view-based query rewriting formalisms, namely single-word and arbitrary regular rewritings. We present an algorithm that for a given finite set of workload queries, i.e. for a set of regular languages, computes a set of views that can answer every query in the workload and has minimal possible cardinality. If, in addition, a database instance is given then one can construct a viewset such that its size, i.e. amount of space required to store results, is minimal on the database instance.
For the entire collection see [Zbl 1133.68008].
For the entire collection see [Zbl 1133.68008].
References:
| [1] | Afonin, S.; Khazova, E., Membership and finiteness problems for rational sets of regular languages, International Journal of Foundations of Computer Science, 17, 3, 493-506 (2006) · Zbl 1103.68062 · doi:10.1142/S0129054106003954 |
| [2] | Afonin, S.; Khazova, E.; Andre, J. M., A note on finitely generated semigroups of regular languages, Proceedings of the International Conference “Semigroups and Formal Languages”, 1-8 (2007), Singapore: World Scientific, Singapore · Zbl 1127.20048 |
| [3] | Calvanese, D.; De Giacomo, G.; Lenzerini, M.; Vardi, M., Rewriting of regular expressions and regular path queries, Journal of Computer and System Sciences, 64, 443-465 (2002) · Zbl 1015.68083 · doi:10.1006/jcss.2001.1805 |
| [4] | Calvanese, D.; De Giacomo, G.; Lenzerini, M.; Vardi, M. Y.; Eiter, T.; Libkin, L., View-based query processing: On the relationship between rewriting, answering and losslessness, Database Theory - ICDT 2005, 321-336 (2004), Heidelberg: Springer, Heidelberg · Zbl 1108.68443 |
| [5] | Calvanese, D., Giacomo, G.D., Lenzerini, M., Vardi, M.Y.: Answering regular path queries using views. In: ICDE, pp. 389-398 (2000) |
| [6] | Chirkova, R.; Halevy, A. Y.; Suciu, D., A formal perspective on the view selection problem, The VLDB Journal, 11, 3, 216-237 (2002) · Zbl 1047.68045 · doi:10.1007/s00778-002-0070-0 |
| [7] | Chirkova, R.; Li, C., Materializing views with minimal size to answer queries, PODS 2003, 38-48 (2003), New York: ACM Press, New York · doi:10.1145/773153.773158 |
| [8] | Conway, J., Regular Algebra and Finite Machines (1971), Boca Raton: Chapman and Hall, Boca Raton · Zbl 0231.94041 |
| [9] | Franklin, M.; Halevy, A.; Maier, D., From databases to dataspaces: a new abstraction for information management, SIGMOD Rec., 34, 4, 27-33 (2005) · doi:10.1145/1107499.1107502 |
| [10] | Grahne, G.; Thomo, A., Algebraic rewritings for optimizing regular path queries, Theoretical Computer Science, 296, 3, 453-471 (2003) · Zbl 1045.68072 · doi:10.1016/S0304-3975(02)00739-9 |
| [11] | Grahne, G.; Thomo, A., Query containment and rewriting using views for regular path queries under constraints, PODS 2003, 111-122 (2003), New York: ACM Press, New York · doi:10.1145/773153.773165 |
| [12] | Grahne, G.; Thomo, A., Boundedness of regular path queries in data integration systems, Proc. of IDEAS, 85-92 (2007), Los Alamitos: IEEE Computer Society, Los Alamitos |
| [13] | Halevy, A. Y., Theory of answering queries using views, SIGMOD Record (ACM Special Interest Group on Management of Data), 29, 4, 40-47 (2000) |
| [14] | Hashiguchi, K., Representation theorems on regular languages, Journal of computer and system sciences, 27, 101-115 (1983) · Zbl 0516.68063 · doi:10.1016/0022-0000(83)90031-4 |
| [15] | Kirsten, D.; Diekert, V.; Habib, M., Desert automata and the finite substitution problem, STACS 2004, 305-316 (2004), Heidelberg: Springer, Heidelberg · Zbl 1122.68467 |
| [16] | Leung, H.; Podolskiy, V., The limitedness problem on distance automata: Hashiguchi’s method revisited, Theoretical Computer Science, 310, 1-3, 147-158 (2004) · Zbl 1071.68045 · doi:10.1016/S0304-3975(03)00377-3 |
| [17] | Li, C.; Bawa, M.; Ullman, J. D.; Van den Bussche, J.; Vianu, V., Minimizing view sets without losing query-answering power, Database Theory - ICDT 2001, 99-113 (2000), Heidelberg: Springer, Heidelberg · Zbl 1047.68579 · doi:10.1007/3-540-44503-X_7 |
| [18] | Mandhani, B., Suciu, D.: Query caching and view selection for XML databases. In: Böhm, K., Jensen, C.S., Haas, L.M., Kersten, M.L., Larson, P.-Å., Ooi, B.C. (eds.) VLDB, pp. 469-480. ACM Press, New York (2005) |
| [19] | Polák, L.; Champarnaud, J.-M.; Maurel, D., Syntactic semiring and language equations, Implementation and Application of Automata, 182-193 (2003), Heidelberg: Springer, Heidelberg · Zbl 1033.68068 · doi:10.1007/3-540-44977-9_17 |
| [20] | Segoufin, L.; Vianu, V., Views and queries: determinacy and rewriting, PODS 2005, 49-60 (2005), New York: ACM Press, New York · doi:10.1145/1065167.1065174 |
| [21] | Tajima, K.; Fukui, Y.; Nascimento, M. A.; Özsu, M. T.; Kossmann, D.; Miller, R. J.; Blakeley, J. A.; Schiefer, K. B., Answering XPath queries over networks by sending minimal views, VLDB, 48-59 (2004), San Francisco: Morgan Kaufmann, San Francisco |
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.
