Relevant bibliographies by topics / Regular queries

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Books
  4. Book chapters
  5. Conference papers
  6. Reports

Academic literature on the topic 'Regular queries'

Author: Grafiati
Published: 22 February 2025

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Regular queries.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Regular queries"

1

Grahne, Gösta, Alex Thomo, and William W. Wadge. "Preferential Regular Path Queries." Fundamenta Informaticae 89, no. 2-3 (2008): 259–88. https://doi.org/10.3233/fun-2008-892-304.

Full text
Abstract:
In this paper, we introduce preferential regular path queries. These are regular path queries whose symbols are annotated with preference weights for "scaling" up or down the intrinsic importance of matching a symbol against a (semistructured) database edge label. Annotated regular path queries are expressed syntactically as annotated regular expressions. We interpret these expressions in a uniform semiring framework, which allows different semantic interpretations for the same syntactic annotations. For our preference queries, we study three important aspects: (1) (progressive) query answering (2) (certain) query answering in LAV data-integration systems, and (3) query containment and equivalence. In all of these, we obtain important positive results, which encourage the use of our preference framework for enhanced querying of semistructured databases.
APA, Harvard, Vancouver, ISO, and other styles
2

Liu, Yanhong A., Tom Rothamel, Fuxiang Yu, Scott D. Stoller, and Nanjun Hu. "Parametric regular path queries." ACM SIGPLAN Notices 39, no. 6 (2004): 219–30. http://dx.doi.org/10.1145/996893.996868.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Calvanese, Diego, Giuseppe De Giacomo, Maurizio Lenzerini, and Moshe Y. Vardi. "Rewriting of Regular Expressions and Regular Path Queries." Journal of Computer and System Sciences 64, no. 3 (2002): 443–65. http://dx.doi.org/10.1006/jcss.2001.1805.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Bosc, Patrick, and Olivier Pivert. "Flexible Queries for Regular Databases." IFAC Proceedings Volumes 31, no. 15 (1998): 619–24. http://dx.doi.org/10.1016/s1474-6670(17)40620-3.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Calvanese, D., G. De Giacomo, M. Lenzerini, and M. Y. Vardi. "Reasoning on regular path queries." ACM SIGMOD Record 32, no. 4 (2003): 83–92. http://dx.doi.org/10.1145/959060.959076.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Reutter, Juan L., Miguel Romero, and Moshe Y. Vardi. "Regular Queries on Graph Databases." Theory of Computing Systems 61, no. 1 (2016): 31–83. http://dx.doi.org/10.1007/s00224-016-9676-2.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Abiteboul, Serge, and Victor Vianu. "Regular Path Queries with Constraints." Journal of Computer and System Sciences 58, no. 3 (1999): 428–52. http://dx.doi.org/10.1006/jcss.1999.1627.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Chauhan, Komal, Kartik Jain, Sayan Ranu, Srikanta Bedathur, and Amitabha Bagchi. "Answering regular path queries through exemplars." Proceedings of the VLDB Endowment 15, no. 2 (2021): 299–311. http://dx.doi.org/10.14778/3489496.3489510.

Full text
Abstract:
Regular simple path query (RPQ) is one of the fundamental operators in graph analytics. In an RPQ, the input is a graph, a source node and a regular expression. The goal is to identify all nodes that are connected to the source through a simple path whose label sequence satisfies the given regular expression. The regular expression acts as a formal specification of the search space that is of interest to the user. Although regular expressions have high expressive power, they act as barrier to non-technical users. Furthermore, to fully realize the power of regular expressions, the user must be familiar with the domain of the graph dataset. In this study, we address this bottleneck by bridging RPQs with the query-by-example paradigm. More specifically, we ask the user for an exemplar pair that characterizes the paths of interest, and the regular expression is automatically inferred from this exemplar. This novel problem introduces several new challenges. How do we infer the regex? Given that answering RPQs is NP-hard, how do we scale to large graphs? We address these challenges through a unique combination of Biermann and Feldman's algorithm with NFA-guided random walks with restarts. Extensive experiments on multiple real, million-scale datasets establish that RQuBE is at least 3 orders of magnitude faster than baseline strategies with an average accuracy in excess of 90%.
APA, Harvard, Vancouver, ISO, and other styles
9

Tetzel, Frank, Wolfgang Lehner, and Romans Kasperovics. "Efficient Compilation of Regular Path Queries." Datenbank-Spektrum 20, no. 3 (2020): 243–59. http://dx.doi.org/10.1007/s13222-020-00353-9.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Grahne, Gösta, and Alex Thomo. "Regular path queries under approximate semantics." Annals of Mathematics and Artificial Intelligence 46, no. 1-2 (2006): 165–90. http://dx.doi.org/10.1007/s10472-005-9016-8.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic "Regular queries"

