Search

A natural language interface (NLI) to databases is an interface that translates a natural language question to a structured query that is executable by database management systems (DBMS). However, an NLI that is trained in the general domain is hard to apply in the spatial domain due to the idiosyncrasy and expressiveness of the spatial semantics. Moreover, there are a wide range of database servers available, and a unilingual NLI model limits its practical usage. In this article, we propose to not only address the spatial domain generalization challenge, but also support multilingual back-end, i.e., supporting different query languages, such as SQL and Prolog. For the challenge of spatial semantics, we propose a spatial comprehension model that is able to recognize the meaning of spatial entities based on the semantics of context and effectively resolve the ambiguity given the spatial semantics. The spatial semantics learned from the spatial comprehension model is then injected to the natural language question to ease the burden of capturing the spatial-specific semantics. We also propose to add a prefix symbol to support the multilingual back-end (e.g., query languages). With our spatial comprehension model and symbol injections, our NLI for the spatial domain, named SpatialNLI, is able to capture the semantic structure of the question and translate it to the corresponding syntax of an executable query accurately. We also experimentally ascertain that SpatialNLI outperforms state-of-the-art methods. [ABSTRACT FROM AUTHOR]

The number of databases as well as their size and complexity is increasing. This creates a barrier to use especially for non-experts, who have to come to grips with the nature of the data, the way it has been represented in the database, and the specific query languages or user interfaces by which data are accessed. These difficulties worsen in research settings, where it is common to work with many different databases. One approach to improving this situation is to allow users to pose their queries in natural language. In this work we describe a machine learning framework, Polyglotter, that in a general way supports the mapping of natural language searches to database queries. Importantly, it does not require the creation of manually annotated data for training and therefore can be applied easily to multiple domains. The framework is polyglot in the sense that it supports multiple different database engines that are accessed with a variety of query languages, including SQL and Cypher. Furthermore Polyglotter supports multi-class queries. Good performance is achieved on both toy and real databases, as well as a human-annotated WikiSQL query set. Thus Polyglotter may help database maintainers make their resources more accessible. [ABSTRACT FROM AUTHOR]

In recent past, there has been a steep increase in the use of online platforms for the search of desired products. Real estate industry is no exception and has started initiating rent/sale of houses through online platforms. In this paper, we propose a deep neural network framework to facilitate automatic search of homes based on their floor plans. The salient features of this framework are that the query can be either an image (existing floor plan) or a sketch through a sketch pad interface. Our proposed framework automatically determines the type of query (image or sketch) and retrieves similar floor plan images from the database. The critical contributions of our proposed approach are: (1) a novel unified floor plan retrieval framework using multimodal query, i.e., an intuitive and convenient sketch query mode as well as a query by example mode ; (2) a conjunction of autoencoder, Cyclic GAN and CNN for the task of domain mapping and floor plan image retrieval. We have reported results of extensive experimentation and comparison with baseline results to establish the effectiveness of our approach. [ABSTRACT FROM AUTHOR]

Model transformation is a key enabling technology of Model-Driven Engineering (MDE). Existing model transformation languages are shaped by and for MDE practitioners—a user group with needs and capabilities which are not necessarily characteristic of modelers in general. Consequently, these languages are largely ill-equipped for adoption by end-user modelers in areas such as requirements engineering, business process management, or enterprise architecture. We aim to introduce a model transformation language addressing the skills and requirements of end-user modelers. With this contribution, we hope to broaden the application scope of model transformation and MDE technology in general. We discuss the profile of end-user modelers and propose a set of design guidelines for model transformation languages addressing them. We then introduce Visual Model Transformation Language (VMTL) following these guidelines. VMTL draws on our previous work on the usability-oriented Visual Model Query Language. We implement VMTL using the Henshin model transformation engine, and empirically investigate its learnability via two user experiments and a think-aloud protocol analysis. Our experiments, although conducted on computer science students exhibiting only some of the characteristics of end-user modelers, show that VMTL compares favorably in terms of learnability with two state-of the-art model transformation languages: Epsilon and Henshin. Our think-aloud protocol analysis confirms many of the design decisions adopted for VMTL, while also indicating possible improvements. [ABSTRACT FROM AUTHOR]

With the development of the Internet of Things (IoT), the industrial vehicle ad hoc networks are revolving into the Internet of Industrial Vehicles (IoIV). Due to the popularity of the geographical devices used on the Industrial vehicle, location-based information is extensively available in IoIV. This development calls for spatial keyword queries (SKQ), which takes into account both the locations and textual descriptions of objects. This paper addresses the issue of processing SKQ in IoIV environment, which focuses on two types of SKQ queries, namely Boolean kNN Queries and Top-k Queries. A general air index called Extended Spatial Keyword query index in IoIV environment (ESKIV) is proposed, which supports both network space pruning and textual pruning simultaneously. Based on ESKIV, efficient algorithms are designed to deal with these two types of SKQ respectively. The proposed ESKIV also can be used to deal with other kinds of queries, such as range SKQ. Finally, extensive simulations are conducted to demonstrate the efficiency of our ESKIV index and the corresponding query processing algorithms. [ABSTRACT FROM AUTHOR]

One of the challenges of managing an RDF database is predicting performance of SPARQL queries before they are executed. Performance characteristics, such as the execution time and memory usage, can help data consumers identify unexpected long-running queries before they start and estimate the system workload for query scheduling. Extensive works address such performance prediction problem in traditional SQL queries but they are not directly applicable to SPARQL queries. In this paper, we adopt machine learning techniques to predict the performance of SPARQL queries. Our work focuses on modeling features of a SPARQL query to a vector representation. Our feature modeling method does not depend on the knowledge of underlying systems and the structure of the underlying data, but only on the nature of SPARQL queries. Then we use these features to train prediction models. We propose a two-step prediction process and consider performances in both cold and warm stages. Evaluations are performed on real world SPRAQL queries, whose execution time ranges from milliseconds to hours. The results demonstrate that the proposed approach can effectively predict SPARQL query performance and outperforms state-of-the-art approaches. [ABSTRACT FROM AUTHOR]

