Accedi

Bibliografie tematiche / Regular queries / Articoli di riviste

Segui questo link per vedere altri tipi di pubblicazioni sul tema: Regular queries.

Articoli di riviste sul tema "Regular queries"

Autore: Grafiati

Pubblicato: 22 febbraio 2025

Cita una fonte nei formati APA, MLA, Chicago, Harvard e in molti altri stili

Scegli il tipo di fonte:

Vedi i top-50 articoli di riviste per l'attività di ricerca sul tema "Regular queries".

Accanto a ogni fonte nell'elenco di riferimenti c'è un pulsante "Aggiungi alla bibliografia". Premilo e genereremo automaticamente la citazione bibliografica dell'opera scelta nello stile citazionale di cui hai bisogno: APA, MLA, Harvard, Chicago, Vancouver ecc.

Puoi anche scaricare il testo completo della pubblicazione scientifica nel formato .pdf e leggere online l'abstract (il sommario) dell'opera se è presente nei metadati.

Vedi gli articoli di riviste di molte aree scientifiche e compila una bibliografia corretta.

1

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

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

2

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

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

3

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

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

4

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

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

5

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

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

6

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

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

7

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

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

8

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

Testo completo

Abstract (sommario):

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%.

Gli stili APA, Harvard, Vancouver, ISO e altri

9

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

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

10

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

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

11

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

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

12

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

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

13

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

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

14

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

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

15

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

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

16

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

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

17

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

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

18

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

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

19

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

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

20

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

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

21

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

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

22

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

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

23

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

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

24

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

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

25

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

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

26

Lee, Jinsoo, Minh-Duc Pham, Jihwan Lee, Wook-Shin Han, Hune Cho, Hwanjo Yu e 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.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

27

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

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

28

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

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

29

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

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

30

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

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

31

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

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

32

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

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

33

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

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

34

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

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

35

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

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

36

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

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

37

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

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

38

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

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

39

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

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

40

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

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

41

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

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

42

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

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

43

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

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

44

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

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

45

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

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

46

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

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

47

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

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

48

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

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

49

Friedman, Reva C., e 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, n. 4 (ottobre 1996): 405–36. http://dx.doi.org/10.1177/016235329601900403.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

50

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

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

Offriamo sconti su tutti i piani premium per gli autori le cui opere sono incluse in raccolte letterarie tematiche. Contattaci per ottenere un codice promozionale unico!