1

Al, Serhali Antonio. "Earliest Query Answering for Regular Queries with Complete Subhedge Projection." Electronic Thesis or Diss., Université de Lille (2022-....), 2024. http://www.theses.fr/2024ULILB037.

Full text
Abstract:
Les requêtes logiques sont au cœur des bases de données graphes, du traitementd'événements complexes et du traitement de flux Xml. L'efficacité des algorithmesde réponse à ces requêtes est cruciale en pratique, malgré la complexité théoriqueinhérente du problème algorithmique sous-jacent, qui exclut toute solution à la foispleinement générale et efficace.Nous réexaminons le problème de la réponse au plus tôt aux requêtes régulièressur des séquences d'arbres de données, souvent appelées haies. Ce problème a étéétudié pour la première fois par Gauwin et al. en 2011. Leur motivation initiale,qui demeure notre principale application, est de répondre aux requêtes régulièresXPath sur des flux XML avec la latence la plus faible possible. Les réponses auxrequêtes doivent être produites immédiatement dès qu'elles deviennent certaines,indépendamment de la continuation du flux.Gauwin et al. (2011) ont montré que la réponse au plus tôt aux requêtes pourles automates à mots imbriqués déterministes est en temps polynomial. Mal-heureusement, leur algorithme de réponse n'était pas suffisament performant enpratique lorsqu'il était appliqué aux requêtes régulières XPath sur des flux XML :les automates obtenus étaient énormes même pour de petites requêtes XPath, letemps de traitement par événement du flux était trop élevé, et aucune projectiond'événements non pertinents n'était disponible. Par conséquent, les meilleurs outilsactuels pour évaluer les requêtes régulières XPath sur des flux XML - obtenus parSebastian et al. (2015) - reposent sur une approximation des réponses au plus tôtqui évite la nécessité de déterminiser des automates à mots imbriqués.Dans cette thèse, nous montrons que la réponse au plus tôt aux requêtes régulièresXPath est réalisable en pratique. Pour ce faire, nous développons un nouvel algo-rithme pour les automates de haies déterministes pas-à-pas (dShas). Ce modèled'automate plus récent de Sakho et al. (2021) combine de manière naturelle lesautomates à états finis déterministes pour les mots et les arbres. Nous renforçonsnotre algorithme avec une projection complète de sous-haies afin de projeter aumaximum des sous-haies non pertinentes. Nous montrons comment obtenir depetits dShas pour des requêtes régulières XPath extraites de programmes XSLTet XQuery pratiques par Lick et Schmitz, par déterminisation guidée par schéma,développons un algorithme de streaming pour des requêtes monadiques définiespar dSha avec une meilleure complexité dans le pire des cas, et introduisons lespremiers algorithmes complets de projection de sous-haies pour les dShas.Il s'avère que la projection complète de sous-haies rend la réponse au plus tôt avecles dShas compétitive en termes d'efficacité temporelle par rapport aux meilleursoutils de streaming existants pour les requêtes régulières XPath générales, tout enétant plus efficace en mémoire dans les cas où ces outils ne fonctionnent pas au plustôt. Nous croyons que les progrès algorithmiques réalisés sur l'approche au plus tôtsur les flux de données dans la présente thèse permettront finalement d'avoir cettemême approche sur les hyperflux, comme proposé par Sakho et al. (2021)<br>Logical queries are at the core of graph databases, complex event processing, andXML stream processing. The efficiency of query answering algorithms is crucial inpractice, despite the inherent theoretical complexity of the underlying algorithmicproblem, which rules out any solution that is at the same time fully general andefficient.We reconsider the problem of how to answer regular queries on sequences ofdata trees - often called hedges - in an earliest manner. This problem was firststudied by Gauwin et al. in 2011. Their original motivation, and still our mainapplication, is to answer regular XPath queries on XML streams with the lowestpossible latency. Query answers should be output immediately whenever theybecome certain independently of the continuation of the stream.Earliest query answering for deterministic nested word automata was shown tobe in polynomial time by Gauwin et al (2011). Unfortunately, their earliest queryanswering algorithm for was not successful in practice when applied to regularXPath queries on Xml streams: the deterministic nested word automata obtainedwere huge even for small XPath queries, the processing time per event of the streamwas too high, and no projection of irrelevant events was available. Therefore, thebest current tools for evaluating regular XPath queries on XML streams - obtainedby Sebastian et al. (2015) - is based on an approximation of earliest query answeringthat avoids the need to determinize nested word automata.In this thesis, we show that earliest query answering for regular XPath queries isfeasible in practice. For this, we develop a new earliest query answering algorithmfor deterministic stepwise hedge automata (dShas). This more recent automatonmodel from Sakho et al (2021) combines deterministic finite state automata forwords and trees in a natural manner. We enhance our algorithm with completesubhedge projection in order to project irrelevant subhedges maximally. We showhow to obtain small dShas for regular XPath queries harvested from practical XSLTand XQuery programs by Lick and Schmitz by schema-based determinization, de-velop a streaming algorithm for monadic queries defined by dSha with better worstcase complexity, and the first complete subhedge projection algorithms for dShas.It turns out that complete subhedge projection makes earliest query answeringwith dShas competitive in time efficiency with the best existing streaming tools forgeneral regular XPath queries, while being more memory efficient in cases wherethese tools are not earliest. We believe that the algorithmic progress made onearliest query answering on streams in the present thesis will eventually enableearliest query answering on hyperstreams as proposed by Sakho et al. (2021)
APA, Harvard, Vancouver, ISO, and other styles
2