We optimize multiway equijoins on relational tables using degree information. We give a new bound that uses degree information to more tightly bound the maximum output size of a query. On real data, our bound on the number of triangles in a social network can be up to 95 times tighter than existing worst case bounds. We show that using only a constant amount of degree information, we are able to obtain join algorithms with a running time that has a smaller exponent than existing algorithms-for any database instance. We also show that this degree information can be obtained in nearly linear time, which yields asymptotically faster algorithms in the serial setting and lower communication cost algorithms in the MapReduce setting. In the serial setting, the data complexity of join processing can be expressed as a function O(INx + OUT) in terms of input size IN and output size OUT in which x depends on the query. An upper bound for x is given by the fractional hypertreewidth. We are interested in situations in which we can get algorithms for which x is strictly smaller than the fractional hypertreewidth. We say that a join can be processed in subquadratic time if x < 2. Building on the AYZ algorithm for processing cycle joins in quadratic time, for a restricted class of joins which we call 1-series-parallel graphs, we obtain a complete decision procedure for identifying subquadratic solvability (subject to the 3-SUM problem requiring quadratic time). Our 3-SUM based quadratic lower bound is tight, making it the only known tight bound for joins that does not require any assumption about the matrix multiplication exponent ω. We also give a MapReduce algorithm that meets our improved communication bound and handles essentially optimal parallelism. [ABSTRACT FROM AUTHOR]

SPARQL is the standard query language for RDF data. The distinctive feature of SPARQL is the OPTIONAL operator, which allows for partial answers when complete answers are not available due to lack of information. However, optional matching is computationally expensive—query answering is PSPACE-complete. The well-designed fragment of SPARQL achieves much better computational properties by restricting the use of optional matching—query answering becomes coNP-complete. On the downside, well-designed SPARQL captures far from all real-life queries—in fact, only about half of the queries over DBpedia that use OPTIONAL are well-designed. In the present paper, we study queries outside of well-designed SPARQL. We introduce the class of weakly well-designed queries that subsumes well-designed queries and includes most common meaningful non-well-designed queries: our analysis shows that the new fragment captures over 99% of DBpedia queries with OPTIONAL. At the same time, query answering for weakly well-designed SPARQL remains coNP-complete, and our fragment is in a certain sense maximal for this complexity. We show that the fragment’s expressive power is strictly in-between well-designed and full SPARQL. Finally, we provide an intuitive normal form for weakly well-designed queries and study the complexity of containment and equivalence. [ABSTRACT FROM AUTHOR]

We present a cheating-sensitive quantum protocol for Privacy-Preserving Nearest Neighbor Query based on Oblivious Quantum Key Distribution and Quantum Encryption. Compared with the classical related protocols, our proposed protocol has higher security, because the security of our protocol is based on basic physical principles of quantum mechanics, instead of difficulty assumptions. Especially, our protocol takes single photons as quantum resources and only needs to perform single-photon projective measurement. Therefore, it is feasible to implement this protocol with the present technologies. [ABSTRACT FROM AUTHOR]

We study the compressed representation of a ranked tree by a (string) straight-line program (SLP) for its preorder traversal, and compare it with the well-studied representation by straight-line context free tree grammars (which are also known as tree straight-line programs or TSLPs). Although SLPs may be exponentially more succinct than TSLPs, we show that many simple tree queries can still be performed efficiently on SLPs, such as computing the height of a tree, tree navigation, or evaluation of Boolean expressions. Other problems on tree traversals turn out to be intractable, e.g. pattern matching and evaluation of tree automata. These problems can be still solved in polynomial time for TSLPs. [ABSTRACT FROM AUTHOR]

An enterprise database contains a global, integrated, and consistent representation of a company’s data. Multi-level modeling facilitates the definition and maintenance of such an integrated conceptual data model in a dynamic environment of changing data requirements of diverse applications. Multi-level models transcend the traditional separation of class and object with clabjects as the central modeling primitive, which allows for a more flexible and natural representation of many real-world use cases. In deep instantiation, the number of instantiation levels of a clabject or property is indicated by a single potency. Dual deep modeling (DDM) differentiates between source potency and target potency of a property or association and supports the flexible instantiation and refinement of the property by statements connecting clabjects at different modeling levels. DDM comes with multiple generalization of clabjects, subsetting/specialization of properties, and multi-level cardinality constraints. Examples are presented using a UML-style notation for DDM together with UML class and object diagrams for the representation of two-level user views derived from the multi-level model. Syntax and semantics of DDM are formalized and implemented in F-Logic, supporting the modeler with integrity checks and rich query facilities. [ABSTRACT FROM AUTHOR]

Session search, the task of document retrieval for a series of queries in a session, has been receiving increasing attention from the information retrieval research community. Session search exhibits the properties of rich user-system interactions and temporal dependency. These properties lead to our proposal of using partially observable Markov decision process to model session search. On the basis of a design choice schema for states, actions and rewards, we evaluate different combinations of these choices over the TREC 2012 and 2013 session track datasets. According to the experimental results, practical design recommendations for using PODMP in session search are discussed. [ABSTRACT FROM AUTHOR]

In this paper we describe a data structure that supports pattern matching queries on a dynamically arriving text over an alphabet of constant size. Each new symbol can be prepended to T in O(1) worst-case time. At any moment, we can report all occurrences of a pattern P in the current text in $$O(|P|+k)$$ time, where | P| is the length of P and k is the number of occurrences. This resolves, under assumption of constant size alphabet, a long-standing open problem of existence of a real-time indexing method for string matching (see Amir and Nor in Real-time indexing over fixed finite alphabets, pp. 1086-1095, 2008). [ABSTRACT FROM AUTHOR]

