Search results for "query"
showing 10 items of 125 documents
Quantum Query Complexity for Some Graph Problems
2004
The paper [4] by H. Buhrman and R. de Wolf contains an impressive survey of solved and open problems in quantum query complexity, including many graph problems. We use recent results by A.Ambainis [1] to prove higher lower bounds for some of these problems. Some of our new lower bounds do not close the gap between the best upper and lower bounds. We prove in these cases that it is impossible to provide a better application of Ambainis’ technique for these problems.
Quantum Algorithm for Dyck Language with Multiple Types of Brackets
2021
We consider the recognition problem of the Dyck Language generalized for multiple types of brackets. We provide an algorithm with quantum query complexity \(O(\sqrt{n}(\log n)^{0.5k})\), where n is the length of input and k is the maximal nesting depth of brackets. Additionally, we show the lower bound for this problem which is \(\varOmega (\sqrt{n}c^{k})\) for some constant c.
ViziQuer: A Visual Notation for RDF Data Analysis Queries
2019
Visual SPARQL query notations aim at easing the RDF data querying task. At the current state of the art there is still no generally accepted visual graph-based notation suitable to describe RDF data analysis queries that involve aggregation and subqueries. In this paper we present a visual diagram-centered notation for SPARQL select query formulation, capable to handle aggregate/statistics queries and hierarchic queries with subquery structure. The notation is supported by a web-based prototype tool. We present the notation examples, describe its syntax and semantics and describe studies with possible end users, involving both IT and medicine students.
IntentStreams
2015
The user's understanding of information needs and the information available in the data collection can evolve during an exploratory search session. Search systems tailored for well-defined narrow search tasks may be suboptimal for exploratory search where the user can sequentially refine the expressions of her information needs and explore alternative search directions. A major challenge for exploratory search systems design is how to support such behavior and expose the user to relevant yet novel information that can be difficult to discover by using conventional query formulation techniques. We introduce IntentStreams, a system for exploratory search that provides interactive query refine…
Grammars++ for modelling information in text
1999
Abstract Grammars provide a convenient means to describe the set of valid instances in a text database. Flexibility in choosing a grammar can be exploited to provide information modelling capability by designing productions in the grammar to represent entities and relationships of interest to database applications. Additional constraints can be specified by attaching predicates to selected nonterminals in the grammar. When used for database definition, grammars can provide the functionality that users have come to expect of database schemas. Extended grammars can also be used to specify database manipulation, including query, update, view definition, and index specification.
PDB: A pictorial database oriented to data analysis
1993
The paper describes a new pictorial database oriented to image analysis, implemented inside the MIDAS data analysis system. Pictorial databases need expressive data structures in order to represent a wide class of information from the numerical to the visual. The model of the database is relational; however, a full normalization is not achievable, owing to the complexity of the visual information. The paper reports the general design and notes on the software implementation. Preliminary experiments show the performance of the pictorial database. Copyright © 1993 John Wiley & Sons, Ltd
Querying the Guarded Fragment with Transitivity
2016
We study the problem of answering a union of Boolean conjunctive queries q against a database Δ, and a logical theory φ which falls in the guarded fragment with transitive guards (GF + TG). We trace the frontier between decidability and undecidability of the problem under consideration. Surprisingly, we show that query answering under GF2 + TG, i.e., the two-variable fragment of GF + TG, is already undecidable (even without equality), whereas its monadic fragment is decidable; in fact, it is 2exptime-complete in combined complexity and coNP-complete in data complexity. We also show that for a restricted class of queries, query answering under GF+TG is decidable. © 2013 Springer-Verlag.
On the Power of Tree-Walking Automata
2000
Tree-walking automata (TWAs) recently received new attention in the fields of formal languages and databases. Towards a better understanding of their expressiveness, we characterize them in terms of transitive closure logic formulas in normal form. It is conjectured by Engelfriet and Hoogeboom that TWAs cannot define all regular tree languages, or equivalently, all of monadic second-order logic. We prove this conjecture for a restricted, but powerful, class of TWAs. In particular, we show that 1-bounded TWAs, that is TWAs that are only allowed to traverse every edge of the input tree at most once in every direction, cannot define all regular languages. We then extend this result to a class …
Patient documentation for the ultrasound laboratory
1991
The development of a PC based system for the storage of patient data in the echocardiography laboratory is described. Special design objectives were low cost and user friendliness, including an integrated special query language. After 3 years of use, the system stores 80000 diagnoses from 12000 patients without any relevant slowdown of response. Future developments concerning the communication between the database system and an echocardiographic sector scanner are discussed.
Automated source code transformations on fourth generation languages
2004
To control the operation of large application suites or to tailor a special purpose application to particular need, developers frequently use application specific languages, such as batch, scripting, and query languages. These languages which are also referred to as fourth generation languages (4GLs) therefore play an important role in today's economy. Incompatibilities between different versions of 4GLs and changing requirements may make massive changes on a company's library of 4GL programs necessary. Here, we explore possibilities for performing mass changes on 4GLs and show how the transformation of programs written in 4GLs compares to the transformation of mainstream programming langua…