Einloggen

Thematische Bibliographien / Regular queries / Zeitschriftenartikel

Um die anderen Arten von Veröffentlichungen zu diesem Thema anzuzeigen, folgen Sie diesem Link: Regular queries.

Zeitschriftenartikel zum Thema „Regular queries“

Autor: Grafiati

Veröffentlicht am 22. Februar 2025

Geben Sie eine Quelle nach APA, MLA, Chicago, Harvard und anderen Zitierweisen an

Wählen Sie eine Art der Quelle aus:

Machen Sie sich mit Top-50 Zeitschriftenartikel für die Forschung zum Thema "Regular queries" bekannt.

Neben jedem Werk im Literaturverzeichnis ist die Option "Zur Bibliographie hinzufügen" verfügbar. Nutzen Sie sie, wird Ihre bibliographische Angabe des gewählten Werkes nach der nötigen Zitierweise (APA, MLA, Harvard, Chicago, Vancouver usw.) automatisch gestaltet.

Sie können auch den vollen Text der wissenschaftlichen Publikation im PDF-Format herunterladen und eine Online-Annotation der Arbeit lesen, wenn die relevanten Parameter in den Metadaten verfügbar sind.

Sehen Sie die Zeitschriftenartikel für verschiedene Spezialgebieten durch und erstellen Sie Ihre Bibliographie auf korrekte Weise.

1

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

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

2

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

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

3

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

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

4

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

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

5

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

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

6

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

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

7

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

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

8

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

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

9

Tetzel, Frank, Wolfgang Lehner und Romans Kasperovics. „Efficient Compilation of Regular Path Queries“. Datenbank-Spektrum 20, Nr. 3 (09.09.2020): 243–59. http://dx.doi.org/10.1007/s13222-020-00353-9.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

10

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

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

11

Zhang, Ling, Shaleen Deep, Avrilia Floratou, Anja Gruenheid, Jignesh M. Patel und Yiwen Zhu. „Exploiting Structure in Regular Expression Queries“. Proceedings of the ACM on Management of Data 1, Nr. 2 (13.06.2023): 1–28. http://dx.doi.org/10.1145/3589297.

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

12

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

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

13

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

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

14

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

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

15

Mazowiecki, Filip, Filip Murlak und Adam Witkowski. „Monadic Datalog and Regular Tree Pattern Queries“. ACM Transactions on Database Systems 41, Nr. 3 (08.08.2016): 1–43. http://dx.doi.org/10.1145/2925986.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

16

Martens, Wim, und Tina Trautner. „Dichotomies for Evaluating Simple Regular Path Queries“. ACM Transactions on Database Systems 44, Nr. 4 (17.12.2019): 1–46. http://dx.doi.org/10.1145/3331446.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

17

Grahne, Gösta, und Alex Thomo. „Algebraic rewritings for optimizing regular path queries“. Theoretical Computer Science 296, Nr. 3 (März 2003): 453–71. http://dx.doi.org/10.1016/s0304-3975(02)00739-9.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

18

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

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

19

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

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

20

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

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

21

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

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

22

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

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

23

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

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

24

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

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

25

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

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

26

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

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

27

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

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

28

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

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

29

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

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

30

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

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

31

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

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

32

Prezza, Nicola. „Subpath Queries on Compressed Graphs: A Survey“. Algorithms 14, Nr. 1 (05.01.2021): 14. http://dx.doi.org/10.3390/a14010014.

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

33

TAN, TONY, und DOMAGOJ VRGOČ. „REGULAR EXPRESSIONS FOR QUERYING DATA GRAPHS“. International Journal of Foundations of Computer Science 25, Nr. 08 (Dezember 2014): 971–85. http://dx.doi.org/10.1142/s0129054114400188.

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

34

Nguyen, Van-Quyet, Van-Hau Nguyen, Minh-Quy Nguyen, Quyet-Thang Huynh und Kyungbaek Kim. „Efficiently Estimating Joining Cost of Subqueries in Regular Path Queries“. Electronics 10, Nr. 9 (21.04.2021): 990. http://dx.doi.org/10.3390/electronics10090990.

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

35

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

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

36

Alkhateeb, Faisal, und Jerome Euzenat. „Constrained regular expressions for answering RDF-path queries modulo RDFS“. International Journal of Web Information Systems 10, Nr. 1 (14.04.2014): 24–50. http://dx.doi.org/10.1108/ijwis-05-2013-0013.

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

37

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

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

38

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

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

39

Gibney, Daniel, und Sharma V. Thankachan. „Text Indexing for Regular Expression Matching“. Algorithms 14, Nr. 5 (23.04.2021): 133. http://dx.doi.org/10.3390/a14050133.

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

40

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

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

41

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

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

42

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

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

43

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

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

44

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

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

45

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

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

46

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

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

47

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

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

48

Haneef, Farah, und Muddassar A. Sindhu. „DLIQ: A Deterministic Finite Automaton Learning Algorithm through Inverse Queries“. Information Technology and Control 51, Nr. 4 (12.12.2022): 611–24. http://dx.doi.org/10.5755/j01.itc.51.4.31394.

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

49

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

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

50

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

Der volle Inhalt der Quelle

Annotation:

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 und andere Zitierweisen

Wir bieten Rabatte auf alle Premium-Pläne für Autoren, deren Werke in thematische Literatursammlungen aufgenommen wurden. Kontaktieren Sie uns, um einen einzigartigen Promo-Code zu erhalten!