We study the complexity of quantum query algorithms that make p queries in parallel in each timestep. This model is in part motivated by the fact that decoherence times of qubits are typically small, so it makes sense to parallelize quantum algorithms as much as possible. We show tight bounds for a number of problems, specifically $$\Theta ((n/p)^{2/3})$$ p-parallel queries for element distinctness and $$\Theta ((n/p)^{k/(k+1)})$$ for $$k$$ -sum. Our upper bounds are obtained by parallelized quantum walk algorithms, and our lower bounds are based on a relatively small modification of the adversary lower bound method, combined with recent results of Belovs et al. on learning graphs. We also prove some general bounds, in particular that quantum and classical p-parallel query complexity are polynomially related for all total functions f when p is small compared to f's block sensitivity. [ABSTRACT FROM AUTHOR]

LaMacchia, Lauter and Mityagin presented a strong security model for authenticated key agreement, namely the $$\mathrm {eCK}$$ model. They also constructed a protocol, namely the NAXOS protocol, that enjoys a simple security proof in the $$\mathrm {eCK}$$ model. However, the NAXOS protocol uses a random oracle-based technique to combine the long-term secret key and the per session randomness, so-called NAXOS trick, in order to achieve the $$\mathrm {eCK}$$ security definition. For NAXOS trick-based protocols, the leakage of per session randomness modeled in the $$\mathrm {eCK}$$ model is somewhat unnatural, because the $$\mathrm {eCK}$$ model leaks per session randomness, while the output of the NAXOS trick computation remains safe. In this work, we present a standard model $$\mathrm {eCK}$$ -secure protocol construction, eliminating the NAXOS trick. Moreover, our protocol is a generic construction, which can be instantiated with arbitrary suitable cryptographic primitives. Thus, we present a generic $$\mathrm {eCK}$$ -secure, NAXOS-free, standard model key exchange protocol. To the best of our knowledge this is the first paper on generic transformation of a $$\mathrm {CCA2}$$ -secure public-key encryption scheme to an $$\mathrm {eCK}$$ -secure key exchange protocol in the standard model. [ABSTRACT FROM AUTHOR]

Modern information systems are increasingly large and consist of an interplay of technical components and social actors (humans and organizations). Such interplay threatens the security of the overall system and calls for verification techniques that enable determining compliance with security policies. Existing verification frameworks either have a limited expressiveness that inhibits the specification of real-world requirements or rely on formal languages that are difficult to use for most analysts. In this paper, we overcome the limitations of existing approaches by presenting the SecBPMN framework. Our proposal includes: (1) the SecBPMN-ml modeling language, a security-oriented extension of BPMN for specifying composite information systems; (2) the SecBPMN-Q query language for representing security policies; and (3) a query engine that enables checking SecBPMN-Q policies against SecBPMN-ml specifications. We evaluate our approach by studying its understandability and perceived complexity with experts, running scalability analysis of the query engine, and through an application to a large case study concerning air traffic management. [ABSTRACT FROM AUTHOR]

In this work we establish and investigate connections between causes for query answers in databases, database repairs with respect to denial constraints, and consistency-based diagnosis. The first two are relatively new research areas in databases, and the third one is an established subject in knowledge representation. We show how to obtain database repairs from causes, and the other way around. Causality problems are formulated as diagnosis problems, and the diagnoses provide causes and their responsibilities. The vast body of research on database repairs can be applied to the newer problems of computing actual causes for query answers and their responsibilities. These connections are interesting per se. They also allow us, after a transition inspired by consistency-based diagnosis to computational problems on hitting-sets and vertex covers in hypergraphs, to obtain several new algorithmic and complexity results for database causality. [ABSTRACT FROM AUTHOR]

The article studies the rewriting mechanisms for intensional documents in the Active XML framework, abstracted in the form of active context-free games. The safe rewriting problem studied in this article is to decide whether the first player, JULIET, has a winning strategy for a given game and (nested) word; this corresponds to a successful rewriting strategy for a given intensional document. The article examines several extensions of active context-free games. The primary extension allows for more expressive schemas (namely XML schemas and regular nested word languages) for both target and replacement languages and has the effect that games are played on nested words instead of (flat) words as in previous studies. Other extensions consider validation of input parameters of web services, and an alternative semantics based on insertion of values returned by the services. In general, the complexity of the safe rewriting problem is highly intractable (doubly exponential time), but the article identifies relevant tractable cases. [ABSTRACT FROM AUTHOR]

Graph databases are currently one of the most popular paradigms for storing data. One of the key conceptual differences between graph and relational databases is the focus on navigational queries that ask whether some nodes are connected by paths satisfying certain restrictions. This focus has driven the definition of several different query languages and the subsequent study of their fundamental properties. We define the graph query language of Regular Queries, which is a natural extension of unions of conjunctive 2-way regular path queries (UC2RPQs) and unions of conjunctive nested 2-way regular path queries (UCN2RPQs). Regular queries allow expressing complex regular patterns between nodes. We formalize regular queries as nonrecursive Datalog programs extended with the transitive closure of binary predicates. This language has been previously considered, but its algorithmic properties are not well understood. Our main contribution is to show elementary tight bounds for the containment problem for regular queries. Specifically, we show that this problem is 2Expspace-complete. For all extensions of regular queries known to date, the containment problem turns out to be non-elementary. Together with the fact that evaluating regular queries is not harder than evaluating UCN2RPQs, our results show that regular queries achieve a good balance between expressiveness and complexity, and constitute a well-behaved class that deserves further investigation. [ABSTRACT FROM AUTHOR]

In this paper, a query-based summarization method, which uses a combination of semantic relations between words and their syntactic composition, to extract meaningful sentences from document sets is introduced. The problem with current statistical methods is that they fail to capture the meaning when comparing a sentence and a user query; hence there is often a conflict between the extracted sentences and users' requirements. However, this particular method can improve the quality of document summaries because it is able to avoid extracting a sentence whose similarity with the query is high but whose meaning is different. The method is executed by computing the semantic and syntactic similarity of the sentence-to-sentence and sentence-to-query. To reduce redundancy in summary, this method uses the greedy algorithm to impose diversity penalty on the sentences. In addition, the proposed method expands the words in both the query and the sentences to tackle the problem of information limit. It bridges the lexical gaps for semantically similar contexts that are expressed using different wording. The experimental results display that the proposed method is able to improve performance compared with the participating systems in DUC 2006. The experimental results also showed that the proposed method demonstrates better performance as compared to other existing techniques on DUC 2005 and DUC 2006 datasets. [ABSTRACT FROM AUTHOR]

In general, access control mechanisms in DBMSs ensure that users access only those portions of data for which they have authorizations, according to a predefined set of access control policies. However, it has been shown that access control mechanisms might be not enough. A clear example is the inference problem due to functional dependencies, which might allow a user to discover unauthorized data by exploiting authorized data. In this paper, we wish to investigate data dependencies (e.g., functional dependencies, foreign key constraints, and knowledge-based implications) from a different perspective. In particular, the aim was to investigate data dependencies as a mean for increasing the DBMS utility, that is, the number of queries that can be safely answered, rather than as channels for releasing sensitive data. We believe that, under given circumstances, this unauthorized release may give more benefits than issues. As such, we present a query rewriting technique capable of extending defined access control policies by exploiting data dependencies, in order to authorize unauthorized but inferable data. [ABSTRACT FROM AUTHOR]

The web becomes an overwhelmingly huge repository of data. At the same time, users demand access to the information on the web in a more natural way. In other words, users require interaction with the web using natural linguistic terms and expect human comprehensive answers. The introduction of Resource Description Framework (RDF) is a promising step towards significant changes how systems can utilize the web. The very nature of RDF format that ensures high interconnectivity of pieces of data creates an opportunity to process and analyse data in a different way. In this paper, we address the problem of processing web information using fuzzy-based technologies. In particular, we adopt a linguistic representation model to determining alternatives that match a given reference with the highest possible degree and satisfying some specific criteria. The process of comparing alternatives to the reference is feature-driven while an entity is described by its features. The proposed methodology is able to deal with features of different nature and utilize comparison mechanisms suitable for each type of features. The utilization of 2-tuple allows for comparing and aggregating linguistic-based descriptions of features, especially when the reference does not specify values of features explicitly. In experiments, we show the utilization of our approach in the domain of pharmacy. The obtained results show the advantage of using the feature-based comparison process and linguistic aggregation procedure over results obtained using the RDF query language SPARQL (SPARQL Protocol and RDF Query Language). [ABSTRACT FROM AUTHOR]

We have developed a novel method to describe human white matter anatomy using an approach that is both intuitive and simple to use, and which automatically extracts white matter tracts from diffusion MRI volumes. Further, our method simplifies the quantification and statistical analysis of white matter tracts on large diffusion MRI databases. This work reflects the careful syntactical definition of major white matter fiber tracts in the human brain based on a neuroanatomist's expert knowledge. The framework is based on a novel query language with a near-to-English textual syntax. This query language makes it possible to construct a dictionary of anatomical definitions that describe white matter tracts. The definitions include adjacent gray and white matter regions, and rules for spatial relations. This novel method makes it possible to automatically label white matter anatomy across subjects. After describing this method, we provide an example of its implementation where we encode anatomical knowledge in human white matter for ten association and 15 projection tracts per hemisphere, along with seven commissural tracts. Importantly, this novel method is comparable in accuracy to manual labeling. Finally, we present results applying this method to create a white matter atlas from 77 healthy subjects, and we use this atlas in a small proof-of-concept study to detect changes in association tracts that characterize schizophrenia. [ABSTRACT FROM AUTHOR]

Identifying dependencies that hold in relational databases is essential to produce good databases designs. In particular, functional and multivalued dependencies are used to obtain relation schemes that satisfy the 4th normal form, a property that is considered satisfactory for most applications. It is known that the class of sets of functional dependencies is learnable in the exact model of learning with queries. Also a subclass of multivalued dependencies, the class of consequent-restricted multivalued dependencies, has been shown to be learnable in this model. In this paper, we present an algorithm that learns a class that contains sets of both functional and multivalued dependencies under some restrictions imposed on the antecedents of dependencies. We also show, as a by-product, an algorithm that learns a non-trivial subclass of 2-quasi Horn formulas, closely related to the class just mentioned. [ABSTRACT FROM AUTHOR]

With the proliferation of public web archives, it is becoming more important to better profile their contents, both to understand their immense holdings as well as to support routing of requests in the Memento aggregator. To save time, the Memento aggregator should only poll the archives that are likely to have a copy of the requested URI. Using the crawler index files produced after crawling, we can generate profiles of the archives that summarize their holdings and can be used to inform routing of the Memento aggregator's URI requests. Previous work in profiling ranged from using full URIs (no false positives, but with large profiles) to using only top-level domains (TLDs) (smaller profiles, but with many false positives). This work explores strategies in between these two extremes. In our experiments, we correctly identified about 78 % of the URIs that were present or not present in the archive with less than 1 % relative cost as compared to the complete knowledge profile and 94 % URIs with less than 10 % relative cost without any false negatives. With respect to the TLD-only profile, the registered domain profile doubled the routing precision, while complete hostname and one path segment gave a tenfold increase in the routing precision. [ABSTRACT FROM AUTHOR]

Given a set of k-dimensional objects, the skyline-CL query returns all clusters over skyline objects according to their cardinalities. A naïve solution to this problem can be implemented in two phases: (1) using existing skyline query algorithms to obtain all skyline objects and (2) utilizing the DBSCAN algorithm to cluster these skyline objects. However, it is extremely inefficient in real applications because phases 1 and 2 are all CPU-sensitive. Motivated by the above facts, in this paper, we present Algorithm for Efficient Processing of the Skyline-CL Query (AEPSQ), an efficient sound and complete algorithm for returning all skyline clusters. During the process of obtaining skyline objects, the AEPSQ algorithm organizes these objects as a novel k-ary tree SI -Tree which is first proposed in our paper, and employs several interesting properties of SI -Tree to produce skyline clusters fast. Furthermore, we present detailed theoretical analyses and extensive experiments that demonstrate our algorithm is both efficient and effective. [ABSTRACT FROM AUTHOR]

