In many applications and domains,temporal constraints between actions, and their probabilities play an important role. We propose the first approach in the literature coping with probabilistic quantitative constraints...In many applications and domains,temporal constraints between actions, and their probabilities play an important role. We propose the first approach in the literature coping with probabilistic quantitative constraints. To achieve such a challenging goal, we extend the widely used simple temporal problem(STP) framework to consider probabilities.Specifically,we propose i) a formal representation of probabilistic quantitative constraints, ii) an algorithm,based on the operations of intersection and composition,for the propagation of such temporal constraints, and iii) facilities to support query answering on a set of such constraints. As a result, we provide users with the first homogeneous method supporting the treatment(representing,reasoning,and querying) of probabilistic quantitative constraints, as required by many applications and domains.展开更多
Description logics (DLs) play an important role in representing and reasoning domain knowledge. Conjunctive queries stemmed from the domain of relational databases, and have attracted more attentions in semantic Web...Description logics (DLs) play an important role in representing and reasoning domain knowledge. Conjunctive queries stemmed from the domain of relational databases, and have attracted more attentions in semantic Web recently. To acquire a tractable DL for query answering, DL-Lite is proposed. Due to the large amount of imprecision and uncertainty in the real world, it is essential to extend DLs to deal with these vague and imprecise information. We thus propose a new fuzzy DL f-DLR-Lite.n, which allows for the presence of n-ary relations and the occurrence of concept conjunction on the left land of inclusion axioms. We also suggest an improved fuzzy query language, which supports the presence of thresholds and user defined weights. We also show that the query answering algorithm over the extended DL is still FOL reducible and shows polynomial data complexity. DL f-DLR-Lite,n can make up for the disadvantages of knowledge representation and reasoning of classic DLs, and the enhanced query language expresses user intentions more precisely and reasonably.展开更多
Big data introduces challenges to query answering, from theory to practice. A number of questions arise. What queries are "tractable" on big data? How can we make big data "small" so that it is feasible to find e...Big data introduces challenges to query answering, from theory to practice. A number of questions arise. What queries are "tractable" on big data? How can we make big data "small" so that it is feasible to find exact query answers?When exact answers are beyond reach in practice, what approximation theory can help us strike a balance between the quality of approximate query answers and the costs of computing such answers? To get sensible query answers in big data,what else do we necessarily do in addition to coping with the size of the data? This position paper aims to provide an overview of recent advances in the study of querying big data. We propose approaches to tackling these challenging issues,and identify open problems for future research.展开更多
We consider the problem of efficiently computing distributed geographical k-NN queries in an unstructured peer-to-peer (P2P) system, in which each peer is managed by an individual organization and can only communica...We consider the problem of efficiently computing distributed geographical k-NN queries in an unstructured peer-to-peer (P2P) system, in which each peer is managed by an individual organization and can only communicate with its logical neighboring peers. Such queries are based on local filter query statistics, and require as less communication cost as possible which makes it more difficult than the existing distributed k-NN queries. Especially, we hope to reduce candidate peers and degrade communication cost. In this paper, we propose an efficient pruning technique to minimize the number of candidate peers to be processed to answer the k-NN queries. Our approach is especially suitable for continuous k-NN queries when updating peers, including changing ranges of peers, dynamically leaving or joining peers, and updating data in a peer. In addition, simulation results show that the proposed approach outperforms the existing Minimum Bounding Rectangle (MBR)-based query approaches, especially for continuous queries.展开更多
In this paper, we introduce a concept of Annotation Based Query Answer, and a method for its computation, which can answer queries on relational databases that may violate a set of functional dependencies. In this app...In this paper, we introduce a concept of Annotation Based Query Answer, and a method for its computation, which can answer queries on relational databases that may violate a set of functional dependencies. In this approach, inconsistency is viewed as a property of data and described with annotations. To be more precise, every piece of data in a relation can have zero or more annotations with it and annotations are propagated along with queries from the source to the output. With annotations, inconsistent data in both input tables and query answers can be marked out but preserved, instead of being filtered in most previous work. Thus this approach can avoid information loss, a vital and common deficiency of most previous work in this area. To calculate query answers on an annotated database, we propose an algorithm to annotate the input tables, and redefine the five basic relational algebra operations (selection, projection, join, union and difference) so that annotations can be correctly propagated as the valid set of functional dependency changes during query processing. We also prove the soundness and completeness of the whole annotation computing system. Finally, we implement a prototype of our system, and give some performance experiments, which demonstrate that our approach is reasonable in running time, and excellent in information preserving.展开更多
Many latest high performance distributed computational environments come with high bandwidth in commu- nication. Such high bandwidth distributed systems provide unprecedented opportunities for analyzing huge datasets,...Many latest high performance distributed computational environments come with high bandwidth in commu- nication. Such high bandwidth distributed systems provide unprecedented opportunities for analyzing huge datasets, but simultaneously posts new technical challenges. For users, progressive query answering is important. For utility of systems, load balancing is critical. How we can achieve progressive and load balancing distributed computation is an interesting and promising research direction. As skyline analysis has been shown very useful in many multi-criteria decision making applications, in this paper, we study the problem of progressive and load balancing distributed skyline analysis. We propose a simple yet scalable approach which comes with several nice properties for progressive and load balancing query answering. We conduct extensive experiments which demonstrate the feasibility and effectiveness of the proposed method.展开更多
基金partially supported by Istituto Nazionale diAlta Matematica(INdAM)
文摘In many applications and domains,temporal constraints between actions, and their probabilities play an important role. We propose the first approach in the literature coping with probabilistic quantitative constraints. To achieve such a challenging goal, we extend the widely used simple temporal problem(STP) framework to consider probabilities.Specifically,we propose i) a formal representation of probabilistic quantitative constraints, ii) an algorithm,based on the operations of intersection and composition,for the propagation of such temporal constraints, and iii) facilities to support query answering on a set of such constraints. As a result, we provide users with the first homogeneous method supporting the treatment(representing,reasoning,and querying) of probabilistic quantitative constraints, as required by many applications and domains.
基金the Program for New Century Excellent Talents in University (NCET-05-0288)the Specialized Research Fund for the Doctoral Program of Higher Education of China (20050145024)
文摘Description logics (DLs) play an important role in representing and reasoning domain knowledge. Conjunctive queries stemmed from the domain of relational databases, and have attracted more attentions in semantic Web recently. To acquire a tractable DL for query answering, DL-Lite is proposed. Due to the large amount of imprecision and uncertainty in the real world, it is essential to extend DLs to deal with these vague and imprecise information. We thus propose a new fuzzy DL f-DLR-Lite.n, which allows for the presence of n-ary relations and the occurrence of concept conjunction on the left land of inclusion axioms. We also suggest an improved fuzzy query language, which supports the presence of thresholds and user defined weights. We also show that the query answering algorithm over the extended DL is still FOL reducible and shows polynomial data complexity. DL f-DLR-Lite,n can make up for the disadvantages of knowledge representation and reasoning of classic DLs, and the enhanced query language expresses user intentions more precisely and reasonably.
基金supported in part by the National Basic Research 973 Program of China under Grant No.2014CB340302Fan is also supported in part by the National Natural Science Foundation of China under Grant No.61133002+3 种基金the Guangdong Innovative Research Team Program under Grant No.2011D005Shenzhen Peacock Program under Grant No.1105100030834361the Engineering and Physical Sciences Research Council of UK under Grant No.EP/J015377/1the National Science Foundation of USA under Grant No.III-1302212
文摘Big data introduces challenges to query answering, from theory to practice. A number of questions arise. What queries are "tractable" on big data? How can we make big data "small" so that it is feasible to find exact query answers?When exact answers are beyond reach in practice, what approximation theory can help us strike a balance between the quality of approximate query answers and the costs of computing such answers? To get sensible query answers in big data,what else do we necessarily do in addition to coping with the size of the data? This position paper aims to provide an overview of recent advances in the study of querying big data. We propose approaches to tackling these challenging issues,and identify open problems for future research.
基金the Program for New Century Excellent Talents in Universities(Grant No.NCET-06-0290)the National Natural Science Foundation of China(Grant Nos.60503036,and 60773221)+1 种基金the National High-Tech Development 863 Program of China(Grant No.2006AA09Z139)the Fok Ying Tong Education Foundation Award(Grant No.104027)
文摘We consider the problem of efficiently computing distributed geographical k-NN queries in an unstructured peer-to-peer (P2P) system, in which each peer is managed by an individual organization and can only communicate with its logical neighboring peers. Such queries are based on local filter query statistics, and require as less communication cost as possible which makes it more difficult than the existing distributed k-NN queries. Especially, we hope to reduce candidate peers and degrade communication cost. In this paper, we propose an efficient pruning technique to minimize the number of candidate peers to be processed to answer the k-NN queries. Our approach is especially suitable for continuous k-NN queries when updating peers, including changing ranges of peers, dynamically leaving or joining peers, and updating data in a peer. In addition, simulation results show that the proposed approach outperforms the existing Minimum Bounding Rectangle (MBR)-based query approaches, especially for continuous queries.
基金Supported by the National Natural Science Foundation of China under Grant No. 60603043the Program of Shanghai Municipal Education Commission under Grant No.06FZ030
文摘In this paper, we introduce a concept of Annotation Based Query Answer, and a method for its computation, which can answer queries on relational databases that may violate a set of functional dependencies. In this approach, inconsistency is viewed as a property of data and described with annotations. To be more precise, every piece of data in a relation can have zero or more annotations with it and annotations are propagated along with queries from the source to the output. With annotations, inconsistent data in both input tables and query answers can be marked out but preserved, instead of being filtered in most previous work. Thus this approach can avoid information loss, a vital and common deficiency of most previous work in this area. To calculate query answers on an annotated database, we propose an algorithm to annotate the input tables, and redefine the five basic relational algebra operations (selection, projection, join, union and difference) so that annotations can be correctly propagated as the valid set of functional dependency changes during query processing. We also prove the soundness and completeness of the whole annotation computing system. Finally, we implement a prototype of our system, and give some performance experiments, which demonstrate that our approach is reasonable in running time, and excellent in information preserving.
基金Supported by the Doctoral Research Foundation of the Natural Science Foundation of Guangdong Province under Grant No.8451064101000054the National Natural Science Foundation of China under Grant Nos. 60773198,60703111+3 种基金Natural Science Foundation of Guangdong Province under Grant Nos. 06104916,8151027501000021Research Foundation of Science and Technology PlanProject in Guangdong Province under Grant No. 2008B050100040Program for New Century Excellent Talents in University ofChina under Grant No. NCET-06-0727the Fundamental Research Funds for the Central Universities,SCUT,under Grant No.2009ZM0008
文摘Many latest high performance distributed computational environments come with high bandwidth in commu- nication. Such high bandwidth distributed systems provide unprecedented opportunities for analyzing huge datasets, but simultaneously posts new technical challenges. For users, progressive query answering is important. For utility of systems, load balancing is critical. How we can achieve progressive and load balancing distributed computation is an interesting and promising research direction. As skyline analysis has been shown very useful in many multi-criteria decision making applications, in this paper, we study the problem of progressive and load balancing distributed skyline analysis. We propose a simple yet scalable approach which comes with several nice properties for progressive and load balancing query answering. We conduct extensive experiments which demonstrate the feasibility and effectiveness of the proposed method.