Boher, Genís Pau. "Functional genomics of the periderm: the biosynthetic gene FHT, the transcriptional regulator StRiK and the transcriptome deciphering." Doctoral thesis, Universitat de Girona, 2017. http://hdl.handle.net/10803/403400.

Full text
Abstract:
We have developed new molecular tools to characterize the FHT and StRIK genes in the tuber periderm. Regarding FHT gene, our results demonstrated that is induced very specifically in suberizing tissues what makes FHT a good marker of the suberization process. Regarding StRIK gene, it has been shown to be a good candidate for the periderm regulation since its silencing causes changes in genes expression related to the transposition of DNA, RNA processing and stress. Finally, by RNA-seq we have identified a wide range of new candidate genes for the formation of the cork oak periderm. Among these genes several are related to the formation of the cell wall, cell primary metabolism and suberin accumulation. Other relevant genes are those involved in the regulation of meristem such as auxin transporters and the ethylene metabolism and signaling. The expression patterns of some genes have been studied during the cork growing season.<br>Hem desenvolupat noves eines moleculars per a la caracterització dels gens FHT i StRIK en el peridermis del tubercle. Els nostres resultats mostren que FHT s’indueix de forma molt específica en teixits suberificats el que el fa un bon marcador del procés de suberificació. En relació al gen StRIK, hem vist que es un bon candidat a la regulació de la peridermis ja que el seu silenciament provoca canvis d’expressió en gens relacionats amb la transposició de l’ADN, el processament de l’RNA i l’estrès. Mitjançant RNA-seq hem identificat nous gens candidats per la formació de la peridermis en l’alzina surera, entre ells destaquen gens relacionats amb la formació de la paret cel·lular, el metabolisme primari i l’acumulació de suberina. També destaquen gens relacionats amb la regulació del meristema com ara els transportadors d’auxines i el metabolisme i senyalització per etilè. L’expressió d’alguns gens s’ha analitzat durant la formació del suro.
APA, Harvard, Vancouver, ISO, and other styles
3

Shoaran, Maryam. "Distributed multi-source regular path queries." Thesis, 2007. http://hdl.handle.net/1828/2471.

Full text
Abstract:
Regular path queries are the building block of almost any mechanism for querying semistructured data. Despite the fact that the main applications of such data are distributed, there are only few works dealing with distributed evaluation of regular path queries. In this thesis we present a message-efficient and truly distributed algorithm for computing the answer to regular path queries in a multi-source semistructured database setting. Our algorithm has several desirable properties. First, it is general as it works for the larger class of weighted regular path queries on weighted semistructured databases. Second, it performs a progressive evaluation, that is, partial answers can be represented to the user as soon as they are computed while she is waiting for new answers to arrive. Third, the proposed algorithm is symmetric among processes, i.e., they all run the same algorithm. And finally, it does not need a separate termination detection algorithm as it can detect the global termination simply by using an spanning tree.
APA, Harvard, Vancouver, ISO, and other styles
4

Miao, Zhuo. "Grid-aware evaluation of regular path queries on large Spatial networks." Thesis, 2007. http://hdl.handle.net/1828/192.