Search over encrypted data recently became a critical operation that raised a considerable amount of interest in both academia and industry. Especially, as outsourcing, sensitive data to cloud prove to be a strong trend to benefit from the unmatched storage and computing capacities thereof. Indeed, privacy-preserving search over encrypted data, an apt term to address privacy-related issues concomitant in outsourcing sensitive data, have been widely investigated in the literature under different models and assumptions. In this work, we propose an efficient scheme that allows privacy-preserving search over encrypted data using queries with multiple keywords. Most important contributions of this work are as follows. Firstly, using a property referred as $$\delta $$ - mean query obfuscation, the proposed scheme hides the search patterns, which are allowed to leak in many works in the literature including our preliminary work on the subject Orencik et al. (2013) []. Secondly, a two-server setting is employed to eliminate the correlation between the queries and matching documents sent to the user under the assumption that the two servers are not colluding. Thirdly, we propose a novel compression scheme that reduces both the communication cost between the two servers and the computation cost of the search operation more than 55 times compared to the standard approach. And finally, the proposed scheme also provides an effective scoring and ranking capability that is based on term frequency-inverse document frequency (tf-idf) weights of keyword-document pairs. Our analyses demonstrate that the proposed scheme is privacy-preserving, efficient and effective. [ABSTRACT FROM AUTHOR]

Due to its wide applications, subgraph query has attracted lots of attentions in database community. In this paper, we focus on subgraph query over a single large graph G, i.e., finding all embeddings of query Q in G. Different from existing feature-based approaches, we map all edges into a two-dimensional space R and propose a bitmap structure to index R. At run time, we find a set of adjacent edge pairs (AEP) or star- style patterns (SSP) to cover Q. We develop edge join (EJ) algorithms to address both AEP and SSP subqueries. Based on the bitmap index, our method can optimize I/O and CPU cost. More importantly, our index has the linear space complexity instead of exponential complexity in feature-based approaches, which indicates that our index can scale well with respect to large data size. Furthermore, our index has light maintenance overhead, which has not been considered in most of existing work. Extensive experiments show that our method significantly outperforms existing ones in both online and offline processing with respect to query response time, index building time, index size and index maintenance overhead. [ABSTRACT FROM AUTHOR]

In the last decades the popularity of natural language interfaces to databases (NLIDBs) has increased, because in many cases information obtained from them is used for making important business decisions. Unfortunately, the complexity of their customization by database administrators make them difficult to use. In order for a NLIDB to obtain a high percentage of correctly translated queries, it is necessary that it is correctly customized for the database to be queried. In most cases the performance reported in NLIDB literature is the highest possible; i.e., the performance obtained when the interfaces were customized by the implementers. However, for end users it is more important the performance that the interface can yield when the NLIDB is customized by someone different from the implementers. Unfortunately, there exist very few articles that report NLIDB performance when the NLIDBs are not customized by the implementers. This article presents a semantically-enriched data dictionary (which permits solving many of the problems that occur when translating from natural language to SQL) and an experiment in which two groups of undergraduate students customized our NLIDB and English language frontend (ELF), considered one of the best available commercial NLIDBs. The experimental results show that, when customized by the first group, our NLIDB obtained a 44.69 % of correctly answered queries and ELF 11.83 % for the ATIS database, and when customized by the second group, our NLIDB attained 77.05 % and ELF 13.48 %. The performance attained by our NLIDB, when customized by ourselves was 90 %. [ABSTRACT FROM AUTHOR]

Query formalisms and facilities have received significant attention in the past decades resulting in the development of query languages with varying characteristics; many of them resemble sql. Query facilities typically ship as part of database management systems or, sometimes, bundled with programming languages. For applications written in imperative programming languages, database management systems impose an expensive model transformation. In-memory data structures can represent sophisticated relationships in a manner that is efficient in terms of storage and processing overhead, but most general purpose programming languages lack an interpreter and/or an expressive query language for manipulating interactive queries. Issuing interactive ad-hoc queries on program data structures is tough. This work presents a method and an implementation for representing an application's arbitrary imperative programming data model as a queryable relational one. The Pico COllections Query Library ( pi co ql) uses a domain specific language to define a relational representation of application data structures and an sql interface implementation. Queries are issued interactively and are type safe. We demonstrate our relational representation for objects and the library's usefulness on three large c++ projects. pi co ql enhances query expressiveness and boosts productivity compared to querying via traditional programming constructs. [ABSTRACT FROM AUTHOR]

Node selecting tree automata (NSTAs) constitute a general formalism defining unary queries over trees. Basically, a node is selected by an NSTA when it is visited in a selecting state during an accepting run. We consider twig patterns as an abstraction of XPath. Since the queries definable by NSTAs form a strict superset of twig-definable queries, we study the complexity of the problem to decide whether the query by a given NSTA is twig-definable. In particular, we obtain that the latter problem is EXPTIME-complete. In addition, we show that it is also EXPTIME-complete to decide whether the query by a given NSTA is definable by a node selecting string automaton. [ABSTRACT FROM AUTHOR]

The framework of database repairs is a principled approach to managing inconsistency in databases. In particular, the consistent answers of a query on an inconsistent database provide sound semantics and the guarantee that the values obtained are those returned by the query on every repair of the given inconsistent database. In this paper, we carry out a systematic investigation of the data complexity of the consistent answers of conjunctive queries for set-based repairs and with respect to classes of constraints that, in recent years, have been extensively studied in the context of data exchange and data integration. Our results, which range from polynomial-time computability to undecidability, complement or improve on earlier work, and provide a fairly comprehensive picture of the data complexity of consistent query answering. We also address the problem of finding a 'representative' or 'useful' repair of an inconsistent database. To this effect, we introduce the notion of a universal repair, as well as relaxations of it, and then apply it to the investigation of the data complexity of consistent query answering. [ABSTRACT FROM AUTHOR]

