Special Issue: Data Management and Data Mining

• Articles • Previous Articles     Next Articles

An Efficient Algorithm for Processing Multi-Relation Queries in Relational Databases

Liu Weiyi;   

  1. Yunnan University;
  • Online:1990-05-10 Published:1990-05-10

After a relation scheme R is decomposed into the set of schemes ρ={R_1,...,R_n},we may pose queries as if R existed in the database,taking a join of R_i s,when it is necessary to implement the query.Suppose a query involves a set of attributes S(?)R,we want to find the smallest subset of ρ whose union includes S.We prove that the problem is NP-complete and present a polynomial-bounded approximation algorithm.A subset of ρ whose union includes S and has a decomposition into 3NF with a lossless join and prese...

Key words: leakage current; dont care bits; minimum leakage vector; leakage power;

[1] K.L.Schenk, and J.R.Pinkert, An Algorithm for Servicing Multi-Relational Queries, ACM/SIGMOD International Symposium on Management of Data, 1977, 10-19.

[2] J.D.Ullman, Principles of the Database System, Computer Science Press, Potomac, Md., 1983.

[3] Ellis Horowitz and Sartaj Sahani, Fundamentals of Computer Algorithm, Computer Science Press, Potomac, Md., 1978.
[1] Yong Guan (关永) and Jingling Xue (薛京灵), Senior Member, IEEE, Member, ACM. Leakage-Aware Modulo Scheduling for Embedded VLIW Processors [J]. , 2011, 26(3): 405-417.
[2] Wei Wang, Yu Hu, Yin-He Han, Xiao-Wei Li, and You-Sheng Zhang. Leakage Current Optimization Techniques During Test Based on Don t Care Bits Assignment [J]. , 2007, 22(5): 673-680 .
[3] Yong-Jun Xu, Zu-Ying Luo, Xiao-Wei Li, Li-Jian Li, and Xian-Long Hong. Leakage Current Estimation of CMOS Circuit with Stack Effect [J]. , 2004, 19(5): 0-0.
Full text



[1] Ma Jun; Ma Shaohan;. An O(k~2n~2) Algorithm to Find a k-Partition in a k-Connected Graph[J]. , 1994, 9(1): 86 -91 .
[2] Chen Yiyun;. Head Boundedness of Nonterminating Rewritings[J]. , 1995, 10(3): 281 -284 .
[3] QI Yuesheng; WANG Baozhong; KANG Lishan;. Genetic Programming with Simple Loops[J]. , 1999, 14(4): 429 -433 .
[4] Long Zheng (郑龙), Mian-Xiong Dong (董冕雄), Student Member, IEEE, Kaoru Ota, Hai Jin (金海), Senior Member, IEEE, Member, ACM, Song Guo, Senior Member, IEEE, Member, ACM, and Jun Ma (马俊), Student Member, IEEE. Energy Efficiency of a Multi-Core Processor by Tag Reduction[J]. , 2011, 26(3): 491 -503 .
[5] Yang Liu, Huai-Kou Miao, Hong-Wei Zeng, Yan Ma, and Pan Liu. Nondeterministic Probabilistic Petri Net — A New Method to Study Qualitative and Quantitative Behaviors of System[J]. , 2013, 28(1): 203 -216 .
[6] Irfan Ahmad and Sabri A. Mahmoud. Arabic Bank Check Processing: State of the Art[J]. , 2013, 28(2): 285 -299 .
[7] Hyeong-Il Kim and Jae-Woo Chang. k-Nearest Neighbor Query Processing Algorithms for a Query Region in Road Networks[J]. , 2013, 28(4): 585 -596 .
[8] Jin-Kai Zhang, Cui-Xia Ma, Yong-Jin Liu, Qiu-Fang Fu, and Xiao-Lan Fu . Collaborative Interaction for Videos on Mobile Devices Based on Sketch Gestures[J]. , 2013, 28(5): 810 -817 .
[9] Sheng Zhang, Zhu-Zhong Qian, Jie Wu, Sang-Lu Lu. Service-Oriented Resource Allocation in Clouds: Pursuing Flexibility and Efficiency[J]. , 2015, 30(2): 421 -436 .
[10] Yu Zhang, Miao Liu, Hai-Xia Xia. Clustering Context-Dependent Opinion Target Words in Chinese Product Reviews[J]. , 2015, 30(5): 1109 -1119 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved