I/O-Efficient Algorithms for CDBs.
DOI: 10.1007/978-3-662-04031-7_16
关键词: Efficient algorithm 、 Constraint (information theory) 、 Theoretical computer science 、 Computer science 、 Auxiliary memory 、 Range query (data structures) 、 Join (sigma algebra)
摘要: In this chapter, we study the I/O aspects of constraint databases. The goal chapter is to show that for many problems arising in databases, it possible design theoretically and practically efficient algorithms. addition, certain are provably hard with result no algorithms them. This has three parts: Algorithms retrieval constraints from secondary storage (disk) Algorithms join between two sets constraints Lower bounds above
springer.com
sci-hub.st 参考文章(24)
Sridhar Ramaswamy, Sairam Subramanian, Path Caching: A Technique for Optimal External Searching symposium on principles of database systems. pp. 25- 35 ,(1994)
Sridhar Ramaswamy, Efficient Indexing for Constraint and Temporal Databases international conference on database theory. pp. 419- 431 ,(1997) , 10.1007/3-540-62222-5_61
Mark H. Overmars, The design of dynamic data structures ,(1983)
Herbert Edelsbrunner, A new approach to rectangle intersections International Journal of Computer Mathematics. ,vol. 13, pp. 221- 229 ,(2010) , 10.1080/00207168308803365
Dan E. Willard, George S. Lueker, Adding range restriction capability to dynamic data structures Journal of the ACM. ,vol. 32, pp. 597- 617 ,(1985) , 10.1145/3828.3839
Paris Kanellakis, Sridhar Ramaswamy, Darren E. Vengroff, Jeffrey Scott Vitter, Indexing for Data Models with Constraints and Classes conference on learning theory. ,vol. 52, pp. 589- 612 ,(1994) , 10.1006/JCSS.1996.0043
Vasilis Samoladas, Daniel P. Miranker, A lower bound theorem for indexing schemes and its application to multidimensional range queries symposium on principles of database systems. pp. 44- 51 ,(1998) , 10.1145/275487.275493
Lars Arge, Vasilis Samoladas, Jeffrey Scott Vitter, On two-dimensional indexability and optimal range search indexing symposium on principles of database systems. pp. 346- 357 ,(1999) , 10.1145/303976.304010
Elias Koutsoupias, D. S. Taylor, Tight bounds for 2-dimensional indexing schemes symposium on principles of database systems. pp. 52- 58 ,(1998) , 10.1145/275487.275494
Joseph M. Hellerstein, Elias Koutsoupias, Christos H. Papadimitriou, On the analysis of indexing schemes symposium on principles of database systems. pp. 249- 256 ,(1997) , 10.1145/263661.263688