In this paper, we design and analyze parallel algorithms for skyline queries. The skyline of a multidimensional set consists of the points for which no other point exists that is at least as good along every dimension. As a framework for parallel computation, we use both the MP model proposed in Koutris and Suciu (), which requires that the data is perfectly load-balanced, and a variation of the model in Afrati and Ullman (), the GMP model, which demands weaker load balancing constraints. In addition to load balancing, we want to minimize the number of blocking steps, where all processors must wait and synchronize. We propose a 2-step algorithm in the MP model for any dimension of the dataset, as well a 1-step algorithm for the case of 2 and 3 dimensions. Finally, we present a 1-step algorithm in the GMP model for any number of dimensions and a 1-step algorithm in the MP model for uniform distributions of data points. [ABSTRACT FROM AUTHOR]

A common goal of privacy research is to release synthetic data that satisfies a formal privacy guarantee and can be used by an analyst in place of the original data. To achieve reasonable accuracy, a synthetic data set must be tuned to support a specified set of queries accurately, sacrificing fidelity for other queries. This work considers methods for producing synthetic data under differential privacy and investigates what makes a set of queries 'easy' or 'hard' to answer. We consider this issue in the particular case of answering sets of linear counting queries using the matrix mechanism (Li et al. ), a recent differentially-private mechanism that can reduce error by adding complex correlated noise adapted to a specified workload. Our main result is a novel lower bound on the minimum total error required to simultaneously release answers to a set of workload queries when using the matrix mechanism. The bound reveals that the hardness of a query workload is related to the spectral properties of the workload when it is represented in matrix form. Under ( 휖, δ)-differential privacy, we prove that this bound is tight for many common workloads such as the set of all predicate queries and the set of all k-way marginals. Our empirical study also indicates this bound is close-to-tight on workloads consisting of random interval queries or random marginals. [ABSTRACT FROM AUTHOR]

We study highly expressive query languages for unordered data trees, using as formal vehicles Active XML and extensions of languages in the while family. All languages may be seen as adding some form of control on top of a set of basic pattern queries. The results highlight the impact and interplay of different factors: the expressive power of basic queries, the embedding of computation into data (as in Active XML), and the use of deterministic vs. nondeterministic control. All languages are Turing complete, but not necessarily query complete in the sense of Chandra and Harel. Indeed, we show that some combinations of features yield serious limitations, analogous to FO definability in the relational context. On the other hand, the limitations come with benefits such as the existence of powerful normal forms providing opportunities for optimization. Other languages are 'almost' complete, but fall short because of subtle limitations reminiscent of the copy elimination problem in object databases. [ABSTRACT FROM AUTHOR]

Networks of relational transducers can serve as a formal model for declarative networking, focusing on distributed database querying applications. In declarative networking, a crucial property is eventual consistency, meaning that the final output does not depend on the message delays and reorderings caused by the network. Here, we formalize eventual consistency as a confluence notion, meaning that finite executions of the system can always be extended to yield the desired output. We show that confluence is decidable when the transducers satisfy some syntactic restrictions, some of which have also been considered in earlier work on automated verification of relational transducers. This simple class of transducer networks computes exactly all distributed queries expressible by unions of conjunctive queries with negation. [ABSTRACT FROM AUTHOR]

Information Retrieval (IR) systems aim to retrieve data that satisfies certain requirements and constitute an important service in many types of networks, including Delay/Disruption Tolerant Networks (DTNs). In current DTN based IR systems, the data that satisfies a query is assumed to be stored on a single node. Therefore, once a node receives a query in which it has the corresponding data, the query can be resolved completely. However, in scenarios where a query requires data from multiple nodes, these IR systems may fail. Henceforth, in this paper, we propose Distributed Data-Centric Information Retrieval (DDC-IR), a data centric IR system that supports all query types; e.g., continuous and complex. More importantly, it is designed specifically to operate in DTNs. It also incorporates a new packet, aka Query Reply Packet, that includes both a query and one or more replies. We show how this packet facilitates efficient query resolution and enables data centric routing. In addition, it uses caching so that nodes store popular queries that has the effect of speeding up query resolution. We have conducted an extensive simulation study to compare DDC-IR to state of the art IR systems using the popular Random Waypoint model and a trace-file containing student movements on a campus. The results show that DDC-IR is able to resolve 50 % more queries and has an 80 % lower buffer occupancy level than existing IR systems. We also tested DDC-IR in networks with varying sizes. For networks with 100 nodes, DDC-IR is able to resolve queries while current IR systems fail to resolve any queries. In particular, when the number of nodes increases, current IR systems fail to resolve any queries, whilst DDC-IR is able to resolve complex and continuous queries. The influence of the number of sub-queries on query resolution time is also studied. Specifically, when the number of sub-queries in a complex query increases from five to nine, DDC-IR uses 50 % more time to resolve a query. In comparison, prior IR systems fail to resolve any queries. [ABSTRACT FROM AUTHOR]

Software traceability is a required element in the development and certification of safety-critical software systems. However, trace links, which are created at significant cost and effort, are often underutilized in practice due primarily to the fact that project stakeholders often lack the skills needed to formulate complex trace queries. To mitigate this problem, we present a solution which transforms spoken or written natural language queries into structured query language (SQL). TiQi includes a general database query mechanism and a domain-specific model populated with trace query concepts, project-specific terminology, token disambiguators, and query transformation rules. We report results from four different experiments exploring user preferences for natural language queries, accuracy of the generated trace queries, efficacy of the underlying disambiguators, and stability of the trace query concepts. Experiments are conducted against two different datasets and show that users have a preference for written NL queries. Queries were transformed at accuracy rates ranging from 47 to 93 %. [ABSTRACT FROM AUTHOR]