Full text
Abstract:
Regular path queries (RPQs), expressed as regular expressions over the alphabet of database edge-labels, are commonly used for guided navigation of graph databases. RPQs are the basic building block of almost all the query languages for graph databases, providing the user with a nice and simple way to express recursion. While convenient to use, RPQs are notorious for their high computational demand. Except for few theoretical works, there has been little work evaluating RPQs on databases of great practical interest, such as large spatial networks. In this thesis, we present a grid-aware, fault tolerant distributed algorithm for answering RPQs on spatial networks. We engineer each part of the algorithm to account for the assumed computational-grid setting. We experimentally evaluate our algorithm, and show that for typical user queries, our algorithm satisfies the desiderata for distributed computing in general, and computational-grids in particular.
APA, Harvard, Vancouver, ISO, and other styles
5

Tamashiro, Manuel. "Towards practically feasible answering of regular path queries in LAV data integration." Thesis, 2007. http://hdl.handle.net/1828/129.

Full text
Abstract:
Regular path queries (RPQ’s) are given by means of regular expressions and ask for matching patterns on labeled graphs. RPQ’s have recently received great attention in the context of semistructured data, which are data whose structure is irregular, partially known, or subject to frequent changes. One of the most important problems in databases today is the integration of semistructured data from multiple sources modeled as views. In this setting, the database is not available, and given a user query, the system has to answer based solely on the information provided by the views. The problem is computationally hard, and the well-known algorithm for solving it runs in 2EXPTIME. In this paper, we provide practical evidence that this algorithm performs poorly on the average as well. Then, we propose automata- theoretic techniques which make the view-based answering of RPQ’s more feasible in practice.
APA, Harvard, Vancouver, ISO, and other styles
6

Wen-GanLi and 李文淦. "FulDex: A Fully-Indexing-Enabled Memory Representation Model for Supporting XML Regular Expression Queries." Thesis, 2015. http://ndltd.ncl.edu.tw/handle/43178941967819820797.

Full text
Abstract:
碩士<br>國立成功大學<br>資訊工程學系<br>103<br>XML has been widely used in the field of service computing because of its simplicity, generality and usability. In general, there are two phases in processing an XML document: parsing the XML document and querying over the XML document. However, querying over XML documents with regular expressions is a time intensive process. Although efforts have been made on optimizing regular expression string matchings and XML queries based on database, little emphasis has been put on optimizing XML regular expression queries based on memory representations. In this work, we present a fully-indexing-enabled memory representation, called FulDex, for supporting efficient XML regular expression queries. The key feature of the model is providing an index table for indexing all characters of elements and attributes inside a document so as to decrease the number of candidates that need to be matched with a regular expression query. The experimental results show that the average execution time of FulDex is superior to the one of the other 7 tools with 94% cases; and the average execution time of FulDex for a regular expression query over a large XML document (1.58GB) is 93.05% less than the one of RapidXML.
APA, Harvard, Vancouver, ISO, and other styles
7

Shoaran, Maryam. "Automata methods and techniques for graph-structured data." Thesis, 2011. http://hdl.handle.net/1828/3249.

Full text
Abstract:
Graph-structured data (GSD) is a popular model to represent complex information in a wide variety of applications such as social networks, biological data management, digital libraries, and traffic networks. The flexibility of this model allows the information to evolve and easily integrate with heterogeneous data from many sources. In this dissertation we study three important problems on GSD. A consistent theme of our work is the use of automata methods and techniques to process and reason about GSD. First, we address the problem of answering queries on GSD in a distributed environment. We focus on regular path queries (RPQs) – given by regular expressions matching paths in graph-data. RPQs are the building blocks of almost any mechanism for querying GSD. We present a fault-tolerant, message-efficient, and truly distributed algorithm for answering RPQs. Our algorithm works for the larger class of weighted RPQs on weighted GSDs. Second, we consider the problem of answering RPQs on incomplete GSD, where different data sources are represented by materialized database views. We explore the connection between “certain answers” (CAs) and answers obtained from “view-based rewritings” (VBRs) for RPQs. CAs are answers that can be obtained on each database consistent with the views. Computing all of CAs for RPQs is NP-hard, and one has to resort to an exponential algorithm in the size of the data–view materializations. On the other hand, VBRs are query reformulations in terms of the view definitions. They can be used to obtain query answers in polynomial time in the size of the data. These answers are CAs, but unfortunately for RPQs, not all of the CAs can be obtained in this way. In this work, we show the surprising result that for RPQs under local semantics, using VBRs to answer RPQs gives all the CAs. The importance of this result is that under such semantics, the CAs can be obtained in polynomial time in the size of the data. Third, we focus on XML–an important special case of GSD. The scenario we consider is streaming XML between exchanging parties. The problem we study is flexible validation of streaming XML under the realistic assumption that the schemas of the exchanging parties evolve, and thus diverge from one another. We represent schemas by using Visibly Pushdown Automata (VPAs), which recognize Visibly Pushdown Languages (VPLs). We model evolution for XML by defining formal language operators on VPLs. We show that VPLs are closed under the defined language operators and this enables us to expand the schemas (for XML) in order to account for flexible or constrained evolution.<br>Graduate
APA, Harvard, Vancouver, ISO, and other styles

Books on the topic "Regular queries"

1

Brocki, Marcin, Małgorzata Maj, and Stanisława Trebunia-Staszel, eds. Anthropology and Ethnology During World War II. The Activity of Sektion Rassen- und Volkstumsforschung Institut für Deutsche Ostarbeit in the Light of New Source Materials. Wydawnictwo Uniwersytetu Jagiellońskiego, 2019. http://dx.doi.org/10.4467/k9915.19/19.19.15528.

Full text
Abstract:
After reading this voluminous and, contrary to what the title might suggest, engaging study, I have no doubt that it is a great scientific achievement. Firstly, the authors managed to develop an approach to the otherwise sensitive subject of the IDO heritage that enables a cool, albeit not entirely distanced way of looking at the history of a certain institution, as well as at the entanglement of many people in its activity. The fact that the institution was established in dark times, and, in addition, by Hans Frank, should not a priori put it in the context of regular Nazi propaganda and degenerated science. The authors managed to separate what in the IDO output was based on objective research from what could never be defined as scientific. Secondly, the high level of competence of the papers in this tome makes one confident about the applied methods of presentation and interpretation of the available material, which, moreover, is still subject to further verification. This publication is not yet the final outcome of several years of research and queries, but a stop-over, an important one, on the way to further work, which is signaled throughout the book. So it is an example of work in progress. Prof. dr hab. Wojciech Józef Burszta
APA, Harvard, Vancouver, ISO, and other styles
2

The Rector of Dr---r's case concerning the power of suspension from the sacrament stated: In a letter from his friend : wherein the three following queries are briefly examined, and modestly resolved, viz. I. Whether a rector hath power to suspend any of the parishioners committed to his charge, from a temporary reception of the sacrament?, and in what cases he may exercise that power?, II. What is the bishops office in such a case?, and whether he may restore such persons so suspended, without a judicial cognizance of the crime objected?, III. Whether in such a case the bishop may regularly command the rector, and whether such commands are obliging? Printed for Edward Mory ... and sold by M. Gunne ..., 1985.

Find full text
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Regular queries"

1

Liu, Yanhong A., and Fuxiang Yu. "Solving Regular Path Queries." In Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2002. http://dx.doi.org/10.1007/3-540-45442-x_12.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

de Moor, Oege, David Lacey, and Eric Van Wyk. "Universal Regular Path Queries." In Automatic Program Development. Springer Netherlands, 2008. http://dx.doi.org/10.1007/978-1-4020-6585-9_11.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Grahne, Gösta, Alex Thomo, and William Wadge. "Preferentially Annotated Regular Path Queries." In Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2006. http://dx.doi.org/10.1007/11965893_22.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Ferretti, Claudio, and Giancarlo Mauri. "Identifying unrecognizable regular languages by queries." In Machine Learning: ECML-94. Springer Berlin Heidelberg, 1994. http://dx.doi.org/10.1007/3-540-57868-4_72.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Koschmieder, André, and Ulf Leser. "Regular Path Queries on Large Graphs." In Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2012. http://dx.doi.org/10.1007/978-3-642-31235-9_12.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Bosc, Patrick, and Olivier Pivert. "Fuzzy Queries Against Regular and Fuzzy Databases." In Flexible Query Answering Systems. Springer US, 1997. http://dx.doi.org/10.1007/978-1-4615-6075-3_10.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Stefanescu, Dan, and Alex Thomo. "Enhanced Regular Path Queries on Semistructured Databases." In Current Trends in Database Technology – EDBT 2006. Springer Berlin Heidelberg, 2006. http://dx.doi.org/10.1007/11896548_53.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Flesca, Sergio, and Sergio Greco. "Partially Ordered Regular Languages for Graph Queries." In Automata, Languages and Programming. Springer Berlin Heidelberg, 1999. http://dx.doi.org/10.1007/3-540-48523-6_29.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Grahne, Gösta, and Alex Thomo. "Algebraic Rewritings for Optimizing Regular Path Queries." In Database Theory — ICDT 2001. Springer Berlin Heidelberg, 2001. http://dx.doi.org/10.1007/3-540-44503-x_19.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Mazowiecki, Filip, Filip Murlak, and Adam Witkowski. "Monadic Datalog and Regular Tree Pattern Queries." In Mathematical Foundations of Computer Science 2014. Springer Berlin Heidelberg, 2014. http://dx.doi.org/10.1007/978-3-662-44522-8_36.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Regular queries"

