Log in

Relevant bibliographies by topics / Regular queries / Journal articles

To see the other types of publications on this topic, follow the link: Regular queries.

Journal articles 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 top 50 journal articles for your research 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.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Grahne, Gösta, Alex Thomo, and William W. Wadge. "Preferential Regular Path Queries." Fundamenta Informaticae 89, no. 2-3 (January 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 (June 9, 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 (May 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 (June 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 (December 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 (April 16, 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 (June 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 (October 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 (September 9, 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 (February 2006): 165–90. http://dx.doi.org/10.1007/s10472-005-9016-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

Zhang, Ling, Shaleen Deep, Avrilia Floratou, Anja Gruenheid, Jignesh M. Patel, and Yiwen Zhu. "Exploiting Structure in Regular Expression Queries." Proceedings of the ACM on Management of Data 1, no. 2 (June 13, 2023): 1–28. http://dx.doi.org/10.1145/3589297.

Full text

Abstract:

Regular expression, or regex, is widely used to extract critical information from a large corpus of formatted text by finding patterns of interest. In tasks like log processing, the speed of regex matching is crucial. Data scientists and developers regularly use regex libraries that implement optimized regular expression matching using modern automata theory. However, computing state transitions in the underlying regex evaluation engine can be inefficient when a regex query contains a multitude of string literals. This inefficiency is further exasperated when analyzing large data volumes. This paper presents BLARE, Blazingly Fast Regular Expression, a regular expression matching framework that is inspired by the mechanisms that are used in database engines, which use a declarative framework to explore multiple equivalent execution plans, all of which produce the correct final result. Similarly, BLARE decomposes a regex into multiple regex and string components and then creates evaluation strategies in which the components can be evaluated in an order that is not strictly a left-to-right translation of the input regex query. Rather than using a cost-based optimization approach, BLARE uses an adaptive runtime strategy based on a multi-armed bandit approach to find an efficient execution plan. BLARE is also modular and can be built on top of any existing regex library. We implemented BLARE on four commonly used regex libraries, RE2, PCRE2, Boost Regex, and ICU Regex, and evaluated it using two production workloads and one open-source workload. BLARE was 1.6× to 3.7× faster than RE2 and 3.4× to 7.9× faster than Boost Regex. PCRE2 did not finish on one of the workloads, but on the remaining two workloads, BLARE improved the performance of PCRE2 by 3.1× to over 100×. For the open-source dataset, BLARE provided a speed up of 61.7× for ICU Regex. BLARE code is publicly available at https://github.com/mush-zhang/Blare.

APA, Harvard, Vancouver, ISO, and other styles

12

Bienvenu, Meghyn, Magdalena Ortiz, and Mantas Simkus. "Regular Path Queries in Lightweight Description Logics: Complexity and Algorithms." Journal of Artificial Intelligence Research 53 (July 22, 2015): 315–74. http://dx.doi.org/10.1613/jair.4577.

Full text

Abstract:

Conjunctive regular path queries are an expressive extension of the well-known class of conjunctive queries. Such queries have been extensively studied in the (graph) database community, since they support a controlled form of recursion and enable sophisticated path navigation. Somewhat surprisingly, there has been little work aimed at using such queries in the context of description logic (DL) knowledge bases, particularly for the lightweight DLs that are considered best suited for data-intensive applications. This paper aims to bridge this gap by providing algorithms and tight complexity bounds for answering two-way conjunctive regular path queries over DL knowledge bases formulated in lightweight DLs of the DL-Lite and EL families. Our results demonstrate that in data complexity, the cost of moving to this richer query language is as low as one could wish for: the problem is NL-complete for DL-Lite and P-complete for EL. The combined complexity of query answering increases from NP- to PSpace-complete, but for two-way regular path queries (without conjunction), we show that query answering is tractable even with respect to combined complexity. Our results reveal two-way conjunctive regular path queries as a promising language for querying data enriched by ontologies formulated in DLs of the DL-Lite and EL families or the corresponding OWL 2 QL and EL profiles.

APA, Harvard, Vancouver, ISO, and other styles

13

Fernández Gil, Oliver, and Anni-Yasmin Turhan. "Answering Regular Path Queries Under Approximate Semantics in Lightweight Description Logics." Proceedings of the AAAI Conference on Artificial Intelligence 35, no. 7 (May 18, 2021): 6340–48. http://dx.doi.org/10.1609/aaai.v35i7.16787.

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-Lite_R 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

14

Niehren, Joachim, Sylvain Salvati, and Rustam Azimov. "Jumping Evaluation of Nested Regular Path Queries." Electronic Proceedings in Theoretical Computer Science 364 (August 4, 2022): 79–92. http://dx.doi.org/10.4204/eptcs.364.8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

Mazowiecki, Filip, Filip Murlak, and Adam Witkowski. "Monadic Datalog and Regular Tree Pattern Queries." ACM Transactions on Database Systems 41, no. 3 (August 8, 2016): 1–43. http://dx.doi.org/10.1145/2925986.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

Martens, Wim, and Tina Trautner. "Dichotomies for Evaluating Simple Regular Path Queries." ACM Transactions on Database Systems 44, no. 4 (December 17, 2019): 1–46. http://dx.doi.org/10.1145/3331446.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

Grahne, Gösta, and Alex Thomo. "Algebraic rewritings for optimizing regular path queries." Theoretical Computer Science 296, no. 3 (March 2003): 453–71. http://dx.doi.org/10.1016/s0304-3975(02)00739-9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

Flesca, Sergio, and Sergio Greco. "Partially ordered regular languages for graph queries." Journal of Computer and System Sciences 70, no. 1 (February 2005): 1–25. http://dx.doi.org/10.1016/j.jcss.2003.04.003.

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

Angluin, Dana. "Learning regular sets from queries and counterexamples." Information and Computation 75, no. 2 (November 1987): 87–106. http://dx.doi.org/10.1016/0890-5401(87)90052-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

BONIFATI, ANGELA, STEFANIA DUMBRAVA, and EMILIO JESÚS GALLEGO ARIAS. "Certified Graph View Maintenance with Regular Datalog." Theory and Practice of Logic Programming 18, no. 3-4 (July 2018): 372–89. http://dx.doi.org/10.1017/s1471068418000224.

Full text

Abstract:

AbstractWe employ the Coq proof assistant to develop a mechanically-certified framework for evaluating graph queries and incrementally maintaining materialized graph instances, also called views. The language we use for defining queries and views is Regular Datalog (RD) – a notable fragment of non-recursive Datalog that can express complex navigational queries, with transitive closure as native operator. We first design and encode the theory of RD and then mechanize a RD-specific evaluation algorithm capable of fine-grained, incremental graph view computation, which we prove sound with respect to the declarative RD semantics. By using the Coq extraction mechanism, we test an OCaml version of the verified engine on a set of preliminary benchmarks. Our development is particularly focused on leveraging existing verification and notational techniques to: a) define mechanized properties that can be easily understood by logicians and database researchers and b) attain formal verification with limited effort. Our work is the first step towards a unified, machine-verified, formal framework for dynamic graph query languages and their evaluation engines.

APA, Harvard, Vancouver, ISO, and other styles

21

Shoaran, Maryam, and Alex Thomo. "Fault-tolerant computation of distributed regular path queries." Theoretical Computer Science 410, no. 1 (January 2009): 62–77. http://dx.doi.org/10.1016/j.tcs.2008.09.061.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

Klassen, R. K., and I. A. Kazantsev. "AUTOMATICAL PRETRANSLATION OF SQL-QUERIES TO A REGULAR PLAN IN CLUSTERIX-LIKE DBMS." Vestnik komp'iuternykh i informatsionnykh tekhnologii, no. 196 (October 2020): 11–20. http://dx.doi.org/10.14489/vkit.2020.10.pp.011-020.

Full text

Abstract:

Previously completed designs for pretranslating SQL queries did not bring significant success. Nevertheless, such a pretranslator is necessary for the possibility of using Clusterix-like database management systems (DBMSs) by a wide circle of specialists. The article proposes an original approach to pretranslating SQL queries without writing operations to the regular plan for Clusterix-like DBMSs. The possibility of implementing such a pretranslator is discussed. The concepts of a hard and a simple SQL query are given. The basis of the pretranslator is a library for parsing arbitrary grammars antlr4, which is used to build a SQL query tree. A software-implemented pretranslator uses it to build queries that meet the regular plan.

APA, Harvard, Vancouver, ISO, and other styles

23

Klassen, R. K., and I. A. Kazantsev. "AUTOMATICAL PRETRANSLATION OF SQL-QUERIES TO A REGULAR PLAN IN CLUSTERIX-LIKE DBMS." Vestnik komp'iuternykh i informatsionnykh tekhnologii, no. 196 (October 2020): 11–20. http://dx.doi.org/10.14489/vkit.2020.10.pp.011-020.

Full text

Abstract:

Previously completed designs for pretranslating SQL queries did not bring significant success. Nevertheless, such a pretranslator is necessary for the possibility of using Clusterix-like database management systems (DBMSs) by a wide circle of specialists. The article proposes an original approach to pretranslating SQL queries without writing operations to the regular plan for Clusterix-like DBMSs. The possibility of implementing such a pretranslator is discussed. The concepts of a hard and a simple SQL query are given. The basis of the pretranslator is a library for parsing arbitrary grammars antlr4, which is used to build a SQL query tree. A software-implemented pretranslator uses it to build queries that meet the regular plan.

APA, Harvard, Vancouver, ISO, and other styles

24

Dimartino, Mirko M., Peter T. Wood, Andrea Cali, and Alexandra Poulovassilis. "Efficient Ontology-Mediated Query Answering: Extending DL-liteR and Linear ELH." Journal of Artificial Intelligence Research 82 (February 11, 2025): 851–99. https://doi.org/10.1613/jair.1.16401.

Full text

Abstract:

The OWL 2 QL profile of the OWL 2 Web Ontology Language, based on the family of description logics called DL-Lite, is designed so that data stored in a standard relational database system (RDBMS) can be queried through an ontology via a rewriting mechanism, i.e., by rewriting the query into an SQL query that is then answered by the RDBMS system, without any changes to the data. In this paper we propose a language whose expressive power goes beyond that of DL-Lite while still allowing query answering via rewriting of queries into unions of conjunctive two-way regular path queries (UC2RPQs) instead of SQL queries. Our language is an extension of both OWL 2 QL and linear ELH: OWL 2 QL is extended by allowing qualified existential quantification on the left-hand side of concept inclusion axioms, and linear ELH by allowing inverses in role inclusion axioms. We identify a syntactic property of the extended language that guarantees UC2RPQ-rewritability. We propose a novel rewriting technique for conjunctive queries (CQs) under our ontology language that makes use of nondeterministic finite state automata. We show that CQ answering in our setting is NLOGSPACE-complete with respect to data complexity and NP-complete for combined complexity; we also show that answering instance queries is NLOGSPACE-complete for data complexity and in PTIME for combined complexity.

APA, Harvard, Vancouver, ISO, and other styles

25

Guo, Xintong, Hong Gao, and Zhaonian Zou. "Distributed processing of regular path queries in RDF graphs." Knowledge and Information Systems 63, no. 4 (January 13, 2021): 993–1027. http://dx.doi.org/10.1007/s10115-020-01536-2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Lee, Jinsoo, Minh-Duc Pham, Jihwan Lee, Wook-Shin Han, Hune Cho, Hwanjo Yu, and Jeong-Hoon Lee. "Processing SPARQL queries with regular expressions in RDF databases." BMC Bioinformatics 12, Suppl 2 (2011): S6. http://dx.doi.org/10.1186/1471-2105-12-s2-s6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

Liang, Qi, Dian Ouyang, Fan Zhang, Jianye Yang, Xuemin Lin, and Zhihong Tian. "Efficient Regular Simple Path Queries under Transitive Restricted Expressions." Proceedings of the VLDB Endowment 17, no. 7 (March 2024): 1710–22. http://dx.doi.org/10.14778/3654621.3654636.

Full text

Abstract:

There are two fundamental problems in regular simple path queries (RSPQs). One is the reachability problem which asks whether there exists a simple path between the source and the target vertex matching the given regular expression, and the other is the enumeration problem which aims to find all the matched simple paths. As an important computing component of graph databases, RSPQs are supported in many graph database query languages such as PGQL and openCypher. However, answering RSPQs is known to be NP-hard, making it challenging to design scalable solutions to support a wide range of expressions. In this paper, we first introduce the class of transitive restricted expression , which covers more than 99% of real-world queries. Then, we propose an efficient algorithm framework to support both reachability and enumeration problems under transitive restricted expression constraints. To boost the performance, we develop novel techniques for reachability detection, the search of candidate vertices, and the reduction of redundant path computation. Extensive experiments demonstrate that our exact method can achieve comparable efficiency to the state-of-the-art approximate approach, and outperforms the state-of-the-art exact methods by up to 2 orders of magnitude.

APA, Harvard, Vancouver, ISO, and other styles

28

Fan, Wenfei, Jianzhong Li, Shuai Ma, Nan Tang, and Yinghui Wu. "Adding regular expressions to graph reachability and pattern queries." Frontiers of Computer Science 6, no. 3 (June 2012): 313–38. http://dx.doi.org/10.1007/s11704-012-1312-y.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

Grahne, Gösta, and Alex Thomo. "Bounded regular path queries in view-based data integration." Information Processing Letters 109, no. 13 (June 2009): 739–44. http://dx.doi.org/10.1016/j.ipl.2009.03.011.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

Bagan, Guillaume, Angela Bonifati, and Benoit Groz. "A trichotomy for regular simple path queries on graphs." Journal of Computer and System Sciences 108 (March 2020): 29–48. http://dx.doi.org/10.1016/j.jcss.2019.08.006.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

Ginsburg, Seymour, and X. Sean Wang. "Regular Sequence Operations and Their Use in Database Queries." Journal of Computer and System Sciences 56, no. 1 (February 1998): 1–26. http://dx.doi.org/10.1006/jcss.1997.1514.

Full text

APA, Harvard, Vancouver, ISO, and other styles

32

Prezza, Nicola. "Subpath Queries on Compressed Graphs: A Survey." Algorithms 14, no. 1 (January 5, 2021): 14. http://dx.doi.org/10.3390/a14010014.

Full text

Abstract:

Text indexing is a classical algorithmic problem that has been studied for over four decades: given a text T, pre-process it off-line so that, later, we can quickly count and locate the occurrences of any string (the query pattern) in T in time proportional to the query’s length. The earliest optimal-time solution to the problem, the suffix tree, dates back to 1973 and requires up to two orders of magnitude more space than the plain text just to be stored. In the year 2000, two breakthrough works showed that efficient queries can be achieved without this space overhead: a fast index be stored in a space proportional to the text’s entropy. These contributions had an enormous impact in bioinformatics: today, virtually any DNA aligner employs compressed indexes. Recent trends considered more powerful compression schemes (dictionary compressors) and generalizations of the problem to labeled graphs: after all, texts can be viewed as labeled directed paths. In turn, since finite state automata can be considered as a particular case of labeled graphs, these findings created a bridge between the fields of compressed indexing and regular language theory, ultimately allowing to index regular languages and promising to shed new light on problems, such as regular expression matching. This survey is a gentle introduction to the main landmarks of the fascinating journey that took us from suffix trees to today’s compressed indexes for labeled graphs and regular languages.

APA, Harvard, Vancouver, ISO, and other styles

33

TAN, TONY, and DOMAGOJ VRGOČ. "REGULAR EXPRESSIONS FOR QUERYING DATA GRAPHS." International Journal of Foundations of Computer Science 25, no. 08 (December 2014): 971–85. http://dx.doi.org/10.1142/s0129054114400188.

Full text

Abstract:

The standard regular expressions over finite alphabets have been widely accepted as the most basic formalism to query graph databases. However, the major drawback of this approach is that it ignores the presence of data. In this paper we study the so called regular expressions with binding (REWB), that is, regular expressions equipped with variables to store data within a well defined scope. In particular, we study the complexity of the query evaluation of REWB queries over graph databases.

APA, Harvard, Vancouver, ISO, and other styles

34

Nguyen, Van-Quyet, Van-Hau Nguyen, Minh-Quy Nguyen, Quyet-Thang Huynh, and Kyungbaek Kim. "Efficiently Estimating Joining Cost of Subqueries in Regular Path Queries." Electronics 10, no. 9 (April 21, 2021): 990. http://dx.doi.org/10.3390/electronics10090990.

Full text

Abstract:

Evaluating Regular Path Queries (RPQs) have been of interest since they were used as a powerful way to explore paths and patterns in graph databases. Traditional automata-based approaches are restricted in the graph size and/or highly complex queries, which causes a high evaluation cost (e.g., memory space and response time) on large graphs. Recently, although using the approach based on the threshold rare label for large graphs has been achieving some success, they could not often guarantee the minimum searching cost. Alternatively, the Unit-Subquery Cost Matrix (USCM) has been studied and obtained the viability of the usage of subqueries. Nevertheless, this method has an issue, which is, it does not cumulate the cost among subqueries that causes the long response time on a large graph. In order to overcome this issue, this paper proposes a method for estimating joining cost of subqueries to accelerate the USCM based parallel evaluation of RPQs on a large graph, namely USCM-Join. Through real-world datasets, we experimentally show that the USCM-Join outperforms others and estimating the joining cost enhances the USCM based approach up to around 20% in terms of response time.

APA, Harvard, Vancouver, ISO, and other styles

35

Alon, Noga, Michael Krivelevich, Ilan Newman, and Mario Szegedy. "Regular Languages are Testable with a Constant Number of Queries." SIAM Journal on Computing 30, no. 6 (January 2001): 1842–62. http://dx.doi.org/10.1137/s0097539700366528.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

Alkhateeb, Faisal, and Jerome Euzenat. "Constrained regular expressions for answering RDF-path queries modulo RDFS." International Journal of Web Information Systems 10, no. 1 (April 14, 2014): 24–50. http://dx.doi.org/10.1108/ijwis-05-2013-0013.

Full text

Abstract:

Purpose – The paper aims to discuss extensions of SPARQL that use regular expressions to navigate RDF graphs and may be used to answer queries considering RDFS semantics (in particular, nSPARQL and our proposal CPSPARQL). Design/methodology/approach – The paper is based upon a theoretical comparison of the expressiveness and complexity of both nSPARQL and the corresponding fragment of CPSPARQL, that we call cpSPARQL. Findings – The paper shows that nSPARQL and cpSPARQL (the fragment of CPSPARQL) have the same complexity through cpSPARQL, being a proper extension of SPARQL graph patterns, is more expressive than nSPARQL. Research limitations/implications – It has not been possible to the authors to compare the performance of our CPSPARQL implementation with other proposals. However, the experimentation has allowed to make interesting observations. Practical implications – The paper includes implications for implementing the SPARQL RDFS entailment regime. Originality/value – The paper demonstrates the usefulness of cpSPARQL language. In particular, cpSPARQL, which is sufficient for capturing RDFS semantics, admits an efficient evaluation algorithm, while the whole CPSPARQL language is in theory as efficient as SPARQL is. Moreover, using such a path language within the SPARQL structure allows for properly extending SPARQL.

APA, Harvard, Vancouver, ISO, and other styles

37

Inaba, Kazuhiro, and Haruo Hosoya. "Compact representation for answer sets of n-ary regular queries." Theoretical Computer Science 411, no. 38-39 (August 2010): 3481–92. http://dx.doi.org/10.1016/j.tcs.2010.05.026.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Freydenberger, Dominik D., and Nicole Schweikardt. "Expressiveness and static analysis of extended conjunctive regular path queries." Journal of Computer and System Sciences 79, no. 6 (September 2013): 892–909. http://dx.doi.org/10.1016/j.jcss.2013.01.008.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

Gibney, Daniel, and Sharma V. Thankachan. "Text Indexing for Regular Expression Matching." Algorithms 14, no. 5 (April 23, 2021): 133. http://dx.doi.org/10.3390/a14050133.

Full text

Abstract:

Finding substrings of a text T that match a regular expression p is a fundamental problem. Despite being the subject of extensive research, no solution with a time complexity significantly better than O(|T||p|) has been found. Backurs and Indyk in FOCS 2016 established conditional lower bounds for the algorithmic problem based on the Strong Exponential Time Hypothesis that helps explain this difficulty. A natural question is whether we can improve the time complexity for matching the regular expression by preprocessing the text T? We show that conditioned on the Online Matrix–Vector Multiplication (OMv) conjecture, even with arbitrary polynomial preprocessing time, a regular expression query on a text cannot be answered in strongly sublinear time, i.e., O(|T|1−ε) for any ε>0. Furthermore, if we extend the OMv conjecture to a plausible conjecture regarding Boolean matrix multiplication with polynomial preprocessing time, which we call Online Matrix–Matrix Multiplication (OMM), we can strengthen this hardness result to there being no solution with a query time that is O(|T|3/2−ε). These results hold for alphabet sizes three or greater. We then provide data structures that answer queries in O(|T||p|τ) time where τ∈[1,|T|] is fixed at construction. These include a solution that works for all regular expressions with Expτ·|T| preprocessing time and space. For patterns containing only ‘concatenation’ and ‘or’ operators (the same type used in the hardness result), we provide (1) a deterministic solution which requires Expτ·|T|log2|T| preprocessing time and space, and (2) when |p|≤|T|z for z=2o(log|T|), a randomized solution with amortized query time which answers queries correctly with high probability, requiring Expτ·|T|2Ωlog|T| preprocessing time and space.

APA, Harvard, Vancouver, ISO, and other styles

40

Metre, K. V. "Location based Continuous Query Processing over Geo-streaming Data." Turkish Journal of Computer and Mathematics Education (TURCOMAT) 12, no. 1S (April 11, 2021): 106–14. http://dx.doi.org/10.17762/turcomat.v12i1s.1583.

Full text

Abstract:

In recent years, many data-intensive and location based applications have emerged that need to process stream data in applications such as network monitoring, telecommunications data management, and sensor networks. Unlike regular queries, a continuous query exists for certain period of time and need to be continuously processed during this time. The algorithms used for data processing for the traditional database systems are not suited to tackle complex and various continuous queries over dynamic streaming data. The indexing for finite queries is preferred to indexing on infinite data to avoid expensive operations of index maintenance. Previous related work focused on moving queries on static objects or static queries on moving object. But now-a-days queries as well as objects are dynamic. So, hybrid indexing for queries significantly reduces the space costs and scales well with the increasing data. To deal with the speed of unbounded data, it is necessary to use data parallelism in query processing. The data parallelism in query processing offers better performance, availability and scalability.

APA, Harvard, Vancouver, ISO, and other styles

41

Kazantsev, I. A., and R. K. Klassen. "IMPROVING THE AUTOMATIC PRETANSLATOR OF SQL-QUERIES TO A REGULAR PLAN." Vestnik komp'iuternykh i informatsionnykh tekhnologii, no. 210 (December 2021): 3–12. http://dx.doi.org/10.14489/vkit.2021.12.pp.003-012.

Full text

Abstract:

We have created an automatic pretranslator prototype and proposing a new approach to improve the automatic pretranslator efficiency by parsing the original SQL (Structured Query Language) query and building a regular tree. The new approach is to create custom handlers for specific SQL constructs. The resulting handlers, instead of omitting some SQL constructs at the sorting and aggregation stage, allow them to be processed at the join stage. Joining operations, in contrast to sorting and aggregation operations, are performed in parallel on several nodes of the computing cluster, which significantly increases the productivity of processing a single query. You can additionally improve performance by reducing the amount of data transferred, due to a more accurate selection of the dimensions of DECIMAL fields and lowering the projection operations to the level of sorting and aggregation if lifting them increases the number of intermediate relation fields. A regular tree for a single request can be built in various ways. Finding the most effective regular plan pretranslator requires constructing many plans. A plan is selected from the set in which join operations are performed with the order of intermediate relations with sizes from smallest to largest. The experiments carried out have shown that the execution time of a stream of requests pretranslated by the pretranslator is not more than the execution time of a similar stream, pretranslated manually, which proves its effectiveness.

APA, Harvard, Vancouver, ISO, and other styles

42

Chockler, Hana, and Orna Kupferman. "ω-Regular languages are testable with a constant number of queries." Theoretical Computer Science 329, no. 1-3 (December 2004): 71–92. http://dx.doi.org/10.1016/j.tcs.2004.08.004.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

Bhrugubanda, Meenakshi. "Analysis of hybrid approach for Answering holistic queries in Wireless Sensor." International Journal of Engineering Technology and Management Sciences 4, no. 5 (September 28, 2020): 53–56. http://dx.doi.org/10.46647/ijetms.2020.v04i05.010.

Full text

Abstract:

Sensor networks are greatly utilized in unique areas like the transportation methods, wellbeing monitoring, soil monitoring, habitat monitoring and so forth. Clients pose queries to sensors and acquire sensing information. In view of the low quality detecting devices, sensor information is regularly boisterous. Continuous queries are more commonly employed to increase the reliability of query result. On this work we revolve round on regular holistic queries like Median. Present methodologies are for essentially the most phase supposed for non-holistic queries like Average. As a result of the no decomposable property of sensors, answering holistic queries are given much less value. We initially recommend two ways elegant on the information correlation be tween’s two rounds, with one for finding the detailed solutions and the other one for opting for the estimated outcome. We at that factor consolidate the two proposed plans into a hybrid methodology, which is flexible to the information evolving velocity. The effects show that our methodology has reduced the traffic rate even as keeping equal accuracy.

APA, Harvard, Vancouver, ISO, and other styles

44

Pang, Yue, Lei Zou, Jeffrey Xu Yu, and Linglin Yang. "Materialized View Selection & View-Based Query Planning for Regular Path Queries." Proceedings of the ACM on Management of Data 2, no. 3 (May 29, 2024): 1–26. http://dx.doi.org/10.1145/3654955.

Full text

Abstract:

A regular path query (RPQ) returns node pairs connected by a path whose edge label sequence satisfies the given regular expression. Given a workload of RPQs, selecting the shared subqueries as materialized views to precompute offline can speed up the online processing. Since the available memory is limited, we define the materialized view selection (MVS) problem for RPQs as minimizing the total workload query cost within a memory budget. To tackle the problem's NP-hardness, we design an efficient MVS algorithm based on heuristics. To prevent redundancies in the selected views, we devise the AND-OR directed acyclic graph with closure (AODC) as the multi-RPQ query plan representation for the workload, which encodes the relations between subqueries. In addition to detecting view redundancy, the AODC also incrementally updates itself during view selection. To support query planning, we design a scalable cost and cardinality estimation scheme for full-fledged RPQs, including Kleene closures. Our method, when applied to the Wikidata Query Logs, shows a 9.73× speedup in the total query processing time compared to ad-hoc processing, using the views it selects.

APA, Harvard, Vancouver, ISO, and other styles

45

Gorelov, S. S. "Optimal schema hierarchies in searching semistructured databases by conjunctive regular path queries." Programming and Computer Software 32, no. 4 (September 2006): 215–27. http://dx.doi.org/10.1134/s0361768806040049.

Full text

APA, Harvard, Vancouver, ISO, and other styles

46

Calvanese, Diego, Thomas Eiter, and Magdalena Ortiz. "Answering regular path queries in expressive Description Logics via alternating tree-automata." Information and Computation 237 (October 2014): 12–55. http://dx.doi.org/10.1016/j.ic.2014.04.002.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Zhang, Siyuan, Zhenying He, Yinan Jing, Kai Zhang, and X. Sean Wang. "MWP: Multi-Window Parallel Evaluation of Regular Path Queries on Streaming Graphs." Proceedings of the ACM on Management of Data 2, no. 1 (March 12, 2024): 1–26. http://dx.doi.org/10.1145/3639260.

Full text

Abstract:

A persistent Regular Path Query (RPQ) on a streaming graph is to continuously find every pair of vertices that are connected by a path in the graph within a sliding window, such that the edge label sequence of this path matches a given regular expression. The existing RPQ evaluation algorithm in the literature incrementally maintains a set of spanning-tree-like data structures to quickly form query results and to avoid reprocessing edges that are shared by multiple sliding windows. This approach allows parallel processing of the graph edges within a sliding window but requires a blocking expiration phase between sliding windows to remove the old edges. This blocking phase can significantly degrade the query performance, especially when the edges arrive quickly and the sliding windows overlap significantly. This paper presents a new RPQ evaluation strategy called Multi-Window Parallel (MWP) method leveraging a new data structure called Timestamped Rooted Digraph (TRD). The novel idea is to incrementally maintain TRDs for the quick formulation of query results, like the aforementioned spanning trees, but simultaneously contain needed information for multiple sliding windows. MWP eliminates the forced blocking expiration phase. Only when memory runs low, a quick "dirty garbage collection" (DGC) process is done to remove some unneeded edges and nodes on TRDs, without incurring large costs. Extensive experiments on real graph datasets show that MWP significantly outperforms the existing algorithm in terms of throughput, tail latency, and scalability, and that DGC provides an effective solution for releasing memory with minimum impact.

APA, Harvard, Vancouver, ISO, and other styles

48

Haneef, Farah, and Muddassar A. Sindhu. "DLIQ: A Deterministic Finite Automaton Learning Algorithm through Inverse Queries." Information Technology and Control 51, no. 4 (December 12, 2022): 611–24. http://dx.doi.org/10.5755/j01.itc.51.4.31394.

Full text

Abstract:

Automaton learning has attained a renewed interest in many interesting areas of software engineering including formal verification, software testing and model inference. An automaton learning algorithm typically learns the regular language of a DFA with the help of queries. These queries are posed by the learner (Learning Algorithm) to a Minimally Adequate Teacher (MAT). The MAT can generally answer two types of queries asked by the learning algorithm; membership queries and equivalence queries. Learning algorithms can be categorized into two broad categories: incremental and complete learning algorithms. Likewise, these can be designed for 1-bit learning or k-bit learning. Existing automaton learning algorithms have polynomial (atleast cubic) time complexity in the presence of a MAT. Therefore, sometimes these algorithms even become fail to learn large complex software systems. In this research work, we have reduced the complexity of the Deterministic Finite Automaton (DFA) learning into lower bounds (from cubic to square form). For this, we introduce an efficient complete DFA learning algorithm through Inverse Queries (DLIQ) based on the concept of inverse queries introduced by John Hopcroft for state minimization of a DFA. The DLIQ algorithm takes O(|Ps||F|+|Σ|N) complexity in the presence of a MAT which is also equipped to answer inverse queries. We give a theoretical analysis of the proposed algorithm along with providing a proof correctness and termination of the DLIQ algorithm. We also compare the performance of DLIQ with ID algorithm by implementing an evaluation framework. Our results depict that DLIQ is more efficient than ID algorithm in terms of time complexity.

APA, Harvard, Vancouver, ISO, and other styles

49

Friedman, Reva C., and Steven W. Lee. "Differentiating Instruction for High-Achieving/Gifted Children in Regular Classrooms: A Field Test of Three Gifted-Education Models." Journal for the Education of the Gifted 19, no. 4 (October 1996): 405–36. http://dx.doi.org/10.1177/016235329601900403.

Full text

Abstract:

The movement toward inclusive schools in this country has necessitated a search for instructional models that would best meet the needs of gifted and high-achieving children in increasingly heterogeneous classrooms. In the present study, a multiple baseline design was used to evaluate three popular models of gifted education implemented by general-education teachers in their classrooms. The study focused on process-oriented dependent variables such as the cognitive level of teacher queries and student responses during classroom interactions. While none of the models showed dramatic changes in cognitive complexity of teacher-student interaction, the Cognitive-Affective Interaction Model (Williams, 1986) demonstrated the best results for increasing the cognitive complexity of classroom interactions and on-task behavior of high-achieving students. A strong relationship was found between the cognitive level of teacher queries and student responses across all models.

APA, Harvard, Vancouver, ISO, and other styles

50

Han, Jongbeen, Yunhyeong Seo, Sangjin Lee, Sunggon Kim, and Yongseok Son. "Design and Implementation of Enabling SQL–Query Processing for Ethereum-Based Blockchain Systems." Electronics 12, no. 20 (October 18, 2023): 4317. http://dx.doi.org/10.3390/electronics12204317.

Full text

Abstract:

A blockchain is designed to establish consistent and reliable agreements in an untrusted and decentralized environment. In addition, the blockchain enables transaction processing and the creation of smart contracts. It empowers end users to execute contracts without any intermediate entities. However, there are some issues when it comes to retrieving information, such as the state and history of smart contracts and regular transactions in the blockchain. For example, in a smart contract, user-defined data structures can be used to recall the state of the smart contract for a range query, which can decrease the general performance. In addition, an external database can be required to retrieve regular transactions for range queries, which increases management costs. To achieve this, we propose a new scheme that enables SQL query operations to retrieve a smart contract and regular transaction information within the blockchain system. To achieve this, we combine an embedded relational database with an Ethereum-based blockchain system to provide the SQL query. It enables range queries on smart contracts without requiring user-defined data structures and decreases management costs for regular transactions without any external database. We implement the proposed blockchain system on quorum, which is an Ethereum-based blockchain system. Also, we evaluate the proposed system using a synthetic benchmark. The performance of retrieving smart contract data is improved by up to approximately 22×, with low memory usage compared with the existing system. Moreover, the proposed system demonstrates a similar search performance to the existing system, even when considering external databases in regular transactions.

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!