Growing size of Semantic Web data demands scalable semantic stores. Hadoop-based distributed and parallel processing frameworks such as HBase and Hive are becoming increasingly popular for storing and retrieving voluminous data. Hive, more specifically, supports complex analytical processing but the query interface does not support data exploration using SPARQL, a standard query language for Semantic Web. We propose a semantic preserving SPARQL to HiveQL translation scheme that provides a querying interface for Hive in an attempt to realize a scalable semantic web triplestore. Major contributions of our research include: semantic preserving SPARQL to HiveQL query translation algorithm and storage schema-independent querying mechanism that accommodates different storage schemes without impacting translation time. The results demonstrate efficient working of proposed translation algorithm and that it supports different types of SPARQL queries. [ABSTRACT FROM AUTHOR]

Extensible markup language (XML) has been widely adopted as a standard to exchange and integrate data over multiple sources. This allows users to explore large datasets through a declarative query interface, such as XQuery and XPath. However, the results of queries posted to such heterogeneous data sources are often inconsistent due to the anomalies arising from structural and semantic inconsistencies. This significantly affects the ability of the system to provide accurate query answers. Most of the prior work on finding consistent query answers (CQAs) lacks the full extensibility to find the CQAs relating to the requirements of data constraints holding conditionally on XML data with inconsistent structures. This paper proposes an approach, called SC2QA, which utilizes XML conditional functional dependency (XCSD) to compute consistent answers for queries posted to arbitrary XML data to improve information quality. An XCSD is a structured and content-based functional dependency holding conditionally on certain objects with diverse structures. The query answer is calculated by qualifying queries with appropriate information derived from the interaction between the query and the XCSDs. Experiments have been conducted on synthetic datasets to demonstrate the effectiveness of SC2QA. [ABSTRACT FROM AUTHOR]

With the increasing popularity of XML database applications, the use of efficient XML query optimizers is becoming very essential. The performance of an XML query optimizer depends heavily on the query selectivity estimators it uses to find the best possible query execution plan. In this work, we propose and evaluate a novel selectivity estimator, based on a structural synopsis, called SynopTech. The main idea of SynopTech is the generation of a summary tree by labeling the nodes of the source XML data tree using a fingerprint function and merging subtrees with similar structures. The generated summary tree is then used by SynopTech to estimate the selectivity of given queries. We experimented the proposed approach with four benchmark datasets of different structural characteristics and using different types of queries. Comparing with the Sampling algorithm, one of the state-of-the-art algorithms for selectivity estimations, SynopTech achieved lower selectivity estimation error rates, yet with very low memory budget. For example, for linear and existential queries, SynopTech had perfect estimations whereas the Sampling algorithm had an error rate of up to 70 %. For regular twig queries, SynopTech had a maximum error rate of 4.12 % whereas the Sampling algorithm had more than 55 %. [ABSTRACT FROM AUTHOR]

In recent years the inverted lists evaluation model along with holistic stack-based algorithms have been established as the most prominent techniques for evaluating XML queries on large persistent XML data. In this framework, we are using materialized views for optimizing XML queries. We consider a novel approach which instead of materializing the answer of a view materializes exactly the inverted sublists that are necessary for computing the answer of the view. This originality allows storing view materializations as compressed bitmaps, a solution that minimizes the materialization space and empowers performing optimization operations as CPU-efficient bitwise operations. To realize the potential of bitmap materialized views in optimizing query performance, we define and address the following problem (view configuration problem): given an XML tree and its schema find a template of tree-pattern views (view configuration) such that: (a) the views of this configuration can answer all the queries that can be issued against the schema, (b) their materialization fits in the space provided, and (c) evaluating the queries using these views minimizes the overall query evaluation cost. We consider an instance of this problem for tree pattern queries. Our intension is to find view configurations whose materializations are small enough to be stored in main memory. We find two candidate solution configurations and we identify cases where views can be excluded from materialization in a configuration without affecting query performance. In order to compare our approach with an approach which also can support the optimization of every query on the schema, we implemented an improvement of a state-of-the-art approach which is based on structural indexes. Our experimental results show that our approach is stable, greatly improves evaluating queries without materialized views, outperforms the structural index approach on all test cases and is very close to the optimal. These results characterize our approach as the best candidate for supporting the optimization of queries in the framework of the inverted lists model. [ABSTRACT FROM AUTHOR]

With the rapid growth in the amount of graph-structured Resource Description Framework (RDF) data, SPARQL query processing has received significant attention. The most important part of SPARQL query processing is its method of subgraph pattern matching. For this, most RDF stores use relation-based approaches, which can produce a vast number of redundant intermediate results during query evaluation. In order to address this problem, we propose an RDF Triple Filtering (R3F) method that exploits the graph-structural information of RDF data. We design a path-based index called the RDF Path index (RP-index) to efficiently provide filter data for the triple filtering. We also propose a relational operator called the RDF Filter (RFLT) that can conduct the triple filtering with little overhead compared to the original query processing. Through comprehensive experiments on large-scale RDF datasets, we demonstrate that R3F can effectively and efficiently reduce the number of redundant intermediate results and improve the query performance. [ABSTRACT FROM AUTHOR]

Several established and novel applications motivate us to study the expressive power of navigational query languages on graphs, which represent binary relations. Our basic language has only the operators union and composition, together with the identity relation. Richer languages can be obtained by adding other features such as intersection, difference, projection and coprojection, converse, and the diversity relation. The expressive power of the languages thus obtained cannot only be evaluated at the level of path queries (queries returning binary relations), but also at the level of Boolean or yes/no queries (expressed by the nonemptiness of an expression). For the languages considered above, adding transitive closure augments the expressive power not only at the level of path queries but also at the level of Boolean queries, for the latter provided that multiple input relations are allowed. This is no longer true in the context of unlabeled graphs (i.e., in the case where there is only one input relation), however. In this paper, we prove that this is indeed not the case for the basic language to which none, one, or both of projection and the diversity relation are added, a surprising result given the limited expressive power of these languages. In combination with earlier work (Fletcher et al. , ), this result yields a complete understanding of the impact of transitive closure on the languages under consideration. [ABSTRACT FROM AUTHOR]

Many commonly used logics, including classical logic and intuitionistic logic, are trivialized in the presence of inconsistency, in the sense that inconsistent premises cause the derivation of any formula. It is thus often useful to define inconsistency-tolerant variants of such logics, which are faithful to the original logic with respect to consistent theories but also allow for nontrivial inconsistent theories. A common way of doing so is by incorporating distance-based considerations for concrete logics. So far this has been done mostly in the context of two-valued semantics. Our purpose in this paper is to show that inconsistency-tolerance can be achieved for any logic that is based on a denotational semantics. For this, we need to trade distances for the more general notion of dissimilarities. We then examine the basic properties of the entailment relations that are obtained and exemplify dissimilarity-based reasoning in various forms of denotational semantics, including multi-valued semantics, non-deterministic semantics, and possible-worlds (Kripke-style) semantics. Moreover, we show that our approach can be viewed as an extension of several well-studied forms of reasoning in the context of belief revision, database integration, consistent query answering, and inconsistency maintenance in knowledge-based systems. [ABSTRACT FROM AUTHOR]

Scientific data analytics in high-performance computing environments has been evolving along with the advancement of computing capabilities. With the onset of exascale computing, the increasing gap between compute performance and I/O bandwidth has rendered the traditional post-simulation processing a tedious process. Despite the challenges due to increased data production, there exists an opportunity to benefit from 'cheap' computing power to perform query-driven exploration and visualization during simulation time. To accelerate such analyses, applications traditionally augment, post-simulation, raw data with large indexes, which are then repeatedly utilized for data exploration. However, the generation of current state-of-the-art indexes involves a compute- and memory-intensive processing, thus rendering them inapplicable in an in situ context. In this paper we propose DIRAQ, a parallel in situ, in network data encoding and reorganization technique that enables the transformation of simulation output into a query-efficient form, with negligible runtime overhead to the simulation run. DIRAQ's effective core-local, precision-based encoding approach incorporates an embedded compressed index that is 3-6 $$\times $$ smaller than current state-of-the-art indexing schemes. Its data-aware index adjustmentation improves performance of group-level index layout creation by up to 35 % and reduces the size of the generated index by up to 27 %. Moreover, DIRAQ's in network index merging strategy enables the creation of aggregated indexes that speed up spatial-context query responses by up to $$10\times $$ versus alternative techniques. DIRAQ's topology-, data-, and memory-aware aggregation strategy results in efficient I/O and yields overall end-to-end encoding and I/O time that is less than that required to write the raw data with MPI collective I/O. [ABSTRACT FROM AUTHOR]

It is a big challenge to guarantee the quality of discovered relevance features in text documents for describing user preferences because of the large number of terms, patterns, and noise. Term-based approaches are used to extract a large number of features, most of which are meaningless noise, and suffer from polysemy and synonymy. Most popular text mining techniques consider the distribution of terms in documents and data sets when calculating the weight of the terms. The innovative technique presented in this paper is called Specific Feature Discovery and is uses positive feedback only to discover positive patterns as high-level features to consider relationship among terms, then high-level patterns deployed to low-level terms to overcome the limitation of patterns. To improve the quality of the extracted features, high-level patterns are extracted from feedback documents. Following this, low-level terms extracted from high-level patterns. Determining the weight of the low-level terms is based on the distribution of the terms in the high-level patterns and the specificity of the terms in a positive group of documents. The specificity of the low-level terms is calculated according to the frequency of the terms in the documents and the frequency of the terms in extracted patterns. There have been extensive experiments in which this technique has been tested using the Reuters Corpus Volume 1 data set and Text REtrieval Conference topics. The results show that the proposed method achieves an encouraging performance in all measures. [ABSTRACT FROM AUTHOR]

Correlations between geo-spatial entities in the real world are universal, and the proper exploitation of such correlations can aid in the understanding and analyzing of geo-spatial data. To improve geo-spatial data retrieval performance, we address the geo-link problem of heterogeneous geo-spatial entities. First, a graph-like multi-view correlation model is proposed that uses feature links to obtain information regarding entities and their interconnections. The proposed model construction algorithm can simultaneously incorporate geo-location, semantic description, visual content and their mutual correlations. It exploits the underlying relationship between the features and calculates the strength of the correlation between the different entities. An improved block-based strategy is then employed that takes all of the different features into consideration, where different features representing various semantic meanings are weighted according to neighboring entities. This allows for an expedited construction process. Experimental results using real data support the superiority of this approach in terms of both speed and comprehensiveness when compared to traditionally used methods. [ABSTRACT FROM AUTHOR]

The symbols for the new IUPAC elements named in November 2016 can introduce subtle ambiguities within cheminformatics software. The ambiguities are described and demonstrated by highlighting inconsistencies between software when handling existing element symbols. [ABSTRACT FROM AUTHOR]

Model-driven software modernization is a discipline in which model-driven development (MDD) techniques are used in the modernization of legacy systems. When existing software artifacts are evolved, they must be transformed into models to apply MDD techniques such as model transformations. Since most modernization scenarios (e.g., application migration) involve dealing with code in general-purpose programming languages (GPL), the extraction of models from GPL code is an essential task in a model-based modernization process. This activity could be performed by tools to bridge grammarware and MDD technical spaces, which is normally carried out by dedicated parsers. Grammar-to-Model Transformation Language (Gra2MoL) is a domain-specific language (DSL) tailored to the extraction of models from GPL code. This DSL is actually a text-to-model transformation language which can be applied to any code conforming to a grammar. Gra2MoL aims to reduce the effort needed to implement grammarware-MDD bridges, since building dedicated parsers is a complex and time-consuming task. Like ATL and RubyTL languages, Gra2MoL incorporates the binding concept needed to write mappings between grammar elements and metamodel elements in a simple declarative style. The language also provides a powerful query language which eases the retrieval of scattered information in syntax trees. Moreover, it incorporates extensibility and grammar reuse mechanisms. This paper describes Gra2MoL in detail and includes a case study based on the application of the language in the extraction of models from Delphi code. [ABSTRACT FROM AUTHOR]