1

Figueira, Diego, S. Krishna, Om Swostik Mishra, and Anantha Padmanabha. "Boundedness for Unions of Conjunctive Regular Path Queries over Simple Regular Expressions." In 21st International Conference on Principles of Knowledge Representation and Reasoning {KR-2023}. International Joint Conferences on Artificial Intelligence Organization, 2024. http://dx.doi.org/10.24963/kr.2024/34.

Full text
Abstract:
The problem of whether a recursive query can be rewritten as query without recursion is a fundamental reasoning task, known as the boundedness problem. Here we study the boundedness problem for Unions of Conjunctive Regular Path Queries (UCRPQs), a navigational query language extensively used in ontology and graph database querying. The boundedness problem for UCRPQs is known to be decidable, ExpSpace-complete. Here we focus our analysis on UCRPQs using simple regular expressions, which are of high practical relevance and enjoy a lower reasoning complexity. We show that the complexity for the boundedness problem for this UCRPQs fragment is Pi-p-2-complete, and that an equivalent bounded query can be produced in polynomial time whenever possible. When the query turns out to be unbounded, we also study the task of finding an equivalent maximally bounded query, which we show to be feasible in Pi-p-2 . As a side result of independent interest stemming from our developments, we study a notion of succinct finite automata and prove that its membership problem is NP-complete.
APA, Harvard, Vancouver, ISO, and other styles
2

Ostropolski-Nalewaja, Piotr, and Sebastian Rudolph. "The Sticky Path to Expressive Querying: Decidability of Navigational Queries under Existential Rules." In 21st International Conference on Principles of Knowledge Representation and Reasoning {KR-2023}. International Joint Conferences on Artificial Intelligence Organization, 2024. http://dx.doi.org/10.24963/kr.2024/54.

Full text
Abstract:
Extensive research in the field of ontology-based query answering has led to the identification of numerous fragments of existential rules (also known as tuple-generating dependencies) that exhibit decidable answering of atomic and conjunctive queries. Motivated by the increased theoretical and practical interest in navigational queries, this paper considers the question for which of these fragments decidability of querying extends to regular path queries (RPQs). In fact, decidability of RPQs has recently been shown to generally hold for the comprehensive family of all fragments that come with the guarantee of universal models being reasonably well-shaped (that is, being of finite cliquewidth). Yet, for the second major family of fragments, known as finite unification sets (short: fus), which are based on first-order-rewritability, corresponding results have been largely elusive so far. We complete the picture by showing that RPQ answering over arbitrary fus rulesets is undecidable. On the positive side, we establish that the problem is decidable for the prominent fus subclass of sticky rulesets, with the caveat that a very mild extension of the RPQ formalism turns the problem undecidable again.
APA, Harvard, Vancouver, ISO, and other styles
3

Liu, Yanhong A., Tom Rothamel, Fuxiang Yu, Scott D. Stoller, and Nanjun Hu. "Parametric regular path queries." In the ACM SIGPLAN 2004 conference. ACM Press, 2004. http://dx.doi.org/10.1145/996841.996868.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Arenas, Marcelo, Pedro Bahamondes, Amir Aghasadeghi, and Julia Stoyanovich. "Temporal Regular Path Queries." In 2022 IEEE 38th International Conference on Data Engineering (ICDE). IEEE, 2022. http://dx.doi.org/10.1109/icde53745.2022.00226.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Calvanese, Diego, Giuseppe De Giacomo, Maurizio Lenzerini, and Moshe Y. Vardi. "Rewriting of regular expressions and regular path queries." In the eighteenth ACM SIGMOD-SIGACT-SIGART symposium. ACM Press, 1999. http://dx.doi.org/10.1145/303976.303996.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Vardi, Moshe Y. "A Theory of Regular Queries." In SIGMOD/PODS'16: International Conference on Management of Data. ACM, 2016. http://dx.doi.org/10.1145/2902251.2902305.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Abiteboul, Serge, and Victor Vianu. "Regular path queries with constraints." In the sixteenth ACM SIGACT-SIGMOD-SIGART symposium. ACM Press, 1997. http://dx.doi.org/10.1145/263661.263676.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Figueira, Diego, Adwait Godbole, S. Krishna, Wim Martens, Matthias Niewerth, and Tina Trautner. "Containment of Simple Conjunctive Regular Path Queries." In 17th International Conference on Principles of Knowledge Representation and Reasoning {KR-2020}. International Joint Conferences on Artificial Intelligence Organization, 2020. http://dx.doi.org/10.24963/kr.2020/38.

Full text
Abstract:
Testing containment of queries is a fundamental reasoning task in knowledge representation. We study here the containment problem for Conjunctive Regular Path Queries (CRPQs), a navigational query language extensively used in ontology and graph database querying. While it is known that containment of CRPQs is EXPSPACE-complete in general, we focus here on severely restricted fragments, which are known to be highly relevant in practice according to several recent studies. We obtain a detailed overview of the complexity of the containment problem, depending on the features used in the regular expressions of the queries, with completeness results for NP, Pi2p, PSPACE or EXPSPACE.
APA, Harvard, Vancouver, ISO, and other styles
9

Nolé, Maurizio, and Carlo Sartiani. "Regular Path Queries on Massive Graphs." In SSDBM '16: Conference on Scientific and Statistical Database Management. ACM, 2016. http://dx.doi.org/10.1145/2949689.2949711.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Tetzel, Frank, Romans Kasperovics, and Wolfgang Lehner. "Graph Traversals for Regular Path Queries." In the 2nd Joint International Workshop. ACM Press, 2019. http://dx.doi.org/10.1145/3327964.3328494.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Reports on the topic "Regular queries"

1

Gil, Oliver Fernández, and Anni-Yasmin Turhan. Answering Regular Path Queries Under Approximate Semantics in Lightweight Description Logics. Technische Universität Dresden, 2020. http://dx.doi.org/10.25368/2022.261.

Full text
Abstract:
Classical regular path queries (RPQs) can be too restrictive for some applications and answering such queries under approximate semantics to relax the query is desirable. While for answering regular path queries over graph databases under approximate semantics algorithms are available, such algorithms are scarce for the ontology-mediated setting. In this paper we extend an approach for answering RPQs over graph databases that uses weighted transducers to approximate paths from the query in two ways. The first extension is to answering approximate conjunctive 2-way regular path queries (C2RPQs) over graph databases and the second is to answering C2RPQs over ELH and DL-LiteR ontologies. We provide results on the computational complexity of the underlying reasoning problems and devise approximate query answering algorithms.
APA, Harvard, Vancouver, ISO, and other styles
2

Baader, Franz, and Francesco Kriegel. Pushing Optimal ABox Repair from EL Towards More Expressive Horn-DLs: Extended Version. Technische Universität Dresden, 2022. http://dx.doi.org/10.25368/2022.131.

Full text
Abstract:
Ontologies based on Description Logic (DL) represent general background knowledge in a terminology (TBox) and the actual data in an ABox. DL systems can then be used to compute consequences (such as answers to certain queries) from an ontology consisting of a TBox and an ABox. Since both human-made and machine-learned data sets may contain errors, which manifest themselves as unintuitive or obviously incorrect consequences, repairing DL-based ontologies in the sense of removing such unwanted consequences is an important topic in DL research. Most of the repair approaches described in the literature produce repairs that are not optimal, in the sense that they do not guarantee that only a minimal set of consequences is removed. In a series of papers, we have developed an approach for computing optimal repairs, starting with the restricted setting of an EL instance store, extending this to the more general setting of a quantified ABox (where some individuals may be anonymous), and then adding a static EL TBox. Here, we extend the expressivity of the underlying DL considerably, by adding nominals, inverse roles, regular role inclusions and the bottom concept to EL, which yields a fragment of the well-known DL Horn-SROIQ. The ideas underlying our repair approach still apply to this DL, though several non-trivial extensions are needed to deal with the new constructors and axioms. The developed repair approach can also be used to treat unwanted consequences expressed by certain conjunctive queries or regular path queries, and to handle Horn-ALCOI TBoxes with regular role inclusions.
APA, Harvard, Vancouver, ISO, and other styles
3

Borgwardt, Stefan, Walter Forkel, and Alisa Kovtunova. Finding New Diamonds: Temporal Minimal-World Query Answering over Sparse ABoxes. Technische Universität Dresden, 2019. http://dx.doi.org/10.25368/2023.223.

Full text
Abstract:
Lightweight temporal ontology languages have become a very active field of research in recent years. Many real-world applications, like processing electronic health records (EHRs), inherently contain a temporal dimension, and require efficient reasoning algorithms. Moreover, since medical data is not recorded on a regular basis, reasoners must deal with sparse data with potentially large temporal gaps. In this paper, we introduce a temporal extension of the tractable language ELH⊥, which features a new class of convex diamond operators that can be used to bridge temporal gaps. We develop a completion algorithm for our logic, which shows that entailment remains tractable. Based on this, we develop a minimal-world semantics for answering metric temporal conjunctive queries with negation. We show that query answering is combined first-order rewritable, and hence in polynomial time in data complexity.
APA, Harvard, Vancouver, ISO, and other styles
4

Mashingia, Jane, S. Maboko, P. I. Mbwiri, et al. Joint Medicines Regulatory Procedure in the East African Community: Registration Timelines and Way Forward. Purdue University, 2021. http://dx.doi.org/10.5703/1288284317429.

Full text
Abstract:
A review of the East African Community (EAC) joint regulatory review process was conducted, registration timelines analyzed and key milestones, challenges and opportunities documented for the period of July 2015 to January 2020. A total of 113 applications were submitted for joint scientific review. Among these, 109 applications were assessed, 57 were recommended for marketing authorisation, 52 applications had queries to applicants and four applications were under review. A total median approval time for all products ranged from 53 to 102 days. The maximum time taken by a regulator to review the dossier was 391 days and the minimum time was 44 days. For applicants, the maximum time to respond to queries was 927 days and the minimum time was nine days. The total median time for granting marketing authorisation by the National Medicines Regulatory Authorities (NMRA) decreased from 174 to 39 working days in 2015 and 2019 respectively. However, not all EAC NMRA has granted marketing authorisation to all 57 products due to non-payment of applicable fees by applicants. Long regulatory approval timelines were contributed by limited capacity for timely scientific review of dossier by some NMRA, lack of online portal to share dossiersand assessment reports, delay in responding to queries by applicants and deficiencies in dossier. The metric tool and register of medical products submitted for joint scientific review had incomplete data. Challenges were identified and actions recommended to ensure regional regulatory system optimization, efficiency, transparency, sustainability and accountability.
APA, Harvard, Vancouver, ISO, and other styles
5

Rosato-Scott, Claire, Dani J. Barrington, Amita Bhakta, Sarah J. House, Islay Mactaggart, and Jane Wilbur. Como falar sobre incontinência: Uma lista de controlo. The Sanitation Learning Hub, Institute of Development Studies, 2020. http://dx.doi.org/10.19088/slh.2020.009.

Full text
Abstract:
Incontinência é o termo médico usado para descrever as perdas involuntárias de urina ou de fezes. Mulheres, homens, raparigas, rapazes e pessoas de todos os sexos e em qualquer idade podem ter incontinência. Uma pessoa com incontinência pode ter perdas de urina ou de fezes esporádicas, regulares ou constantes; e essas perdas podem dar-se a qualquer hora, dia ou noite. Uma pessoa também pode ter perdas de matéria fecal ou urinária por não conseguir chegar a tempo à casa de banho ou por não querer usar as instalações sanitárias disponíveis. Chama-se a esse tipo de incontinência «incontinência social» ou «funcional». Em muitos Países de Baixo e Médio Rendimento (PBMR), o conhecimento da incontinência está ainda na sua fase inicial: o termo «incontinência» pode ser desconhecido, o conhecimento deste estado clínico é raro e há falta de apoio. As pessoas que têm incontinência podem ser estigmatizadas por causa disso, o que pode afectar a sua vontade ou confiança para falar sobre esta questão. É preciso compreender melhor a incontinência nos PBMR e qual a melhor forma de apoiar as pessoas que vivem com ela, para melhorar a sua qualidade de vida. Isto exige conversar com indivíduos que têm incontinência e com quem cuida deles: essas pessoas têm a experiência concreta do que significa viver com a incontinência do ponto de vista prático, emocional e social, para elas próprias e para as suas famílias. A incontinência pode ter uma série de impactos sobre as pessoas que vivem com ela e sobre os seus cuidadores. Estes impactos são o aumento do stress e da angústia; maior necessidade de água e sabão; e pouca capacidade de participar em actividades comunitárias, escolares ou laborais. Viver com incontinência também pode levar a uma série de questões de protecção. Os desafios que as pessoas podem enfrentam são bastante diversos e podem variar de pessoa para pessoa e de lar para lar. A lista de controlo que se segue e as respectivas referências às páginas de “Precisamos de falar sobre incontinência” podem ser usadas para aumentar os seus conhecimentos sobre incontinência e sobre as opções disponíveis para apoiar as pessoas que vivem com ela, e dar orientações sobre como ter conversas para compreender a melhor maneira de apoiar as pessoas que vivem com incontinência na sua zona.
APA, Harvard, Vancouver, ISO, and other styles
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography